search

wannesm / dtaidistance

Time series distances: Dynamic Time Warping (fast DTW implementation in C)
Other
1.08k stars 184 forks source link

kbest_matches_fast is 5.5x slower on master than on 26c3962; k = None is 2.3x faster than k = len(series)-1 #185

Closed tommedema closed 1 year ago

tommedema commented 1 year ago

Recently I was surprised that my scripts seem to be running significantly slower (very noticeable), and so I did some digging.

Consider this standalone test case:

%%timeit

from dtaidistance.subsequence.dtw import subsequence_search
import numpy as np

series = np.array(
    [[0.032258063554763794, 0.12903225421905518, 0.09677419066429138, 0.19354838132858276, 0.22580644488334656], [0.14516128599643707, 0.4516128897666931, 0.5483871102333069, 0.4193548262119293, 0.032258063554763794], [0.22580644488334656, 0.11290322244167328, 0.06451612710952759, 0.11290322244167328, 0.3870967626571655], [0.09677419066429138, 0.19354838132858276, 0.16129031777381897, 0.12903225421905518, 0.22580644488334656], [0.16129031777381897, 0.06451612710952759, 0.032258063554763794, 0.09677419066429138, 0.12903225421905518], [0.7096773982048035, 0.7419354915618896, 0.5806451439857483, 0.5483871102333069, 0.774193525314331], [0.5806451439857483, 0.5483871102333069, 0.4516128897666931, 0.25806450843811035, 0.6451612710952759], [0.16129031777381897, 0.35483869910240173, 0.25806450843811035, 0.12903225421905518, 0.3870967626571655], [0.5806451439857483, 0.7580645084381104, 0.9354838728904724, 0.9032257795333862, 0.8709677457809448], [0.8709677457809448, 0.9677419066429138, 0.8064516186714172, 0.6129032373428345, 0.7419354915618896], [0.8064516186714172, 0.9354838728904724, 0.8709677457809448, 0.9032257795333862, 0.774193525314331], [0.8387096524238586, 0.774193525314331, 0.7419354915618896, 0.8709677457809448, 0.9354838728904724], [0.8387096524238586, 0.8709677457809448, 0.8064516186714172, 0.774193525314331, 0.9032257795333862], [0.9354838728904724, 0.9677419066429138, 0.8709677457809448, 0.9032257795333862, 0.8387096524238586], [0.8709677457809448, 1.0, 0.9354838728904724, 0.9677419066429138, 0.9032257795333862], [0.9677419066429138, 0.8709677457809448, 0.4838709533214569, 0.5645161271095276, 0.7096773982048035], [0.7096773982048035, 0.8064516186714172, 1.0, 0.9032257795333862, 0.9677419066429138], [0.4516128897666931, 0.6612903475761414, 0.6612903475761414, 0.8064516186714172, 0.9032257795333862], [0.3870967626571655, 0.4516128897666931, 0.6612903475761414, 0.6612903475761414, 0.8064516186714172], [0.12903225421905518, 0.09677419066429138, 0.3870967626571655, 0.4516128897666931, 0.6451612710952759], [0.8709677457809448, 0.7096773982048035, 0.6451612710952759, 0.25806450843811035, 0.5483871102333069], [0.14516128599643707, 0.5483871102333069, 0.8709677457809448, 0.7096773982048035, 0.6451612710952759], [0.25806450843811035, 0.12903225421905518, 0.22580644488334656, 0.16129031777381897, 0.5645161271095276], [0.8064516186714172, 0.5161290168762207, 0.7096773982048035, 0.7419354915618896, 0.774193525314331], [0.9677419066429138, 0.9032257795333862, 0.8064516186714172, 0.5806451439857483, 0.774193525314331], [0.9354838728904724, 1.0, 0.8387096524238586, 0.9677419066429138, 0.9032257795333862], [0.9032257795333862, 0.9354838728904724, 1.0, 0.8709677457809448, 0.9677419066429138], [0.8709677457809448, 0.8064516186714172, 0.9354838728904724, 0.9677419066429138, 1.0], [0.6774193644523621, 1.0, 0.8709677457809448, 0.8387096524238586, 0.9677419066429138], [0.32258063554763794, 0.29032257199287415, 0.4193548262119293, 0.6935483813285828, 1.0], [0.5483871102333069, 0.32258063554763794, 0.29032257199287415, 0.4193548262119293, 0.725806474685669], [0.6451612710952759, 0.5161290168762207, 0.774193525314331, 0.4838709533214569, 0.29032257199287415], [0.35483869910240173, 0.32258063554763794, 0.6129032373428345, 0.4516128897666931, 0.774193525314331], [0.12903225421905518, 0.22580644488334656, 0.19354838132858276, 0.35483869910240173, 0.32258063554763794], [0.06451612710952759, 0.12903225421905518, 0.22580644488334656, 0.19354838132858276, 0.32258063554763794], [0.09677419066429138, 0.032258063554763794, 0.06451612710952759, 0.12903225421905518, 0.19354838132858276], [0.16129031777381897, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759, 0.12903225421905518], [0.19354838132858276, 0.12903225421905518, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759], [0.4193548262119293, 0.29032257199287415, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759], [0.4516128897666931, 0.3870967626571655, 0.25806450843811035, 0.06451612710952759, 0.032258063554763794], [0.4516128897666931, 0.25806450843811035, 0.7419354915618896, 0.5806451439857483, 0.3870967626571655], [0.16129031777381897, 0.22580644488334656, 0.4516128897666931, 0.25806450843811035, 0.7419354915618896], [0.5161290168762207, 0.16129031777381897, 0.22580644488334656, 0.4516128897666931, 0.25806450843811035], [0.5483871102333069, 0.4838709533214569, 0.16129031777381897, 0.22580644488334656, 0.4193548262119293], [0.12903225421905518, 0.5161290168762207, 0.4516128897666931, 0.16129031777381897, 0.22580644488334656], [0.6129032373428345, 0.16129031777381897, 0.09677419066429138, 0.12903225421905518, 0.4193548262119293], [0.7419354915618896, 0.5806451439857483, 0.16129031777381897, 0.09677419066429138, 0.12903225421905518], [0.32258063554763794, 0.12903225421905518, 0.35483869910240173, 0.5806451439857483, 0.6129032373428345], [0.3870967626571655, 0.32258063554763794, 0.12903225421905518, 0.35483869910240173, 0.5806451439857483], [0.29032257199287415, 0.3870967626571655, 0.32258063554763794, 0.12903225421905518, 0.35483869910240173], [0.12903225421905518, 0.09677419066429138, 0.25806450843811035, 0.32258063554763794, 0.29032257199287415], [0.4193548262119293, 0.12903225421905518, 0.09677419066429138, 0.25806450843811035, 0.29032257199287415], [0.16129031777381897, 0.12903225421905518, 0.25806450843811035, 0.32258063554763794, 0.29032257199287415], [0.06451612710952759, 0.032258063554763794, 0.16129031777381897, 0.12903225421905518, 0.25806450843811035], [0.16129031777381897, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794, 0.12903225421905518], [0.8709677457809448, 0.8064516186714172, 0.9032257795333862, 0.9677419066429138, 1.0], [0.9032257795333862, 1.0, 0.9354838728904724, 0.8709677457809448, 0.9677419066429138], [0.5806451439857483, 0.6774193644523621, 0.6290322542190552, 0.9032257795333862, 1.0], [0.5806451439857483, 0.6129032373428345, 0.7096773982048035, 0.6612903475761414, 0.9354838728904724], [0.4838709533214569, 0.5806451439857483, 0.6451612710952759, 0.6774193644523621, 0.7419354915618896], [0.7419354915618896, 0.5161290168762207, 0.6129032373428345, 0.6774193644523621, 0.7096773982048035], [0.4516128897666931, 0.5161290168762207, 0.7419354915618896, 0.5806451439857483, 0.6774193644523621], [0.774193525314331, 0.4838709533214569, 0.5161290168762207, 0.5806451439857483, 0.7419354915618896], [0.8064516186714172, 0.774193525314331, 0.5161290168762207, 0.5483871102333069, 0.6129032373428345], [0.6451612710952759, 0.5806451439857483, 0.7419354915618896, 1.0, 0.9677419066429138], [0.9677419066429138, 0.6774193644523621, 0.6129032373428345, 0.774193525314331, 1.0], [1.0, 0.9677419066429138, 0.8709677457809448, 0.8064516186714172, 0.9354838728904724], [0.8387096524238586, 0.9032257795333862, 0.9354838728904724, 0.9677419066429138, 1.0], [0.8387096524238586, 0.8709677457809448, 0.9032257795333862, 0.9677419066429138, 1.0], [0.19354838132858276, 0.4516128897666931, 0.6451612710952759, 0.774193525314331, 0.7419354915618896], [0.06451612710952759, 0.16129031777381897, 0.19354838132858276, 0.4516128897666931, 0.6451612710952759], [0.20967741310596466, 0.06451612710952759, 0.032258063554763794, 0.09677419066429138, 0.14516128599643707], [0.09677419066429138, 0.16129031777381897, 0.22580644488334656, 0.06451612710952759, 0.032258063554763794], [0.19354838132858276, 0.16129031777381897, 0.29032257199287415, 0.09677419066429138, 0.032258063554763794], [0.06451612710952759, 0.032258063554763794, 0.22580644488334656, 0.30645161867141724, 0.4193548262119293], [0.5645161271095276, 0.12903225421905518, 0.06451612710952759, 0.032258063554763794, 0.22580644488334656], [1.0, 0.8387096524238586, 0.06451612710952759, 0.5, 0.09677419066429138], [0.22580644488334656, 0.3870967626571655, 0.4354838728904724, 1.0, 0.8387096524238586], [1.0, 0.9354838728904724, 0.6451612710952759, 0.5161290168762207, 0.35483869910240173], [0.9677419066429138, 0.8709677457809448, 0.774193525314331, 0.8225806355476379, 0.8225806355476379], [0.5806451439857483, 0.9354838728904724, 0.6774193644523621, 0.8387096524238586, 0.9677419066429138], [0.5161290168762207, 0.5806451439857483, 0.9677419066429138, 0.6774193644523621, 0.8387096524238586], [0.9354838728904724, 1.0, 0.6451612710952759, 0.5806451439857483, 0.7096773982048035], [0.25806450843811035, 0.22580644488334656, 0.29032257199287415, 0.32258063554763794, 0.7419354915618896], [0.12903225421905518, 0.22580644488334656, 0.29032257199287415, 0.25806450843811035, 0.35483869910240173], [0.9354838728904724, 0.9677419066429138, 0.9032257795333862, 0.5483871102333069, 0.6129032373428345], [0.8709677457809448, 1.0, 0.9677419066429138, 0.9032257795333862, 0.9354838728904724], [0.8548387289047241, 0.6451612710952759, 0.5806451439857483, 0.8064516186714172, 0.8548387289047241], [0.9677419066429138, 0.8709677457809448, 0.6774193644523621, 0.6129032373428345, 0.8387096524238586], [1.0, 0.9677419066429138, 0.8709677457809448, 0.7096773982048035, 0.6451612710952759], [0.9354838728904724, 0.8387096524238586, 1.0, 0.9677419066429138, 0.8709677457809448], [0.8064516186714172, 0.774193525314331, 0.9354838728904724, 0.8709677457809448, 0.9677419066429138], [0.4516128897666931, 0.5322580933570862, 0.5806451439857483, 0.7096773982048035, 0.774193525314331], [0.35483869910240173, 0.032258063554763794, 0.7419354915618896, 0.5806451439857483, 0.5483871102333069], [0.09677419066429138, 0.16129031777381897, 0.29032257199287415, 0.25806450843811035, 0.22580644488334656], [0.29032257199287415, 0.04838709533214569, 0.19354838132858276, 0.04838709533214569, 0.09677419066429138], [0.5483871102333069, 0.5161290168762207, 0.6774193644523621, 0.6451612710952759, 0.9032257795333862], [0.4838709533214569, 0.7096773982048035, 0.6774193644523621, 0.774193525314331, 0.6451612710952759], [1.0, 0.9032257795333862, 0.774193525314331, 0.8064516186714172, 0.725806474685669], [0.9032257795333862, 0.8709677457809448, 0.9354838728904724, 0.9677419066429138, 1.0], [0.7096773982048035, 0.6451612710952759, 0.8387096524238586, 0.9354838728904724, 0.9032257795333862], [0.25806450843811035, 0.4516128897666931, 0.6451612710952759, 0.4193548262119293, 0.5161290168762207], [0.22580644488334656, 0.12903225421905518, 0.06451612710952759, 0.25806450843811035, 0.4193548262119293], [0.19354838132858276, 0.22580644488334656, 0.12903225421905518, 0.06451612710952759, 0.25806450843811035], [0.19354838132858276, 0.09677419066429138, 0.29032257199287415, 0.12903225421905518, 0.16129031777381897], [0.19354838132858276, 0.06451612710952759, 0.12903225421905518, 0.09677419066429138, 0.22580644488334656], [0.06451612710952759, 0.09677419066429138, 0.12903225421905518, 0.032258063554763794, 0.16129031777381897], [0.17741934955120087, 0.17741934955120087, 0.032258063554763794, 0.06451612710952759, 0.09677419066429138], [1.0, 0.6774193644523621, 0.6129032373428345, 0.3709677457809448, 0.06451612710952759], [0.8064516186714172, 1.0, 0.6451612710952759, 0.5806451439857483, 0.33870968222618103], [0.774193525314331, 0.8709677457809448, 0.8387096524238586, 0.7096773982048035, 0.9354838728904724], [0.7419354915618896, 0.774193525314331, 0.8709677457809448, 0.8387096524238586, 0.7096773982048035], [0.5806451439857483, 0.4516128897666931, 0.4838709533214569, 0.6774193644523621, 0.7096773982048035], [0.5161290168762207, 0.5806451439857483, 0.4516128897666931, 0.4838709533214569, 0.6774193644523621], [0.24193547666072845, 0.5161290168762207, 0.5806451439857483, 0.4516128897666931, 0.4838709533214569], [0.24193547666072845, 0.29032257199287415, 0.24193547666072845, 0.4516128897666931, 0.5161290168762207], [0.06451612710952759, 0.032258063554763794, 0.12903225421905518, 0.19354838132858276, 0.22580644488334656], [0.16129031777381897, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794, 0.12903225421905518], [0.16129031777381897, 0.12903225421905518, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759], [0.16129031777381897, 0.12903225421905518, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794], [0.16129031777381897, 0.12903225421905518, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794], [0.29032257199287415, 0.16129031777381897, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794], [0.12903225421905518, 0.06451612710952759, 0.09677419066429138, 0.032258063554763794, 0.16129031777381897], [0.22580644488334656, 0.14516128599643707, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794], [0.24193547666072845, 0.08064515888690948, 0.16129031777381897, 0.08064515888690948, 0.032258063554763794], [0.3870967626571655, 0.29032257199287415, 0.20967741310596466, 0.032258063554763794, 0.09677419066429138], [0.19354838132858276, 0.032258063554763794, 0.35483869910240173, 0.30645161867141724, 0.5161290168762207], [0.5161290168762207, 0.19354838132858276, 0.032258063554763794, 0.3870967626571655, 0.30645161867141724], [0.6290322542190552, 0.7096773982048035, 0.5806451439857483, 0.7419354915618896, 0.35483869910240173], [0.5161290168762207, 0.8064516186714172, 0.6612903475761414, 0.7419354915618896, 0.6129032373428345], [0.9032257795333862, 0.9677419066429138, 1.0, 0.8064516186714172, 0.6451612710952759], [0.774193525314331, 0.9032257795333862, 0.9677419066429138, 1.0, 0.8064516186714172], [1.0, 0.9032257795333862, 0.9354838728904724, 0.8709677457809448, 0.9677419066429138], [0.6129032373428345, 0.4193548262119293, 0.5806451439857483, 1.0, 0.9677419066429138], [0.9032257795333862, 0.5483871102333069, 0.5967742204666138, 0.774193525314331, 0.6774193644523621], [0.7419354915618896, 0.8387096524238586, 0.9032257795333862, 0.6129032373428345, 0.6612903475761414], [0.8709677457809448, 0.9032257795333862, 0.9354838728904724, 0.9677419066429138, 1.0], [0.8709677457809448, 0.9032257795333862, 0.9354838728904724, 0.9677419066429138, 1.0], [0.774193525314331, 0.8064516186714172, 0.9354838728904724, 0.9677419066429138, 1.0], [0.9677419066429138, 1.0, 0.9354838728904724, 0.8709677457809448, 0.9032257795333862], [0.9032257795333862, 0.8709677457809448, 0.9354838728904724, 0.9677419066429138, 1.0], [0.7419354915618896, 0.8709677457809448, 0.9354838728904724, 0.9677419066429138, 1.0], [0.8709677457809448, 0.8387096524238586, 0.8064516186714172, 0.9354838728904724, 1.0], [1.0, 0.9032257795333862, 0.8709677457809448, 0.8387096524238586, 0.9677419066429138], [0.3870967626571655, 0.5483871102333069, 0.8387096524238586, 0.9677419066429138, 1.0], [0.20967741310596466, 0.09677419066429138, 0.3870967626571655, 0.5483871102333069, 0.9032257795333862], [0.9677419066429138, 0.7580645084381104, 0.16129031777381897, 0.29032257199287415, 0.4838709533214569], [0.19354838132858276, 0.9354838728904724, 0.725806474685669, 0.16129031777381897, 0.29032257199287415], [0.29032257199287415, 0.25806450843811035, 0.32258063554763794, 0.16129031777381897, 0.8387096524238586], [0.3709677457809448, 0.27419355511665344, 0.5161290168762207, 0.27419355511665344, 0.7096773982048035], [0.8064516186714172, 0.774193525314331, 0.6290322542190552, 0.33870968222618103, 0.25806450843811035], [0.4838709533214569, 0.35483869910240173, 0.4193548262119293, 0.3870967626571655, 0.6774193644523621], [0.29032257199287415, 0.3870967626571655, 0.4516128897666931, 0.4193548262119293, 0.35483869910240173], [0.9354838728904724, 0.9677419066429138, 0.25806450843811035, 0.19354838132858276, 0.06451612710952759], [0.5161290168762207, 0.8387096524238586, 0.6451612710952759, 0.5161290168762207, 0.5161290168762207], [0.4032258093357086, 0.4516128897666931, 0.5806451439857483, 0.4032258093357086, 0.32258063554763794], [0.14516128599643707, 0.32258063554763794, 0.5161290168762207, 0.4032258093357086, 0.4838709533214569], [0.032258063554763794, 0.14516128599643707, 0.32258063554763794, 0.5161290168762207, 0.4354838728904724], [0.06451612710952759, 0.032258063554763794, 0.14516128599643707, 0.32258063554763794, 0.5161290168762207], [0.22580644488334656, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794, 0.14516128599643707], [0.5806451439857483, 0.4838709533214569, 0.3870967626571655, 0.12903225421905518, 0.032258063554763794], [0.9677419066429138, 0.9354838728904724, 0.8225806355476379, 0.7096773982048035, 0.5483871102333069], [0.8064516186714172, 0.8387096524238586, 0.8709677457809448, 0.9677419066429138, 0.9354838728904724], [0.725806474685669, 0.774193525314331, 0.8064516186714172, 0.8387096524238586, 0.8709677457809448], [0.6451612710952759, 0.725806474685669, 0.774193525314331, 0.8064516186714172, 0.8387096524238586], [0.09677419066429138, 0.5483871102333069, 0.32258063554763794, 0.6451612710952759, 0.725806474685669], [0.032258063554763794, 0.06451612710952759, 0.09677419066429138, 0.5483871102333069, 0.32258063554763794], [0.12903225421905518, 0.032258063554763794, 0.06451612710952759, 0.09677419066429138, 0.5161290168762207], [0.22580644488334656, 0.12903225421905518, 0.032258063554763794, 0.06451612710952759, 0.09677419066429138], [0.4838709533214569, 0.4516128897666931, 0.22580644488334656, 0.09677419066429138, 0.17741934955120087], [0.17741934955120087, 0.17741934955120087, 0.32258063554763794, 0.25806450843811035, 0.35483869910240173], [0.12903225421905518, 0.22580644488334656, 0.25806450843811035, 0.17741934955120087, 0.17741934955120087], [0.09677419066429138, 0.032258063554763794, 0.12903225421905518, 0.16129031777381897, 0.19354838132858276], [0.35483869910240173, 0.06451612710952759, 0.09677419066429138, 0.032258063554763794, 0.12903225421905518], [0.22580644488334656, 0.35483869910240173, 0.06451612710952759, 0.09677419066429138, 0.032258063554763794], [0.3870967626571655, 0.12903225421905518, 0.16129031777381897, 0.32258063554763794, 0.032258063554763794], [0.9032257795333862, 1.0, 0.8709677457809448, 0.8387096524238586, 0.9677419066429138], [0.8387096524238586, 0.9354838728904724, 1.0, 0.9032257795333862, 0.8709677457809448], [0.9677419066429138, 0.8709677457809448, 0.9354838728904724, 1.0, 0.9032257795333862], [0.8709677457809448, 0.9677419066429138, 0.9032257795333862, 0.9354838728904724, 1.0], [0.8064516186714172, 0.8709677457809448, 0.9354838728904724, 0.9677419066429138, 1.0], [0.774193525314331, 0.7419354915618896, 0.9032257795333862, 0.9354838728904724, 1.0], [0.8709677457809448, 0.8064516186714172, 0.774193525314331, 0.9354838728904724, 0.9677419066429138], [0.8064516186714172, 0.9032257795333862, 0.9354838728904724, 0.9677419066429138, 1.0], [0.7419354915618896, 0.8387096524238586, 0.9354838728904724, 0.9677419066429138, 1.0], [0.6935483813285828, 0.774193525314331, 0.8709677457809448, 0.9677419066429138, 1.0], [0.4193548262119293, 0.5806451439857483, 0.8387096524238586, 0.7419354915618896, 0.7903226017951965], [0.5806451439857483, 0.5483871102333069, 0.4838709533214569, 0.6451612710952759, 0.8387096524238586], [0.8387096524238586, 1.0, 0.9032257795333862, 0.6451612710952759, 0.6774193644523621], [0.7419354915618896, 0.8709677457809448, 0.9354838728904724, 1.0, 0.9032257795333862], [1.0, 0.8870967626571655, 0.8064516186714172, 0.9354838728904724, 0.9677419066429138], [0.774193525314331, 0.7096773982048035, 0.8709677457809448, 1.0, 0.9677419066429138], [0.9677419066429138, 0.9354838728904724, 1.0, 0.8064516186714172, 0.8709677457809448], [0.8387096524238586, 0.9032257795333862, 0.9354838728904724, 0.9677419066429138, 1.0], [0.9032257795333862, 0.8064516186714172, 0.8709677457809448, 0.9354838728904724, 1.0], [0.8709677457809448, 0.9354838728904724, 0.8387096524238586, 0.9032257795333862, 0.9677419066429138], [1.0, 0.9032257795333862, 0.9677419066429138, 0.8709677457809448, 0.9354838728904724], [1.0, 0.12903225421905518, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794], [0.8387096524238586, 0.9032257795333862, 0.9354838728904724, 0.9677419066429138, 1.0], [0.9032257795333862, 0.8709677457809448, 0.9354838728904724, 0.9677419066429138, 1.0], [0.7903226017951965, 0.25806450843811035, 0.14516128599643707, 0.4516128897666931, 1.0], [0.6290322542190552, 0.22580644488334656, 0.6290322542190552, 0.4516128897666931, 0.7580645084381104], [0.6774193644523621, 0.35483869910240173, 0.16129031777381897, 0.09677419066429138, 0.27419355511665344], [0.16129031777381897, 0.35483869910240173, 0.4032258093357086, 0.6451612710952759, 0.5483871102333069], [0.12903225421905518, 0.032258063554763794, 0.16129031777381897, 0.35483869910240173, 0.4032258093357086], [0.09677419066429138, 0.22580644488334656, 0.06451612710952759, 0.12903225421905518, 0.032258063554763794], [0.29032257199287415, 0.06451612710952759, 0.19354838132858276, 0.032258063554763794, 0.09677419066429138], [0.14516128599643707, 0.14516128599643707, 0.29032257199287415, 0.22580644488334656, 0.19354838132858276], [0.032258063554763794, 0.19354838132858276, 0.14516128599643707, 0.14516128599643707, 0.22580644488334656], [0.4354838728904724, 0.6612903475761414, 0.29032257199287415, 0.06451612710952759, 0.032258063554763794], [0.4838709533214569, 0.3870967626571655, 0.4354838728904724, 0.6612903475761414, 0.29032257199287415], [0.6774193644523621, 0.8064516186714172, 0.7419354915618896, 0.5161290168762207, 0.6290322542190552], [0.8709677457809448, 0.6774193644523621, 0.8064516186714172, 0.7419354915618896, 0.5483871102333069], [0.774193525314331, 0.9677419066429138, 0.8709677457809448, 0.7096773982048035, 0.8064516186714172], [0.8709677457809448, 0.9032257795333862, 1.0, 0.8387096524238586, 0.9677419066429138], [0.725806474685669, 0.9677419066429138, 0.9032257795333862, 0.9354838728904724, 1.0], [0.8225806355476379, 0.9677419066429138, 0.5806451439857483, 0.8225806355476379, 1.0], [0.8064516186714172, 0.9354838728904724, 0.9677419066429138, 1.0, 0.8709677457809448], [0.9032257795333862, 0.8387096524238586, 0.9354838728904724, 0.9677419066429138, 1.0], [0.6129032373428345, 0.8709677457809448, 0.9677419066429138, 0.9032257795333862, 1.0], [0.9032257795333862, 0.8709677457809448, 0.6774193644523621, 0.9354838728904724, 1.0], [1.0, 0.9354838728904724, 0.9032257795333862, 0.7096773982048035, 0.9677419066429138], [0.9677419066429138, 0.8064516186714172, 0.5806451439857483, 0.774193525314331, 0.8387096524238586], [1.0, 0.9677419066429138, 0.8387096524238586, 0.6129032373428345, 0.8064516186714172], [0.9354838728904724, 1.0, 0.9677419066429138, 0.8387096524238586, 0.6451612710952759], [0.6451612710952759, 0.8387096524238586, 0.9354838728904724, 0.9677419066429138, 1.0], [0.9354838728904724, 1.0, 0.9677419066429138, 0.8387096524238586, 0.8064516186714172], [0.7096773982048035, 0.774193525314331, 0.9032257795333862, 0.9677419066429138, 1.0], [0.6774193644523621, 0.7096773982048035, 0.774193525314331, 0.8387096524238586, 0.9677419066429138], [0.9516128897666931, 0.7096773982048035, 0.7419354915618896, 0.8064516186714172, 0.8709677457809448], [0.4354838728904724, 0.5806451439857483, 0.6774193644523621, 0.7096773982048035, 0.7419354915618896], [0.32258063554763794, 0.29032257199287415, 0.6129032373428345, 0.4354838728904724, 0.5806451439857483], [0.19354838132858276, 0.09677419066429138, 0.32258063554763794, 0.29032257199287415, 0.5483871102333069], [0.22580644488334656, 0.35483869910240173, 0.19354838132858276, 0.09677419066429138, 0.29032257199287415], [0.32258063554763794, 0.29032257199287415, 0.4193548262119293, 0.16129031777381897, 0.25806450843811035], [0.16129031777381897, 0.12903225421905518, 0.25806450843811035, 0.22580644488334656, 0.35483869910240173], [0.19354838132858276, 0.16129031777381897, 0.12903225421905518, 0.25806450843811035, 0.22580644488334656], [0.29032257199287415, 0.19354838132858276, 0.16129031777381897, 0.12903225421905518, 0.22580644488334656], [0.06451612710952759, 0.032258063554763794, 0.09677419066429138, 0.19354838132858276, 0.12903225421905518], [0.12903225421905518, 0.06451612710952759, 0.032258063554763794, 0.09677419066429138, 0.16129031777381897], [0.16129031777381897, 0.12903225421905518, 0.06451612710952759, 0.032258063554763794, 0.09677419066429138], [0.12903225421905518, 0.16129031777381897, 0.09677419066429138, 0.06451612710952759, 0.032258063554763794], [0.19354838132858276, 0.12903225421905518, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759], [0.16129031777381897, 0.09677419066429138, 0.12903225421905518, 0.06451612710952759, 0.032258063554763794], [0.12903225421905518, 0.16129031777381897, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759], [0.16129031777381897, 0.12903225421905518, 0.06451612710952759, 0.09677419066429138, 0.032258063554763794], [0.22580644488334656, 0.12903225421905518, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759], [1.0, 0.8387096524238586, 0.9516128897666931, 0.8709677457809448, 0.9516128897666931], [0.8870967626571655, 0.6451612710952759, 0.7096773982048035, 0.5483871102333069, 0.6129032373428345], [0.8387096524238586, 1.0, 0.8870967626571655, 0.6451612710952759, 0.7096773982048035], [0.032258063554763794, 0.25806450843811035, 0.5483871102333069, 0.5806451439857483, 0.5161290168762207], [0.5322580933570862, 0.774193525314331, 0.25806450843811035, 0.06451612710952759, 0.032258063554763794], [0.12903225421905518, 0.06451612710952759, 0.09677419066429138, 0.29032257199287415, 0.32258063554763794], [0.19354838132858276, 0.16129031777381897, 0.29032257199287415, 0.04838709533214569, 0.04838709533214569], [0.3870967626571655, 0.29032257199287415, 0.09677419066429138, 0.16129031777381897, 0.12903225421905518], [0.4354838728904724, 0.25806450843811035, 0.22580644488334656, 0.4838709533214569, 0.3870967626571655], [0.5161290168762207, 0.4354838728904724, 0.29032257199287415, 0.25806450843811035, 0.4838709533214569], [0.9677419066429138, 0.9354838728904724, 0.8387096524238586, 0.5806451439857483, 0.6451612710952759], [0.774193525314331, 0.8709677457809448, 0.9032257795333862, 1.0, 0.9677419066429138], [0.5161290168762207, 0.4516128897666931, 0.5483871102333069, 0.32258063554763794, 0.25806450843811035], [0.12903225421905518, 0.16129031777381897, 0.09677419066429138, 0.032258063554763794, 0.06451612710952759], [0.19354838132858276, 0.22580644488334656, 0.16129031777381897, 0.032258063554763794, 0.06451612710952759], [0.19354838132858276, 0.032258063554763794, 0.06451612710952759, 0.09677419066429138, 0.12903225421905518], [0.19354838132858276, 0.16129031777381897, 0.032258063554763794, 0.06451612710952759, 0.09677419066429138], [0.22580644488334656, 0.16129031777381897, 0.12903225421905518, 0.032258063554763794, 0.06451612710952759], [0.5161290168762207, 0.32258063554763794, 0.4193548262119293, 0.25806450843811035, 0.3870967626571655], [0.9677419066429138, 0.8709677457809448, 0.6451612710952759, 0.4838709533214569, 0.5161290168762207], [0.6774193644523621, 0.774193525314331, 0.8387096524238586, 0.8064516186714172, 0.8709677457809448], [0.4516128897666931, 0.5161290168762207, 0.5483871102333069, 0.6774193644523621, 0.774193525314331], [0.032258063554763794, 0.12903225421905518, 0.09677419066429138, 0.19354838132858276, 0.16129031777381897], [0.06451612710952759, 0.032258063554763794, 0.12903225421905518, 0.09677419066429138, 0.16129031777381897], [0.25806450843811035, 0.16129031777381897, 0.06451612710952759, 0.032258063554763794, 0.09677419066429138], [0.9032257795333862, 0.5161290168762207, 0.6774193644523621, 0.8225806355476379, 0.9677419066429138], [0.9677419066429138, 0.9354838728904724, 0.5483871102333069, 0.7096773982048035, 0.8548387289047241]]
).astype(np.float32)

