Anyone help develop an algorythm?

Anyone help develop an algorythm?

[Matthew Givens]

Okay, I have need for a special case sorting algorythm.  The best I've 
come up with is a streamlined, modified bubble sort, but performance 
isn't good enough, since I can have between 5000 and 15000 records.  
Here's the situation:

I have a linked list, each node corresponding to an array (contiguous in 
memory) of fixed length strings.  The default size of each array is 100, 
but that is user configurable and can change at run time.  So, call the 
size of the S and the length of each string in the array L.  Also, call 
the number of nodes in the linked list N.

Now, I have to sort these multiple nodes as if the whole shebang was a 
single, contiguous array.  The best I've been able to come up with is a 
modified Bubble Sort using page number as part of the looping structure.  
It looks a little weird, but it works.  Too slow, though.

This algorythm is for work, and I have to have it operational by the end 
of May.  Performance is a major consideration.

Any suggestions are appreciated.

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>

Re: Anyone help develop an algorythm?

[Robert A Duff]

In article <5jddg7$uf0@newssvr01-int.news.prodigy.com>,
Matthew Givens <NKSW39B@prodigy.com> wrote:
>I have a linked list, each node corresponding to an array (contiguous in 
>memory) of fixed length strings. ...

Perhaps you should construct an array on the side, containing pointers
to all the strings.  Then sort that, using your favorite (fast) sorting
algorithm.

Constructing the array can be done in linear time.  You can walk the
list once to determine the size of the array.  Or perhaps your program
already knows the size.  Or perhaps it knows some reasonable upper bound
on the size.  Then walk the list again, putting pointers to each string
in the array.  (The strings need to be "aliased".)  Then do the sort.

- Bob

Re: Anyone help develop an algorythm?

[Tucker Taft]

Matthew Givens (NKSW39B@prodigy.com) wrote:

: Okay, I have need for a special case sorting algorythm.  The best I've 
: come up with is a streamlined, modified bubble sort, but performance 
: isn't good enough, since I can have between 5000 and 15000 records.  
: Here's the situation:

: I have a linked list, each node corresponding to an array (contiguous in 
: memory) of fixed length strings.  The default size of each array is 100, 
: but that is user configurable and can change at run time.  So, call the 
: size of the S and the length of each string in the array L.  Also, call 
: the number of nodes in the linked list N.

: Now, I have to sort these multiple nodes as if the whole shebang was a 
: single, contiguous array.  The best I've been able to come up with is a 
: modified Bubble Sort using page number as part of the looping structure.  
: It looks a little weird, but it works.  Too slow, though.

There is a variant of quick-sort that works on linked lists.
The trick is to use the first element in the list as the "pivot" and
then build up two new linked lists containing the left and right partitions,
and then recurse as usual.  I would think this could be generalized
to handle a linked list of arrays (left as an exercise to the reader ;-).

Alternatively, you might be able to use a heap sort to merge the
result of quick-sorting each array in the list.

: This algorythm is for work, and I have to have it operational by the end 
: of May.  Performance is a major consideration.

Then avoid bubble sort like the plague.

: Any suggestions are appreciated.

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Anyone help develop an algorythm?

[Joel VanLaven]

Matthew Givens (NKSW39B@prodigy.com) wrote:
: Okay, I have need for a special case sorting algorythm.  The best I've 
: come up with is a streamlined, modified bubble sort, but performance 
: isn't good enough, since I can have between 5000 and 15000 records.  
: Here's the situation:

: I have a linked list, each node corresponding to an array (contiguous in 
: memory) of fixed length strings.  The default size of each array is 100, 
: but that is user configurable and can change at run time.  So, call the 
: size of the S and the length of each string in the array L.  Also, call 
: the number of nodes in the linked list N.

: Now, I have to sort these multiple nodes as if the whole shebang was a 
: single, contiguous array.  The best I've been able to come up with is a 
: modified Bubble Sort using page number as part of the looping structure.  
: It looks a little weird, but it works.  Too slow, though.

: This algorythm is for work, and I have to have it operational by the end 
: of May.  Performance is a major consideration.

: Any suggestions are appreciated.

I would be inclined to go with a merge sort (of some kind or other).  
Allow me to quote from Robert Sedgewick's _Algorithms_ (I highly
recommend this book).  "Mergesort is the method of choice for sorting
a linked list, where sequential access is the only kind of access
available."  It is quite simple, has O(NlogN) worst-case performance and
in your situation ought to require additional memory of at most 1 array
of strings (plus a teensy bit).  Of course sort each array by any method
you prefer (quicksort, heapsort, shellsort, or selection sort). 
 
