Re: Data structure for fast associative array with lookup by both key and index

On May 28, 8:04 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
Gene wrote:
On May 26, 2:17 pm, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
Gene wrote:
On May 26, 5:23 am, "A.J." <naijir...@xxxxxxxxx> wrote:

I'm looking for a data structure for an associative array with the
following properties:

... snip ...

CBFalconer's hashlib is excellent, but I'm guessing from your design
that you need deletions to "collapse" the array index space so there
are no holes. I can't see a way this can be done in O(1). The order
stats tree is a nice O(log n) solution. You pay O(log n) on insert
(with respect to a hash table e.g.) in order to allow deletions to be
O(log n) rather than O(n).

Thanks. However hashlib can do O(1) deletions. The hashwalk
function allows compression to a single list at any time (O(N)).
The result is invalid after further insertion/deletions, but will
survive searches. It also seems to be accurate, in that I have had
no reports of flaws in several years.

Thanks. But I guess I'm not clear on what you're proposing. If you
add A, C, D to initially empty x then x[1]=A, x[2]=C, x[3]=D. Now
delete A. You are saying that moving C and D to positions x[1] and
x[2] will require O(n). Yes? With the order statistics tree, the
deletion remains O(log n). That's what I was getting at.

A hash table is NOT an array. Things don't normally get moved.
Get it and look. It's not that big.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
<http://kadaitcha.cx/vista/dogsbreakfast/index.html>
cbfalconer at maineline dot net

--
Posted via a free Usenet account fromhttp://www.teranews.com- Hide quoted text -

- Show quoted text -

Thanks. I guess I'm not communicating very well. I had looked at your
package long before this conversation. It's nice. I have implemented
similar designs myself.

The OP however is asking for a data structure that can be indexed in
order of insertion _with deletion_. When item K is deleted from an
array of N items, items at index positions K+1 to N must be "moved
down" to fill the hole to maintain the orginal order, and the new
array length is N-1. With a simple array, this is an O(N)
operation.

With an order stats tree index, you don't need O(N). Time O(log N)
per operation is enough to delete from a balanced tree -- a standard
tradeoff. Inserts get more expensive than the array, O(1) to O(log
N), but deletes get cheaper, O(N) to O(log N).

With a hash table mapping indices to values, deleting a hash element
ought to be O(1). It obviously is with yours, since you just mark
items deleted in a closed table. But still leaves the "move down". I
don't see how this can be accomplished with anything less than O(N) --
looking up items K+1 to N, deleting, and reinserting with new keys.

Again, this is the OP's requirement, not mine.

If you have a way, I'm truly interested.

.

Relevant Pages

  • Re: Question About LinkedList
    ... I can't do an array of arrays because the database ... backing array, ... and sometimes requires moving all the ... Additions and deletions at beginning or end are O ...
    (comp.lang.java.programmer)
  • Inserting or deleting elements in an array
    ... Is there a simple way to either insert elements into an array or to ... without copying the array to another? ... elements and only one or two insertions or deletions are ever ...
    (microsoft.public.scripting.vbscript)
  • Duck Typed Concepts for Ruby (was Re: A use case for an ordered hash)
    ... An Sequencable mixin can be defined that implements all sorts of operations such as append, concat, splice, sort, etc. ... extending an instance of Array with Sorted if the array is known to be sorted. ... Now returning to the thread at hand we can see that the difference between the associative array and hash hierarchies is that the hash hierarchy depends upon Hashable keys. ...
    (comp.lang.ruby)
  • Re: Suggestions for double-hashing scheme
    ... >> The items that are being moved are the items in the hash table itself, ... >> which are of fixed size (they are in an array, ... > typedef struct { ... One "uchar" aka 'unsigned char' is plenty to hold a probe ...
    (comp.programming)
  • [SUMMARY] Index and Query (#54)
    ... This was a fun quiz for me because I really don't know anything about indexing ... We see in initializethat the index is just a Hash. ... an Array of symbolic document names where the word can be found ). ...
    (comp.lang.ruby)