起：

我有一大串(1024^2)三元組稱(chēng)為ori，其中很多是需要合并的（如果只是正負(fù)號(hào)和排列順序不同）。需要得到合并后的三元組列表

承：

如果用一般算法，就是新建一個(gè)list，將ori中的三元組一個(gè)一個(gè)加進(jìn)去，每一次加進(jìn)去，就要遍歷list中所有三元組，能合并的合并。

這樣做顯然會(huì)很慢，在我的機(jī)子上跑了90s。

轉(zhuǎn)：

如果三元組按大小排列是(a,b,c)，想到用a作為hash下標(biāo)。這樣判斷融合的時(shí)候就只要hash到a下標(biāo)，然后解決沖突嘗試融合：

沖突解決，一開(kāi)始我實(shí)現(xiàn)是最簡(jiǎn)單的，如果a位置已經(jīng)占元素了，就往后找空位：

但實(shí)際用下來(lái)沖突很多，所以還是很慢。因?yàn)槲业膐ri中有大量a相同但b,c不同的三元組。

所以想到，如果解決一次沖突，后移的次數(shù)(k)太多，那就重新Hash到另一個(gè)位置。

因?yàn)槲业臄?shù)據(jù)a的特征是1e6，且?guī)缀?lt;5e5的數(shù)，而hashArr預(yù)設(shè)的大小是1e6，所以后半截幾乎是空的，可以轉(zhuǎn)到后面去：

但這樣只快了25%，感覺(jué)reverse了之后還是沖突了很多。于是想尋找一個(gè)更好的reverse方法（也就是對(duì)a的hash方法。因?yàn)閍已經(jīng)是對(duì)trip的一種hash方法了，所以這里隨便叫reverse）。

我受git上開(kāi)源PNG壓縮用的hash代碼啟發(fā)，以沖突a‘為種子，再a進(jìn)行位移和異或：

速度直接從90s到3s，省97%！終于感覺(jué)到Hash的力量了

合

以前覺(jué)得算法和數(shù)據(jù)結(jié)構(gòu)不重要，因?yàn)闆](méi)有hit到硬件性能瓶頸，包括光追的BVH。現(xiàn)在都得還債...