Hacker News Reader

Comment by lqdc13 | Hacker News Reader

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

View on HN

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.

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

Article seems to be mostly about efficient, not fast.

"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.

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.

Reply on news.ycombinator.com