5
\$\begingroup\$

I already know how to merge two linked list, but I needed to code a function that'll merge three already sorted linked lists into one.

I wrote a code and it is working fine, it takes care of null lists and so. I just don't know if it's efficient enough. What do you think? How can I improve this code?

typedef struct clist {
int num;
struct clist *next;
} clist;

clist *cmerge(clist *c1, clist *c2, clist *c3) {
// Input parameters are pointers to the first items of the lists, out parameter is the pointer to the first item of the merged list
clist *ret = NULL, *curr = NULL, *last = NULL;
int i=1,n;
while(i) {
    i = 0;
    n = (c1) ? c1->num : (c2) ? c2->num : (c3) ? c3->num : 0;
    if(c1 && c1->num <= n) {
        n = c1->num;
        i = 1;
    }
    if(c2 && c2->num <= n) {
        n = c2->num;
        i = 2;
    }
    if(c3 && c3->num <= n) {
        n = c3->num;
        i = 3;
    }
    switch(i) {
    case 1:
        curr = c1;
        c1 = c1->next;
        break;
    case 2:
        curr = c2;
        c2 = c2->next;
        break;
    case 3:
        curr = c3;
        c3 = c3->next;
        break;
    default :
        curr = NULL;
    }
    if (!ret) ret = curr;
    else last->next = curr;
    last = curr;
}
return ret;
}
\$\endgroup\$

migrated from stackoverflow.com May 31 '16 at 20:20

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ Efficiency? Split off the cases for one or two lists empty. Avoid conditional code "in the loop", e.g., if (!ret) - have a local clist b4 = { 0 }, initialise curr to it and return b4.next. (And don't do as I did: don't use funny names. The only excuse for abbreviations like curr is they may make code more readable due to alignment, if not brevity.) After finding the minimum of two heads, you could try and append the initial part of the third list that "is no greater", followed by that minimum, making full use of that first comparison. Beware cache/branch prediction effects. \$\endgroup\$ – greybeard Jun 1 '16 at 8:51
6
\$\begingroup\$

The code works as it is, but it uses a number of local variables that aren't actually needed. An alternative approach might be this:

clist *cmerge(clist *c1, clist *c2, clist *c3) {
    clist *ret;
    clist *curr = NULL;
    while (1) {
        if (c3 && (!c2 || (c2 && c3->num < c2->num))) {
            clist *temp = c2;
            c2 = c3;
            c3 = temp;
        }
        if (c2 && (!c1 || (c1 && c2->num < c1->num))) {
            clist *temp = c1;
            c1 = c2;
            c2 = temp;
        }
        // use c1 as next node
        if (curr) {
            curr->next = c1;
            curr = curr->next;
        } else {
            ret = curr = c1;
        }
        if (c1) {
            c1 = c1->next;
        } else {
            return ret;
        }
    }
    return ret;   // never actually reached
}

The code works by arranging the three lists so that the smallest next number is always pointed to by c1. That simplifies appending the node to the result list.

Another approach is to use the two-list merge twice. That approach has the advantage that it could easily be adapted to be a variadic function taking any number of lists at a slight cost in efficiency.

Performance Testing

Results of time testing on two Linux boxes are shown below, demonstrating that this code runs measurably faster than the original.

First, here's the test harness code:

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>

/* 
 * the various implementations go here
 */

/* start at some number in (0,100) and increment by
 * some other number in (0,10) for count iterations
 * passed pointer is assumed to have count contiguous
 * nodes.
 */
clist *fill_random_list(int count, clist *curr) {
    clist *first = NULL, *last = NULL;
    assert(curr != NULL);
    int increment = rand() % 10;
    for (int n=rand() % 100 ; count; --count, ++curr) {
        curr->num = n;
        n += increment;
        curr->next = NULL;
        if (last == NULL) {
            first = last = curr;
        } else {
            last->next = curr;
            last = curr;
        }
    }
    return first;
}

// return true iff list is sorted
bool is_sorted(clist *list) 
{
    if (list == NULL) {
        return true;
    }
    int prev = list->num;
    for (list = list->next; list; list = list->next) {
        if (prev > list->num) {
            return false;
        }
        prev = list->num;
    }
    return true;
}

int main()
{
    const size_t list_size = 5000000;
    srand(time(NULL));
    clist *one = malloc(list_size * sizeof(clist));
    clist *two = malloc(list_size * sizeof(clist));
    clist *three = malloc(list_size * sizeof(clist));
    clist *big;
    struct {
        const char *name;
        clist* (*func)(clist*, clist*, clist*);
        double elapsed;
    } tests[] = {
        { "original", cmerge_orig, 0 },
        { "Edward", cmerge_edward, 0 },
        { "mdfst13", cmerge_mdfst13, 0 },
        { NULL, NULL, 0}
    };

    for (int iterations = 100; iterations; --iterations) {
        for (size_t i=0; tests[i].func; ++i) {
            fill_random_list(list_size, one);
            assert(is_sorted(one));
            fill_random_list(list_size, two);
            assert(is_sorted(two));
            fill_random_list(list_size, three);
            assert(is_sorted(three));
            clock_t start = clock();
            big = tests[i].func(one, two, three);
            tests[i].elapsed += (double)(clock() - start)/CLOCKS_PER_SEC;
            assert(is_sorted(big));
        }
    }
    // print results
    for (size_t i = 0; tests[i].func; ++i) {
        printf("%12s\t%.10f\t%f%% %s than %s\n", tests[i].name, tests[i].elapsed,
            100.0*fabs(tests[i].elapsed-tests[0].elapsed)/tests[0].elapsed, 
            (tests[i].elapsed > tests[0].elapsed ? "slower" : "faster"),
            tests[0].name
        );
    }
    free(one);
    free(two);
    free(three);
}

