c++ - 计算 C 数组中三元组的频率以进行索引

Question

我有一个整数数组(可能有数千个)，比如

int p[] = {0, 0, 0, 1, 0, 1, 2, 0, 2, 1, 0, 1, 0, 0, 0, 3, 0, 3, 5, 1, 7, ...

我想从中为每个唯一的三元组生成一组索引；对于上面的列表，类似于:

0, 1, 2, 1, 0, 3, 4, ...

我已经编写了一个简单的 C++ 实现(尽管普通的 C 或 Obj-C 实现也可以做得一样好或更好)，但我确信还有改进的余地:

for (int i = 0; i < 24*3; i++) {
    std::ostringstream sstr;
    sstr << p[3*i] << "," << p[3*i + 1] << "," << p[3*i + 2];
    freq[sstr.str()] += 1;
}

for (auto i = freq.begin(); i != freq.end(); i++) {
    std::cout << i->first << " => " << i->second << std::endl;
}

这只是计算每个三元组的频率，但可以简单地调整以分配所需的索引。我的问题是，如何提高时间/空间效率(请记住运行时目标是移动设备)？具体来说，

1) 为此，有什么数据结构比 std::map 更好？我想避免引入新的依赖项(例如 boost，除非它是仅 header )2) 有没有比 string 更好用的 key ？我考虑过使用数字来提高空间效率，例如 5^a * 3^b * 2^c，但担心超出数字限制3) 是否有比此处概述的算法/方法更好的算法/方法？

Answer 1

同意 Armen 的观点，这通常没问题。我可能会制作一个以三元组作为键并以一组索引作为值的映射:

typedef std::set<size_t> index_set;
typedef std::tuple<int,int,int> triple;
typedef std::map<triple, index_set> frequency_map;

然后:

const auto t = std::make_tuple(p[i], p[i+1], p[i+2]);
freqs[t].insert(i);

那么 freqs[t] 中的每个 i 都是 (p[i], p[i+1], p[i+2] ) 等于 t。