Comments (3)
I think we can be cleverer on ArrayAgentSet, if it is acceptable to mutate the array. The general strategy would be something like what follows.
def selectRandom(a: Array[Agent], n: Int = 0): Option[Agent] = {
if (a.isEmpty || n >= a.length)
None
else {
val i = Random.nextInt(a.length - n) + n
val agent = a(i)
if (agent.isAlive)
Some(Agent)
else {
a(i) = a(n)
a(n) = agent
selectRandom(a, n + 1)
}
}
}
As I understand the time-complexity of get/update, this would be O(1) in the best case and only O(n) in the worst-case, which is what we have now anyway.
from netlogo.
If it were possible for AgentSets to subscribe to "death events" for contained agents, this would be a lot easier to do efficiently in both cases.
from netlogo.
You can actually do something quite similar to @mrerrormessage's solution without modifying the array. Instead, you can use a map to track which elements have been eliminated and redirect to those still in the candidate pool. As a bonus, this can operate on any Seq
-like data structure, not just arrays. Note that these methods also generalize to n-of
to make that O(sample size)-ish. Here's a generalized solution I came up with:
def sample[T: Manifest](s: Seq[T], sampleSize: Int, pred: T => Boolean = (x: T) => true): Seq[T] = {
val m = new mutable.OpenHashMap[Int, T](s.size)
val res = new Array[T](sampleSize)
var insertIndex = 0
var startIndex = 0
while (insertIndex < sampleSize) {
val i = Random.nextInt(s.size - startIndex) + startIndex
val x: T = m.put(i, s(startIndex)).getOrElse(s(i))
if (pred(x)) {
res(insertIndex) = x: T
insertIndex += 1
}
startIndex+=1
}
res
}
However, note that the constant factor on the hashmap lookup does hurt the performance of this. I compared it to @mrerrormessage's solution, but cloning the array at the beginning. Under 500 elements, the array version still beats the map version, especially if a decent percent of the agents are dead. Above that, the map version wins, unless the sample size is largish or there are a lot of dead agents. I tried various types of maps (OpenHashMap
performed by far the best) and with size hints (though they didn't help).
I also tried doing this with immutable Vector
s, since their pretty perfect for this situation (constant time read and write, persistent), but the map version beat it by a lot.
I tested a couple other solutions too, but nothing worth mentioning. Main takeaway: hot damn, cloning arrays is fast.
A hybrid solution that clones the array when the agentset is small and uses a map when big could be nice, but is perhaps is unnecessarily complicated.
from netlogo.
Related Issues (20)
- Broken symlink access in models library viewer HOT 3
- Unable to save included file being edited in separate window HOT 1
- Error in behavior space HOT 1
- java.lang.IllegalStateException: cannot open system clipboard HOT 1
- Objective and automated ABM framework comparison HOT 3
- Arrow (`->`) is listed in the "Built-In Variables" section of dictionnary HOT 2
- BehaviorSpace updates plots when running headlessly HOT 2
- BehaviorSpace does not remember the number of threads from prior dialog
- Exception when reopening included file saved in separate window HOT 1
- BehaviorSpace bug (experiment runs on close) HOT 1
- BehaviorSpace enhancement: remember output file name
- If an included file is edited and closed it is not compiled.
- Why does a statistical code change the calculation result of the procedure? HOT 2
- Extension updates through the manager do not remove existing files HOT 1
- Using a constant as a global variable name gives unclear closing bracket error
- Users unable to join my activity on Hubnet - Netlogo HOT 2
- NetLogo 6.3.0 not using bundled Java 17 by default on Linux HOT 4
- Leaving and returning to a "dirty" Code Tab causes unnecessary compilation HOT 1
- Opening separate code tab with compilation error causes exception HOT 1
- How to use the command with-local-randomness correctly? HOT 6
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from netlogo.