0

我有一个按行长降序排列的大量字符串文本文件。我想将整个东西加载到一个字符串数组中，对每个元素执行 Levenshtein，创建一个组 UUID 并将其放入一个数组中。所以第二个数组将是一个哈希表，其中键是前一个字符串的内存地址，值是 UUID。

我想在迭代字符串时执行指针运算以获得最佳性能。

在迭代地进行 levenshtein ga-zillions 之后，我想填充另一个文本文件，其内容很简单，即组的 UUID、冒号和原始文本文件中的行。

我有 wikibooks 中的 levenshtein 算法：

template<class T> unsigned int levenshtein_distance(const T &s1, const T & s2) {
    const size_t len1 = s1.size(), len2 = s2.size();
    vector<unsigned int> col(len2+1), prevCol(len2+1);

    for (unsigned int i = 0; i < prevCol.size(); i++)
            prevCol[i] = i;
    for (unsigned int i = 0; i < len1; i++) {
            col[0] = i+1;
            for (unsigned int j = 0; j < len2; j++)
                    col[j+1] = min( min( 1 + col[j], 1 + prevCol[1 + j]),
                                                            prevCol[j] + (s1[i]==s2[j] ? 0 : 1) );
            col.swap(prevCol);
    }
    return prevCol[len2];
}

我已经完成了一些 C++、一些 C、大量的 Obj-C。我使用的是 Windows 7。您如何建议我这样做？什么样的字符串数组？如何转换文本文件中的文本字符串以供提供的函数使用？

我基本上是在寻找尽可能多的技巧，因为字符串让我在 C++ 中感到困惑。哦，C++ 也是如此！

谢谢

4

1 回答 1

0

对于纯粹的访问时间，您将很难击败完整的内存读取，然后通过单程对其进行索引，构建一个指针列表并在遇到的每个 CR/LF 处硬写一个空终止符。行号将是您存储所有这些指针的容器的索引，为此我可能会使用std::deque<>.

boost:: 伙计们可能会更进一步，但为了快速访问，它很难击败一大堆内存和一大堆索引它的指针。当然，这整个事情都假设你可以把它放进内存。如果你不能，这会变得更加复杂，但如果你可以（并且可以假设你总是可以） malloc/walk-and-terminate/push-ptr-into-deque 看起来很干净。为了真正让它冒烟，我还会用指针存储每个字符串的长度，所以你std::deque<>会是struct { char* ptr; size_t len; }. 这样做会消除大量不需要的 strlen() 等。它还将消除对任何内容进行空终止的需要。

于 2012-09-15T18:41:04.560 回答