Initialize array in amortized constant time -- what is this trick called?
- by user946850
There is this data structure that trades performance of array access against the need to iterate over it when clearing it. You keep a generation counter with each entry, and also a global generation counter. The "clear" operation increases the generation counter. On each access, you compare local vs. global generation counters; if they differ, the value is treated as "clean".
This has come up in this answer on Stack Overflow recently, but I don't remember if this trick has an official name. Does it?
One use case is Dijkstra's algorithm if only a tiny subset of the nodes has to be relaxed, and if this has to be done repeatedly.
