Doing a little analysis on your code the overview is this:
================== PerfTool ==================
task |aver(s) |sum(s) |count |std
main loop | 0.863| 0.863| 1| 0.000
+-int loop | 0.001| 0.862| 758| 0.001
+-is_it_pal? | 0.000| 0.092| 287661| 0.000
+-store_res | 0.000| 0.082| 287661| 0.000
init | 0.019| 0.019| 1| 0.000
overall | 0.18| 0.88| 576082|-
As you can see for a string long 750 char it takes a total of 0.9s
Internally.
My expectation is that the most part was take by pieces:
# is it a palindrome?
# store result
# is it the best so far?
But this is not true, because they took less than 0.2s of 0.8s take by internal loop.
So, the major lost of time is here:
zip(range(len(array) - substring_length), [x + substring_length for x in range(len(array) - substring_length)]):
the data preparation for the internal loop, takes 0.6s (75% of the internal loop)
this is the less efficient part of whole algo.
The time is spent in create and destroy tons of substrings, so the direction is to use another data structure in order to avoid this effect.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…