The code creates three sorted lists with random-ish values. It uses assert() to rather gracelessly bail out on error (either a supposedly sorted list isn't or out of memory) and the timing doesn't account for possible rollover, but it works well enough for this purpose.

Merging 3 lists, each 5,000,000 items, cumulative time for 100 iterations

x86_64, 8 core, 3.4GHz, gcc 5.3.1

    original    2.3338780000    0.000000% faster than original
      Edward    2.2184270000    4.946745% faster than original
     mdfst13    4.1236940000    76.688499% slower than original

ARM v7, 4 core, 900MHz, gcc 4.6.3

    original    57.1399730000   0.000000% faster than original
      Edward    53.4537210000   6.451267% faster than original
     mdfst13    63.4887120000   11.110854% slower than original

Compile command:

gcc -O2 -Wall -Wextra -pedantic -std=c99 mergetest.c -o mergetest

\$\endgroup\$
  • \$\begingroup\$ (Returning just because one list out of three is empty looks unwarranted.) \$\endgroup\$ – greybeard Jun 2 '16 at 7:09
  • \$\begingroup\$ @greybeard: The code above that sorts the list so that if it gets to that point and c1 is empty, all lists are empty, hence the exit. \$\endgroup\$ – Edward Jun 2 '16 at 10:23
  • \$\begingroup\$ Not sure what you don't like about the answer. Can you clarify? \$\endgroup\$ – Edward Jun 2 '16 at 15:46
  • \$\begingroup\$ (I habitually put in parenthesis parts of comments that are not related directly to the question and/or answer. The dislike was on level 2…) (Not sure :-/ I think I put the redundant c2 && in (!c2 || (c2 && c3->num < c2->num) (c1 dito) to an attempt to improve readability that doesn't work with me. The only language tag reading c, I guess I miss a swap macro - a nit, just as conditionally initialising curr & ret in the loop. That leaves the theme of the question being just don't know if it's efficient enough and pointers getting checked against NULL more than once per trip.) \$\endgroup\$ – greybeard Jun 2 '16 at 20:24
  • \$\begingroup\$ The redundant c2 && ... is for the benefit of clarity to human readers. Generated code is identical with it omitted, but I think the intent is slightly less clear. Also, performance info updated. \$\endgroup\$ – Edward Jun 3 '16 at 16:32
3
\$\begingroup\$

I already know how to merge two linked list, but I needed to code a function that'll merge three already sorted linked lists into one.

If I saw this as a requirement and had a function (say the one from this post)

static clist * cmerge2(clist *c1, clist *c2) {
    clist dummy_head = { 0, NULL };
    clist *tail = &dummy_head;

    while ( c1 && c2 ) {   
        clist **min = (c1->num <= c2->num) ? &c1 : &c2;
        clist *next = (*min)->next;
        tail = tail->next = *min;
        *min = next;
    }

    tail->next = c1 ? c1 : c2;

    return dummy_head.next;
}

that would merge two lists into one, I'd just do

clist *cmerge(clist *c1, clist *c2, clist *c3) {
    return cmerge2(cmerge2(c1, c2), c3);
}

Unless performance is at an absolute premium, this is going to be good enough. And I'm not sure that it's necessarily worse. Note that your code has to check a number of edge cases on every iteration even though they only change status once. You also have to do three comparisons for every node. This code only does one comparison per node (although it does does process c1 and c2 twice, so two comparisons for their nodes). The simpler code might actually do fewer tests, as it has to check fewer situations. You should time it on some standard inputs to see.

This code is much shorter and easier to maintain. It's also better tested, as there are many existing tests for merging two lists.

\$\endgroup\$
  • \$\begingroup\$ Now if you would reduce the check against NULL to just one pointer per trip… (A "3-list variant" of this was my second thought seeing Edward's code. It would be interesting to peek at the code with current compilers, especially (architectural) register use.) \$\endgroup\$ – greybeard Jun 3 '16 at 15:25
  • \$\begingroup\$ I added this implementation to the timing tests in my answer. It only tests one specific scenario but gives a rough indication of relative performance on two different architectures. \$\endgroup\$ – Edward Jun 3 '16 at 21:30
1
\$\begingroup\$

For concise code you'd better to use min priority queue. Note that specific implementation of priority queue for three items is rather simple (for example, binary heap based on array containing three pairs (L=list number; V=current value (num field) of this list)
Pseudocode:

Add elements with the first values of all lists to PQ
At each stage extract from PQ item with minimal V
Add this value to the new list
Insert into PQ item with the same L and with next value
(If next field of current list is nil (end), add pair with MaxInt value)
If PQ.ExtractMin returns MaxInt - stop the process, all lists are exhausted
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.