[prev in list] [next in list] [prev in thread] [next in thread] 

List:       klink
Subject:    Fast String Index
From:       Mark Bucciarelli <mark () hubcapconsulting ! com>
Date:       2005-08-31 18:36:06
Message-ID: 20050831183606.GH648 () rabbit
[Download RAW message or body]

I assume at some point Tenor will have to do the following task: given a
string key, lookup a corresponding record.

I just implemented this task using an extremely performant algorithm,
and wanted to share the reference with the list.

It's an algorithm designed by Jon Bentley (wrote Programming Perls, Bell
Labs ex-employee). It's called a ternery search tree and man is it fast.
With my 2.6Gh box I was able to perform 400,000 lookups a second on a
table with 10,000 entries and a eight character key (small table, but
still ...).

Here are the references:

    http://www.cs.princeton.edu/~rs/strings/paper.pdf

    http://www.cs.princeton.edu/~rs/strings/tstdemo.c

He also describes a multi-key quicksort and other fast ways to sort
strings. In general, a great read for those who enjoy algorithms.

m

_______________________________________________
Klink mailing list
Klink@kde.org
https://mail.kde.org/mailman/listinfo/klink

[prev in list] [next in list] [prev in thread] [next in thread]