ADRIFT Forum


The place to discuss the ADRIFT Interactive Fiction toolkit

Indexing ALR speedup

This forum is the place to discuss the older ADRIFT versions 3.9 and 4.0.

Please refer to the ADRIFT 4 Manual for more information.

Indexing ALR speedup

Postby phkb » Wed Jun 29, 2011 7:35 am

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.
My IF-related stuff can be found here
User avatar
phkb
 
Posts: 376
Joined: Thu Jan 06, 2005 3:27 am
Location: Sydney, Australia

Re: Indexing ALR speedup

Postby Campbell » Wed Jun 29, 2011 8:23 am

Well, it resorts all the entries, longest to shortest, so you could try doing that before importing to see if it makes a difference.
ADRIFT Developer developer.
User avatar
Campbell
Site Admin
 
Posts: 4654
Joined: Sun Jun 23, 2002 11:05 am
Location: Edinburgh, Scotland

Re: Indexing ALR speedup

Postby ralphmerridew » Wed Jun 29, 2011 11:44 am

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.
Bloodhounds can make you laugh and cuss in the same breath. They are endearing, faithful, and can sling drool ten feet in any direction. -- Virginia Lanier
User avatar
ralphmerridew
 
Posts: 2574
Joined: Fri Dec 13, 2002 11:56 pm
Location: Missouri
Points: 10

Re: Indexing ALR speedup

Postby phkb » Wed Jun 29, 2011 8:50 pm

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.
My IF-related stuff can be found here
User avatar
phkb
 
Posts: 376
Joined: Thu Jan 06, 2005 3:27 am
Location: Sydney, Australia

Re: Indexing ALR speedup

Postby phkb » Wed Jun 29, 2011 8:52 pm

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.
My IF-related stuff can be found here
User avatar
phkb
 
Posts: 376
Joined: Thu Jan 06, 2005 3:27 am
Location: Sydney, Australia

Re: Indexing ALR speedup

Postby Campbell » Wed Jun 29, 2011 9:03 pm

That sounds like it just appended to an existing set. Is it all doubled up if you export back out?
ADRIFT Developer developer.
User avatar
Campbell
Site Admin
 
Posts: 4654
Joined: Sun Jun 23, 2002 11:05 am
Location: Edinburgh, Scotland


Return to ADRIFT 3.9 and 4.0

Who is online

Users browsing this forum: No registered users and 7 guests

cron