C ANSI, отсортированные массивы и уникальные массивы

Question

Вот моя проблема. Я написал скрипт на python, который сканирует файл и извлекает из него строки в большом массиве. Я делаю что-то вроде:

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

Мне потребовался 1 час, чтобы сделать скрипт на python. Но это слишком медленно для больших файлов (8 минут для 400 файлов это слишком долго) Поэтому я решил написать эту партию на C. Через один день я все еще не закончил ее.

Я уже смотрел на такие вещи, как отсортированные массивы ( сортированные массивы GNU C ) Я хотел бы проверить, есть ли строка между № 1 и № 2 уже в массиве строк, и если нет, добавьте ее. Я думал, что будут очевидные функции, такие как добавление строки в предварительно отсортированный массив (и сохранение ее отсортированной) и / или добавление строки в предварительно отсортированный массив , если ее еще нет в .

Единственные решения, которые я нашел, это

1. используйте lsearch ()
2. используйте bsearch (), и, если не найден, добавьте его и пересортируйте массив ()

Вторая функция принимает возраст (qsort () слишком длинная), а первая становится слишком длинной после тысячи элементов (потому что они не отсортированы).

Вы знаете, где я мог бы посмотреть / что я мог сделать / какую библиотеку я мог бы использовать? Я предполагаю, что я не единственный на свете, кто хочет поместить строку в предварительно отсортированный строковый массив, только если его нет (и сохранить его отсортированным)! ;)

Большое спасибо

Olivier

Примечание: я хочу остаться C ANSI

Answer 1

Я не знаю библиотеки для Ansi C, чтобы сделать это, но это не так сложно реализовать самостоятельно. Вы хотите написать «список отсортированных массивов» для строк. Я кратко расскажу, как это будет выглядеть:

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;
}

Это даст вам сложность O (log (n)) для сортированной вставки с двойной проверкой. Если вы хотите еще больше улучшить время выполнения, вы можете использовать более совершенные структуры данных в качестве хеш-карт.

Answer 2

Используйте связанный список строк при чтении файла, чтобы вы могли вставить текущую строку вместо необходимости сдвигать / сортировать строки для каждой вставки.

Есть несколько способов, которыми вы могли бы оптимизировать поиск / вставку (например, используя индексы, хеш-карты, triemaps и т. Д.), Но сложно сказать, какой из них подходит для вашего использования, и я не буду пытаться перечислять / объясни им все.

Как только вы закончите (и узнаете, какой размер фактически необходим вашему массиву), вы можете выделить необходимую память и скопировать строковые указатели из связанного списка в выделенный массив, освободив узлы списка в процессе.

(Или, как правильно заметил pmg, просто продолжайте напрямую использовать этот связанный список / карту.)