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)?

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.


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 !).

Posted on 2003-05-24 05:17:27 by MCoder
For the lazy coders, here is the link containing (well commented) C source-code:

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

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