假設一個排序的整數串列如下：
data = [1] * 3 [4] * 5 [5] * 2 [9] * 3
# [1, 1, 1, 4, 4, 4, 4, 4, 5, 5, 9, 9, 9]
我想找到值發生變化的索引，即
[3, 8, 10, 13]
一種方法是使用itertools.groupby：
cursor = 0
result = []
for key, group in groupby(data):
cursor = sum(1 for _ in group)
result.append(cursor)
print(result)
輸出
[3, 8, 10, 13]
這種方法是 O(n)。另一種可能的方法是使用bisect.bisect_left：
cursor = 0
result = []
while cursor < len(data):
cursor = bisect_left(data, data[cursor] 1, cursor, len(data))
result.append(cursor)
print(result)
輸出
[3, 8, 10, 13]
這種方法是 O(k*log n)，其中 k 是不同元素的數量。這種方法的一個變體是使用指數搜索。
有沒有更快或更高效的方法來做到這一點？
uj5u.com熱心網友回復：
我在兩組資料上測驗了您的方法的執行時間，并使用添加了第三組資料 numpy
data1 = [1] * 30000000 [2] * 30000000 [4] * 50000000 [5] * 20000000 [7] * 40000000 [9] * 30000000 [11] * 10000000 [15] * 30000000
data2 = list(range(10000000))
cursor = 0
result = []
start_time = time.time()
for key, group in groupby(data):
cursor = sum(1 for _ in group)
result.append(cursor)
print(f'groupby {time.time() - start_time} seconds')
cursor = 0
result = []
start_time = time.time()
while cursor < len(data):
cursor = bisect_left(data, data[cursor] 1, cursor, len(data))
result.append(cursor)
print(f'bisect_left {time.time() - start_time} seconds')
data = np.array(data)
start_time = time.time()
[i 1 for i in np.where(data[:-1] != data[1:])[0]] [len(data)]
print(f'numpy {time.time() - start_time} seconds')
# We need to iterate over the results array to add 1 to each index for your expected results.
和 data1
groupby 8.864859104156494 seconds
bisect_left 0.0 seconds
numpy 0.27180027961730957 seconds
和 data2
groupby 3.602466583251953 seconds
bisect_left 5.440978765487671 seconds
numpy 2.2847368717193604 seconds
正如您所提到的bisect_left，這在很大程度上取決于唯一元素的數量，但似乎使用numpy比itertools.groupby在索引串列上進行額外迭代具有更好的性能。
uj5u.com熱心網友回復：
當談到漸近復雜性時，我認為當您應用更均勻分布的分而治之方法時，您可以在二分搜索上平均略有改進：嘗試首先查明發生在靠近輸入串列中間的值變化，從而將范圍分成大約兩半，這將使下一個二分搜索操作路徑減少大約一個。
然而，因為這是 Python，收益可能并不明顯，因為 Python 代碼開銷（如 for yield、yield from、遞回等）。對于您使用的串列大小，它的性能甚至可能更差：
from bisect import bisect_left
def locate(data, start, end):
if start >= end or data[start] == data[end - 1]:
return
mid = (start end) // 2
val = data[mid]
if val == data[start]:
start = mid
val = 1
i = bisect_left(data, val, start 1, end)
yield from locate(data, start, i)
yield i
yield from locate(data, i, end)
data = [1] * 3 [4] * 5 [5] * 2 [9] * 3
print(*locate(data, 0, len(data))) # 3 8 10
請注意，這僅輸出有效索引，因此此示例輸入不包括 13。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/364326.html
上一篇：如何撰寫決議器來構造運算式ab[cd][e].f[g[h[ij]]]的JavaScriptASTMemberExpression？