排序数组和唯一数组

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 ()，如果找不到，添加它并重新排序 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

在读取文件时使用字符串链接列表，因此您可以插入当前字符串，而不必为每次插入移动/排序字符串。

有多种方法可以优化搜索/插入（例如使用索引、哈希图、三元图等），但很难说哪种方法适合您的使用，我不会尝试列出/解释所有这些方法。

完成后（并知道数组实际需要的大小），您可以分配所需的内存，并将字符串指针从链表复制到分配的数组中，释放过程中的列表节点。

（或者，正如 pmg 正确评论的那样，只需继续直接使用该链表/映射即可。）