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

3

我有一个整数数组(可能有数千个元素),例如

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,除非它是头文件) 2)有没有比string更好的密钥?我考虑使用数字来提高空间效率,例如5^a * 3^b * 2^c,但担心超过数值限制 3)是否有比这里概述的更好的算法/方法?

确保你正确检查你的边界。i<24*3 是一种代码异味。你应该做类似这样的事情:const size_t p_size = sizeof(p) / sizeof(*p); for (size_t i = 0; i < p_size - 3; ++i ) { ... }。此外,与其使用 3*i3*i+1 等,我建议使用步长为 3,然后像现在这样进行 p[i]p[i+1],而不是像现在这样进行乘法计算。这通常更有效,并且在维护时更直观。 - Nathan Ernst
好的观点,虽然硬编码的24*3只是上面快速而肮脏示例的产物,在最终代码中它不会像那样。 - bosmacs
3个回答

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

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


1
时间复杂度看起来OK。使用 std::map 看起来OK。至于键,对我来说,一个带有3个 intstruct 比一个 string 更合适。但我认为这并不重要。

0

我肯定会将键更改为一个简单的3个整数结构体;元组也可能是一个不错的想法。这应该会带来实质性的性能提升,因为它会消除字符串的任何潜在堆分配和与字符串流相关的开销。

此外,由于您有成千上万的元素且没有顺序约束,使用 unordered_map 可能是更好的容器选择。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接