首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何有效地找到从每个值到下一个较低/更高值的距离?

问如何有效地找到从每个值到下一个较低/更高值的距离?
EN

Stack Overflow用户
提问于 2021-12-19 01:41:15
回答 2查看 66关注 0票数 0

我将告诉您我使用的是什么结构,请随意推荐像numpy数组之类的任何更改。

无论如何,我有一个五百万个顺序条目的列表,这些条目对应于一个股票价格。

然后我又有两个列表,每一个都是相同的长度-500万条目。这些清单对应于预期的“上限”和预期的“下限”,我预计股票将从这一顺序到达。

我想要做的是检查下限价列表中的所有500万条目,并记录在这个序列中需要多长时间,直到价格最终达到这个下限。然后,我想对上限列表做同样的操作。

下面是一个只包含10个条目的股票价目表的潜在解决方案的示例:

代码语言:javascript
复制
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个下限列表。因此,需要更高的效率)

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2021-12-19 04:55:34

您可以使用类似于所谓“单调队列”的数据结构有效地解决这个问题(在O(N log N)时间内)。你可以在谷歌上搜索,但通常的用例与你的完全不同,所以我只想解释一下。(奇怪的是,这是我在一周内看到的第三个问题,答案需要这样的结构。)

在您的情况下,您将从价格数组的末尾开始工作,将每个价格添加到单调队列的前面。每次输入价格时,可能会丢弃其他一些项目,因此队列中只包含比前面所有项目都更大的项目。这是唯一有可能成为“下一个更高价格”的商品。它们在队列中也是单调增加的,因此您可以使用二进制搜索找到第一个>=目标。因为您需要知道下一个较高值的索引,所以可以存储索引而不是值本身。

这解决了上限问题。下限是相似的,但是随着队列的单调减少。

在python中,如下所示:

代码语言:javascript
复制
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))

输出:

代码语言:javascript
复制
[2, 1, 1, 1, None, None, 1, None, 1, None]
[None, 5, 4, 2, 1, 1, None, 1, None, None]

注意:如果你用@btilly来标出这个答案,请把结果写在评论中!

票数 1
EN

Stack Overflow用户

发布于 2021-12-19 04:21:30

我想要的是清晰而不是效率。用真实数据对象替换Dictionary对象可能是个好主意。

首先,我们需要把你的时刻表变成一棵可搜索的树。

代码语言:javascript
复制
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
        }

接下来,我们需要函数来搜索这棵树:

代码语言:javascript
复制
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

现在,您的搜索可以轻松地编写:

代码语言:javascript
复制
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))
    ]

现在是你的例子问题:

代码语言:javascript
复制
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]))
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/70408459

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档