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
if (!ret)
- have a localclist b4 = { 0 }
, initialisecurr
to it and returnb4.next
. (And don't do as I did: don't use funny names. The only excuse for abbreviations likecurr
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