比起地图，有更好的选择吗？

Question

我正在编写一个C++程序，用于处理长流的符号，并需要存储信息以供进一步分析，在流中出现某个长度的符号序列的位置。例如，在二进制流中：

100110010101

我有一个长度为6的序列如下：

• 从0开始的100110
• 从1开始的001100
• 从2开始的011001
• 等等。

我需要存储的是所有位置的向量，我可以在其中找到一个确定的序列。因此结果应该是类似哈希表的表格，看起来像这样：

序列/ 位置

10010101 | 1 13 147 515

01011011 | 67 212 314 571

00101010 | 2 32 148 322 384 419 455

等等。

现在，我发现将字符串映射到整数很慢，因此由于我提前知道流中的符号情况，我可以利用它将这些固定长度的序列映射到整数。

下一步是创建一个映射，将这些“表示整数”映射到表中相应的索引，我会在其中添加这个序列的下一个出现位置。然而，这很慢，比我能承受的要慢得多。我尝试了std和boost库的有序和无序映射，都没有足够的效率。我测试了一下，这个映射是真正的瓶颈。

这里是伪代码循环：

for (int i=seqleng-1;i<stream.size();i++) {
    //compute characteristic value for the sequence by adding one symbol
    charval*=symb_count;
    charval+=sdata[j][i]-'0';
    //sampspacesize is number off all possible sequence with this symbol count and this length
    charval%=sampspacesize;
    map<uint64,uint64>::iterator &it=map.find(charval);
    //if index exists, add starting position of the sequence to the table
    if (it!=map.end()) {
        (table[it->second].add(i-seqleng+1);
    }
    //if current sequence is found for the first time, extend the table and add the index
    else {
        table.add_row();
        map[charval]=table.last_index;
        table[table.last_index].add(i-seqleng+1)
    }
}

所以问题是，我能否使用比地图更好的东西来记录表中对应索引的记录，或者这是最好的方法了吗？

注意：我知道这里有一个快速的方法，那就是创建足够大的存储空间以容纳每个可能的符号序列（意味着如果我有长度为10且有4个符号的序列，则我保留4 ^ 10个插槽并可以省略映射），但我将需要使用长度和符号数量，这将导致保留远超计算机容量的内存量。但实际使用的插槽数不会超过1亿（这由最大流长度保证），这可以很好地存储在计算机中。

如有不清楚的地方，请随时提问，这是我在这里的第一个大问题，所以我缺乏表达自己的经验，以便让其他人理解。

- TStancek

---

你想将序列映射到位置，还是将位置映射到序列？ - Richard Hodges

你似乎有一个 std::map<sequence, tableIndex> map 和 MyVector<MyVector<Position>>。为什么不直接使用 std::map<sequence, std::vector<Position>> map ？ - Jarod42

@Jarod42，它甚至变得更慢了。在地图中使用更复杂的结构，加载循环就会变得更慢。我一直在努力将其简化为一次只加载一个符号并将整数映射到整数，但是从这里开始，我无法提高速度，因为这些是最简单的数据类型，而我所知道的唯一方法就是使用map。 - TStancek

如果您只使用符号 1 和 0，那么为什么不将其存储为 unordered_map 在例如 uint_8t 上，其中您的键是对应于二进制展开式的数字？在读取源字符串时，您只需要逐个字符地读取，并随着读取而进行左移。 - donkopotamus

auto p = map.insert({charval, table.last_index}); if (p.second) { table.add_row(); } table[p.first->second].add(i-seqleng+1);。请参阅map::insert的返回值。 - Jarod42

Answer 1

预分配空间的无序映射通常是存储任何稀疏数据的最快方式。

考虑到std::string具有SSO，我认为像这样的东西几乎是最快的:

(我使用了一个unordered_multimap，但我可能误解了要求)

#include <unordered_map>
#include <string>
#include <iostream>

using sequence = std::string; /// @todo - perhaps replace with something faster if necessary

using sequence_position_map = std::unordered_multimap<sequence, std::size_t>;


int main()
{
    auto constexpr sequence_size = std::size_t(6);
    sequence_position_map sequences;
    std::string input = "11000111010110100011110110111000001111010101010101111010";

    if (sequence_size <= input.size()) {
        sequences.reserve(input.size() - sequence_size);

        auto first = std::size_t(0);
        auto last = input.size();

        while (first + sequence_size < last) {
            sequences.emplace(input.substr(first, sequence_size), first);
            ++first;
        }
    }

    std::cout << "results:\n";
    auto first = sequences.begin();
    auto last = sequences.end();
    while(first != last) {
        auto range = sequences.equal_range(first->first);

        std::cout << "sequence: " << first->first;
        std::cout << " at positions: ";
        const char* sep = "";
        while (first != range.second) {
            std::cout << sep << first->second;
            sep = ", ";
            ++first;
        }
        std::cout << "\n";
    }
}

输出：

results:
sequence: 010101 at positions: 38, 40, 42, 44
sequence: 000011 at positions: 30
sequence: 000001 at positions: 29
sequence: 110000 at positions: 27
sequence: 011100 at positions: 25
sequence: 101110 at positions: 24
sequence: 010111 at positions: 46
sequence: 110111 at positions: 23
sequence: 011011 at positions: 22
sequence: 111011 at positions: 19
sequence: 111000 at positions: 26
sequence: 111101 at positions: 18, 34, 49
sequence: 011110 at positions: 17, 33, 48
sequence: 001111 at positions: 16, 32
sequence: 110110 at positions: 20
sequence: 101010 at positions: 37, 39, 41, 43
sequence: 010001 at positions: 13
sequence: 101000 at positions: 12
sequence: 101111 at positions: 47
sequence: 110100 at positions: 11
sequence: 011010 at positions: 10
sequence: 101101 at positions: 9, 21
sequence: 010110 at positions: 8
sequence: 101011 at positions: 7, 45
sequence: 111010 at positions: 5, 35
sequence: 011101 at positions: 4
sequence: 001110 at positions: 3
sequence: 100000 at positions: 28
sequence: 000111 at positions: 2, 15, 31
sequence: 100011 at positions: 1, 14
sequence: 110001 at positions: 0
sequence: 110101 at positions: 6, 36

- Richard Hodges

---

谢谢你的建议，我会尝试一下，看看能否加速。 - TStancek

抱歉，我犯了一个错误。速度大约相同，我忘记使用multimap，只使用了map。 - TStancek

@TStancek，我们可以尝试将字符串转换为位，这将使比较速度稍微更快。 - Richard Hodges

我已经做了，但不是位(bit)，而是整数(int)。问题是我认为在有序映射中，它比无序映射慢得多，在这种情况下，它会一直自平衡。我能否强制它创建一个具有固定深度的平衡树，以便每个存储元素都不会移动？ - TStancek

@TStancek 我之前进行了一些测试，比较了无序映射和有序映射的性能。结果是可以预测的，并且非常支持无序映射。 https://dev59.com/cloV5IYBdhLWcg3wVNeZ - Richard Hodges

Answer 2

在评论和答案中收到了许多建议后，我测试了其中的大部分，并选择了最快的可能性，减少了由映射引起的瓶颈，使其几乎与没有“map”时运行时间相同（但会产生不正确的数据，因此需要找到可以将其减少到的最小速度）。

这是通过将unordered_map<uint64,uint>和vector<vector<uint>>替换为unordered_map<uint64, vector<uint> >来实现的，更确切地说是使用boost::unordered_map。我还使用unord_map<string,vector<uint>>进行了测试，令我惊讶的是它并没有我所预期的那么慢。但是它确实慢一些。

此外，可能是由于ordered_map将节点移动以保持其内部结构的平衡，ord_map<uint64, vector<uint>>比ord_map<uint64,uint>和vector<vector<uint>>慢了一些。但由于unord_map在计算过程中不移动其内部数据，似乎它是可以使用的最快配置。

- TStancek