Algorithms in the std lib

[Andrei Alexandrescu]

Daniel de Kok wrote:
> 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.)

Yah; in fact I already have a Trie implementation (prefix tree) hanging 
on around std. I'm just afraid to bite the bullet in choosing a 
container overall design. I'd need more experience, and currently bugs 
in dmd's copy constructors prevent most experimentation with value types.


Andrei