Quote from Forum Archives on November 10, 1997, 3:30 pm

Posted by: mel <mel@...>

I'm trying to come up with the fastest sort and while I seem to be on the
right track, I'm wondering if there isn't a faster/better way...

I am using the FB INDEX$ to hold data in memory, variable length style.
Which works fine except when it comes to a sort condition. For example, I
have about 1350 items in a list and I sort them on my PPC 7300 and it takes
about 1.5 seconds. Things being proportional, the bigger the INDEX$ gets
the slower the sort is bound to be.

The sort is based on the Combsort that I tend to favour because it seems to
be the fastest. Note, nothing is swapped in the INDEX$ itself, only the
array that contains the pointers to the INDEX$ elements. My ndx(count)
array.

If I load in a completely sorted list and delete the first item, we do a
lot of swaps (about 1300 or so) before the list is sorted. If I delete the
last item in the list, we only do about 2 swaps, but it seems to take the
same amount of time to get there.

LOCAL FN ndxCombSort(whichID):' this is my sort routine
DIM gap,switch,count,testElem,totalItems
totalItems=totalEntries-1:' we need to account for the 0 entry
'
gap = totalItems:' this is the total number of entries in the database
DO
gap=gap/1.3
IF gap < 1 THEN gap = 1
switch = _False
FOR count = 0 TO totalItems - gap
testElem = count + gap
'
LONG IF INDEX$(ndx(count),_fldrNdx)>INDEX$(ndx(testElem),_fldrNdx)
SWAP ndx(count),ndx(testElem):' we swap the index pointers to the lines
INC (switch):' show that we made a swap
END IF
'
NEXT count
UNTIL switch = _False AND gap = 1
'
hasFileChanged=_True:' show that changes to the file were made
END FN

My guess is that you take a big speed hit when you have an INDEX$ and you
ask for a specific element in it. I suspect somewhere in the compiler, it
performs a search from the beginning the list and counts through the
strings til it finds the element requested. And you do this enough time and
you start to lose time because of this "searching" for the element. This I
don't know for sure, but I suspect thats how it goes.

So now I question whether or not it would be faster to use XREF (I don't
know which to use in this case XREF or XREF@; any ideas appreciated). Then
step through the whole index$ and build line pointers to create my own
direct reference to each element in the index$ and then sort using
PSTR$(ptr&).

So how fast is PSTR$? No idea.

How fast can you build up and tear down an XREF array? No idea.

How fast can one step through a list and build the line pointers to each
element in the index$? Again, no idea.

Would it be faster to use an array in Globals to hold the line pointers?
Maybe...

Sorry if this seems a little technical. Ultimately programming comes down
to this. You push your own abilities to make a good product. And yes, I've
written some real stinkers too...I use them as examples of "how not to".

And when you start getting delusions of creating a great peice of software
and think you got it all figured out, and the beta testers say the sort
routine sucks, it kind of sets you back on earth. With a flat tire. At 60
miles an hour. In a blinding snow storm. Down a hill. With no brakes. In a
Yugo...

Mel Patrick - theWabbitGuy - mel@intergate.bc.ca
www.intergate.bc.ca/business/mel