Memoizes range for efficiency

[colinhanrahan]

This breaks determinism, but only because the order of cells in agents' cellsInRange changes. I'm looking into why, because the order should really be the same. Also, a good next step to optimize findNeighborhood would be to make cellsInRange a set and find its intersection with Sugarscape's self.agents list.

If the memoization takes up too much storage, we can instead store the difference between the current range and the previous range (the additional cells added) rather than storing the whole list for every distance.

[colinhanrahan]

The order was different because self.cellsInRange was a reference to cell.ranges[distance] instead of a copy, which was then shuffling cell.ranges[distance] in findBestCell. This has been fixed and determinism is now maintained with the current repo.

@nkremerh can you run a mass test to compare runtime when you get the chance?

[colinhanrahan]

Finding 50 different radial ranges for 50x50 cells in the environment takes exponentially too long. Thoughts?

[nkremerh]

If cell X can see cell Y at range 10, then cell Y can also see cell X at range 10, etc. See if that provides a useful reduction?

[colinhanrahan]

@nkremerh Ready for testing.

[nkremerh]

Initial testing (50 seeds out to 2k timesteps) shows a significant time reduction:

Current repo head:

real    15m38.914s
user    231m6.808s
sys 0m10.446s

This branch:

real    11m14.852s
user    166m25.475s
sys 0m7.853s

Will test more thoroughly before merge, but I will be checking style and general fit and finish first.

[nkremerh]

Let me know if any of the readability changes I made accidentally broke any logic.

[colinhanrahan]

No, everything looks good. In terms of other optimizations, I'm eyeing findNeighborhood to see if I can use set intersection with an agent's cells in range and a set of all cells with agents on them. I'm not sure if it would actually be faster with larger numbers of agents.

As for this PR, there might be a way to speed up radial range calculations when the max distance is smaller. Currently, even when the max distance is less than the environment size, every cell combination has to be checked (2500 choose 2). I'm going to keep thinking about this for now, but barring any further breaks or issues, the current implementation can be merged.

[nkremerh]

Testing 20 seeds with radial vision and movement and moore neighborhoods:

Current repo head:

real    60m26.204s
user    229m56.582s
sys 0m2.806s

This branch:

real    8m40.028s
user    75m46.485s
sys 0m5.386s

Even with the same seeds and configs, the outcomes between the two branches are different due to when random events happen. However, the societal outcomes are more or less the same.