Note that selection sort (still O(N^2)) is much better than bubble sort
and is "just as simple".  It would also be easy to apply to your 
situation (as the primary sort).  Basically, if you are really using
bubble sort, almost anything at all would be better.  Of course it might
be that you are not using what I call a buuble sort.

Hope that helps some.
-- 
-- Joel VanLaven

Re: Anyone help develop an algorythm?

[Robert Dewar]

Matthew says

<<Okay, I have need for a special case sorting algorythm.  The best I've
come up with is a streamlined, modified bubble sort, but performance
isn't good enough, since I can have between 5000 and 15000 records.
Here's the situation:

I have a linked list, each node corresponding to an array (contiguous in
memory) of fixed length strings.  The default size of each array is 100,
but that is user configurable and can change at run time.  So, call the
size of the S and the length of each string in the array L.  Also, call
the number of nodes in the linked list N.

Now, I have to sort these multiple nodes as if the whole shebang was a
single, contiguous array.  The best I've been able to come up with is a
modified Bubble Sort using page number as part of the looping structure.
It looks a little weird, but it works.  Too slow, though.

This algorythm is for work, and I have to have it operational by the end
of May.  Performance is a major consideration.

Any suggestions are appreciated.
>>

Ugh! bubble sort sounds, even modified as you say, sounds like a horrible
choice here. Have a look at the g-hesora or g-hesorg files in the GNAT
distribution for efficient sorts (this is a modified heapsort, using the
modification i developed in my thesis work 30 years ago, which halves
the number of comaprisons). It is setup with a procedural interface
that should be easy to adapt to your application.

Re: Anyone help develop an algorythm?

[Tom Moran]

Your problem statement is unclear.  Are you saying your linked list has
N nodes, at each node is an array of some number of elements, each
element is a string of (equal) length L, and you want to treat is as a
great big array of strings of length L and you want to sort that big
array?

Re: Anyone help develop an algorythm?

[Michael F Brenner]

Several of the fastest ways to sort your array of strings include not
sorting them at all. In a prior post I gave code for partially balanced
tree searches which do a partial sort in less time than true sorts, 
balancing (pardon the pun) the requirements for small sort time versus
the time for small lookup time. Three faster methods include an address
finite state machine, an calculation sort, and a hash code sort. Hash
codes are just imperfect address calculation sorts, and will not be
discussed here. Address calculations are becoming more and more possible
as machine addresses get larger, and virtual hardware with translation
lookaside buffers become the rule rather than the exception on modern
risc CPUs. However, I will assume that you have a tiny PC such as
a Pentium like I have, with a pitiful few dozen megs of RAM to fit
the arrays and the workspace. Therefore, we come to the FSA possibility.
FSAs at first glance seem to take K**(L+1) words of memory, where
K is the size of the alphabet used for the lookup strings, and L is
the number of lookup strings. However, this matrix is extremely
sparse. First, we notice that K can be reduces from 256 down to 
approximately 27 by collapsing all special characters and making
everything lower case, if the words are in English. Second, we notice
that most of the potential states are unused, so we only need to store
the matrix for m states, where m is the sum of the lengths of the 
lookup strings. So we now have a reduced matrix of 27m words length.
This can be implemented directly in code instead of in matrix form, using
such constructs as CASE statements or GOTO statements. One last 
possibility to mention is the dream of perfect hash codes. If you
happen to come across a fast-to-compute formula that happens to
compute the lookup function of your list of words, then by all means
use it. It is not always possible to derive such a magic formula
for all possible inputs, however. 

Re: Anyone help develop an algorythm?

[Robert Dewar]

Joel says

<<I would be inclined to go with a merge sort (of some kind or other).
Allow me to quote from Robert Sedgewick's _Algorithms_ (I highly
recommend this book).  "Mergesort is the method of choice for sorting
a linked list, where sequential access is the only kind of access
available."  It is quite simple, has O(NlogN) worst-case performance and
in your situation ought to require additional memory of at most 1 array
of strings (plus a teensy bit).  Of course sort each array by any method
you prefer (quicksort, heapsort, shellsort, or selection sort).>>

That seems a kind of confused mixture. If you are going to use merge sort,
use merge sort. you don't need any arrays, and you don't need to use any
other algorithm. The algorithm is trivial, split the list into two halves,
sort each half recursively, and then do a merge, end of story. This has
worst case NlogN and is what Sedgewick means when he makes his suggestion.

Re: Anyone help develop an algorythm?