query = np.array([0.9677419, 0.9032258, 0.5483871, 0.58064514, 0.6451613]).astype(np.float32)

maxDistance = 0.07331936806440353

sa = subsequence_search(query, series, dists_options = {'use_c': True, 'max_dist': maxDistance})

best = sa.kbest_matches_fast(k = None) # change to: len(series)-1

results = list(filter(lambda r: r.idx != -1 and r.distance <= maxDistance, best))

assert len(results) == 1

When running this on commit 26c3962 with k = None:

711 µs ± 4.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

When running this on commit 26c3962 with k = len(series)-1 (note that there seems to be a bug where setting k = len(series) results in an OutOfBoundError:

1.61 ms ± 4.85 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

When running this on master with k = len(series)-1 (I cannot test None here due to issue #184)

8.79 ms ± 1.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

This is 5.5x slower than on 26c3962.

There seem to be 3 issues here:

  1. k = None is much faster than k = len(series)-1, which seems counterintuitive
  2. master is much slower than a few commits ago at 26c3962
  3. setting k = len(series) results in an OutOfBoundError (k = len(series)-1 works)

I wonder if some of the attempts to lower RAM usage at #183 have caused these issues. Of course, speed is more important than RAM usage for most use cases. Especially if I can use float32.

For now I am going to revert to 26c3962 to avoid issue #185 and #184

wannesm commented 1 year ago
  1. k = None is indeed faster than k = len(series)-1, but this is intended as the assumption is that k is small. When using k, one needs to keep track of the k best instances, which incurs some overhead. This is more expensive in this case. When using larger series, the cost of DTW should start dominating and saving on DTW computations should make k!=None faster again. For small values for k, it should also be faster. Thus, in case you know you will need large values of k and the series are short, it's probably better to set k to None and filter afterwards.
  2. The difference should be less than 5.5 by now (there was an unintended sort called multiple times in the bug mentioned in #184). For me it is now a difference of about 2x.
  3. This error is also not showing for me anymore.
tommedema commented 1 year ago

Great, thanks @wannesm

Any idea on what caused the performance hit since 26c3962? If it is still 2x faster than on master I may stay on that commit for a while. :)

wannesm commented 1 year ago

When adding more unit tests for subsequence search I found another silly bug which caused all values to be saved twice. The difference between None and len(series)-1 is now almost zero.

The original regression since 26c3962 was mainly because the final sort operation was erroneously executed after each distance calculation. I was trying to be too fast, sorry for confusion.

tommedema commented 1 year ago

Nice one! 🙌

On Tue, Nov 1, 2022 at 02:50 wannesm @.***> wrote:

When adding more unit tests for subsequence search I found another silly bug which caused all values to be saved twice. The difference between None and len(series)-1 is now almost zero.

— Reply to this email directly, view it on GitHub https://github.com/wannesm/dtaidistance/issues/185#issuecomment-1298284316, or unsubscribe https://github.com/notifications/unsubscribe-auth/AACRAOPNX4RMNLMW4EEMVX3WGDRVBANCNFSM6AAAAAARMAKZIA . You are receiving this because you modified the open/close state.Message ID: @.***>