根据上面的帖子优化了一版
从 5*200*25k 个 distance 用 10s 了
到 5*200*200k 个 distance 用 15s

之后一个点的全量数据对比 (5*1M ）个 distance 在 20s 内能搞定，考虑用队列离线算~

@0o0o0o0
@tzm41
@yuruizhe
@also24

昨天想了一个思路，准备动手去做
还是空间换时间，而且要利用好“diff < n”这个条件去筛。

128bit diff <=3 那么把 128bit 分成四段，至少能有一段是完全一致的。

1M 个 分成 4M 段 每段按照哈希值存到一个桶里面，会有 2^32 个桶，每个桶基本不会有冲突。
之后每个 hash 找近邻的时候只需要找 4 段对应的 hash 取个并集，算一下这部分就好。

@vchar2ex 我已经找到实现了，我的问题不是如何算 hash，而是如何降低复杂度快速去找。

@yuruizhe 没毛病，空间换时间。
你空间给小了和 1-count 预处理效果差不多
给大了……你给不起。。
128bit 不小的。。。

@imn1 更正一下，FFI

我的场景这个判重已经足够了，稍后算一下几个 hash 算法的 dist 的权重，做一个新的阈值。

@imn1 世界上最好的语言对 OpenCV 的封装不好。。。
当然 php74 之后就有 ffp 了，拭目以待吧~

@also24 我直接硬数的，反正 n^2 的算法里面的 n 次 bit 计算怎么搞都不差太多……
但是优点确实是能省好多 distance
毛估，distance 计算数量减少百分之 90，但是多算了 n 次绝对值相减，里外里效率提升 50%这样

ext_gmp 的 distance 已经很省时间了

@lizytalk lsh 是分段的，会降低敏感度，因为图片无法分段。

@imn1 处理的已经是针对 hash，而不是图片了。

踩了一个语言的坑，有一些代码写的还不够 dry，目前已经优化到计算
5*200*25k 个 distance 用 10s 了。

@also24 又做了一个优化，比较 distance 之前算下 bit count 的差值，超过阈值就不算了。
这样又可以快一点点。

@imn1 我尝试了一下算 hash dup 的算力。
必要的缓存优化我做了，hash 全部读取到内存没有 io 问题。

计算 5(个算法）*200 个 src*10k 个目标的汉明距离大概需要 1 分钟
i5 [email protected] 睿频到 2.2 的单核

如果目标上升到 1M(100 倍），5*200 这组需要的时间将会上升到 100 分钟

当然换一个好点的 cpu 提升 10 倍也就顶天了，10 分钟算 200 个（因为前面的 target 少）

1M=200*5000, 算均值是 5 分钟一批，需要 25000 分钟，大概 400 个小时。

@imn1 非常感谢这么详细的回答！

其实我还没开始计算百万级的汉明距离(o(n^2))，因为汉明码还没有预处理完——数据在 nas 上得先下载下来再算。
好吧，刚才打点看了一下，不是 io 的问题，就是 hash 算的慢（算 hash 呢，还没比呢）

服务器是一台 thinkpad 的，i5 4200u(1.6G~2.6G)
单线程跑满 hash 一个 100k 的图片大概需要 200ms （单线程），其他开销<5ms(数据库，网络，本地临时文件写）

算法（采用了 ah,dh, PercepiahHash，另外一个包的 ph 和 dh ），都是 php 的，算了 5 个 hash 。

我不太清楚其他语言算这个是不是能快一些，反正服务器也比较渣，之后跑判重肯定换个环境了，只是数据都在一个工程比较好管理。


等 hash 跑完我先用 dist=0 （完全匹配，基于数据库算下增量数据）简单提供一个服务，之后再慢慢跑 dist=1,2,3 的情况。

毛菇如果把历史数据都读取到内存当中算一趟的时间应该在可接受的范围内吧……

@also24 嗯 可以按照 1 的个数将分组缩小 128/dist 倍，计算量也减少这么多。
@liukangxu 感谢！

@all

算了 25k of 720k 的摘要 hash，用 dhash 就能找到约 0.5k 的 dup，相当于汉明距离=0

这个已经足够 make sense 了~

汉明距离 1+的以后慢慢算，可以结合几种不同的 hash 去重~

@ifzzzh
@liukangxu
我看下这俩算法，不过我估计学不会……

@newdongyuwei 已经在跑 p,dhash 了

确实 dhash 好一些，还挑了几个别的算法。
全量跑一遍 1M*5 个 hash 算法得两三天(主要是资源在 nas 上 io 慢机器也不快）


@momocraft

排序肯定不行，排序相当于只有前缀分组，会漏掉特别多
@ipwx
对，有这玩意么
其实细想一下，汉明距离就是 n-dimission 的距离，不过 nlgn 的算法仅限于 2 维来着？

@douglas1997 128bit 已经是图像指纹了，不是两个 1M 比指纹，是 1M 个 128bit 的 hash 比距离

自问自答：

user.daz 不指定类型就完事儿了。。
但是代码还是很丑，只能算是能跑通。。

@xupefei
@ccpp132

主要考虑到在 ahk 脚本访问共享内存 /socket 太复杂了。。。