[Steve Doiel]

In article <E8yGpJ.Dyu@world.std.com>, bobduff@world.std.com says...
>
>In article <5jddg7$uf0@newssvr01-int.news.prodigy.com>,
>Matthew Givens <NKSW39B@prodigy.com> wrote:
>>I have a linked list, each node corresponding to an array (contiguous in 
>>memory) of fixed length strings. ...
>
>Perhaps you should construct an array on the side, containing pointers
>to all the strings.  Then sort that, using your favorite (fast) sorting
>algorithm.
>
>Constructing the array can be done in linear time.  You can walk the
>list once to determine the size of the array.  Or perhaps your program
>already knows the size.  Or perhaps it knows some reasonable upper bound
>on the size.  Then walk the list again, putting pointers to each string
>in the array.  (The strings need to be "aliased".)  Then do the sort.
>
>- Bob

Agreed... but with two notes:

  1) Check out the PAL to see if you can use an "off the shelf" sort... the
     last thing you should have to do is implement a sort _again_
     (what ever happened to software re-use?).

  2) The strings do not necesarily need to be aliased if each element in
     your array contains a pointer to the array and in index to the element,
     although the aliased approach is likely to be more efficient.

Steve Doiel

Re: Anyone help develop an algorythm?

[Tucker Taft]

Matthew Givens (NKSW39B@prodigy.com) wrote:
: stt@houdini.camb.inmet.com (Tucker Taft) wrote:
: >
: >There is a variant of quick-sort that works on linked lists.
: >The trick is to use the first element in the list as the "pivot" and
: >then build up two new linked lists containing the left and right 
: >partitions,
: >and then recurse as usual.  I would think this could be generalized
: >to handle a linked list of arrays (left as an exercise to the reader ;-).


: Could you give me a reference (or two) where I might be able to find the 
: Quick Sort variation you mentioned?

"The Handbook of Algorithms and Data Structures in Pascal and C"
Second Edition, G.H. Gonnet, R. Baeza-Yates, Addison-Wesley,
look for "Quick Sort on Lists" in the table of contents.

You can also derive the algorithm yourself if you understand
how "normal" Quick Sort works.

For your case of a list of arrays, I suspect you could create a hybrid
of "normal" Quick Sort and a linked-list version.  The requirements
of Quick Sort are an ability to iterate though any partition of an
array, and to make exchanges.  If your iteration "cursor" consists of a 
pointer to the "current" array, and an index into the current array, and 
a partition were represented by two such cursors, then I believe you
could use the basic Quick Sort algorithm relatively straightforwardly.

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Anyone help develop an algorythm?

[Robert Dewar]

<<>There is a variant of quick-sort that works on linked lists.
>The trick is to use the first element in the list as the "pivot" and
>then build up two new linked lists containing the left and right
partitions,
>and then recurse as usual.  I would think this could be generalized
>to handle a linked list of arrays (left as an exercise to the reader ;-).


Could you give me a reference (or two) where I might be able to find the
Quick Sort variation you mentioned?
>>


This is not quick sort at all. The essence of quick sort is the in place
exchange -- otherwise you are just talking about a simple recursive
sort, known for a long time before quicksort was published by Hoare.

The algorithm is trivial enough, just form two lists one of elements
greater than the pivot, one of elements less than the pivot, and then
recursively sort both lists and append one to the other.

However, this algorithm is NEVER preferable to a straight 2-way merge
sort, since its average behavior is the same, and its worst case performance
is quadratic.

The only reasonable way to sort a list is with a two way merge sort. 
Divide the list into equal parts, sort each sublist recurs9ively, and
then do a 2-way merge to form the result. This sort is average and
worst case NlogN, is easy to program, and has no disadvatanges over
other methods that I can see.

Re: Anyone help develop an algorythm?

[Robert Dewar]

Matthew Givens says

<<Now, I know a bit about heap, and it seems to require contiguous storage,
t do it's thing.  As do most sorting algorythms.  I need one that can
accomodate the difference.>>

