Algorithms in the std lib

[Daniel de Kok]

On Tue, Feb 17, 2009 at 5:50 PM, bearophile <bearophileHUGS at lycos.com> wrote:
> Andrei Alexandrescu:
>> Ok, I can implement all that... but twice?!? :o)
>
> Sorry for the double posting.
> And regarding the implementation, first of all it can be seen if you and other people think it's generally
> useful stuff. Later I'll offer some/most implementations :-)

How about suffix array construction? It's a very underused useful data
structure where you compose a parallel array to data array that is
sorted by suffix. This is often used in natural language processing to
be able to quickly count the frequency of arbitrary long n-grams
without having to store counts of n-grams in a large hash map or
traversing the data array in linear order.

This is a probably pretty lame implementation that I made as one of my
first tiny D programs (I have only started to learn D in tiny bits):

http://static.danieldk.org/snippets/d/sarr.d

Take care,
Daniel

(P.s. there are some algorithms that can construct suffix arrays
faster than a regular sort, but they usually have a lot of
requirements, like perfect hashing of all the elements.)