ContiniousSpace: Speedup get_neighbors by using KDTree#1619
ContiniousSpace: Speedup get_neighbors by using KDTree#1619
get_neighbors by using KDTree#1619Conversation
Speedup the get_neighbors() function in ContiniousSpace by using a KDTree. It improves performance especially with a large number of agents. For small number of agents, the performance is roughly the same, without large regressions.
It's now needed for the KDTree functionality in the get_neighbors function of ContiniousSpace.
|
We didn't have SciPy as an dependency before, so I don't know if that's an acceptable addition. |
|
I actually evaluated the possibility to use a KDTree sometime ago instead of the current implementation, unfortunately if I recall well they are really really slower to build and update, in this case this is not showing because flockers has a fixed number of agents so this doesn't apply, but a lot of performance degradation will happen if removal and adding of agents happened. As a side note, I think that you didn't update the KDTree when agents are added, this would result in wrong calculations on the neighbors. But anyway this algorithm is not a good choice for the reasons mentioned above. |
|
Thanks for this insights, unfortunate to hear but good to know. I will close this PR. |
2 participants
Speedup the
get_neighbors()function inContiniousSpaceby using a SciPy KDTree. It improves performance especially with a large number of agents. For small number of agents, the performance is roughly the same, without large regressions.I've run some benchmarks on the boid_flockers model, with different number of agents, measuring the total runtime in seconds.
Please review carefully, both changes in functionality/behaviour as performance.