賞金將在 7 天后到期。此問題的答案有資格獲得 50聲望賞金。 Ali_Sh正在尋找一個規范的答案：
這個問題已經有了答案，我想直接得到 Jerome 的賞金答案。但是，由于這個問題是一個有趣的話題，人們會回到它，我在帖子上放了一個賞金，以獲得更多的關注杰羅姆沒有解釋的可能的新專業方法。 答案可以考慮問題的任何方面（不限于原始問題的需要），例如陣列大小效應、多執行緒等。
我需要一個更快的代碼來洗掉與另一個一維陣列（陣列長度?1e5-5e5->很少達到7e5）常見的一維陣列（陣列長度?10-15）的值，它們是包含整數的索引陣列. 陣列中沒有重復，它們沒有排序，修改后的值的順序必須保留在主陣列中。我知道可以使用這樣的np.setdiff1dor np.in1d（在 no-python 模式下 numba 不支持這兩者）和其他類似的帖子（例如this）沒有更有效的方法來做到這一點，但性能在這里很重要，因為所有主索引陣列中的值將在回圈中逐漸被洗掉。
import numpy as np
import numba as nb
n = 500000
r = 10
arr1 = np.random.permutation(n)
arr2 = np.random.randint(0, n, r)
# @nb.jit
def setdif1d_np(a, b):
return np.setdiff1d(a, b, assume_unique=True)
# @nb.jit
def setdif1d_in1d_np(a, b):
return a[~np.in1d(a, b)]
norok2為 2D 陣列提出了另一個相關的帖子，即比那里描述的通常方法快約 15 倍的解決方案（使用 numba 的類似散列的方式）。如果可以為一維陣列準備此解決方案，它可能是最好的：
@nb.njit
def mul_xor_hash(arr, init=65537, k=37):
result = init
for x in arr.view(np.uint64):
result = (result * k) ^ x
return result
@nb.njit
def setdiff2d_nb(arr1, arr2):
# : build `delta` set using hashes
delta = {mul_xor_hash(arr2[0])}
for i in range(1, arr2.shape[0]):
delta.add(mul_xor_hash(arr2[i]))
# : compute the size of the result
n = 0
for i in range(arr1.shape[0]):
if mul_xor_hash(arr1[i]) not in delta:
n = 1
# : build the result
result = np.empty((n, arr1.shape[-1]), dtype=arr1.dtype)
j = 0
for i in range(arr1.shape[0]):
if mul_xor_hash(arr1[i]) not in delta:
result[j] = arr1[i]
j = 1
return result
我試圖為一維陣列做準備，但我對此有一些問題/疑問。
- 一開始，IDU究竟做
mul_xor_hash了什么，是否init和k是否被任意選擇 - 為什么
mul_xor_hash沒有nb.njit：
File "C:/Users/Ali/Desktop/test - Copy - Copy.py", line 21, in mul_xor_hash
result = (result * k) ^ x
TypeError: ufunc 'bitwise_xor' not supported for the input types, and the inputs could not be safely coerced to any supported types according to the casting rule ''safe''
- IDK 如何
mul_xor_hash在 1D 陣列上實作（如果可以的話），我猜這可能會使它比 2D 更快，所以我將輸入陣列廣播到 2D by[None, :]，這會得到以下錯誤arr2：
print(mul_xor_hash(arr2[0]))
ValueError: new type not compatible with array
- 和做
delta什么
我正在尋找這方面最有效的方法。在沒有比norok2 解決方案更好的方法的情況下，如何為一維陣列準備這個解決方案？
uj5u.com熱心網友回復：
了解基于哈希的解決方案
首先，IDU mul_xor_hash 到底是做什么的，init 和 k 是否被任意選擇
mul_xor_hash是一個自定義哈希函式。眾所周知，混合異或和乘法（可能帶有移位）的函式計算原始資料緩沖區的散列相對較快。乘法往往會打亂位，并且 xor 用于以某種方式將結果組合/累加為固定大小的小值（即最終散列）。有許多不同的散列函式。在給定的背景關系中，有些比其他更快，有些比其他導致更多的沖突。導致太多沖突的快速散列函式在實踐中可能是無用的，因為它會導致需要比較所有沖突值的病態情況。這就是為什么快速散列函式難以實作的原因。
init并且k是引數肯定會導致哈希非常平衡。這在這樣的哈希函式中很常見。k乘法需要足夠大才能混洗位，并且通常也應該是素數（由于模算術行為，諸如二的冪之類的值往往會增加沖突）。init僅對非常小的陣列（例如，具有 1 個專案）起重要作用：它通過將最終哈希與非平凡常量進行異或來幫助減少沖突。事實上，如果arr.size = 1，那么result = (init * k) ^ arr[0]whereinit * k是一個常數。arr[0]擁有一個等于arr[0]例如可以除以哈希表中的桶數）。因此，init應該是一個相對較大的數字，init * k也應該是一個很大的非平凡值（素數是一個很好的目標值）。
為什么沒有 nb.njit mul_xor_hash 將無法作業
這取決于輸入。輸入需要是一維陣列，并且具有可被 8 整除的位元組原始大小（例如，64 位專案、2n x 32 位專案、4n x 16 位 1 或 8n 8 位專案）。下面是一些例子：
mul_xor_hash(np.random.rand(10))
mul_xor_hash(np.arange(10)) # Do not work with 9
以及 delta 做什么
它set包含arr2行的散列，因此找到匹配行比比較沒有散列的行更快。
如何為一維陣列準備這個解決方案？
AFAIK，散列僅用于避免行比較，但這是因為輸入是二維陣列。在 1D 中，沒有這樣的問題。
這種方法有一個很大的問題：它只有在沒有哈希沖突的情況下才有效。否則，實作錯誤地假設值相等，即使它們不相等！@norok 在評論中明確提到了它：
請注意，還應實施散列的沖突處理
更快的實施
將@norok 的 2D 解決方案用于 1D 并不是一個好主意，因為散列不會使其更快地使用它們。事實上，set無論如何，a 已經在內部使用了哈希函式。更不用說需要正確實施碰撞（由 a 完成set）。
使用 aset是一個相對好的主意，因為它會導致復雜性在O(n m)wheren = len(arr1)和m = len(arr2)。話雖如此，如果arr1轉換為 a set，那么它將太大而無法放入 L1 快取（由于arr1您的情況的大小），從而導致緩慢的快取未命中。此外，不斷增長的大小set將導致值被重新散列，這是無效的。如果arr2轉換為 a set，那么許多哈希表提取將不會非常有效，因為arr2在您的情況下非常小。這就是為什么這個解決方案是次優的。
一種解決方案是拆分arr1成塊，然后set基于目標塊構建一個。然后，您可以檢查一個值是否在集合中或無效。由于規模不斷擴大，構建該集合的效率仍然不高。這個問題是由于 Python 本身沒有像其他語言（例如 C ）那樣提供為資料結構保留一些空間的方法。避免此問題的一種解決方案是簡單地重新實作一個哈希表，這不是微不足道和麻煩的。實際上，布隆過濾器可以用來加速這個程序，因為它們可以快速找到兩個集合之間是否沒有沖突arr1并且arr2平均（盡管它們實作起來并不簡單）。
另一個優化是使用多個執行緒并行計算塊，因為它們是獨立的。話雖如此，附加到最終陣列并不容易有效地并行執行，特別是因為您不希望修改訂單。一種解決方案是將副本從并行回圈中移開并串行執行，但這很慢，AFAIK 目前在 Numba 中沒有簡單的方法可以做到這一點（因為并行層非常有限）。考慮使用 C/C 等本地語言來實作高效的并行實作。
最后，散列可能非常復雜，與使用嵌套回圈的天真實作相比，速度可能非常小，因為arr2只有很少的專案，現代處理器可以使用SIMD 指令快速比較值（而基于散列的方法幾乎無法受益來自他們在主流處理器上）。展開可以幫助撰寫一個非常簡單和快速的實作。同樣，不幸的是，Numba 在內部使用 LLVM-Jit，這似乎無法對這樣一個簡單的代碼進行矢量化（當然是由于LLVM-Jit 甚至 LLVM 本身缺少優化）。因此，非向量化代碼最終會慢一點（而不是在現代主流處理器上快 4~10 倍）。一種解決方案是使用 C/C 代碼來代替（或者可能是 Cython）。
這是使用基本回圈過濾器的串行實作：
@nb.njit('uint32(int32)')
def hash_32bit_4k(value):
return (np.uint32(value) * np.uint32(27_644_437)) & np.uint32(0x0FFF)
@nb.njit(['int32[:](int32[:], int32[:])', 'int32[:](int32[::1], int32[::1])'])
def setdiff1d_nb_faster(arr1, arr2):
out = np.empty_like(arr1)
bloomFilter = np.zeros(4096, dtype=np.uint8)
for j in range(arr2.size):
bloomFilter[hash_32bit_4k(arr2[j])] = True
cur = 0
for i in range(arr1.size):
# If the bloom-filter value is true, we know arr1[i] is not in arr2.
# Otherwise, there is maybe a false positive (conflict) and we need to check to be sure.
if bloomFilter[hash_32bit_4k(arr1[i])] and arr1[i] in arr2:
continue
out[cur] = arr1[i]
cur = 1
return out[:cur]
這是一個未經測驗的變體，應該適用于 64 位整數（浮點數需要記憶體視圖，也可能需要一個素數常量）：
@nb.njit('uint64(int64)')
def hash_32bit_4k(value):
return (np.uint64(value) * np.uint64(67_280_421_310_721)) & np.uint64(0x0FFF)
請注意，如果小陣列中的所有值都包含在每個回圈的主陣列中，那么我們可以通過在找到它們時arr1[i] in arr2洗掉值來加速該部分。arr2話雖如此，碰撞和發現應該非常罕見，所以我不認為這會明顯更快（更不用說它增加了一些開銷和復雜性）。如果專案是按塊計算的，則可以直接復制最后一個塊而無需任何檢查，但好處應該仍然相對較小。請注意，此策略對于前面提到的幼稚 (C/C ) SIMD 實作可能是有效的（它可能快 2 倍左右）。
結果
以下是我基于 i5-9600KF 的機器上的結果：
setdif1d_np: 2.65 ms
setdif1d_in1d_np: 2.61 ms
setdiff1d_nb: 2.33 ms
setdiff1d_nb_faster: 0.73 ms
提供的比其他的快大約 3~4 倍。
uj5u.com熱心網友回復：
我發現散列沒有幫助。對于 2D 情況，將 1d 陣列轉換為單個數字并將它們放在一個集合中只是技巧。
下面是我轉換為一維陣列的 norok2 的方法（并添加了注釋以加快編譯速度）。請注意，這僅比您已有的方法快一點（20-30%）。當然，在第二次函式呼叫之后，首先由于編譯它會稍微慢一些。
@nb.njit('int32[:](int32[:], int32[:])')
def setdiff1d_nb(arr1, arr2):
# : build `delta` set using hashes
delta = set()
for i in range(0, arr2.shape[0]):
delta.add(arr2[i])
# : build the result
n = len(arr1) - len(arr2)
result = np.empty(n, dtype=arr1.dtype)
j = 0
for i in range(arr1.shape[0]):
if arr1[i] not in delta:
result[j] = arr1[i]
j = 1
return result
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/515414.html