{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Short study of the Lempel-Ziv complexity\n", "\n", "In this short [Jupyter notebook](https://www.Jupyter.org/) aims at defining and explaining the [Lempel-Ziv complexity](https://en.wikipedia.org/wiki/Lempel-Ziv_complexity).\n", "\n", "[I](http://perso.crans.org/besson/) will give examples, and benchmarks of different implementations.\n", "\n", "- **Reference:** Abraham Lempel and Jacob Ziv, *« On the Complexity of Finite Sequences »*, IEEE Trans. on Information Theory, January 1976, p. 75–81, vol. 22, n°1." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Short definition\n", "The Lempel-Ziv complexity is defined as the number of different substrings encountered as the stream is viewed from begining to the end.\n", "\n", "As an example:\n", "\n", "```python\n", ">>> s = '1001111011000010'\n", ">>> lempel_ziv_complexity(s) # 1 / 0 / 01 / 1110 / 1100 / 0010\n", "6\n", "```\n", "\n", "Marking in the different substrings, this sequence $s$ has complexity $\\mathrm{Lempel}$-$\\mathrm{Ziv}(s) = 6$ because $s = 1001111011000010 = 1 / 0 / 01 / 1110 / 1100 / 0010$.\n", "\n", "- See the page https://en.wikipedia.org/wiki/Lempel-Ziv_complexity for more details." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Other examples:\n", "\n", "```python\n", ">>> lempel_ziv_complexity('1010101010101010') # 1 / 0 / 10\n", "3\n", ">>> lempel_ziv_complexity('1001111011000010000010') # 1 / 0 / 01 / 1110 / 1100 / 0010 / 000 / 010\n", "7\n", ">>> lempel_ziv_complexity('100111101100001000001010') # 1 / 0 / 01 / 1110 / 1100 / 0010 / 000 / 010 / 10\n", "8\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Python implementation" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def lempel_ziv_complexity(binary_sequence):\n", " \"\"\"Lempel-Ziv complexity for a binary sequence, in simple Python code.\"\"\"\n", " u, v, w = 0, 1, 1\n", " v_max = 1\n", " length = len(binary_sequence)\n", " complexity = 1\n", " while True:\n", " if binary_sequence[u + v - 1] == binary_sequence[w + v - 1]:\n", " v += 1\n", " if w + v >= length:\n", " complexity += 1\n", " break\n", " else:\n", " if v > v_max:\n", " v_max = v\n", " u += 1\n", " if u == w:\n", " complexity += 1\n", " w += v_max\n", " if w > length:\n", " break\n", " else:\n", " u = 0\n", " v = 1\n", " v_max = 1\n", " else:\n", " v = 1\n", " return complexity" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Tests (1/2)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = '1001111011000010'\n", "lempel_ziv_complexity(s) # 1 / 0 / 01 / 1110 / 1100 / 0010" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7.03 µs ± 457 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity(s)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity('1010101010101010') # 1 / 0 / 10" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity('1001111011000010000010') # 1 / 0 / 01 / 1110" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity('100111101100001000001010') # 1 / 0 / 01 / 1110 / 1100 / 0010 / 000 / 010 / 10" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "19.4 µs ± 2.31 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity('100111101100001000001010')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can start to see that the time complexity of this function seems to grow exponentially as the complexity grows." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Cython implementation\n", "As [this blog post](https://jakevdp.github.io/blog/2013/06/15/numba-vs-cython-take-2/) explains it, we can easily try to use [Cython](http://Cython.org/) in a notebook cell." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%load_ext cython" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "%%cython\n", "from __future__ import division\n", "import cython\n", "\n", "ctypedef unsigned int DTYPE_t\n", "\n", "@cython.boundscheck(False) # turn off bounds-checking for entire function, quicker but less safe\n", "def lempel_ziv_complexity_cython(str binary_sequence):\n", " \"\"\"Lempel-Ziv complexity for a binary sequence, in simple Cython code (C extension).\"\"\"\n", " cdef DTYPE_t u = 0\n", " cdef DTYPE_t v = 1\n", " cdef DTYPE_t w = 1\n", " cdef DTYPE_t v_max = 1\n", " cdef DTYPE_t length = len(binary_sequence)\n", " cdef DTYPE_t complexity = 1\n", " # that was the only needed part, typing statically all the variables\n", " while True:\n", " if binary_sequence[u + v - 1] == binary_sequence[w + v - 1]:\n", " v += 1\n", " if w + v >= length:\n", " complexity += 1\n", " break\n", " else:\n", " if v > v_max:\n", " v_max = v\n", " u += 1\n", " if u == w:\n", " complexity += 1\n", " w += v_max\n", " if w > length:\n", " break\n", " else:\n", " u = 0\n", " v = 1\n", " v_max = 1\n", " else:\n", " v = 1\n", " return complexity" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let try it!" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = '1001111011000010'\n", "lempel_ziv_complexity_cython(s) # 1 / 0 / 01 / 1110 / 1100 / 0010" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "130 ns ± 8.72 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity_cython(s)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity_cython('1010101010101010') # 1 / 0 / 10" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity_cython('1001111011000010000010') # 1 / 0 / 01 / 1110" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity_cython('100111101100001000001010') # 1 / 0 / 01 / 1110 / 1100 / 0010 / 000 / 010 / 10" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "259 ns ± 13.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity_cython('100111101100001000001010')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> $\\implies$ Yay! It seems faster indeed!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Numba implementation\n", "As [this blog post](https://jakevdp.github.io/blog/2013/06/15/numba-vs-cython-take-2/) explains it, we can also try to use [Numba](http://Numba.PyData.org/) in a notebook cell." ] }, { "cell_type": "code", "execution_count": 87, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from numba import jit" ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [], "source": [ "@jit(\"int32(boolean[:])\")\n", "def lempel_ziv_complexity_numba_x(binary_sequence):\n", " \"\"\"Lempel-Ziv complexity for a binary sequence, in Python code using numba.jit() for automatic speedup (hopefully).\"\"\"\n", " u, v, w = 0, 1, 1\n", " v_max = 1\n", " length = len(binary_sequence)\n", " complexity = 1\n", " while True:\n", " if binary_sequence[u + v - 1] == binary_sequence[w + v - 1]:\n", " v += 1\n", " if w + v >= length:\n", " complexity += 1\n", " break\n", " else:\n", " if v > v_max:\n", " v_max = v\n", " u += 1\n", " if u == w:\n", " complexity += 1\n", " w += v_max\n", " if w > length:\n", " break\n", " else:\n", " u = 0\n", " v = 1\n", " v_max = 1\n", " else:\n", " v = 1\n", " return complexity\n", "\n", "def str_to_numpy(s):\n", " \"\"\"str to np.array of bool\"\"\"\n", " return np.array([int(i) for i in s], dtype=np.bool)\n", "\n", "def lempel_ziv_complexity_numba(s):\n", " return lempel_ziv_complexity_numba_x(str_to_numpy(s))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let try it!" ] }, { "cell_type": "code", "execution_count": 95, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([ True, False, False, True, True, True, True, False, True,\n", " True, False, False, False, False, True, False], dtype=bool)" ] }, "execution_count": 95, "metadata": {}, "output_type": "execute_result" } ], "source": [ "str_to_numpy(s)" ] }, { "cell_type": "code", "execution_count": 96, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 96, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = '1001111011000010'\n", "lempel_ziv_complexity_numba(s) # 1 / 0 / 01 / 1110 / 1100 / 0010" ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "6.16 µs ± 228 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity_numba(s)" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity_numba('1010101010101010') # 1 / 0 / 10" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7" ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity_numba('1001111011000010000010') # 1 / 0 / 01 / 1110" ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 100, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lempel_ziv_complexity_numba('100111101100001000001010') # 1 / 0 / 01 / 1110 / 1100 / 0010 / 000 / 010 / 10" ] }, { "cell_type": "code", "execution_count": 101, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "9.35 µs ± 1.22 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity_numba('100111101100001000001010')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> $\\implies$ Well... It doesn't seem that much faster from the naive Python code.\n", "> We specified the signature when calling [`@numba.jit`](http://numba.pydata.org/numba-doc/latest/user/jit.html), and used the more appropriate data structure (string is probably the smaller, numpy array are probably faster).\n", "> But even these tricks didn't help that much.\n", "\n", "> I tested, and without specifying the signature, the fastest approach is using string, compared to using lists or numpy arrays.\n", "> Note that the [`@jit`](http://numba.pydata.org/numba-doc/latest/user/jit.html)-powered function is compiled at runtime when first being called, so the signature used for the *first* call is determining the signature used by the compile function" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Tests (2/2)\n", "\n", "To test more robustly, let us generate some (uniformly) random binary sequences." ] }, { "cell_type": "code", "execution_count": 57, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from numpy.random import binomial\n", "\n", "def bernoulli(p, size=1):\n", " \"\"\"One or more samples from a Bernoulli of probability p.\"\"\"\n", " return binomial(1, p, size)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1])" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bernoulli(0.5, 20)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That's probably not optimal, but we can generate a string with:" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'10011100011111111011'" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join(str(i) for i in bernoulli(0.5, 20))" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def random_binary_sequence(n, p=0.5):\n", " \"\"\"Uniform random binary sequence of size n, with rate of 0/1 being p.\"\"\"\n", " return ''.join(str(i) for i in bernoulli(p, n))" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'11100011000111010111000110001110001110010010010010'" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "'00000100100000100000000000000000000100000000000000'" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "'00000010000010011100111010010000000000000010100010'" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "'11000111100001111001100000101011011011011010110110'" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "'11111001110101111111111101111111010111111111110111'" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "'11111111111111101111101111110111111001111110111111'" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_binary_sequence(50)\n", "random_binary_sequence(50, p=0.1)\n", "random_binary_sequence(50, p=0.25)\n", "random_binary_sequence(50, p=0.5)\n", "random_binary_sequence(50, p=0.75)\n", "random_binary_sequence(50, p=0.9)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And so, this function can test to check that the three implementations (naive, Cython-powered, Numba-powered) always give the same result." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def tests_3_functions(n, p=0.5, debug=True):\n", " s = random_binary_sequence(n, p=p)\n", " c1 = lempel_ziv_complexity(s)\n", " if debug:\n", " print(\"Sequence s = {} ==> complexity C = {}\".format(s, c1))\n", " c2 = lempel_ziv_complexity_cython(s)\n", " c3 = lempel_ziv_complexity_numba(s)\n", " assert c1 == c2 == c3, \"Error: the sequence {} gave different values of the Lempel-Ziv complexity from 3 functions ({}, {}, {})...\".format(s, c1, c2, c3)\n", " return c1" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sequence s = 11010 ==> complexity C = 3\n" ] }, { "data": { "text/plain": [ "3" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tests_3_functions(5)" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sequence s = 00011000000010010111 ==> complexity C = 6\n" ] }, { "data": { "text/plain": [ "6" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tests_3_functions(20)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sequence s = 00111111110000010000100011000010001100110001001101 ==> complexity C = 8\n" ] }, { "data": { "text/plain": [ "8" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tests_3_functions(50)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sequence s = 01011110110110010010101101110000101110100011011101100101001000001100111000011000101000000010010010010100101101101010111010001100011000100111111101101111000010001111001110010000001100011011111001001011101110001000111101100110100111011010101000010100011000010001101101000101111101001011111001100111001010100010010001111000101100110000100000010100111111000110110011110101000100110101000011001010111010101111101100111010101011110001100001111111000100100000001000100100101011010111011001101110110111111110 ==> complexity C = 60\n" ] }, { "data": { "text/plain": [ "60" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tests_3_functions(500)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sequence s = 00001100000110000110100011111111010111110000010110100111111000000111011011000001011101101101011100101110010001010000011011110100001011001011000101100001000000110100110011111100010111000101000011100010010100011110011110011101011101110011110001110110100100111110010010110010100100100101001010110100111111000010011110101011110001010010000110101000000111001010101000101001101000111100001100101111010010001011111111110001111001100011010011101011001111110110011101100011001000001000110101001010000000101011111101010110111110000000001000111000000011110101001110101011111100000101011111000100000000110110011011011111001111101000110001011111011010011100100110010001011011001001100111000001100111101011000010100010111100010000111001111001100001010001010010100110101111001010011010110001100001100011110011101101000110000010010010111110101011000000101110110011100110110011111111010011001101011101010001110001000001000000001111010000000010000101011001111001101110100110000100110000010010011110111001001111110100101000010101001101011111111010010110011000011001101001110010100010111100001011001000011000001000011111001000011110001010111111111100000000110101110110001100010111100101100010001001101010101000110010100101010100001111010001001001111010100010101101101110010110011001010110101111010011000100011110001110011000001000010010000000000001000001011010100010111001001000101000001101100100011100011110011010010010110011000101110011110000010000100110100100000011011100110111101110110101110010111000011110100110001011010111000111001110101110001100000111011100011100000010000101010110010011000000001111100101010101110100111111101011001100101111000011101111010101001000111001110100100011110000110001110100010101001100101010000101101000010110010000011100000111001111101110100010011010111101000010100011011100111001110000001000011110111001110100110010110000010011111101000011101010000001011101011111100110111010111000101110010011110110110000000110110000110010000011110000111000101001001101011101101101010011010100101000011101010110011100000110100010001101110101001011111110100101010011111110100111000110010111010100000100101001010100000000000000101001111111001010010111011000000001100111111011011100100011011100010101000111000000100101100000110111100101100100110010001000000111000010011100001010111010001011111111011101010101101101000100010110101110001110100101001111101111101100110100101100110111001011011110011110100010100010110101110110000111000100000010101011100101010101100001011100101000100110100110010100101100010010010100010100110001010101001011001100001001111110000101000000111110001101010110001000000111111111101100001101011011000110000010111111101111010001100111011100111001100010110111010110011011100111101110010100011011011000001011111111001000001010001010001100011010101011100010000101111111101000100110110110001110111100011011101010100101010100111011111111001001000000001010001100100111111000111010110111100101001101100001100101101000001111010110000010101000010101000110110001100101010110111110111110110110101101000010101000001111101100001100010111111111001101111000111110100111001010111111110000111111100100110010000101011111010100001001101010101010111111110100010010010101000100011100101011101100001010011100011101111111100000100100111101011011000110010011111110000011010011000111110110110110000111010101101100101101100010100101011010001110111011111100010011011100110000000011111011010001101110110000110001101011111110011011110001111100111011001100011111010010000111000000110001101010101011010000110110011111010101111101001100000000110001111010110110001111111010100001100101000011011101010111000010110110010100001010011010010101011011100001010101011100111011110001100110101000011001000010100111000100110001000110111100010100110111011111101110011000100000011100010011001010001110010011011111110111100000111001010110000011011010011010011000000111100011101101110110101010010001111100100011100001101011001010101001100101101101011010011001011001100100011010001011000101011000011000101010110000110000011111111101000001100011100111110110001000111000111111011111110101000001100001100010111001101011100001010011000001110100010011001001101101111010100100001010011110100110001000001010010110111110001011101000000110011111001110011011011100111000101010101010011100100001000011001100001101100011100110101010010011110101110000111000001111010100011111100011101000010101111010001101100010111111110110000101010111000000101111001001111110011110001110111101000010010001101000001011100010000011000000011101010100000101001001100101001001001001001111111101100111001110110001000001100001010011001001110111111101111100011100011101001000000100000010111101001101001100010101001110100101000010110101011100011111100001100110111010111111110010001000011000101110111110010100011111111001001011110010101111101110111101000000001111010000010001100011011010001101110010110111011000110110111100111111011001000101101011000101110010011010010111001000101000111010101000000010111111010011001110010110001010001111011110001101001100000110000001 ==> complexity C = 420\n" ] }, { "data": { "text/plain": [ "420" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tests_3_functions(5000)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Benchmarks\n", "\n", "On two example of strings (binary sequences), we can compare our three implementation." ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "16.7 µs ± 471 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n", "249 ns ± 6.71 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n", "7.98 µs ± 236 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity('100111101100001000001010')\n", "%timeit lempel_ziv_complexity_cython('100111101100001000001010')\n", "%timeit lempel_ziv_complexity_numba('100111101100001000001010')" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "139 µs ± 4.33 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "1.94 µs ± 83.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n", "22 µs ± 364 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n" ] } ], "source": [ "%timeit lempel_ziv_complexity('10011110110000100000101000100100101010010111111011001111111110101001010110101010')\n", "%timeit lempel_ziv_complexity_cython('10011110110000100000101000100100101010010111111011001111111110101001010110101010')\n", "%timeit lempel_ziv_complexity_numba('10011110110000100000101000100100101010010111111011001111111110101001010110101010')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let check the time used by all the three functions, for longer and longer sequences:" ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "28.2 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "52.3 µs ± 2.75 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "108 µs ± 1.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "359 µs ± 91.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n", "862 µs ± 64.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n", "3.16 ms ± 299 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n" ] } ], "source": [ "%timeit tests_3_functions(10, debug=False)\n", "%timeit tests_3_functions(20, debug=False)\n", "%timeit tests_3_functions(40, debug=False)\n", "%timeit tests_3_functions(80, debug=False)\n", "%timeit tests_3_functions(160, debug=False)\n", "%timeit tests_3_functions(320, debug=False)" ] }, { "cell_type": "code", "execution_count": 105, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def test_cython(n):\n", " s = random_binary_sequence(n)\n", " c = lempel_ziv_complexity_cython(s)\n", " return c" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "17.1 µs ± 490 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "28.8 µs ± 959 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "62.4 µs ± 6.77 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "125 µs ± 7.15 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n", "216 µs ± 13.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n", "459 µs ± 16.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n" ] } ], "source": [ "%timeit test_cython(10)\n", "%timeit test_cython(20)\n", "%timeit test_cython(40)\n", "%timeit test_cython(80)\n", "%timeit test_cython(160)\n", "%timeit test_cython(320)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1.18 ms ± 214 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n", "2.38 ms ± 144 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n", "5.93 ms ± 71.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n", "17.1 ms ± 168 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n" ] } ], "source": [ "%timeit test_cython(640)\n", "%timeit test_cython(1280)\n", "%timeit test_cython(2560)\n", "%timeit test_cython(5120)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "52.1 ms ± 584 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n", "178 ms ± 6.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" ] } ], "source": [ "%timeit test_cython(10240)\n", "%timeit test_cython(20480)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Complexity ?\n", "$\\implies$ The function `lempel_ziv_complexity_cython` seems to be indeed (almost) linear in $n$, the length of the binary sequence $S$.\n", "\n", "But let check more precisely, as it could also have a complexity of $\\mathcal{O}(n \\log n)$." ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import seaborn as sns\n", "%matplotlib inline\n", "sns.set(context=\"notebook\", style=\"darkgrid\", palette=\"hls\", font=\"sans-serif\", font_scale=1.4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It's durty, but let us capture manually the times given by the experiments above." ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [], "source": [ "x = [10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240, 20480]\n", "y = [18, 30, 55, 107, 205, 471, 977, 2270, 5970, 17300, 56600, 185000]" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "