Re: [boost] [proposal] Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)
Rene Rivera wrote:
Martin Knoblauch Revuelta wrote:
How about a sequence container [..].
I was wondering how long it would take this to make it from the usenet groups to here :-)
I've mentioned this type of container here in the past, under the name of "rank_tree". Very soon now I will have the version I wrote, and use, ported to the framework that Bernhard produced for the SoC tree project. You can look at the draft TR <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/libs/tree/doc/html/d2102.html?format=raw> that mentions it, and other trees.
I don't have time to look at your implementation right now. But perhaps you could comment on how you think your implementation might fit within the above. And of course if there's something we haven't thought about.
Well, maybe the most important thing is the experimental feature NPSV that I added in version 1.1. I described it briefly in my message, but there's a detailed description in the notes for version 1.1 of stlavlarray.h. The example program in npsvexample.cpp shows it's behaviour. Example where NPSV would be useful: a simple avl_array (or rank_tree) would waste a lot of memory when used for small contained types. This can be solved with NPSV, by storing more than one contained type element in every tree node. The 'width' of the node would be the number of occupied elements in the node, which would contain a circular buffer. Additionally, avl_array has the next characteristics (use it as a check list): * On iterators, ++ and -- are O(1) * begin(), end(), rbegin() and rend() are all O(1) * Copy constructor, assignment operator and destructor are O(n) * Other constructors, where the number of elements is known, are O(n) * Comparison operators are all O(n) * reverse(), merge(), and unique are O(n) * avl_array swap is O(1) * element swap is O(1) unless when NPSV is used _and_ the elements' widths don't match (then it is O(log n)) * element swap also works between two different avl_arrays * resize, range-insert and range-erase take O(m log n) when m is small, but O(n) when m is reasonably significant compared to n. (m: number of elements to insert/erase; n: size of the array) * move() is O(log n) unless it is a single-position move, in which case it is done with a swap * both sort() and stable_sort() are provided with O(n log n) * search tree methods are provided * insert_anywhere() inserts without rotations favouring balance (though still O(log n)) * Iterators follow their referenced elements, even when theese are moved from an avl_array to another one Can all this be done with generic trees while keeping them simple, efficient and usable for other purposes where the hierarchy is visible to the user? Regards, Martin Knoblauch Revuelta
This does look like a valuable addition to the currently available sequence containers, and I would love to see it developed into a boost library. Out of curiosity, since I didn't see it mentioned in previous posts (maybe I'm blind and missed it)... What operations on the container cause existing iterators to be invalidated?
On 10/26/06, Jason Hise <0xchaos@gmail.com> wrote:
[..] Out of curiosity, since I didn't see it mentioned in previous posts (maybe I'm blind and missed it)... What operations on the container cause existing iterators to be invalidated?
Only deletion of the refereced element, or destruction of the whole container. Iterators referencing end() are only invalidated when the container is destroyed. Other operations, like moving elements, sorting the array, merging, swapping... don't invalidate iterators, because the tree nodes are never moved in memory. Iterators contain only a simple pointer to a node. Nothing but the node itself ties them to a concrete container. That's why many methods have been declared static. Regards, Martin Knoblauch Revuelta
Rene Rivera wrote
I've mentioned this type of container here in the past, under the name of "rank_tree". Very soon now I will have the version I wrote, and use, ported to the framework that Bernhard produced for the SoC tree project. You can look at the draft TR <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/libs/tree/doc/html/d2102.html?format=raw> that mentions it, and other trees.
I don't have time to look at your implementation right now. But perhaps you could comment on how you think your implementation might fit within the above. And of course if there's something we haven't thought about.
From the beginning, I designed the avl_array with the clear intention of hiding the tree nature of the implementation to the user's eyes. In
I've taken a look at your code in <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/boost/tree/augmentors/rank.hpp> Now I see what you call rank: for every node, the rank is one plus the number of nodes in its left subtree. Is this right? In avl-array I use the count approach: for every node, the count is the total number of nodes in its subtree (including himself and the nodes in both left and right subtrees). For implementing the "Non-Proportional Sequence View" in SoC trees, a new augmentor would be necessary. Optionally, it might include also a normal rank augmentor. For the NPSV, it would need two variables of a parametric type (say W). One of them would be the width (in your rank and my count, every node counts as one, but in NPSV it is not necessarily one, and it can be changed). The other variable would be a sum of widths. Here, a rank-like sum would be prone to cumulative errors (if W is a float, for example), so I would use a count-like sum. In avl_array, those fields are called node_width and total_width respectively. In avl_array I get a low algorithmic complexity (O(1) instead of O(log n), or O(n) instead of O(n log n)) in many operations by having all nodes of the tree linked in-order in a circular doubly linked list. Have you considered adding such feature to soc trees? (Sorry, I don't have too much time to search for it either) I think it would be an important advantage. Massive insertions/removals, assignment and most constructors are O(n) thanks to the method avl_array::build_known_size_tree(), which builds a perfectly balanced tree taking the nodes in sequence order, and without function call recursion. this concrete case, I can't think of any benefit coming out of exposing the tree hierarchy. In part because of the banlance operations. I'm rather skeptic regarding the relation performance/maintainability/usability of a possible integration with a tree library. Though, I must recognize I still don't know the internals of the SoC project, so if you think it's a good idea to add these features (all, or just some of them) to the SoC tree project, I'll be glad to collaborate. Regards, Martin Knoblauch Revuelta
Martin Knoblauch Revuelta wrote:
Rene Rivera wrote
I've mentioned this type of container here in the past, under the name of "rank_tree". Very soon now I will have the version I wrote, and use, ported to the framework that Bernhard produced for the SoC tree project. You can look at the draft TR <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/libs/tree/doc/html/d2102.html?format=raw> that mentions it, and other trees.
I don't have time to look at your implementation right now. But perhaps you could comment on how you think your implementation might fit within the above. And of course if there's something we haven't thought about.
I've taken a look at your code in <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/boost/tree/augmentors/rank.hpp>
Now I see what you call rank: for every node, the rank is one plus the number of nodes in its left subtree. Is this right?
The exact definition varies, but essentially it keeps the "rank" of the node which is the position from the "start" of the node in an inorder traversal of the tree. This can be done by storing a count equivalent to the number of nodes in the tree at the node. The name, and the basic algorithms comes from the "Introduction to Algorithms" [CLRS] <http://www.bookpool.com/sm/0262032937> (I refer to it as the white book because the book was almost entirely white on the 1st edition which is what I used in college). Note the above code is what Bernhard wrote, my code is referenced at the bottom <http://redshift-software.com/~grafik/RankTree.h>. And I'm working on creating the adapter style container referred to in the TR paper.
Have you considered adding such feature to soc trees? (Sorry, I don't have too much time to search for it either) I think it would be an important advantage.
Yes. Bernhard started out with such optimizations in mind. The TR proposal avoids specifying such implementation details to not limit such possibilities.
Massive insertions/removals, assignment and most constructors are O(n) thanks to the method avl_array::build_known_size_tree(), which builds a perfectly balanced tree taking the nodes in sequence order, and without function call recursion.
Yes, the operator=() is also linear on my implementation.
From the beginning, I designed the avl_array with the clear intention of hiding the tree nature of the implementation to the user's eyes. In this concrete case, I can't think of any benefit coming out of exposing the tree hierarchy. In part because of the banlance operations.
That would be one big difference, which has been brought up before in the same context. I don't see a harm to have access to the tree. If you really want to limit such access you can make a separate adaptor. Sorry about the short and quick reply... I'll get to a longer reply to this in the weekend (rather busy with work right now). -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
From the beginning, I designed the avl_array with the clear intention of hiding the tree nature of the implementation to the user's eyes. In this concrete case, I can't think of any benefit coming out of exposing the tree hierarchy. In part because of the banlance operations.
That would be one big difference, which has been brought up before in the same context. I don't see a harm to have access to the tree. If you really want to limit such access you can make a separate adaptor.
Would there be any benefit to accessing the data structure as a tree in client code? If so, shouldn't std::map do the same? My opinion is that this is a sequence container that gives certain complexity guarantees, and over-specifying the public interface restricts potential future implementations. The fact that the sequence uses a tree internally is an implementation detail. And actually, given that, I think it should be renamed to something that reflects the strengths of the container, rather than after the implementation structure. (Not sure what a good name would be, but something to think about). Just my $0.02.
On 10/26/06, Jason Hise <0xchaos@gmail.com> wrote:
[..] I think it should be renamed to something that reflects the strengths of the container, rather than after the implementation structure. (Not sure what a good name would be, but something to think about).
This is one of the first things I have wanted to discuss. I named it avl_array one and a half year ago, when I made the first C implementation, with the idea of thinking a better name someday... AVL: impementation-specific. Bad name Array: can give a wrong impression of how iterators work. Bad name Tree: the tree is vital, but it is not used as a tree. Bad name List: there's a list, but it is like a roller coaster. Bad name Log: will be confused log files. Bad name Thing: hummm Rank tree is at least as good as avl array, of course. I woud like a name focused on what it provides: a sequence, random access, insertion/deletion, logarithmic complexity, alternative index derived from the sum of 'widths'... Regards, Martin Knoblauch Revuelta
On 10/27/06, Martin Knoblauch Revuelta <mkrevuelta@gmail.com> wrote:
This is one of the first things I have wanted to discuss. I named it avl_array one and a half year ago, when I made the first C implementation, with the idea of thinking a better name someday... [...]
What about log-list or llist (think of SGI's slist)? Or if you want to emphatize the random access property, log-array or larray. --- Giovanni P. Deretta
Giovanni Piero Deretta wrote:
On 10/27/06, Martin Knoblauch Revuelta <mkrevuelta@gmail.com> wrote:
This is one of the first things I have wanted to discuss. I named it avl_array one and a half year ago, when I made the first C implementation, with the idea of thinking a better name someday... [...]
What about log-list or llist (think of SGI's slist)? Or if you want to emphatize the random access property, log-array or larray.
Or "chain", or "random_list", John.
On Mon, 30 Oct 2006, John Maddock wrote:
Giovanni Piero Deretta wrote:
What about log-list or llist (think of SGI's slist)? Or if you want to emphatize the random access property, log-array or larray.
Or "chain", or "random_list",
Or then "rlist"? -- François Duranleau LIGUM, Université de Montréal
On 10/30/06, François Duranleau <duranlef@iro.umontreal.ca> wrote:
On Mon, 30 Oct 2006, John Maddock wrote:
Giovanni Piero Deretta wrote:
What about log-list or llist (think of SGI's slist)? Or if you want to emphatize the random access property, log-array or larray.
Or "chain", or "random_list",
Or then "rlist"?
How about "ra_list" or "ralist" to emphasize "random access" rather than just "random"? --Michael Fawcett
On 10/30/06, Michael Fawcett <michael.fawcett@gmail.com> wrote:
On 10/30/06, François Duranleau <duranlef@iro.umontreal.ca> wrote:
On Mon, 30 Oct 2006, John Maddock wrote:
Giovanni Piero Deretta wrote:
What about log-list or llist (think of SGI's slist)? Or if you want to emphatize the random access property, log-array or larray.
Or "chain", or "random_list",
Or then "rlist"?
How about "ra_list" or "ralist" to emphasize "random access" rather than just "random"?
I think the reason to perfer a new word to an augmented form of list is that this really is a new type of sequence. A singly linked list (slist in SGI) is a specialization of a linked list that trades some functionality for some space. A balanced tree is not a specialization of a linked list, but a new structure altogether. Perhaps it would be best to leave the ultimate decision up to the library author, who came up with the idea and may want the privlege of choosing a name for it. If he would prefer to leave the decision to group concensus, we could put the name to a vote. -Jason
On 10/30/06, Jason Hise <0xchaos@gmail.com> wrote:
On 10/30/06, Michael Fawcett <michael.fawcett@gmail.com> wrote:
On 10/30/06, François Duranleau <duranlef@iro.umontreal.ca> wrote:
On Mon, 30 Oct 2006, John Maddock wrote:
Giovanni Piero Deretta wrote:
What about log-list or llist (think of SGI's slist)? Or if you want to emphatize the random access property, log-array or larray.
Or "chain", or "random_list",
Or then "rlist"?
How about "ra_list" or "ralist" to emphasize "random access" rather than just "random"?
I think the reason to perfer a new word to an augmented form of list is that this really is a new type of sequence. A singly linked list (slist in SGI) is a specialization of a linked list that trades some functionality for some space. A balanced tree is not a specialization of a linked list, but a new structure altogether.
How about ra_sequence then?
Perhaps it would be best to leave the ultimate decision up to the library author, who came up with the idea and may want the privlege of choosing a name for it. If he would prefer to leave the decision to group concensus, we could put the name to a vote.
It seemed like the author was asking for suggestions. I can't speak definitively for the others, but I don't think anyone was presuming to name the library for him. --Michael Fawcett
On 10/30/06, Michael Fawcett <michael.fawcett@gmail.com> wrote:
How about ra_sequence?
Random access sequence sounds like the definition of vector more than a new container type. Actually, I wonder if it is even valid to say that this container supports random access... although it supports the syntax for it, isn't random access defined as being constant time?
Perhaps it would be best to leave the ultimate decision up to the library author, who came up with the idea and may want the privlege of choosing a name for it. If he would prefer to leave the decision to group concensus, we could put the name to a vote.
It seemed like the author was asking for suggestions. I can't speak definitively for the others, but I don't think anyone was presuming to name the library for him.
I guess I felt guilty that I brought up the naming issue, even though he subsequently mentioned he was looking for a better name, because it derailed the topic to some degree. What I meant to say was that focusing on reading through and commenting on his implementation is probably a higher priority, and the name discussion should either be happening parallel to that or it should be put on the back burner. My apologies if the statement sounded accusatory. -Jason
On 10/30/06, Jason Hise <0xchaos@gmail.com> wrote:
On 10/30/06, Michael Fawcett <michael.fawcett@gmail.com> wrote:
How about ra_sequence?
Random access sequence sounds like the definition of vector more than a new container type.
The name must encompass "Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)" (the subject line conveniently enough), and in hindsight, none of my suggestions cover everything the author wants to convey.
Actually, I wonder if it is even valid to say that this container supports random access... although it supports the syntax for it, isn't random access defined as being constant time?
I don't think so. I'm pretty sure RandomAccess only means that the iterator supports the required arithmetic syntax, i.e. ++iter, iter++, iter + n, iter += n. I am by no means an iterator guru.
I guess I felt guilty that I brought up the naming issue, even though he subsequently mentioned he was looking for a better name, because it derailed the topic to some degree. What I meant to say was that focusing on reading through and commenting on his implementation is probably a higher priority, and the name discussion should either be happening parallel to that or it should be put on the back burner.
Agreed.
My apologies if the statement sounded accusatory.
None necessary, I only responded to clarify that my e-mail was merely a humble suggestion. --Michael Fawcett
I have started looking through the code. It looks like some pretty good work thus far. My first comments: A minor nit: you probably shouldn't be using _STL_ as part of your include guards... it makes it look as though the library is already a part of the stl (and it isn't... yet ;) ) Instead of defining your own greater than and less than functors, it may be preferable to use greater and less, defined in the <functional> header. Just like yours, the stl greater requires Ts to be less than comparable rather than greater than comparable. Your static allocator is probably a bad idea... if someone creates a static instance of this container type, the allocator could be destroyed before the container destructor is invoked. The container destructor would then reference the non-existant object. There are ways around this, but IMO it would just be better practice to have each container own its allocator. You use c-style casts from literals to type W, which should either be changed to C++ style casts or explicit constructor calls. It would be good to find a way to rewrite your try-catch blocks in terms of helper commit or rollback objects, which release resources in their destructors unless cancelled (after a successful operation, calling cancel on such an object would be the equivalent of commit). This way, the code will still compile if the end user chooses to disable exception handling, or if the compiler does not support it. The header is pretty large... breaking it into smaller files, even if these aren't publicly exposed, might help readability and maintainability. The commenting is good, but nothing is a substitute for formal library documentation. At the very least, an html or pdf file should be provided. The most important things to cover are which concepts are implemented by your container and iterators and what the complexity guarantees of all operations are. A discussion of the implementation or links to online resources about it would be nice as well, but not as vital as the first two items. -Jason
On 10/31/06, Jason Hise <0xchaos@gmail.com> wrote:
I have started looking through the code. It looks like some pretty good work thus far. My first comments:
A minor nit: you probably shouldn't be using _STL_ as part of your include guards... it makes it look as though the library is already a part of the stl (and it isn't... yet ;) )
You are right. Changed.
Instead of defining your own greater than and less than functors, it may be preferable to use greater and less, defined in the <functional> header. Just like yours, the stl greater requires Ts to be less than comparable rather than greater than comparable.
Right again.
Your static allocator is probably a bad idea... if someone creates a static instance of this container type, the allocator could be destroyed before the container destructor is invoked. The container destructor would then reference the non-existant object. There are ways around this, but IMO it would just be better practice to have each container own its allocator.
I see. I didn't think of that case (a static container). Can I allocate something wit an allocator object, and deallocate it with a different allocator object of the same class (even after the first one was destroyed)? For short: are allocators fully static? I mean, the SGI documentation says they must be, but is it the same in std and boost? If yes, then I can safely do as you guess.
You use c-style casts from literals to type W, which should either be changed to C++ style casts or explicit constructor calls.
Ok. :)
It would be good to find a way to rewrite your try-catch blocks in terms of helper commit or rollback objects, which release resources in their destructors unless cancelled (after a successful operation, calling cancel on such an object would be the equivalent of commit). This way, the code will still compile if the end user chooses to disable exception handling, or if the compiler does not support it.
I'll think how to do this.
The header is pretty large... breaking it into smaller files, even if these aren't publicly exposed, might help readability and maintainability.
I agree. It has already become far too large.
The commenting is good, but nothing is a substitute for formal library documentation. At the very least, an html or pdf file should be provided. The most important things to cover are which concepts are implemented by your container and iterators and what the complexity guarantees of all operations are. A discussion of the implementation or links to online resources about it would be nice as well, but not as vital as the first two items.
I'll work on these. Thanks a lot! Martin
On 10/30/06, Jason Hise <0xchaos@gmail.com> wrote:
Actually, I wonder if it is even valid to say that this container supports random access... although it supports the syntax for it, isn't random access defined as being constant time?
From: Michael Fawcett
I don't think so. I'm pretty sure RandomAccess only means that the iterator supports the required arithmetic syntax, i.e. ++iter, iter++, iter + n, iter += n. I am by no means an iterator guru.
Sorry. Jason is right. Section 24.1 paragraph 8 of the standard: All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). (If there weren't a constant time requirement, there would be no point in distinguishing bi-directional iterators from random access iterators. bi-directional iterators can always implement += n by repeated increment.) -- Martin Bonner Martin.Bonner@Pitechnology.com Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB24 6WZ, ENGLAND Tel: +44 (0)1223 203894
On 10/31/06, Martin Bonner <martin.bonner@pitechnology.com> wrote:
On 10/30/06, Jason Hise <0xchaos@gmail.com> wrote:
Actually, I wonder if it is even valid to say that this container supports random access... although it supports the syntax for it, isn't random access defined as being constant time?
From: Michael Fawcett
I don't think so. I'm pretty sure RandomAccess only means that the iterator supports the required arithmetic syntax, i.e. ++iter, iter++, iter + n, iter += n. I am by no means an iterator guru.
Sorry. Jason is right. Section 24.1 paragraph 8 of the standard: All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized).
(If there weren't a constant time requirement, there would be no point in distinguishing bi-directional iterators from random access iterators. bi-directional iterators can always implement += n by repeated increment.)
Thanks for the clarification, it makes perfect sense. That neatly removes all "random access" suggestions from the name list. =) --Michael Fawcett
This discussion has moved to the thread of the original message, with subject "[proposal] Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)" and date Oct 25, 2006. I think I broke the original thread by mistake because I had the "digest" option activated, so it was my fault. Sorry ;-) Regards, Martin
On 10/30/06, Jason Hise <0xchaos@gmail.com> wrote:
On 10/30/06, Michael Fawcett <michael.fawcett@gmail.com> wrote:
How about ra_sequence?
Random access sequence sounds like the definition of vector more than a new container type. Actually, I wonder if it is even valid to say that this container supports random access... although it supports the syntax for it, isn't random access defined as being constant time?
I think I read that somewhere too.
Perhaps it would be best to leave the ultimate decision up to the library author, who came up with the idea and may want the privlege of choosing a name for it. If he would prefer to leave the decision to group concensus, we could put the name to a vote.
It seemed like the author was asking for suggestions. I can't speak definitively for the others, but I don't think anyone was presuming to name the library for him.
Oh, sorry. I was actually asking for help in the naming issue (too).
[..] focusing on reading through and commenting on his implementation is probably a higher priority, [..]
Yes, I'd love to read your comments about both, interface and implementation. I still have not written a separate documentation, but you will find _lots_ of comments (really). So, what should I change in first place? ;-) Back to the naming issue, and more important: another precedent of the idea in boost, "order-statistics trees" together with "ranked indices" are the names used in the "future work" section of multi_index documentation: http://www.boost.org/libs/multi_index/doc/future_work.html#ranked_indices
From there: http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree
Though, I can't see how is it related to "Order statistic" (I'm not a mathematician): http://en.wikipedia.org/wiki/Order_statistics#Computing_order_statistics Thanks in advance, Martin
On 10/30/06, Martin Knoblauch Revuelta
Back to the naming issue, and more important: another precedent of the idea in boost, "order-statistics trees" together with "ranked indices" are the names used in the "future work" section of multi_index documentation: http://www.boost.org/libs/multi_index/doc/future_work.html#ranked_indices
My opinion is still that os-tree is a name for the underlying data structure, not the sequence interface itself. Rank may be a good adjective for some sort of composite name though. Maybe 'rankseq', or 'ranklist'. I still like the simplicity of 'chain' though. -Jason
What about the "Non-Proportional Sequence View"? That's new, isn't it? Regards, Martin Knoblauch Revuelta
I think random access list, or ralist, would be the most technically descriptive. However, perhaps it would be preferable to create an association between an existing word that is currently unused for sequences and this new type of sequence container. How about chain? vector, deque, chain, list... I think it fits right in. On 10/27/06, Martin Knoblauch Revuelta <mkrevuelta@gmail.com> wrote:
What about the "Non-Proportional Sequence View"? That's new, isn't it?
Regards,
Martin Knoblauch Revuelta _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I woud like a name focused on what it provides: a sequence, random access, insertion/deletion, logarithmic complexity, alternative index derived from the sum of 'widths'...
The technical term which you'll find in accepted text books for the ADT is OS-dictionary, or Order-Statistics Dictionary. Random-access dictionary might be just as adequate. Binary Tree with Rank does not speak about the ADT but about its implementation. As for the compaction of elements in width, it seems to fit with the framework of weighted data structures. There is quite a body of work focussing on the entropy function (where the weights describe some probability of access), but that's not what you have here, where the weights describe the number of elements/representatives. But that seems to fit with weight-balanced trees and the like. On Oct 28, 2006, at 10:37 AM, Jason Hise wrote:
I think random access list, or ralist, would be the most technically descriptive.
However, perhaps it would be preferable to create an association between an existing word that is currently unused for sequences and this new type of sequence container. How about chain?
vector, deque, chain, list... I think it fits right in.
I've never heard of RALists, which can be implemented in a number of ways (Skip lists, Jump lists, binary trees), so I don't think it's a very good term. Chain is plain bad, due to its ambiguity with chaining (hashing) and its quasi-synonymity with list in a number of contexts (buffer chain, hashing, etc.) -- Hervé Brönnimann CIS Polytechnic University
On 10/28/06, Hervé Brönnimann <hervebronnimann@mac.com> wrote:
I woud like a name focused on what it provides: a sequence, random access, insertion/deletion, logarithmic complexity, alternative index derived from the sum of 'widths'...
The technical term which you'll find in accepted text books for the ADT is OS-dictionary, or Order-Statistics Dictionary. Random-access dictionary might be just as adequate. Binary Tree with Rank does not speak about the ADT but about its implementation
Doesn't 'dictionary' imply a key-value relationship? Granted, one can think of the index as the key, but this key is not bound or related to the object. It changes the moment a new object is inserted before it. This is not an associative container, it is a sequence.
On Oct 28, 2006, at 10:37 AM, Jason Hise wrote:
I think random access list, or ralist, would be the most technically descriptive.
However, perhaps it would be preferable to create an association between an existing word that is currently unused for sequences and this new type of sequence container. How about chain?
vector, deque, chain, list... I think it fits right in.
I've never heard of RALists, which can be implemented in a number of ways (Skip lists, Jump lists, binary trees), so I don't think it's a very good term.
I don't know that this structure with it's complexity guarantees can be implemented in multiple different ways... but how does that imply that the name doesn't fit? The name describes the advantages of the container: it is used as a list that supports random access. I havn't seen this type of sequence container in widespread use elsewhere, so why should we expect that there is an existing term to use as a precident?
Chain is plain bad, due to its ambiguity with chaining (hashing) and its quasi-synonymity with list in a number of contexts (buffer chain, hashing, etc.)
It does not seem to me that this terminology is in conflict. Chaining is a verb, and chain is a noun. So there is no reason that you couldn't implement chaining with a chain, or with a list, or even with a vector. All of these make sense. In fact, I bet that a hash container that implemented chaining with a chain instead of a list might be pretty effective. Is chain really commonly used as a synonym for linked list? I havn't ever encountered that use of the term before. Although there exist naming precidents for the implementation of this structure, I don't believe there is a precident for naming its interface. As such, my opinion is that it is our responsibility to invent the terminology. We should find a name which is short, not already in use, and implies that this is a sequence (not a tree or associative container). Then as more people use it they would come to associate the term with its complexity guarantees. -Jason
I like "chain". The only thing I don't like of it is that I find it more appropiate for list than "list" itself, which sounds to me more appropiate for the new container. How about "tower", or "train". Are they too informal? Martin Knoblauch Revuelta
On 10/30/06, Martin Knoblauch Revuelta <mkrevuelta@gmail.com> wrote:
I like "chain". The only thing I don't like of it is that I find it more appropiate for list than "list" itself, which sounds to me more appropiate for the new container.
I'm inclined to agree with the sentiment, but I think the term 'linked list' has too much momentum to change it to 'linked chain' :)
How about "tower", or "train". Are they too informal?
Creative, although in my opinion those sound more like alternative names for stack and queue, respectively. More ideas, straight from the thesaurus entry on 'sequence': - succession - assortment - series Assortment might describe the behavior of this sequence well. My only worry is that it doesn't necessarily imply an order... -Jason
participants (9)
-
François Duranleau -
Giovanni Piero Deretta -
Hervé Brönnimann -
Jason Hise -
John Maddock -
Martin Bonner -
Martin Knoblauch Revuelta -
Michael Fawcett -
Rene Rivera