Indexing ALR speedup

[phkb]

The ALR on my WIP is now over 8600 lines long, and it is noticably slow when starting a game in the Runner. I was thinking of writing a program to take my ALR and do some pre-sorting of it so when I add it to the game the Runner doesn't have to do so much work. How should I sort the ALR to make this work? By the length of the left-side text? Right-side text? Both together? What if the length is the same on two lines?
Any pointers would be appreciated.

[Campbell]

Well, it resorts all the entries, longest to shortest, so you could try doing that before importing to see if it makes a difference.

[ralphmerridew]

If you're doing a stable sort of the data, then it's probably using Mergesort, which is Theta(n log n), in best and worst case. Presorting the list won't help that much.

A bucket sort variant (used in jAsea) should have Theta(n + {length of longest LHS}) performance, and is completely independent of whether the list is already sorted.

[phkb]

Well, I have just confirmed that presorting the ALR based just on the length of each line makes no difference to the "Processing ALR..." time when the game runs.

[phkb]

Incidentally, after I sorted my ALR, loaded it, and saved the game file, the size of the file jumped 25k! And that was after I removed blank lines and comment lines! I suspect the compression algorithm wasn't quite as efficient with text sprayed all over the place.

[Campbell]

That sounds like it just appended to an existing set. Is it all doubled up if you export back out?