Create array structure in JavaScript that omits indexing

Question

Indexing (maintaining indices) in an array makes Array.prototype.shift and Array.prototype.unshift O(N) instead of O(1).

However, if we just want to use pop() / push() / shift() and unshift() and never use indices for lookup, is there a way to implement a JavaScript array that omits indexing?

I can't think of a way to do it. The only way I can think of doing it would be with arrays, and only using pop() / push() (since those are O(1)) ... but even with multiple arrays, not sure if it's possible.

Looking to do this w/o a linked-list if possible. I implemented a solution to this with a doubly linked list, but wondering if it's possible to do this w/o a linked-list.

End goal: trying to create a FIFO queue where all operations are in constant time, without using a linked-list.

Just use an object or Map and build those methods around them? — Felix Kling
– Felix Kling, Commented Jun 4, 2018 at 21:48
You can build a Linked List, it would support all the operations you mentioned in O(1) — Minderov
– Minderov, Commented Jun 4, 2018 at 21:50
Using only Objects/map - it's impossible to retrieve both the first/last inserted item in O(1). You have to use a linked-list with an object/map in order to retrieve first/last item in O(1). — Alexander Mills
– Alexander Mills, Commented Jun 4, 2018 at 21:50
@FelixKling but what if you remove the last inserted item? You'd have to find the last last item to save it as the last key? Sounds like you'd need to build another data structure just to support that — Minderov
– Minderov, Commented Jun 4, 2018 at 21:56
Not really clear what higher level problem you are trying to solve — charlietfl
– charlietfl, Commented Jun 4, 2018 at 22:06

SomeCallMeTim · Accepted Answer · 2018-06-04 22:34:03Z

1

How about an ES2015 Map that you index with integers?

Let's call the map myFIFOMap.

You keep a first and last integer member as part of your FIFO class. Start them both at zero.

Every time you want to push() into your FIFO queue, you call myFIFOMap.set(++last,item). And pop() looks something like:

const item = myFIFOMap.get(first); 
myFIFOMap.delete(first++); 
return item;

Should be O(1) to push or pop.

Don't forget to check for boundary conditions (e.g., don't let them pop() when first===last).

Given that JavaScript actually uses double precision floating point, you should be able to run ~2^53 objects through your FIFO before you have problems with the integer precision. So if you run 10,000 items through your FIFO per second, that should be good for around 28,000 years of run time.

answered Jun 4, 2018 at 22:34

SomeCallMeTim

4,8822 gold badges30 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Alexander Mills Over a year ago

Yeah but how do you unshift/shift? I guess you can keep track of the first and last by incrementing/decrementing two fields.

Alexander Mills Over a year ago

I wonder if negative numbers/integers are perfectly fine as keys

Felix Kling Over a year ago

@AlexanderMills: Sure it is. Keys can be arbitrary values.

SomeCallMeTim Over a year ago

@AlexanderMills Yes, the numbers can go negative in a map. So it works to shift()/unshift() with the appropriate decrement/increment of first, respectively.

ouni · Accepted Answer · 2018-06-04 22:10:57Z

0

If the data you are storing is primitive (string, integers, floats, or combinations of primitives), you can use a JavaScript TypedArray, cast it into an appropriate typed array view, load it with data, and then keep track of the offset(s) yourself.

In your example, pop, shift, and unshift can all implemented by incrementing/decrementing an integer index. push is more difficult, because a TypedArray is a fixed size: if the ArrayBuffer is full, the only two options are to truncate the data, or allocate a new typed array, since JS cannot store pointers.

If you are storing homogeneous objects (they have the same properties), you can save each value into a TypedArray using different views and offsets to mimic a C struct (see the MDN example), and then use a JS function to serialize/unserialize them from the TypedArray, basically converting the data from a binary representation, into a full-fledged JS object.

answered Jun 4, 2018 at 22:10

ouni

3,3633 gold badges19 silver badges21 bronze badges

1 Comment

Alexander Mills Over a year ago

Yeah this won't work, because (a) need to be general and not just store primitives and (b) cannot be fixed size since most likely use case is as a FIFO queue.

Alexander Mills · Accepted Answer · 2018-06-07 23:29:53Z

0

Going with @SomeCallMeTim 's answer, which I think is on the right track, I have this:

