我有一个整数数组(可能有数千个元素),例如
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*i
、3*i+1
等,我建议使用步长为 3,然后像现在这样进行p[i]
、p[i+1]
,而不是像现在这样进行乘法计算。这通常更有效,并且在维护时更直观。 - Nathan Ernst