NetLogo/NetLogo — Issue #10: performance bug: "one-of turtles" is O(n), should be O(1)-ish
Author: SethTisue
Created: 2011-10-31 19:34:13+00:00
State: open

both TreeAgentSet and ArrayAgentSet are affected

I made a benchmark to measure it, models/test/other/One-Of Turtles Benchmark.nlogo

TreeAgentSet and ArrayAgentSet are different problems.

in the TreeAgentSet case, we know the sets contain no dead agents. we could go straight to a random agent in O(log n) time if we were using a tree that knew the size of it's subtrees. e.g. starting at root if we have 10 agents on the left and 7 on the right, we have a 1 in 18 chance to stop, a 10 in 18 to go left, and a 7 in 18 to go right. but java's TreeMap.Entry doesn't store this information.

in the ArrayAgentSet case, the array may contain dead agents. we could pick randomly and if we hit a dead agent pick again, but then the worst-case runtime is unbounded. can we be cleverer? we can't pick a random location and scan forward for the next live turtle, because that would favor live turtles that follow clusters of dead ones.