排序后的数组和唯一数组

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编写脚本。但这对于大文件来说太慢了（400个文件8分钟太长了）因此，我决定用C编写此批处理。一天后，我仍然没有完成它。

我已经看过排序数组（gnu C sorted arrays）之类的东西我想检查＃1和＃2之间的字符串是否已经在字符串数组中，如果没有，则添加它。我认为会有明显的功能，例如在预先排序的数组中添加字符串（并保持其排序），和/或在预先排序的数组中添加字符串如果尚未在。

我发现的唯一解决方案是

1. 使用lsearch（）
2. 使用bsearch（），如果找不到，将其添加并重新排序array（）

第二个函数需要使用年龄（qsort（）太长），而第一个函数在成千上万的元素之后变得太长（因为它们未排序）。

您知道我可以在哪里/可以做什么/可以使用哪个库吗？我想我不是世界上唯一想在不存在的情况下将字符串放入预先排序的字符串数组中（并保持其排序）的人！ ;）

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正确注释，只需继续直接使用该链接列表/映射。）