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

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

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)有没有比这里概述的更好的算法/方法？

最佳答案

同意 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);

然后 i 中的每个 freqs[t] 都使得 (p[i], p[i+1], p[i+2]) 等于 t 。

关于c++ - 计算 C 数组中三元组的频率以进行索引，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6442063/