A Python implementation of FastDTW

This also incorporated a way of calculating the dtw function, The new calculation resulted in 2x runtime performance with cython providing another 2x performance for a total of 4x. The test data was

import fastdtw
import numpy as np

thetas = np.linspace(0, 2 * np.pi, 1000)
x = np.sin(thetas)
y = np.sin(thetas * 2)
print(fastdtw.fastdtw_py(x, y, radius=1)[0])
print(fastdtw.fastdtw_py2(x, y, radius=1)[0])
print(fastdtw.fastdtw(x, y, radius=1)[0])

with the following conventions: fastdtw_py - code in fastdtw/fastdtw_py.py fastdtw_py2 - pure python method but with new dtw function (this code is not committed but could be regenerated by moving fastdtw.pyx to a pure python module) fastdtw - cythonized code

The new calculation method is faster because it

* removes an unnecessary generator that adds +1 to the window in the
  dtw method.
* minimizes accessing the defaultdict.
* caches the list in expand window rather than recreating it every
  loop

Pull request #4 ended with the decision to go with an alternative indexing method that was faster. This pull request contains the indexing method. See pull request #4 for a speed comparison of the 2 methods.

I had to do the following modifications:

1. Install the msvc for python https://www.microsoft.com/en-us/download/details.aspx?id=44266
2. Adjust the setup.py a) to not use stdlibc++, b) to use cythonize (from Cython.Build import cythonize and in kwargs change ext_module to 'ext_modules': cythonize(extensions), c) import numpy and add include_dirs=[numpy.get_include()], in extensions:

from setuptools import setup, find_packages, Extension
from Cython.Build import cythonize
import os.path
import warnings
import numpy

classifiers = [
    'Programming Language :: Python :: 2',
    'Programming Language :: Python :: 3',
    'Intended Audience :: Science/Research',
    'License :: OSI Approved :: MIT License',
    'Topic :: Scientific/Engineering'
]

extensions = [Extension(
        'fastdtw._fastdtw',
        [os.path.join('fastdtw', "_fastdtw.pyx")],
        language="c++",
        include_dirs=[numpy.get_include()],
#       if you want to debug from MSVC IDE uncomment the following
#        extra_compile_args=["-Zi", "/Od"],
#        extra_link_args=["-debug"],

#        libraries=["stdc++","stdc"]
    )]

kwargs = {
    'name': 'fastdtw',
    'version': '0.3.0',
    'author': 'Kazuaki Tanida',
    'url': 'https://github.com/slaypni/fastdtw',
    'description': 'Dynamic Time Warping (DTW) algorithm with an O(N) time and memory complexity.',
    'license': 'MIT',
    'keywords': ['dtw'],
    'install_requires': ['numpy'],
    'packages': find_packages(),
    'ext_modules':  cythonize(extensions),
    'test_suite': 'tests',
    'setup_requires': ['pytest-runner'],
    'tests_require': ['pytest'],
    'classifiers': classifiers
}

try:
    setup(**kwargs)
except SystemExit:
    del kwargs['ext_modules']
    warnings.warn('compilation failed. Installing pure python package')
    setup(**kwargs)

3. Modify the cpx to use the INFINITY definition from numpy:

#from libc.math cimport INFINITY,pow, fabs
from libc.math cimport pow, fabs
from numpy.math cimport INFINITY

Thank you for your great work!

Jan

This is a great library. Thank you for open sourcing it. It would be nice if it ran a bit faster perhaps with cython extensions. Is there any interest in that?

Don't require pytest-runner outside of tests because setup_requires behaves poorly in certain situations. For example, see https://github.com/pytest-dev/pytest-runner#conditional-requirement and https://github.com/pypa/pip/issues/410.

I have two code. one is use default dist, another is use Euclidean func.. I test two code in my MacBook. and it work! but in AWS lambda it doesn't work.. but I don't know why.. because Euclidean func is work but default doesn't work.. this is AWS lambda error..

>>> from fastdtw import fastdtw
>>> import numpy as np
>>> np.zeros((3,5))
array([[ 0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.]])
>>> a = np.zeros((3,5))
>>> b = np.zeros((3,5))
>>> fastdtw(a,b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "fastdtw.py", line 65, in fastdtw
    return __fastdtw(x, y, radius, dist)
  File "fastdtw.py", line 85, in __fastdtw
    __fastdtw(x_shrinked, y_shrinked, radius=radius, dist=dist)
  File "fastdtw.py", line 80, in __fastdtw
    return dtw(x, y, dist=dist)
  File "fastdtw.py", line 128, in dtw
    (D[i-1, j-1][0]+dt, i-1, j-1), key=lambda a: a[0])
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

but same code In my Mackbook.. it work!

