nimforum mirror - pop for a set - is there something prettier?

HJarausch (orginal) [2020-12-07T17:26:28+01:00] view original

Unfortunately, the built-in (bit) set type doesn't have a pop procedure (as does HashSet).

There must be something prettier than


proc pop[T]( S:var set[T] ) : T =
  if card(S) == 0 :
    raise newException(IndexDefect,"pop on an empty set")
  var found : T
  for e in S :
    found= e
    break
  S.excl(found)
  found

Many thanks for a hint, Helmut

cblake (orginal) [2020-12-07T17:43:47+01:00] view original

Beauty is subjective, but maybe this?

proc pop[T](s: var set[T]): T =
  if card(s) == 0:
    raise newException(IndexDefect, "pop on an empty set")
  for e in s:
    s.excl e
    return e

lqdev (orginal) [2020-12-07T17:44:19+01:00] view original

Well, that's because pop is kind of against how bitsets work. There is no insertion order preserved in a set[T], so really there's nothing to pop.

What would you need a pop operation for?

disruptek (orginal) [2020-12-07T17:53:00+01:00] view original

May as well skip the cardinality test.

Stefan_Salewski (orginal) [2020-12-07T18:00:03+01:00] view original

If pop() operation is your priority, then you may use instead a priority queue like

https://nim-lang.org/docs/heapqueue.html

I wonder how iterating over sets works at all -- looking at items() it iterates from low() to high(), but I do not fully trust the comment in

https://nim-lang.org/docs/iterators.html#items.i%2Cset%5BT%5D

iterates only over the elements that are really in the set

From source code it iterates from low to high, and I would guess that both are type properties.

HJarausch (orginal) [2020-12-07T18:10:43+01:00] view original

What would you need a pop operation for?

There are two cases:

I know there is only one element left in the set, and I want to get this

The elements of a set are processed one at a time in any order until the set is empty. But the algorithm doesn't fit a for loop

mratsim (orginal) [2020-12-07T19:02:37+01:00] view original

There are many implementations of sets and no one size fits all. There are tradeoffs in operations supported, space usage and CPU overhead.

For example Nim sets have:

the smallest space usage.

low CPU overhead for sets operations

high overhead for iteration (since it also iterates on unset items in the range)

supports only operations that are positional (i.e. no random item poping if you don't know it's value)

If you have specific requirements.

Write your own tuned to your needs. I've written plenty:

Sets for random available thread selection in multithreading: https://github.com/mratsim/weave/pull/15/files (ou can see another custom set I replaced inside)

Set for random move in MonteCarlo simulations: https://github.com/mratsim/golem-prime/blob/8953347/src/datatypes.nim#L105-L118

I usually start by writing my requirements, review if Nim sets fits and if not why and the implementation can be derived from those, for example for Monte-Carlo:


    # We need a set/hashset with the following properties:
    #  - Can store up to ~500 elements at most (covered by `set` and `Hashset`)
    #  - Incl and Excl as fast as possible (in hot path) (covered by `set` and `Hashset`)
    #  - Can take the length without iterating (in hot path) (covered by `Hashset`, can use a int16 length field or popcount with `set`)
    #  - Can take a random value from the set as fast as possible (in hot path for Monte-Carlo simulations) (covered by ????)
    #  - Have access to the last inserted elements for ko checking
    
    # Implementation
    # - An array of indices that maps input -> -1 if not present in set or its index in an array of value present (allows incl/excl)
    # - An (array of values + length) present in the set (allows fast random pick).

doofenstein (orginal) [2020-12-07T19:05:12+01:00] view original

on the topic of bit set iteration it's currently very inefficient, because it checks every element instead of using count leading/trailing zeroes.

disruptek (orginal) [2020-12-07T19:39:23+01:00] view original

Another reason to want pop is that you're writing a generic, of which the example is one.

cblake (orginal) [2020-12-07T20:25:01+01:00] view original

Along the lines of what @mratsim suggests you could also speed up iteration over sparsely populated bitsets with something called an Aggregate Bit Vector. The core idea is just for each block of 64-bits in the lower level bit vector, if any bit is 1, you set the bit in the index to be 1. Then you can skip all zero index values 64x faster. You can iterate the design with another index level to iterate 4096x faster. More than 2 index levels would not make any sense for 65536-slot limited Nim set[T]. On each incl/excl you would need to do 2..3 sets, though.

HJarausch (orginal) [2020-12-08T16:04:50+01:00] view original

Thanks for all these comments. If I have a set S I can say


for e in S :
  echo e

Does Nim construct an iterator of S like items(S) [which doesn't work] ? If yes, how is it called - one could assign via let and call it once to an element of a set.

Araq (orginal) [2020-12-08T17:15:46+01:00] view original

I've said it before but many limitations of sets are the result of lacking a good bitops module when I wrote the set implementation. A pop for bitsets is definitely not beyond our limits. However, we need to hesitate to add things that are only useful for code competitions. unicode.reverse -- I am looking at you.

timothee (orginal) [2020-12-08T20:04:24+01:00] view original

pop could be added to std/setutils (refs https://github.com/nim-lang/Nim/pull/16276),

as i argued here https://github.com/nim-lang/Nim/pull/16276#discussion_r537186214 having a dedicated sets module instead of system allows growing it without bloating the rest.

Mirror of forum.nim-lang.org

7220 :: pop for a set - is there something prettier?