Performance issue with node.py about python-pathfinding HOT 6 CLOSED

Very good work! please provide a Pull Request!

from python-pathfinding.

@brean, PR is created please review. Please note if we want to make it even faster the whole thing would need to be rewritten with numba in mind.

from python-pathfinding.

I am not sure about numba, the idea of python-pathfinding was to be as little dependent on other libraries as possible, with education in mind, for performance I would probably go with a c++ wrapper in the first place.

Yeah I agree.

However, with currently over 260 projects using python-pathfinding according to github, I think many of these might benefit from a numba-version, I am unsure how we can provide both.

It would require a rewrite and lots of testing. Numba class support is in beta last I checked.

A numba-version would probable be its own pathfinding-library and we can close this issue.

Yeah I agree too.

Thanks for getting this reviewed and merged so quickly.

from python-pathfinding.

PS: we really need to remove nsmallest from the implementation as that requires looping through the whole open_list which kind of defeats the purpose of using a heapq in the first place.

I see why nsmallest is being used though. The reason is the open_list.remove which invalidates the heap. I read your suppose to heapify to make the heap valid again right after the remove.

An alternative approach maybe to just put the things you want to remove into a dict and when you pop you check the dict to see if it exists in it. If it does you ignore it.

Let me know if you want me to create a PR for both issues.

I noticed the above change also changes the result but the path actually looked at lot better. I am not entirely sure why though, it could be because because if the f value is the same you get a different order than above tuple value.

from python-pathfinding.

Alright this will take some time. Ran the tests and there lots of failures to go through.

from python-pathfinding.

merged. Thanks a lot!
I am not sure about numba, the idea of python-pathfinding was to be as little dependent on other libraries as possible, with education in mind, for performance I would probably go with a c++ wrapper in the first place.
However, with currently over 260 projects using python-pathfinding according to github, I think many of these might benefit from a numba-version, I am unsure how we can provide both.
A numba-version would probable be its own pathfinding-library and we can close this issue.

from python-pathfinding.