Giter Club home page Giter Club logo

debruijnindex's Introduction

debruijnindex

TLDR

Generate a deBruijn Sequence that facilitates an efficient decoding algorithm due to J. Tuliani theis, porting the implementation of jgeisler0303

Description

Generate a deBruijn Sequence that facilitates an efficient decoding algorithm due to J. Tuliani.

Ports the implementation of (jgeisler0303)[https://github.com/jgeisler0303/deBruijnDecode] to python.

Alternative

https://github.com/alexbowe/debdec

Timing

4_7
(16384)
real    12m18.553s
user    11m49.953s
sys     00m21.078s

real    00m00.581s
user    00m00.484s
sys     00m00.094s

4_9
real    1m43.954s
user    1m43.766s
sys     0m0.125s

4_11
real    476m56.538s 7.9h
user    476m02.203s
sys       0m04.109s

206 272 
4_13 2.148 h =     89.5 days
4_15           24.353  days =            66 years
4_17                                 18.148 years
4_19                              4.936.266 years
4_21                          1.342.664.496 years

Timing - no matrix

4_03
real    0m00.153s
user    0m00.063s
sys     0m00.109s

4_05
real    0m00.160s
user    0m00.078s
sys     0m00.078s

4_07
real    0m00.261s
user    0m00.188s
sys     0m00.063s

4_09
real    0m02.264s
user    0m02.063s
sys     0m00.172s

4_11
real    0m33.539s
user    0m31.609s
sys     0m01.891s

4_13
real    9m15.806s
user    8m38.453s
sys     0m33.422s

Timing - no matrix - calculation

3     5     7     9     11    13   15      17         19           21
                                                      10yr         2.158yr
                                           30d        3.749d       787.973d
                                   10h     728h       89.995h      18.911.369h
                              9.5m 600m    43.683m    5.399.725m   1.134.682.152m
0.15s 0.16s 0.26s 2.26s 33.5s 555s 36.048s 2.621.014s 323.983.540s 68.080.929.144s
      1.01  1.62  8.69  14.8  16.6 42.77   72.71      123.61       210.1
            1.63  5.33  1.7   1.12

Numbers

3
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45] (2)
 INFO    :    L             : (1)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :    dbsequence    : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0, 3, 3, 3, 0, 0 ... 2, 1, 1, 1, 2, 2, 0, 0, 3, 0, 1, 2, 3, 0, 2, 3, 2, 0, 2, 1] (64)

5
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765] (4)
 INFO    :    L             : (3)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 3, 0, 2, 1, 1, 2, 1, 2, 3, 0, 0, 0, 1, 0, 2, 0, 0, 3, 0, 1] (1024)

7
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285] (6)
 INFO    :    L             : (5)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 1, 3, 0, 1, 0, 0, 1, 0, 0, 2, 3, 0, 1, 2, 0, 2, 2, 2, 2, 1] (16384)

9
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285, 49149, 196605] (8)
 INFO    :    L             : (7)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :      L[ 5]       : [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 3, 3, 1, 2, 0, 1, 0, 1 ... 0, 1, 0, 0, 1, 1, 1, 2, 2, 2, 0, 3, 3, 0, 2, 2, 0, 2, 0, 2] (16383)
 INFO    :      L[ 6]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 3, 0, 2, 3, 0, 2, 0, 2, 1, 0, 3, 0, 0, 0, 1, 0, 3, 0, 3, 0] (65535)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 0, 1, 3, 0, 1, 3, 1, 3, 2, 1, 0, 1, 1, 1, 2, 1, 0, 1, 0, 1] (262144)

