有没有一种最快的方法来计算数组中的对象重复而不是HashTable?
我会努力尽可能清楚。我已经实现了我的解决方案并且它可以工作,我只需要知道是否最好使用其他数据结构而不是哈希表
这是一个大学问题,但我已经提交给老师并且它有效,我只是想看看是否有人会以不同方式做到这一点。
所以,这是问题所在:
给定图像(PPM 3,所有数据以RGB格式存储在ASCII中)
例如
P3
# The P3 means colors are in ASCII, then 3 columns and 2 rows,
# then 255 for max color, then RGB triplets
3 2
255
255 0 0 0 255 0 0 0 255
255 255 0 255 255 255 0 0 0
我需要将每个像素除以给定的常数,这将是2的幂(2,4,8 ............ 64,128)
c= 32;
Pixel2(255/c,255/c,255/c) = Pixel2(7,7,7)
然后,我需要将所有像素转换为给定宽度的补丁,补丁将累积其包含的像素的RGB值
例如
w=3; imageW = 10; imageH=10;
Patch[0].r = Pixel[0].r + Pixel[1].r + Pixel[2].r +
Pixel[10].r + Pixel[11].r + Pixel[12].r +
Pixel[20].r + Pixel[21].r + Pixel[22].r;
Patch[0].g = Same for g component;
Patch[0].b = Same for b component;
Patch[1].r = Pixel[1].r + Pixel[2].r + Pixel[3].r +
Pixel[11].r + Pixel[12].r + Pixel[13].r +
Pixel[21].r + Pixel[22].r + Pixel[23].r;
etc…
然后,我需要计算图像中每个补丁的重复次数。
所以,我所做的就是我有Image类,它从文件(ifstream)读取图像,还有Pixel类,它有r,g,b和nAparations组件。我读取了像素,将它们除以给定的常数,然后得到补丁,其中包含了包含像素的值。
在此之后,我的Image类中有一个数据向量,它是一个Patches对象数组
例如
data = [Patch0{r comp,g comp, b comp, 1 parition}, Patch1{r comp,g comp, b comp, 1 parition} …..];
现在,我已经完成了它使用哈希表,插入每个修补程序,如果它已经插入,只需更新它的nAppearances组件,如果没有,插入它。
插入完所有内容后,返回一个包含哈希表中所有元素的向量。
这个向量,每个Patch只有一个发生点,而它的nAppearances组件将汇总每个Patch出现在图像中的次数。
还有其他方法吗?或哈希表是最好的方法?
另外,你会使用什么样的哈希函数?目前我正在使用
hash = patch.r * 1 + patch.g *2 + patch.b*3;
tableSize = maximun number of patches (assuming no one repeats)
insert into table[hash%tableSize];
哈希表允许冲突,表中的每个位置都有一个元素列表。
对不起,如果它很大,只是想清楚。如果我的英语不够好,也很抱歉!
谢谢。
没有找到相关结果
已邀请:
2 个回复
队辅坟阮阶
哈希的替代方案: 使用带有RGB 24位数字的std :: set,或使用rgb数字,但使用24位数字进行比较。这样你就可以计算重复数量。它没有哈希那么快。 顺便说一句,如果你能负担得起,2 ^ 24只有16M,如果你使用了一个使用2MB的bitset。您可以运行所有颜色,为每种颜色设置“标志”,然后以这种方式计算重复数。
室邢