sorted arrays and unique arrays

Question

I wrote a script in python that scans a file and extract strings from it in a big array. I do something like:

while (delimiter #1 found)
search for the delimiter #2
if the string between #1 and #2 is not in the "final array", add it.

It took me 1 hour to make the script in python. But it's just too slow for big files (8 minutes for 400 files is far too long) So I decided to write this batch in C. After one day I still haven't finished it.

I've already looked at things like sorted arrays (gnu C sorted arrays) I'd like to check whether the string betwen #1 and #2 is already in an array of strings, and if not, add it. I thought there would be obvious functions like adding a string in a pre-sorted array (and keep it sorted), and / or adding a string in a pre-sorted array if it's not already in.

The only solutions I've found is

use lsearch()
use bsearch (), and if not found, add it and re-sort the array()

The second function takes ages ( qsort() is too long) and the first one is getting too long after thousand of elements (because they're not sorted).

Do you know where I could look / what I could do / which library I could use? I guess I'm not the only one on earth who wants to put a string in a pre-sorted string array only if it's not present (and keep it sorted)! ;)

I suspect the difference between Python and C won't be that great. The biggest time spending is done for reading the files — pmg
– pmg, Commented Mar 31, 2011 at 11:50
Perhaps your problem is that your Python code is sub-optimal. — David Heffernan
– David Heffernan, Commented Mar 31, 2011 at 11:50
@pmg. Wrong. The biggest time is taken when checking "if not string in array". Anyway I've solved the problem : I just use the C parser to output the items found (very simple printf) then I pipe it to "uniq" then "sort". I came from "2m31.596s" to "0m2.497s", almost ten times quicker. Thank you very much for your answer. — Olivier Pons
– Olivier Pons, Commented Mar 31, 2011 at 12:19
How long does parsing in Python, outputting to uniq then sort take? — pmg
– pmg, Commented Mar 31, 2011 at 12:23
time ./scriptpython = Python doing the whole stuff (parsing, sorting, uniq) = 2m31.596s. time ./a.exe > tt = C program parsing = 0m2.170s. time ./a.exe | uniq | sort > tt = whole stuff = 0m2.497s — Olivier Pons
– Olivier Pons, Commented Mar 31, 2011 at 12:28

Thalur · Accepted Answer · 2011-03-31 12:09:58Z

1

I don't know of a library for Ansi C to do this, but it's not that hard to implement yourself. You want to write a "sorted array list" for strings. I'll give a short idea what this would be looking like:

struct SortedArrayList {
    int size;
    int capacity;
    char **element;
}

// returns: >= 0 if the element in contained, < 0 (-insertPos-1) if not
int GetIndexPos(char *text)
{
    if (size == 0) return -1;

    // Binary search through the list of strings
    int left = 0, right = size-1, center;
    int cmp;

    do {
        center = (left+right) / 2;
        cmp = strcmp(element[center],text);
        if (cmp == 0) return center; // found
        if (cmp < 0) left = center+1; // continue right
        else right = center-1; // continue left
    } while (left <= right);
    return -left-1; // not found, return insert position
}

void Add(char *text)
{
    int pos = GetIndexPos(text);
    if (pos >= 0) return; // already present
    pos = -pos-1

    // Expand the array
    size++;
    if (size >= capacity)
    {
        capacity *= 2;
        element = (char**)realloc(element,capacity*sizeof(char*));
    }

    // Add the element at the correct position
    if (pos < size-1) memmove(&element[pos+1],&element[pos],sizeof(char*)*(size-pos-1));
    element[pos] = text;
}

This will give you complexity of O(log(n)) for sorted insertion with duplicate check. If you want to improve the runtime some more, you can use better data structures as hash maps.

edited Mar 31, 2011 at 12:09

answered Mar 31, 2011 at 12:03

Thalur

1,1639 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Olivier Pons Over a year ago

I answered in a comment from my question. Thanks you very much for your answer.

DevSolar · Accepted Answer · 2011-03-31 12:06:58Z

1

Use a linked list of strings while reading the file, so you can insert the current string instead of having to shift / sort the strings for each insert.

There are several ways in which you could optimize the search / insertion (like using indexes, hashmaps, triemaps or whatever), but it's hard to say which would be appropriate for your use, and I won't try to list / explain them all.

Once you are done (and know the size your array actually needs), you can allocate the memory needed, and copy the string pointers from the linked list into the allocated array, releasing the list nodes in the process.

(Or, as pmg correctly commented, simply continue using that linked list / map directly.)

edited Mar 31, 2011 at 12:06

answered Mar 31, 2011 at 12:00

DevSolar

71k22 gold badges141 silver badges217 bronze badges

2 Comments

pmg Over a year ago

+1: maybe he could live without the array and use the linked list for whatever he wants

Olivier Pons Over a year ago

I answered in a comment from my question. Thanks again for your answer.

Collectives™ on Stack Overflow

sorted arrays and unique arrays

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related