[Zope] Finding a match in a large dataset - btrees?

[Andreas Jung]

--On 6. Dezember 2005 14:55:08 +1300 Cameron Beattie <kjcsb at orcon.net.nz> 
wrote:
>
> I want to do this frequently and at low cost i.e. ideally in memory.
> Perhaps the best way is to write a procedure in MySQL however I am
> interested in any python-based alternatives.

Your problem is more an algorithmic problem than q question of the data 
representation. Store the mapping as some BTree (possibly IIBTree using 
normalized integers for the values). Then you have to iterate over all 
prefixes of the dialed number starting with the longest prefix to the 
smallest prefix. Then perform a lookup of the prefix in your BTree...
this is should not take more than five lines of code and requires a maximum
of #(length_of_dialed_number) comparisons. If you want it more complicated 
construct a tree and you'll have a logarithmic number of comparisons. I 
doubt that it is worth the effort since the first solution should be fast 
enough unless your dialed number is hundreds of digits long :-)

-aj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 186 bytes
Desc: not available
Url : http://mail.zope.org/pipermail/zope/attachments/20051206/b6c4f02a/attachment.bin