Please look at g-hesora.ads in the GNAT library. It has a purely
procedural interface that does not require contiguous data, it just
requires a linear indexing access path, which certainly does not
require contiguous data (for example, set up an index vector, or
you could even use a two level structure for indexing (in theory
that might make the sort N logN logN, but in practice it would
just introduce a small extra constant factor.

Re: Anyone help develop an algorythm?

[Matthew Givens]

stt@houdini.camb.inmet.com (Tucker Taft) wrote:
>
>
>
>There is a variant of quick-sort that works on linked lists.
>The trick is to use the first element in the list as the "pivot" and
>then build up two new linked lists containing the left and right 
partitions,
>and then recurse as usual.  I would think this could be generalized
>to handle a linked list of arrays (left as an exercise to the reader ;-).


Could you give me a reference (or two) where I might be able to find the 
Quick Sort variation you mentioned?

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>

Re: Anyone help develop an algorythm?

[Matthew Givens]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
>
>Matthew says
>
>
>Ugh! bubble sort sounds, even modified as you say, sounds like a 
horrible
>choice here. Have a look at the g-hesora or g-hesorg files in the GNAT
>distribution for efficient sorts (this is a modified heapsort, using 
the
>modification i developed in my thesis work 30 years ago, which halves
>the number of comaprisons). It is setup with a procedural interface
>that should be easy to adapt to your application.
>

Guys, please.  Of course I know that the Bubble is the worst sort in 
existence for a large array, but it was the easiest to implement with the 
array divided up into non-contiguous chunks.  It works, but performance 
is unacceptable.  Basically I did it to get something working now, with 
(hopefully) a better method coming later.

Now, I know a bit about heap, and it seems to require contiguous storage, 
t do it's thing.  As do most sorting algorythms.  I need one that can 
accomodate the difference.

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>

Re: Anyone help develop an algorythm?

[Marin David Condic, 561.796.8997, M/S 731-93]

Joel VanLaven <jvl@OCSYSTEMS.COM>writes:
>Note that selection sort (still O(N^2)) is much better than bubble sort
>and is "just as simple".  It would also be easy to apply to your
>situation (as the primary sort).  Basically, if you are really using
>bubble sort, almost anything at all would be better.  Of course it might
>be that you are not using what I call a buuble sort.
>
    Of course, an alternate strategy is to always start development
    using the Slowsort(1) algorithm. Moving to almost anything
    else (including bubble sort) gets you an immediate improvement in
    performance and much customer satisfaction ;-))

    (1) Slowsort is an algorithm developed by myself & Bob Zaret in
    which you generate a random permutation of the list, then check to
    see if the list is sorted. If not, do it again... Behavior is
    O(N!). It was written up in Ada Letters many moons ago.

    MDC

Marin David Condic, Senior Computer Engineer    ATT:        561.796.8997
Pratt & Whitney, GESP                           Fax:        561.796.4669
West Palm Beach, FL                             Internet:   CONDICMA@PWFL.COM
===============================================================================
    "A verbal contract isn't worth the paper it's written on."

        --  Samuel Goldwyn
===============================================================================

Re: Anyone help develop an algorythm?

[Michael F Brenner]

Slow sort is an interesting development, but might not satisfy the realtime
criterion for certain non-genetic embedded systems. Taking the basic loop

     loop
         find two elements which are out of order
         swap them
     end loop

one could enhance it as follows 

     -- precondition: the unsorted array of integers has no repeats and
     --               is already read into the array object_list

     subtype sub_type is object_exact_integer_type range
        get_min (all_objects) .. get_max (all_objects);

     type ar_ray is array (object_exact_integer_type range <>);
     subtype condensed_essence_of_objects is ar_ray range sub_type;

     for i in indexes loop
       ar_ray (object_list (i)) := True;
     end loop;

     for i in sub_type loop
       j := get_next_non_zero_index;
       text_io.put_line (my_image (j));
     end loop;

     -- This sort takes time linear in the number of elements of your
     -- array on any machine in which inputting, outputting, searching
     -- for the next non-zero index, imaging, indexing arrays, and
     -- reading and writing bits in bit arrays can be done in constant
     -- time; the main exception to this will be searching for the next
     -- non-zero index. The BESM-6 computer produced by Russia has a
     -- hardware op-code to do this, however, it is only useful for
     -- sorting arrays whose object values range from 0..7 with no repeats.

Re: Anyone help develop an algorythm?

[Matthew Givens]

Tom Moran <tmoran@bix.com> wrote:
>
>Your problem statement is unclear.  Are you saying your linked list has
>N nodes, at each node is an array of some number of elements, each
>element is a string of (equal) length L, and you want to treat is as a
>great big array of strings of length L and you want to sort that big
>array?

Yes, exactly.

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>

Re: Anyone help develop an algorythm?

[Matthew Givens]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
>
>The only reasonable way to sort a list is with a two way merge sort. 
>Divide the list into equal parts, sort each sublist recurs9ively, and
>then do a 2-way merge to form the result. This sort is average and
>worst case NlogN, is easy to program, and has no disadvatanges over
>other methods that I can see.
>