11
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285, 49149, 196605, 786429, 3145725] (10)
 INFO    :    L             : (9)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :      L[ 5]       : [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 3, 3, 1, 2, 0, 1, 0, 1 ... 0, 1, 0, 0, 1, 1, 1, 2, 2, 2, 0, 3, 3, 0, 2, 2, 0, 2, 0, 2] (16383)
 INFO    :      L[ 6]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 3, 0, 2, 3, 0, 2, 0, 2, 1, 0, 3, 0, 0, 0, 1, 0, 3, 0, 3, 0] (65535)
 INFO    :      L[ 7]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 2, 1, 0, 0 ... 0, 0, 1, 0, 0, 1, 0, 1, 0, 2, 3, 3, 0, 1, 2, 0, 1, 1, 2, 2] (262143)
 INFO    :      L[ 8]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 3, 0, 1, 3, 0, 0 ... 3, 0, 1, 3, 0, 1, 3, 0, 2, 3, 2, 2, 2, 3, 1, 0, 1, 3, 1, 0] (1048575)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 3, 0, 1, 3, 0, 0 ... 0, 1, 2, 0, 1, 2, 0, 1, 3, 0, 3, 3, 3, 0, 2, 1, 2, 0, 2, 1] (4194304)

13
 INFO    :    T             : [0, 2, 4, 15, 1, 7, 9, 6, 3, 8, 12, 11, 5, 10, 13, 14] (16)
 INFO    :    K             : [7, 45, 189, 765, 3069, 12285, 49149, 196605, 786429, 3145725, 12582909, 50331645] (12)
 INFO    :    L             : (11)
 INFO    :      L[ 0]       : [0, 0, 0, 1, 1, 3, 3, 2, 3, 1, 2, 1, 3, 1, 0] (15)
 INFO    :      L[ 1]       : [0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 0, 3, 2, 2 ... 1, 0, 2, 3, 0, 2, 0, 0, 0, 3, 3, 0, 2, 1, 1, 3, 2, 0, 0, 2] (63)
 INFO    :      L[ 2]       : [0, 0, 0, 0, 0, 1, 3, 0, 0, 2, 3, 1, 1, 2, 2, 3, 0, 0, 3, 1 ... 2, 3, 1, 0, 0, 1, 0, 1, 2, 3, 3, 3, 0, 3, 1, 3, 3, 2, 3, 0] (255)
 INFO    :      L[ 3]       : [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 2, 3, 1, 3, 2, 2, 2, 1 ... 1, 0, 0, 2, 3, 0, 2, 3, 1, 0, 0, 0, 0, 1, 1, 3, 3, 3, 2, 2] (1023)
 INFO    :      L[ 4]       : [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 1, 2, 1, 3, 1, 3 ... 0, 2, 3, 0, 3, 3, 0, 3, 3, 1, 2, 3, 0, 1, 3, 1, 1, 1, 1, 0] (4095)
 INFO    :      L[ 5]       : [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 3, 3, 1, 2, 0, 1, 0, 1 ... 0, 1, 0, 0, 1, 1, 1, 2, 2, 2, 0, 3, 3, 0, 2, 2, 0, 2, 0, 2] (16383)
 INFO    :      L[ 6]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 2, 1, 0, 1, 3, 3, 0, 0 ... 3, 0, 2, 3, 0, 2, 0, 2, 1, 0, 3, 0, 0, 0, 1, 0, 3, 0, 3, 0] (65535)
 INFO    :      L[ 7]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 1, 2, 1, 0, 0 ... 0, 0, 1, 0, 0, 1, 0, 1, 0, 2, 3, 3, 0, 1, 2, 0, 1, 1, 2, 2] (262143)
 INFO    :      L[ 8]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 3, 0, 1, 3, 0, 0 ... 3, 0, 1, 3, 0, 1, 3, 0, 2, 3, 2, 2, 2, 3, 1, 0, 1, 3, 1, 0] (1048575)
 INFO    :      L[ 9]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 1, 0, 0 ... 0, 0, 1, 3, 3, 0, 2, 2, 3, 2, 2, 1, 0, 3, 3, 1, 2, 0, 0, 2] (4194303)
 INFO    :      L[10]       : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 1, 1 ... 1, 2, 3, 1, 1, 1, 2, 1, 0, 0, 3, 2, 0, 1, 1, 1, 3, 2, 3, 0] (16777215)
 INFO    :    dbsequence    : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 1, 1 ... 2, 3, 0, 2, 2, 2, 3, 2, 1, 1, 0, 3, 1, 2, 2, 2, 0, 3, 0, 1] (67108864)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.