hashed vector in js

Question

I want to create the following as data stracture in JavaScript.

a container of ordered items
each item has an id, and it can be found and deleted in o(1)
an oreded slice of the container can be retrieved without changing the original container.
an item can be inserted at a specific position in o(1)

I thought to use an array (a=[]) of <items>s with address maping object (b={}) of <item_id, position_in_array>.

Any other ideas?

I don't think ordered containers can have O(1) complexity for either fetch or insert operations... — Frédéric Hamidi
– Frédéric Hamidi, Commented Feb 24, 2012 at 14:39
@FrédéricHamidi: yes they can, see various implementations of priority queues. That said, my answer elaborates why having both is impossible in general. — ninjagecko
– ninjagecko, Commented Feb 24, 2012 at 15:00
@ninjagecko, if my understanding of priority queues is correct, you can only fetch the highest (or lowest) priority item in O(1). Fetching arbitrary items is O(log n) at best. — Frédéric Hamidi
– Frédéric Hamidi, Commented Feb 24, 2012 at 15:08
@FrédéricHamidi: Oh sorry, I talked about priority queues in my answer, so was getting things mixed up when responding to your comment. Nevertheless you still can have an ordered container with O(1) "fetch" complexity. I assume by "fetch" you mean an ordered slice. This can be achieved in O(1) time with a simple array implementation (kept sorted on every insert; correspondingly with a rather high insertion cost). (Also for the record, you can have priority queues which keep track of some kth statistics in O(1) time. It depends on how you choose to implement it or the tradeoffs you make) — ninjagecko
– ninjagecko, Commented Feb 24, 2012 at 15:28
@ninjagecko, indeed, we agree on that point, array items can be fetched in O(1). In the questioner's case, though, it would mean ids are used as indexes, but that can be done :) — Frédéric Hamidi
– Frédéric Hamidi, Commented Feb 24, 2012 at 15:30

ninjagecko · Accepted Answer · 2012-02-24 14:55:47Z

This is generally impossible.

While you can get away with O(1) insertion or O(1) fetch/delete, having both would mean that you could write a general sorting algorithm in O(N) time, while O(N log(N)) is the best one can do unless you have specific kinds of data (like all the data are integers in a fixed range, etc.). To see how you could abuse your solution, merely insert an unsorted array into your container, then retrieve the first item over and over and delete it.

Also some of your constraints are underspecified or in conflict with one another. Having an ID is not necessary unless you are ordering by ID. Also the ability to insert an item in an arbitrary position seems to violate your requirement that the container is always ordered.

Feel free to open another question with a more lenient and open-ended (but still concrete) set of constraints.

Collectives™ on Stack Overflow

hashed vector in js

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related