>>> import numpy as np
>>> from fastdtw import fastdtw
>>> a = np.zeros((4,5))
>>> b = np.zeros((4,5))
>>> fastdtw(a,b)
Out[6]: (0.0, [(0, 0), (1, 1), (2, 2), (3, 3)])
>>> dist,path = fastdtw(a,b)
>>> dist
Out[8]: 0.0
>>> path
Out[9]: [(0, 0), (1, 1), (2, 2), (3, 3)]

I'm struggling understanding a very simple example. I boiled it down to the following test:

from fastdtw import fastdtw
from scipy.spatial.distance import euclidean, sqeuclidean
def test_euclidean_distance():
    q=[0,1,2,3,4,5,6,7,8]
    r=[1,2,3,4,5,6,7,8,0]
    distA, pathA = fastdtw(q, r, radius=2, dist=euclidean)
    distB, pathB = fastdtw(q, r, radius=2, dist=sqeuclidean)
    assert all([a==b for a,b in zip(pathA, pathB)])
    assert distA*distA == distB   # 9*9 == 65 fails

Since the paths are the same I would expect to that also the distances are the same. The correct Euclidean distance should be sqrt(65) (only first and last elements of the input vectors contribute). Since it is 9 it looks like the Manhattan distance is used instead of the Euclidean distance.

I have the feeling that I miss something simple. But could someone give me a hint?

Hi,

with the following code there is possible to synchronize two time series (x and y).

import numpy as np from scipy.spatial.distance import euclidean

from fastdtw import fastdtw

x = np.array([[1,1], [2,2], [3,3], [4,4], [5,5]])
y = np.array([[2,2], [3,3], [4,4]])
distance, path = fastdtw(x, y, dist=euclidean)

Is there any way how to synchronize more than two time series?

I tried to: distance, path = fastdtw(x, y, z, dist=euclidean) but only size-1 arrays can be converted to Python scalars.

Python version: 3.7.1

It's quite an old issue, but I haven't seen it reported here yet (and it clutters up the output of scripts quite a bit).

When using the latest version (0.3.2) of fastdtw and version of numpy>=1.14, a FutureWarning is raised:

Minimum working example:

In [1]: from fastdtw import fastdtw
In [2]: x = [1, 2, 3, 4, 5]
In [3]: y = [1, 2, 3, 4, 5]
In [10]: fastdtw(x, y)
/home/michael/miniconda3/envs/ds/bin/ipython:1: FutureWarning: Conversion of the second argument of issubdtype from `float` to `np.floating` is deprecated. In future, it will be treated as `np.float64 == np.dtype(float).type`.
  #!/home/michael/miniconda3/envs/ds/bin/python
Out[10]: (0.0, [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)])

There are similarly related issues (that have since been resolved on the h5py project. https://github.com/h5py/h5py/issues/961

Thanks!

timeseries1.xlsx timeseries2.xlsx

i tried fastdtw and dtw on the two timeseries that I have uploaded.Both are giving different answers. Should it give the same answer or am I missing out something?

I want to compare sequences of string with fastdtw, typically the lines of a text file, as done by diff.

Is it possible? How would you do this?

Thanks.

Hi!

Thank you for developing and sharing this library. I have been using it quite successfully.

In function __expand_window(), is there a reason for thickening the path with radius before doubling the search window axes rather than the other way around? This way the search window becomes 4 * radius instead of 2 * radius.

Thanks in advance, Vasco.

Bumps certifi from 2019.3.9 to 2022.12.7.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Bumps ipython from 7.4.0 to 7.16.3.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Hi, I see that the main library is implemented in C. Can you please point out steps to load and call the fastdtw function from C language instead of python?

Hi,

When I used pip install fastdtw, I got this error:

Collecting fastdtw Using cached fastdtw-0.3.4.tar.gz (133 kB) Requirement already satisfied: numpy in c:\users\alma\appdata\local\programs\python\python38\lib\site-packages (from fastdtw) (1.21.1) Building wheels for collected packages: fastdtw Building wheel for fastdtw (setup.py) ... error ERROR: Command errored out with exit status 1: command: 'c:\users\alma\appdata\local\programs\python\python38\python.exe' -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py'"'"'; file='"'"'C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(file) if os.path.exists(file) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, file, '"'"'exec'"'"'))' bdist_wheel -d 'C:\Users\Alma\AppData\Local\Temp\pip-wheel-eqz2yrmr' cwd: C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2
Complete output (46 lines): running bdist_wheel running build running build_py creating build creating build\lib.win-amd64-3.8 creating build\lib.win-amd64-3.8\fastdtw copying fastdtw\fastdtw.py -> build\lib.win-amd64-3.8\fastdtw copying fastdtw_init_.py -> build\lib.win-amd64-3.8\fastdtw running build_ext Traceback (most recent call last): File "", line 1, in File "C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py", line 81, in setup(**kwargs) File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\setuptools_init_.py", line 153, in setup return distutils.core.setup(**attrs) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\core.py", line 148, in setup dist.run_commands() File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 966, in run_commands self.run_command(cmd) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 985, in run_command cmd_obj.run() File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\wheel\bdist_wheel.py", line 299, in run self.run_command('build') File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cmd.py", line 313, in run_command self.distribution.run_command(command) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 985, in run_command cmd_obj.run() File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\command\build.py", line 135, in run self.run_command(cmd_name) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cmd.py", line 313, in run_command self.distribution.run_command(command) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 985, in run_command cmd_obj.run() File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\setuptools\command\build_ext.py", line 79, in run _build_ext.run(self) File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\Cython\Distutils\old_build_ext.py", line 186, in run _build_ext.build_ext.run(self) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\command\build_ext.py", line 306, in run self.compiler = new_compiler(compiler=self.compiler, File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\ccompiler.py", line 1032, in new_compiler return klass(None, dry_run, force) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cygwinccompiler.py", line 282, in init CygwinCCompiler.init (self, verbose, dry_run, force) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cygwinccompiler.py", line 126, in init if self.ld_version >= "2.10.90": TypeError: '>=' not supported between instances of 'NoneType' and 'str'