export class Queue {

  lookup = new Map<number, any>();
  first = 0;
  last = 0;
  length = 0;
  elementExists = false; // when first === last, and item exists there

  peek() {
    return this.lookup.get(this.first);
  }

  getByIndex(v: number) {
    return this.lookup.get(v);
  }

  getLength() {
    return this.length;
  }

  pop() {

    const last = this.last;

    if (this.elementExists && this.first === this.last) {
      this.length--;
      this.elementExists = false;
    }
    else if (this.last > this.first) {
      this.length--;
      this.last--;
    }

    const v = this.lookup.get(last);
    this.lookup.delete(last);
    return v;
  }

  shift() {

    const first = this.first;

    if (this.elementExists && this.first === this.last) {
      this.length--;
      this.elementExists = false;
    }
    else if (this.first < this.last) {
      this.length--;
      this.first++;
    }

    const v = this.lookup.get(first);
    this.lookup.delete(first);
    return v;
  }

  push(v: any) {

    this.length++;

    if (this.elementExists && this.first === this.last) {
      this.last++;
    }
    else if (this.first === this.last) {
      this.elementExists = true;
    }
    else {
      this.last++;
    }

    return this.lookup.set(this.last, v);

  }

  enq(v: any) {
    return this.push.apply(this, arguments);
  }

  enqueue(v: any) {
    return this.push.apply(this, arguments);
  }

  deq() {
    return this.shift.apply(this, arguments);
  }

  dequeue() {
    return this.shift.apply(this, arguments);
  }

  unshift(v: any) {

    this.length++;

    if (this.elementExists && this.first === this.last) {
      this.first--;
    }
    else if (this.first === this.last) {
      this.elementExists = true;
    }
    else {
      this.first--;
    }

    return this.lookup.set(this.first, v);
  }

  addToFront(v: any){
    return this.unshift.apply(this,arguments);
  }

  removeAll() {
    return this.clear.apply(this, arguments);
  }

  clear(): void {
    this.length = 0;
    this.elementExists = false;
    this.first = 0;
    this.last = 0;
    this.lookup.clear();
  }

}

takeaways:

it turns out, you can call getByIndex(), as Tim's suggestion points out.
Using Map is surprisingly ~10% faster than POJSO, possibly only because with a POJSO the integers need to get converted to strings for lookup.
The Map implementation is about 20% faster than doubly-linked list, so a doubly-linked list is not that much slower. It's probably slower mostly because we must create a container object with next/prev pointers for each item in the queue, whereas with the non-linked list implementation, we can insert primitives in the queue, etc.
The doubly-linked list allows us to remove/insert items from the middle of the queue in constant time; we cannot do the same with the non-linked list implementation as is.
All of the above are orders of magnitude more performant than a plain array when operating on an array with more than 10,000 elements or so.

I have some constant time queue implementations here: https://github.com/ORESoftware/linked-queue

Tim had a good suggestion, to make getByIndex() easier to use - we can do this:

  getByIndex(v: number) {

    if(!Number.isInteger(v)){
      throw new Error('Argument must be an integer.');
    }

    return this.lookup.get(v + this.first);
  }

that way to get the 5th element in the queue, all we need to do is:

getByIndex(4);

edited Jun 7, 2018 at 23:29

answered Jun 4, 2018 at 23:13

Alexander Mills

102k167 gold badges549 silver badges936 bronze badges

11 Comments

Felix Kling Over a year ago

So, what I was talking about is possible after all ;)

Minderov Over a year ago

Just out of curiosity, why do you think this is better than a Linked List? I don't see accessing an element in Map being faster than fetching an element form the tail of a Linked List. According to ECMAScript Specs Map access time is on average less than O(n) versus O(1) of a Linked List

Alexander Mills Over a year ago

@FelixKling yeah I didn't think about using incrementing/decrementing integers , but that makes it possible to reference previous items

Alexander Mills Over a year ago

@Minderov in this case the only way to know for sure is to try the two different solutions and then see which one is faster.

Minderov Over a year ago

@AlexanderMills I agree. If you are going to test it, please come back with the results after. Very curious!

|

Collectives™ on Stack Overflow

Create array structure in JavaScript that omits indexing

3 Answers 3

4 Comments

1 Comment

11 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

1 Comment

11 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related