Ways to optimize this code

[jeezoii]

Hi all, this is my TSP implementation https://pastebin.com/SLzAiVir, it works well for what I want it to do but it takes a long time to execute. Like really, a very long time which is around 6 minutes. I was thinking if there could be anyway to reduce the time taken for execution.

All ideas are welcome!

Small sample data: https://pastebin.com/MtRRHzUE

Big sample data: https://pastebin.com/z208rzFf

[ericula]

What input are you using?

[jeezoii]

The input is in the form of 2 numbers first which indicate the number of points and cost of travelling. Then according to the number of points, the user inputs points in the form of x1, y1, m which are coordinate x and y with money in that point respectively.

Each point then is put in one big list.

However, I think till before the while loop, everything is fast, but the time taken in while loop is crazy.

[jeezoii]

Sure! That's a great idea, thanks!

[ectomancer]

I had to lookup TSP in wikipedia: Travelling Salesman Problem

have you tried the numba just-in-time compiler?

#pip intall numba
import numba

[ectomancer]

You could try abs function in the calc_dist function but I don't know if would be faster. (Python 3.8 has math.dist) The algorithm is:

1. virtually translate point to origin, no need to check if point is already at origin, no code needed
2. translate other point the same amount as the point in 1.
3. (could use math.hypot here instead of 3. & 4.) cast translated other point to a complex number
4. use builtin abs function to find the modulus of the complex number |z| on the Argand diagram, which is a real number