Re: fast stable sort

cri@xxxxxxxx (Richard Harter) writes:

On 18 Nov 2008 07:02:17 -0800, Tim Rentsch
<txr@xxxxxxxxxxxxxxxxxxx> wrote:

Ben Bacarisse <ben.usenet@xxxxxxxxx> writes:

CBFalconer <cbfalconer@xxxxxxxxx> writes:

Ben Bacarisse wrote:
CBFalconer <cbfalconer@xxxxxxxxx> wrote:
Richard Harter wrote:

There are in place stable versions of mergesort.
<snip>
Such exists in wdfreq.c, an example program on the use of
hashlib. wdfreq has been put in public domain, hashlib is
released under GPC. See:

<http://cbfalconer.home.att.net/download/hashlib.zip>

<snip>
You can't claim to have an in-place merge sort simply because you have
already wasted lots of space by using a space inefficient method of
input. This is the second time I have made this point but you clipped
it without comment last time. If you have no comment about this
central issue, at least leave it un-clipped this time.

It is NOT inefficient. It simply lumps the pointer in with the
string, rather than isolating it in a separate array.

Not from what I see. It lumps an extra pointer in with the only one
really needed (the one that points to the string):

typedef struct wordlink {
char *word; /* Points to the word itself */
unsigned long count; /* of occurances */
struct wordlink *next; /* Used to create a list */
} wordlink, *wordlinkp;

Building a linked list does not constitute using O(1) extra space. It
uses O(N) extra space (one extra pointer per string).

The result
takes the same space,

The same space as what? An N element char * array (along with the
strings they point to) takes exactly N pointers less space than your
linked list. It is this extra space that enable merges sort to work
so easily. Sorting a linked list is not what is meant by "in-place
merge sort".

To be fair, Chuck's comments do bring out an interesting point, which
I would say thusly: when you have an unspecified number of elements
of unknown sizes, these can be put into a linked list that takes only
as much space as an array holding pointers to each. This space
savings occurs because the links do "double duty" of getting to the
strings and linking the strings into an order. If only one ordering
criterion is needed, this linked list can be sorted without the usual
additionl temporary space associated with mergesort. (And yes, I
think it can be done as an in-place algorithm, although I haven't
actually tried to code it.)

That said, the mergesort routine in CBF's library is not an in-place
algorithm, since it uses O( log n ) stack space for the recursion
(which you also point out a few messages downstream). (I didn't
look at the code carefully enough to see if it actually uses the
trick of "double duty" list links.)

What technique are you using to make the links do double duty?
The only one that occurs to me is to have a data record
consisting of a successor link immediately followed by the
element, i.e, using adjacency to get to the element rather than a
link. Is that you had in mind or were you thinking of something
more clever.

Yes, that's it. The point is, if elements are variable sized,
as they are for strings, by saving a pointer to the element
we can use it for pointing to the next item in the list.
Of course this idea loses some appeal if we want to do any
sort of random access on the elements, rather than just
strictly sequential.

Also on a less profound level, how does one define such a record
in C and allocate space for it without using some kind of hack?

I believe it can be done conformantly in C99 using malloc(), namely by:

typedef struct list_of_T {
struct list_of_T *next;
T element_parts[];
} *T_list;

T_list p = malloc( sizeof *p + N * sizeof (T) );
/* check malloc return result */

/* what p points to will hold both a link to the next element
and an array of size N of type T */

/* If T is char, use N = strlen(s) + 1 to hold string s */

In C89/C90, the "struct hack" is the commonly recognized idiom
that does basically the same thing. So it may be a hack, but
at least it's a commonly recognized one. :)

.

Relevant Pages

  • Re: two dimensional arrays passed to functions
    ... > array and then send it down as a single dimmensional array. ... x is an array of char pointers. ... to a pointer to the first element of this array, ... need to copy the strings and not just assign pointers to them). ...
    (comp.lang.c)
  • Re: low-level pointer vs. array question
    ... that the array version is indeed superiour for my purposes. ... memory for pointer variables. ... Note that "it allocates memory only for the strings" ...
    (comp.lang.c)
  • Re: char *arr[n] Vs. char **arr
    ... since the number of small strings is not ... the array format[], and copy the token to that address. ... The malloc statement gives a segfault. ... makes an integer from pointer" etc.. ...
    (comp.lang.c)
  • Re: char *arr[n] Vs. char **arr
    ... since the number of small strings is not ... the array format[], and copy the token to that address. ... The malloc statement gives a segfault. ... makes an integer from pointer" etc.. ...
    (comp.lang.c)
  • Re: fast stable sort
    ... wdfreq has been put in public domain, hashlib is ... It lumps an extra pointer in with the only one ... Building a linked list does not constitute using Oextra space. ... strings and linking the strings into an order. ...
    (comp.programming)