Summary

I have a problem that seems as if it is likely to have many good known solutions with different performance characteristics. Assuming this is the case, a great answer could include code (or pseudo code), but ideally, it would reference the literature and give them name of this problem so I can explore the problem in greater detail and understand the space of solutions.

The problem

I have an initially empty array that can hold identifiers. Any identifiers in the array are unique (they're only ever in the array once).

var identifiers: [Identifier] = []

Over time a process will insert identifiers in to the array. It won't just append them to the end. They can be inserted anywhere in the array.

Identifiers will never be removed from the array – only inserted.

Insertion needs to be quick, so probably the structure won't literally be an array, but something supporting better than linear time insertion (such as a BTree).

After some identifiers have been added to identifiers, I want to be able to query the current position of any given identifier. So I need a function to look this up.

A linear time solution to this is simply to scan through identifiers from the start until an identifier is found, and the answer is the index that was reached.

func find(identifier: Identifier) -> Int? {
  for index in identifiers.indices {
    if identifiers[index] == identifier {
      return index
    }
  }

  return nil
}

But this linear scaling with the size of the array is problematic if the array is very large (perhaps 100s of millions of elements).

A hash map doesn't work

We can't put the positions of the identifiers in to a hash map. This doesn't work because identifier positions are not fixed after insertion in to the array. If other identifiers are inserted before them, they will drift to higher indexes.

However, a possible acceleration for the linear time algorithm would be to cache the initial insertions position of an identifier and begin a linear scan from there. Because identifiers are only inserted, it must be at that index, or an index after it (or not in identifiers at all). Once the identifier is found, the cache can be updated.

Another option could be to update the hash-map after any insertions to correct any positions. However this would slow down insert so that it is potentially a linear time operation (as previously mentioned, identifiers is probably not a literally array but some other structure allowing better than linear time insertion).

Summary

There's a linear time solution, and there's an optimisation using a hash map (at the cost of roughly doubling storage). Is there a much better solution for looking up the current index of an identifier, perhaps in log time?

CodePudding user response：

You can use an order-statistic tree for this, based on a red-black tree or other self-balancing binary tree. Essentially, each node will have an extra integer field, storing the number of descendants it currently has. (Insertion and deletion operations, and their resultant rotations, will only result in updating O(log n) nodes so this can be done efficiently). To query the position of an identifier, you examine the descendant count of its left subtree and the descendant counts of the siblings of each of its right-side ancestors.

Note that while the classic use of an order-statistic tree is for a sorted list, nothing in the logic requires this; "node A is before node B" is all you need for insertion, tree rotations don't require re-evaluating the ordering, and having a pointer to the node (and having nodes store parent pointers) is all you need to query the index. All operations are in O(log n).