Mirror of forum.nim-lang.org

7358 :: system.set

• MichalMarsalek (orginal) [2021-01-09T13:36:11+01:00] view original

  Hello, I am missing two features in the system.set type.

  1. Support for larger ranges. set[uint32] would be huge, but I think that set[int24] (where type int24 = range[0..<2^24]) would be reasonable (2MB)?

  2. func empty(s: set[T]): bool =

     s.card == 0

  But implemented more efficiently (you don't need to know the exact cardinality just to check if a set is empty, you can exit looping through the bitvector as soon as you find a word with nonzero popcount, right?). I'd like to see other functions like

  func intersects(a, b: set[T]): bool =

  not empty(a*b)

  Again implemented more efficiently than that.

---

• mratsim (orginal) [2021-01-09T14:07:38+01:00] view original

  1. Use hashsets or intsets

  • https://nim-lang.org/docs/sets.html
  • https://nim-lang.org/docs/intsets.html

  2. When a set can take at most 2 bytes, it's better to do unconditional popcount instead of a conditional test after each byte.

---

• MichalMarsalek (orginal) [2021-01-09T14:21:08+01:00] view original

  Dammit, I planned to mention I know both hashsets and intsets, this question is not about that.

---

• cblake (orginal) [2021-01-09T18:55:43+01:00] view original

  You can also use the diTab or diSet in adix which can automatically use a "direct index" array where entries are the minimum number of needed bits. E.g. your 24 bits or 21 bits or whatever. It's not a bit vector style and so has different trade offs. E.g., diTab has a faster iteration over a sparsely populated set, but bitvectors likely take up less space.

---