有没有一种最快的方法来计算数组中的对象重复而不是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件事 第一:如果要打哈希颜色: 如果R,G和B是从00到FF的颜色,最简单的事情就是创建一个24位的散列函数,即RRGGBB,然后用一些与散列表大小相对应的素数来修改它。你的哈希表大小是多少?这是素数吗? 例如,65536将是一个非常差的哈希表大小选择。 65539会好的。 unsigned int colornum(unsigned int red,unsigned int green,unsigned int blue) {    返回(红色<< 16 |绿色<< 8 |蓝色); } 哈希只是
colornum(r,g,b) % hashTableSize;
哈希的替代方案: 使用带有RGB 24位数字的std :: set,或使用rgb数字,但使用24位数字进行比较。这样你就可以计算重复数量。它没有哈希那么快。 顺便说一句,如果你能负担得起,2 ^ 24只有16M,如果你使用了一个使用2MB的bitset。您可以运行所有颜色,为每种颜色设置“标志”,然后以这种方式计算重复数。     
使用@CashCow哈希函数我已经获得了相当快的速度。 unsigned int colornum(unsigned int red,unsigned int green,unsigned int blue){return(red<< 16 | green<< 8 | blue); } 哈希只是colornum(r,g,b)%hashTableSize; 问题是,我需要计算许多图像的补丁重复次数(一次一个),并且它们可以变化很大(一个可能只有81个补丁,10x10图像,其他可能是1024x1024,最多不超过100万个补丁,如果所有都是不同的..) 所以我在为每个图像调整hashTableSize(colornum(r,g,b)%hashTableSize)时遇到了问题,因为非常小的图像的大数字不是最佳的,相反会导致很多碰撞...... 我还研究了其他着名的快速哈希函数,如murmurhash2,但我不知道如何正确实现它们。 (我是否仍然需要对他们返回的unsigned int执行%hashtableSize?因为如果它是肯定的那么我认为它们不应该比@CashCow更快,因为我做了很少的操作) 如果它有任何迹象,就在此之后,我将需要检索补丁数组并对其进行排序(因为我需要比较它们并找出差异,据我所知,最快的方法是比较两个对象数组它首先让它们排序正确??)所以如果你知道任何方法可以快速计算重复次数,并且让我以后检索它已经排序说出来。 我在想一个平衡的树可能会做的伎俩,它的渐近最差的查找和插入,但我摆脱了根本不同大小的图像的问题,我也能够检索它们排序的trasversal Inorder (不知道这是英文的名字..)。 任何有关这方面的想法都会被欣赏。再次感谢!     

要回复问题请先登录注册