[sword-devel] Question for Optimization / speed experts
Mon, 06 Jan 2003 22:45:33 +0800
Joachim Ansorg wrote:
>Some questiosn for optimizations experts :)
>I'm working on a piece of code in BibleTime which gives me headaches.
>BibleTime supports displaying different lexicons side by side, it offers only
>the keys which are available in all of the chosen lexicons.
>The function which creates the list of entries which are available in all
>modules is ways too slow and too CPU consuming.
>I implemented it the following way:
> 1. Sort the modules by number of entries (from small to large)
> 2. Use the modules with the fewest entries and go through all of it's
> 3. Is the entry in all other modules? Add the entry to a list of good
>entries it it is, otherwise continue with the next entry of the smallest list
>and compare it with all other chosen modules.
>Assume the user selected BDB together with StrongsHebrew. Each of the modules
>has around 10000 entries. So the outer loop would have 10000 iterations, the
>inner loop would have another 10000 iterations. So we get
>10.000*10.000=100.000.000 = one hunred million iterations. This is ways too
>slow and ways too much.
>This needs on my 1.2GHz Atlon with 512 MB Ram more then five seconds.
>If there are three, four or even five modules side by side we get much more
>Are the other ways to do such a task? Since the entry lists are sorted by the
>alaphabet this would be a good point to start. But I don't know how to do it
>I'd be really glad for help with this case!
initialise a marker to the first entry in each module
FOR each entry in module A
flag the entry as (potentially) good
FOR each other module
WHILE the marked entry in module is BEFORE the marked entry in A
move the marker forward an entry
IF the marked entry is AFTER the marked entry in A
flag the entry as bad
EXIT inner loop
IF the entry is not flagged as bad
add entry to list of good entries
move marker in module A forward an entry
This will iterate exactly once through each entry in each module. It
depends on the modules being sorted, but I understand that's a given anyway.