[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Judy arrays much faster than standard sort?
From: |
Leszek Dubiel |
Subject: |
Judy arrays much faster than standard sort? |
Date: |
Sat, 16 Jan 2010 19:08:51 +0100 |
User-agent: |
Thunderbird 2.0.0.23 (X11/20090817) |
I have found that Judy arrays are faster than standard "sort" program
about 10 times. This is a little bit strange, because I expected sort to
be fastest tool ever.
Heres is my session:
address@hidden wc input
1000000 1000000 5659335 input
address@hidden time ./judy < input > output_judy
The JudySL array used 360076 bytes of memory
real 0m0.603s
user 0m0.528s
sys 0m0.028s
address@hidden time sort < input > output_sort
real 0m6.026s
user 0m5.912s
sys 0m0.072s
address@hidden diff output_*
Judy arrays are described at http://judy.sourceforge.net/, and program
"judy" is compiled from example shown on that site:
#include <stdio.h>
#include <Judy.h>
#define MAXLINE 1000000 // max string (line) length
uint8_t Index[MAXLINE]; // string to insert
int // Usage: JudySort < file_to_sort
main()
{
Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
PWord_t PValue; // Judy array element.
Word_t Bytes; // size of JudySL array.
while (fgets(Index, MAXLINE, stdin) != (char *)NULL)
{
JSLI(PValue, PJArray, Index); // store string into array
if (PValue == PJERR) // if out of memory?
{ // so do something
printf("Malloc failed -- get more ram\n");
exit(1);
}
++(*PValue); // count instances of string
}
Index[0] = '\0'; // start with smallest string.
JSLF(PValue, PJArray, Index); // get first string
while (PValue != NULL)
{
while ((*PValue)--) // print duplicates
printf("%s", Index);
JSLN(PValue, PJArray, Index); // get next string
}
JSLFA(Bytes, PJArray); // free array
fprintf(stderr, "The JudySL array used %lu bytes of memory\n", Bytes);
return (0);
}
- Judy arrays much faster than standard sort?,
Leszek Dubiel <=