Joachim Ansorg wrote:
Hi!My thoughts:
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 entries:
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 loops.
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 best.
I'd be really glad for help with this case!
Thank you!
Joachim
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.
Glen
