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

1. use lsearch()
2. 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)! ;)

Answer 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.