我會告訴你我正在使用什么結構，請隨時推薦任何更改，例如 numpy 陣列或其他東西。
無論如何，我擁有的是與股票價格相對應的 500 萬個連續條目的串列。
然后我還有 2 個串列，每個串列的長度相同 - 500 萬個條目。這些串列對應于預期的“上限”和預期的“下限”，我預計股票將從序列中的那個點達到。
我想要做的是遍歷下限串列中的所有 500 萬個條目，并按順序記錄價格最終達到該下限所需的時間。然后我想對上限串列做同樣的事情。
以下是只有 10 個條目的股票價格串列的潛在解決方案示例：
prices = [15,16,18,22,23,17,15,19,15,18]
upper_limits = [17,18,21,23,25,22,18,21,18,20]
lower_limits = [14,15,16,18,19,15,13,17,14,16]
solved_upper = [2,1,1,1,x,x,1,x,1,x]
solved_lower = [x,5,4,2,1,1,x,1,x,x]
#I think I got this right? Anyways as you can see, the solved lists simply show
#how many entries we have to look at until we find a value that is >= to it for upper, or <= to it
#for lower
那么問題來了，對于大量的條目，如何合理快速地解決這個問題？（實際上，我有 10 個上限串列和 10 個下限串列..所以需要更高的效率）
uj5u.com熱心網友回復：
我要澄清效率。用真實的資料物件替換 Dictionary 物件可能是一個好主意。
首先，我們需要將您的時間序列變成可搜索的樹。
def make_tree (series, i=None, j=None):
if i is None:
i = 0
if j is None:
j = len(series) - 1
if i == j:
return {
"min_i": i,
"max_i": i,
"min_value": series[i],
"max_value": series[i],
"left": None,
"right": None
}
else:
mid = (i j) // 2
left = make_tree(series, i, mid)
right = make_tree(series, mid 1, j)
return {
"min_i": i,
"max_i": j,
"min_value": min(left['min_value'], right['min_value']),
"max_value": max(left['max_value'], right['max_value']),
"left": left,
"right": right
}
接下來我們需要函式來搜索那棵樹：
def find_next_after_at_least(tree, min_i, min_value):
if tree['max_i'] <= min_i or tree['max_value'] < min_value:
return None
elif tree['min_i'] == tree['max_i']:
return tree['min_i'] - min_i
else:
answer = find_next_after_at_least(tree['left'], min_i, min_value)
if answer is None:
answer = find_next_after_at_least(tree['right'], min_i, min_value)
return answer
def find_next_after_at_most(tree, min_i, max_value):
if tree['max_i'] <= min_i or max_value < tree['min_value']:
return None
elif tree['min_i'] == tree['max_i']:
return tree['min_i'] - min_i
else:
answer = find_next_after_at_most(tree['left'], min_i, max_value)
if answer is None:
answer = find_next_after_at_most(tree['right'], min_i, max_value)
return answer
現在您可以輕松撰寫搜索：
def solve_upper(tree, limits):
return [
find_next_after_at_least(tree, i, limits[i])
for i in range(len(limits))
]
def solve_lower(tree, limits):
return [
find_next_after_at_most(tree, i, limits[i])
for i in range(len(limits))
]
現在你的示例問題：
t = make_tree([15,16,18,22,23,17,15,19,15,18])
print(solve_upper(t, [17,18,21,23,25,22,18,21,18,20]))
print(solve_lower(t, [14,15,16,18,19,15,13,17,14,16]))
uj5u.com熱心網友回復：
您可以使用類似于所謂的“單調佇列”的資料結構有效地解決這個問題（在 O(N log N) 時間內）。你可以用谷歌搜索，但通常的用例與你的有很大不同，所以我只是解釋一下。（奇怪的是，這是我在一周內在這里看到的第三個問題，答案需要這樣的結構。）
在您的情況下，您將從價格陣列的末尾開始作業，將每個價格添加到單調佇列的前面。每次輸入價格時，其他一些可能會被丟棄，因此佇列中只保存比之前所有的都大的專案。這些是唯一可能成為“下一個更高價格”的專案。它們也在佇列中單調遞增，因此您可以使用二分搜索找到第一個 >= 目標。由于您需要知道下一個更高值的索引，因此您可以存盤索引而不是值本身。
這就解決了上限問題。下限類似，但佇列單調遞減。
在python中，它看起來像這樣：
def solve_upper(prices, limits):
solved = [0]*len(prices)
q = [0]*len(prices)
qstart = len(q)
for i in range(len(prices)-1, -1, -1):
price = prices[i]
while qstart < len(q) and prices[q[qstart]] <= price:
# the price at the start of q needs to be discarded, since
# it isn't greater than the new one
qstart = 1
# prepend the new price
qstart -= 1
q[qstart] = i
limit = limits[i]
# binary search to find the first price >= limit
minpos = qstart
maxpos = len(q)
while minpos < maxpos:
testpos = minpos (maxpos - minpos)//2
if prices[q[testpos]] < limit:
# too low
minpos = testpos 1
else:
# high enough
maxpos = testpos
if minpos < len(q):
solved[i] = q[minpos]-i
else:
solved[i] = None
return solved
def solve_lower(prices, limits):
solved = [0]*len(prices)
q = [0]*len(prices)
qstart = len(q)
for i in range(len(prices)-1, -1, -1):
price = prices[i]
while qstart < len(q) and prices[q[qstart]] >= price:
# the price at the start of q needs to be discarded, since
# it isn't less than the new one
qstart = 1
# prepend the new price
qstart -= 1
q[qstart] = i
limit = limits[i]
# binary search to find the first price <= limit
minpos = qstart
maxpos = len(q)
while minpos < maxpos:
testpos = minpos (maxpos - minpos)//2
if prices[q[testpos]] > limit:
# too low
minpos = testpos 1
else:
# high enough
maxpos = testpos
if minpos < len(q):
solved[i] = q[minpos]-i
else:
solved[i] = None
return solved
prices = [15,16,18,22,23,17,15,19,15,18]
upper_limits = [17,18,21,23,25,22,18,21,18,20]
lower_limits = [14,15,16,18,19,15,13,17,14,16]
print(solve_upper(prices, upper_limits))
print(solve_lower(prices, lower_limits))
輸出：
[2, 1, 1, 1, None, None, 1, None, 1, None]
[None, 5, 4, 2, 1, 1, None, 1, None, None]
注意：如果您將此答案與@btilly 的答案進行對比，請將結果包含在評論中！
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/386505.html