Home » Developing U++ » U++ Developers corner » New containers - naming
New containers - naming [message #38981] |
Sun, 03 February 2013 19:46 |
|
mirek
Messages: 13985 Registered: November 2005
|
Ultimate Member |
|
|
Hi,
in past weeks, I was working on a new container that will become a basis of couple of other containers.
The new container, which I have named 'InVector', excels at inserting or removing elements at arbitrary locations (trading this feature for somewhat slower operator[]).
It is so fast that it is possible to create 'std::set' equivalent (means, elements are added at UpperBound index, so that InVector stays sorted at all times and it has log(n) search of elements), which is quite superior to set (which is implemented with using binary trees). It is moderately faster and it consumes significantly less memory.
InVector thus makes possible to create a new set of containers, alike to 'Array, Index, VectorMap, ArrayMap', where instead of hashing binary search is used. Of course, hashing is still much faster, but the advantage of binary search is the ability to perform range searches. Also, it consumes less memory than hashing.
Now one small funny problem is how to name these new containers. My current state of mind is somehing like
InArray (Array counterpart)
Order (Index counterpart)
OrderVector (VectorMap counterpart)
OrderArray (ArrayMap counterpart)
Any better ideas?
Mirek
P.S.: InVector can be seen in sandbox/InVector, with tests and benchmarks...
[Updated on: Sun, 03 February 2013 19:47] Report message to a moderator
|
|
|
Re: New containers - naming [message #38982 is a reply to message #38981] |
Sun, 03 February 2013 20:39 |
|
Hi Mirek,
That great, now Il be even more addicted to NTL...
Just to make sure, InVector stands for "insert vector"?
IMHO it would be great if the name of the new containers contained the information how it differs from the regular ones. I think the biggest advantage of this will be the range searches, so what about something like RangeIndex, RangeVector and RangeArray?
BTW: Will you tell us how it works, or is it left as an exercise for the reader? I suspect you told me once about this idea in past over a beer, but I want spoil it just yet for other curious programmers here
Best regards,
Honza
|
|
|
Re: New containers - naming [message #38984 is a reply to message #38982] |
Sun, 03 February 2013 21:17 |
|
mirek
Messages: 13985 Registered: November 2005
|
Ultimate Member |
|
|
dolik.rce wrote on Sun, 03 February 2013 14:39 | Hi Mirek,
That great, now Il be even more addicted to NTL...
Just to make sure, InVector stands for "insert vector"?
|
Well, either that or that it supports "in" positions. Of course, better ideas are welcome
Quote: |
IMHO it would be great if the name of the new containers contained the information how it differs from the regular ones.
I think the biggest advantage of this will be the range searches, so what about something like RangeIndex, RangeVector and RangeArray?
|
Well, my original line of thinking was that the main difference is that keys are ordered... (also note std::unordered_map etc...). But OrderedIndex is perhaps too long, so "Order".
Quote: |
BTW: Will you tell us how it works, or is it left as an exercise for the reader? I suspect you told me once about this idea in past over a beer, but I want spoil it just yet for other curious programmers here
|
The basic storage is Vector<Vector<T>>, the size of inner vectors is kept between some thresholds, otherwise they are split / merged. For such small amount of data, Vector was always faster at inserting/removing than any node based structures.
The key to provide relatively fast index access is sort of numeric binary tree, which is easy to maintain on inserts/removes (removes are not implemented yet) and still quite fast for operator[]. Plus, there is a per thread cache to speed up simple scans. And a good thing is that Find[Upper/Lower]Bound methods can compute the index of an element very cheaply.
Mirek
|
|
|
Re: New containers - naming [message #38985 is a reply to message #38981] |
Sun, 03 February 2013 23:36 |
navi
Messages: 107 Registered: February 2012 Location: Sydney, Australia
|
Experienced Member |
|
|
wow. new container for NTL. awesome.
maybe an acronym prefix? like "aid" (Arbitrary insert delete)
e.g. aidArray, aidVector etc
also from description it sounds very similar to List.
Quote from wiki | ...Lists are typically implemented either as linked lists (either singly or doubly linked) or as arrays ...
... Each element in the list has an index. The first element commonly has index 0 or 1 (or some other predefined integer). Subsequent elements have indices that are 1 higher than the previous element. The last element has index <initial index> + <size> − 1.
It is possible to retrieve the element at a particular index.
It is possible to traverse the list in the order of increasing index.
It is possible to change the element at a particular index to a different value, without affecting any other elements.
It is possible to insert an element at a particular index. The indices of higher elements at that are increased by 1.
It is possible to remove an element at a particular index. The indices of higher elements at that are decreased by 1.
...Lists can be implemented as self-balancing binary search trees holding index-value pairs, providing equal-time access to any element (e.g. all residing in the fringe, and internal nodes storing the right-most child's index, used to guide the search), taking the time logarithmic in the list's size, but as long as it doesn't change much will provide the illusion of random access and enable swap, prefix and append operations in logarithmic time as well...
As the name implies, lists can be used to store a list of records. The items in a list can be sorted for the purpose of fast search (binary search)....
...lists are easier to realize than sets, a finite set in mathematical sense can be realized as a list with additional restrictions, that is, duplicate elements are disallowed and such that order is irrelevant. If the list is sorted, it speeds up determining if a given item is already in the set but in order to ensure the order, it requires more time to add new entry to the list. In efficient implementations, however, sets are implemented using self-balancing binary search trees or hash tables, rather than a list.
|
|
|
|
|
|
|
|
Re: New containers - naming [message #39007 is a reply to message #39003] |
Wed, 06 February 2013 07:56 |
|
mirek
Messages: 13985 Registered: November 2005
|
Ultimate Member |
|
|
zsolt wrote on Tue, 05 February 2013 18:10 | I dont like this BS thing
InsVector or InVector would be good names. They could mean "Insert optimized".
|
I guess InVector/InArray are settled.
What I am not sure is Index/*Map names.
Ok, as Order<T> has no fans, let us be more explicit:
SortedIndex<T, Less>
SortedArrayIndex<T, Less>
SortedVectorMap<K, V, Less>
SortedArrayMap<K, V, Less>
[Updated on: Wed, 06 February 2013 07:59] Report message to a moderator
|
|
|
|
Re: New containers - naming [message #39009 is a reply to message #39007] |
Wed, 06 February 2013 11:36 |
zsolt
Messages: 698 Registered: December 2005 Location: Budapest, Hungary
|
Contributor |
|
|
Quote: | SortedIndex<T, Less>
SortedArrayIndex<T, Less>
SortedVectorMap<K, V, Less>
SortedArrayMap<K, V, Less>
|
These would be good names, I think.
|
|
|
Goto Forum:
Current Time: Sun Jun 16 16:09:35 CEST 2024
Total time taken to generate the page: 0.01712 seconds
|