3 ms·

Is there another implementation we can compare this with? Kind of crazy to say that this is fast without any comparisons with anything else. So far I've been u

by lqdc13 9y ago

Is there another implementation we can compare this with? Kind of crazy to say that this is fast without any comparisons with anything else. So far I've been using suffix trees from here: http://www.daimi.au.dk/~mailund/suffix_tree.html http://www.daimi.au.dk/~mailund/suffix_tree.html

fnl 9y ago
Most uses are in rather obscure bioinformatics packages, where the exact matching of sequences is useful, including BWT compression of the arrays. Easy to Google, but I don't know if any pure-Python versions not written in C exist, and having seen colleagues argue about the best/most correct implementation, I prefer not to link any (Google is your friend...). But so any interesting performance comparison would probably be against a pure C implementation.
deleted 9y ago
[deleted]
dom0 9y ago
Article seems to be mostly about efficient, not fast.
- lqdc13 9y ago
  "Suffix arrays : How to compute them fast with Python" The assumption is it's fast in Python without using Cython etc. My intuition says that looping and iterating in Python is slow. It seems like a great reference implementation, but I don't think anyone should use it if there are implementations that are (possibly) orders of magnitude faster. I guess my bigger issue with this is that in many cases it's much more time efficient to just drop to Cython earlier on instead of fighting with the language.
- Labo333 9y ago
  I'm not sure about the difference, but yes :) I wanted an implementation that could fit on my screen and still be efficient. Of course Python is slow and even my algorithm is not the best (I explained why I chose it). But I believe this is one of the best implementation you can make of prefix doubling, especially against random data and I have never seen my tricks anywhere.
pathsjs 9y ago
You can test it against https://unicredit.github.io/cello/ https://unicredit.github.io/cello/

by lqdc13 9y ago

fnl 9y ago

Most uses are in rather obscure bioinformatics packages, where the exact matching of sequences is useful, including BWT compression of the arrays. Easy to Google, but I don't know if any pure-Python versions not written in C exist, and having seen colleagues argue about the best/most correct implementation, I prefer not to link any (Google is your friend...). But so any interesting performance comparison would probably be against a pure C implementation.

deleted 9y ago

[deleted]

dom0 9y ago

Article seems to be mostly about efficient, not fast.

lqdc13 9y ago
"Suffix arrays : How to compute them fast with Python" The assumption is it's fast in Python without using Cython etc. My intuition says that looping and iterating in Python is slow. It seems like a great reference implementation, but I don't think anyone should use it if there are implementations that are (possibly) orders of magnitude faster. I guess my bigger issue with this is that in many cases it's much more time efficient to just drop to Cython earlier on instead of fighting with the language.
Labo333 9y ago
I'm not sure about the difference, but yes :) I wanted an implementation that could fit on my screen and still be efficient. Of course Python is slow and even my algorithm is not the best (I explained why I chose it). But I believe this is one of the best implementation you can make of prefix doubling, especially against random data and I have never seen my tricks anywhere.

pathsjs 9y ago

You can test it against https://unicredit.github.io/cello/ https://unicredit.github.io/cello/