ERROR: Failed building wheel for fastdtw Running setup.py clean for fastdtw Failed to build fastdtw Installing collected packages: fastdtw Running setup.py install for fastdtw ... error ERROR: Command errored out with exit status 1: command: 'c:\users\alma\appdata\local\programs\python\python38\python.exe' -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py'"'"'; file='"'"'C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(file) if os.path.exists(file) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, file, '"'"'exec'"'"'))' install --record 'C:\Users\Alma\AppData\Local\Temp\pip-record-zr003v8k\install-record.txt' --single-version-externally-managed --compile --install-headers c:\users\alma\appdata\local\programs\python\python38\Include\fastdtw' cwd: C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2
Complete output (48 lines): running install running build running build_py creating build creating build\lib.win-amd64-3.8 creating build\lib.win-amd64-3.8\fastdtw copying fastdtw\fastdtw.py -> build\lib.win-amd64-3.8\fastdtw copying fastdtw_init_.py -> build\lib.win-amd64-3.8\fastdtw running build_ext Traceback (most recent call last): File "", line 1, in File "C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py", line 81, in setup(**kwargs) File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\setuptools_init_.py", line 153, in setup return distutils.core.setup(**attrs) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\core.py", line 148, in setup dist.run_commands() File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 966, in run_commands self.run_command(cmd) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 985, in run_command cmd_obj.run() File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\setuptools\command\install.py", line 61, in run return orig.install.run(self) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\command\install.py", line 545, in run self.run_command('build') File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cmd.py", line 313, in run_command self.distribution.run_command(command) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 985, in run_command cmd_obj.run() File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\command\build.py", line 135, in run self.run_command(cmd_name) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cmd.py", line 313, in run_command self.distribution.run_command(command) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\dist.py", line 985, in run_command cmd_obj.run() File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\setuptools\command\build_ext.py", line 79, in run _build_ext.run(self) File "c:\users\alma\appdata\local\programs\python\python38\lib\site-packages\Cython\Distutils\old_build_ext.py", line 186, in run _build_ext.build_ext.run(self) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\command\build_ext.py", line 306, in run self.compiler = new_compiler(compiler=self.compiler, File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\ccompiler.py", line 1032, in new_compiler return klass(None, dry_run, force) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cygwinccompiler.py", line 282, in init CygwinCCompiler.init (self, verbose, dry_run, force) File "c:\users\alma\appdata\local\programs\python\python38\lib\distutils\cygwinccompiler.py", line 126, in init if self.ld_version >= "2.10.90": TypeError: '>=' not supported between instances of 'NoneType' and 'str'

ERROR: Command errored out with exit status 1: 'c:\users\alma\appdata\local\programs\python\python38\python.exe' -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py'"'"'; file='"'"'C:\Users\Alma\AppData\Local\Temp\pip-install-ntat_l8u\fastdtw_79f25377447c4796a756f2578fb594e2\setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(file) if os.path.exists(file) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, file, '"'"'exec'"'"'))' install --record 'C:\Users\Alma\AppData\Local\Temp\pip-record -zr003v8k\install-record.txt' --single-version-externally-managed --compile --install-headers 'c:\users\alma\appdata\local\programs\python\python38\In clude\fastdtw' Check the logs for full command output.

What should I do? Thanks in advance.

Bumps urllib3 from 1.24.1 to 1.26.5.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.