Hi all

This is my attempt to make a fast word search in a sorted list of words.
It does 1 545 000 searches in just 0.75 sec on my 1.6 GHz PIV
Any faster (without turning to unreadable code)?

KetilO
Posted on 2003-05-19 09:01:29 by KetilO
Since the binary search will do around 10 comparisons on average, it seems likely that a hash-table would perform better.

I have way too much of a cold to code it, though :grin:
Posted on 2003-05-20 07:04:28 by Jibz
Could build a Finite State Machine (FSM), but that uses a lot of memory.

http://www.codeproject.com/string/CIVStringSet.asp?print=true
http://www.informatik.uni-freiburg.de/~edelkamp/MultiSuffixTree/

The fewest number of comparisons.
Posted on 2003-05-20 07:51:25 by bitRAKE
Try to grab the Dawg package from Graham Toal's site: http://www.gtoal.com (sorry, I don't remember the exact link).
It's dedicated to spell checking and wordgames (like Scrabble).
This program compresses very efficiently a dictionary, and is able to retrieve words very quickly (an order of magnitude faster than your program !).

JC
Posted on 2003-05-24 05:17:27 by MCoder
For the lazy coders, here is the link containing (well commented) C source-code:
http://www.gtoal.com/wordgames/dawgutils/

You'll find a Trie generator, which compresses the Dawg even more (using bit-fields, if I remember).

JC
Posted on 2003-05-24 15:30:46 by MCoder