avoid traversing entire agent path for each agent update

CityScope / CS_Cooper-Hewitt

meta repo/sandbox repo for keeping everything related to the Cooper Hewitt exhibition

5 stars 2 forks source link

avoid traversing entire agent path for each agent update #104

Closed aberke closed 5 years ago

aberke commented 5 years ago

Without this change there is an O(N*M) operation for each call of update

where N=number of total agents
where M=length of agent path

With this change the operation is instead O(N) for each update

agrignard commented 5 years ago

@aberke I will try to merge this before the v1.0 release however I just want to understand clearly what you did here:

so instead of calling

if (path.indexOf(toNode) == 0)

you replace it by

if (pathIndex == 0)

where pathIndex is computed only ones?

That's the only main difference I see. Do you think path.indexOf(toNode) iterate through all the graph?

aberke commented 5 years ago

Hi @agrignard, The answer is yes. The reason this is very helpful: ArrayList.indexOf is O(N) in complexity where N is the number of items in the array (i.e. nodes in the path). My use of updating the index is just O(1)