Mirror of forum.nim-lang.org

5622 :: Best way to store/search/etc and an int-int data structure

• drkameleon (orginal) [2019-12-02T08:42:40+01:00] view original

  Couldn't render post #34926.

---

• ducdetronquito (orginal) [2019-12-02T09:17:30+01:00] view original

  Hi, I have no answers yet, but only questions:

  Have you benchmarked this portion of code and are you sure this a bottleneck of your program ?

  Have you tried to use a hash table provided by the standard library ?

---

• Stefan_Salewski (orginal) [2019-12-02T09:35:16+01:00] view original

  For a small number of values linear search may be OK; when values do not change much, you may sort them and do a binary search. Or use a hash table, or maybe a tree structure.

---

• mratsim (orginal) [2019-12-02T11:07:15+01:00] view original

  So you want an integer set? DO you have any constraints on memory use?

  Are those in a specific range like 0 ..< N?

  If yes you may reuse the ideas between sparse sets, which I use to support random sampling for Monte Carlo Tree Search (game simulations, perf bottleneck for IA algorithm) and for my multithreading runtime:

  • https://github.com/mratsim/golem-prime/blob/master/src/core/c_empty_points.nim
  • https://github.com/mratsim/weave/blob/master/weave/datatypes/sparsesets.nim

  You keep 2 arrays: one that maps a key to a position in a second array, the second arrays stores the actual value.

---

• cblake (orginal) [2019-12-02T12:35:33+01:00] view original

  For the curious, that sparse-dense array construction of mratsim's impl is useful when keys are sparse-subsets of a small universe and hails from Preston Briggs' Rice PhD thesis in 1992, but has this more self-contained follow-up paper:

  http://dcs.gla.ac.uk/~pat/ads2/papers/p59-briggs%5b1%5d.pdf

  If you need this to be an "associative array" with "satellite data" as values for given keys, that is a straightforward extension where the dense array can be an array of pairs (or you could have a parallel dense value array).

  At some slightly different point in the design space is Varghese's Aggregate Bit Vectors which do not allow associative extension, https://cseweb.ucsd.edu/~varghese/PAPERS/icnp2002.pdf , which is also pretty easy to implement.

  And, of course, Table[int,int] is not actually that slow either.

---