The problem is that a Merge sort, if I'm not mistaken merges multiple 
arrays/files into a single sorted one.  I don't want that.  I want to 
take the mulitple arrays residing in a linked list and sort them as if 
they were a single array of data.

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>

Re: Anyone help develop an algorythm?

[Robert Dewar]

Matthew said

<<>Your problem statement is unclear.  Are you saying your linked list has
>N nodes, at each node is an array of some number of elements, each
>element is a string of (equal) length L, and you want to treat is as a
>great big array of strings of length L and you want to sort that big
>array?P>>

Yes exactly>>


The question is what form do you want the output in? Do you want to
construct an array of poiners? If so, then it is trivial to sort the
array of pointers, using any standard sorting algorithm. Or do you want
to sort in place keeping the linked list structure throughout -- in 
that case a modified mrge sort is the only feasible answer (modified
to deal with the multi-element nodes).

Re: Anyone help develop an algorythm?

[Matthew Givens]

mfb@mbunix.mitre.org (Michael F Brenner) wrote:
>
>
>Slow sort is an interesting development, but might not satisfy the 
realtime
>criterion for certain non-genetic embedded systems. Taking the basic 
loop
>
>     loop
>         find two elements which are out of order
>         swap them
>     end loop

-- SNIP --

>     -- This sort takes time linear in the number of elements of your
>     -- array on any machine in which inputting, outputting, searching
>     -- for the next non-zero index, imaging, indexing arrays, and
>     -- reading and writing bits in bit arrays can be done in constant
>     -- time; the main exception to this will be searching for the next
>     -- non-zero index. The BESM-6 computer produced by Russia has a
>     -- hardware op-code to do this, however, it is only useful for
>     -- sorting arrays whose object values range from 0..7 with no 
repeats.

Hmmmm, not too many years ago I made my own contribution to the world of 
sorting algorythms with RandomSort.  It was simple, really.  Take the 
array elements, and assign them randomly to a second array.  Then scan 
the second array to see if it's sorted.  If not, scrap everything and do 
it again.  It's worse than the Slow Sort, because there's a chance 
(depending on the Psuedo-Random number generator being used and the seed 
value fed to it) that the list will NEVER be sorted.  It has happened to 
me (I think that almost 24 hours for a 25 element array kind of points to 
never, don't you?).

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>

Re: Anyone help develop an algorythm?

[Matthew Givens]

"Marin David Condic, 561.796.8997, M/S 731-93" <condicma@PWFL.COM> 
wrote:
>
>Joel VanLaven <jvl@OCSYSTEMS.COM>writes:
>>Note that selection sort (still O(N^2)) is much better than bubble 
sort
>>and is "just as simple".  It would also be easy to apply to your
>>situation (as the primary sort).  Basically, if you are really using
>>bubble sort, almost anything at all would be better.  Of course it 
might
>>be that you are not using what I call a buuble sort.
>>
>    Of course, an alternate strategy is to always start development
>    using the Slowsort(1) algorithm. Moving to almost anything
>    else (including bubble sort) gets you an immediate improvement in
>    performance and much customer satisfaction ;-))
>
>    (1) Slowsort is an algorithm developed by myself & Bob Zaret in
>    which you generate a random permutation of the list, then check to
>    see if the list is sorted. If not, do it again... Behavior is
>    O(N!). It was written up in Ada Letters many moons ago.

Interesting.  I developed that one myself (in C) back in 1991.  Well, you 
know what they say about great minds...

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>

Re: Anyone help develop an algorythm?

[Matthew Givens]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
>
>Matthew said
>
><<>Your problem statement is unclear.  Are you saying your linked list 
has
>>N nodes, at each node is an array of some number of elements, each
>>element is a string of (equal) length L, and you want to treat is as a
>>great big array of strings of length L and you want to sort that big
>>array?P>>
>
>Yes exactly>>
>
>
>The question is what form do you want the output in? Do you want to
>construct an array of poiners? If so, then it is trivial to sort the
>array of pointers, using any standard sorting algorithm. Or do you want
>to sort in place keeping the linked list structure throughout -- in 
>that case a modified mrge sort is the only feasible answer (modified
>to deal with the multi-element nodes).

The structure of the data can't change.  The data must be sorted in place,
 not merged into a single list.  And the only merge sorts I know actually 
merge the data into a single list.  Just how do you modify a merge sort 
to sort the data in place?

-
If at first you don't succeed, destroy all evidence that you ever tried. 
<< Iceman >>