我将告诉您我使用的是什么结构,请随意推荐像numpy数组之类的任何更改。
无论如何,我有一个五百万个顺序条目的列表,这些条目对应于一个股票价格。
然后我又有两个列表,每一个都是相同的长度-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个下限列表。因此,需要更高的效率)
发布于 2021-12-19 04:55:34
您可以使用类似于所谓“单调队列”的数据结构有效地解决这个问题(在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来标出这个答案,请把结果写在评论中!
发布于 2021-12-19 04:21:30
我想要的是清晰而不是效率。用真实数据对象替换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]))https://stackoverflow.com/questions/70408459
复制相似问题