python - Python 中的算法帮助，找到 (x,y) 对，其中 y/x > const

Question

我正在构建一个相当庞大的实时赔率系统，而我现在的瓶颈是实际计算。我有大量排序列表，对于每个列表，我需要找到每一对 (x,y)，其中 (y/x) > const。

这就是我目前正在做的；

for f in reversed(xrange(1, len(odds))):
    found = False
    for s in xrange(0, f):
        try:
            edge = odds[s]/odds[f]
        except ZeroDivisionError:
            continue
        if edge > const:
            found = True
            yield odds[f], odds[s]
        else:
            break
    if not found:
        break

只要我确定没有更多的配对，计划就会停止。但是，我每个周期平均要处理 40 个列表，而且我迫切需要缩短周期时间。我对使用 numpy 很好奇，看看是否可以帮助我。

每个单独列表的长度为 < 50。

感谢您的帮助!

编辑 这是一个具有结构的示例列表

(_ , odds1, odds2, odds3, _, _) (_ means not used):
[(260, Decimal('1.45'), Decimal('5.5'), Decimal('4'), 0, 2666298), (35549, Decimal('1.62'), Decimal('4.5'), Decimal('3.5'), 0, 2666298), (35551, Decimal('1.666'), Decimal('4.333'), Decimal('3.6'), 0, 2666298), (35552, Decimal('1.6'), Decimal('3.6'), Decimal('3.35'), 0, 2666298), (35553, Decimal('1.6'), Decimal('3.6'), Decimal('3.35'), 0, 2666298), (54453, Decimal('1.65'), Decimal('4.2'), Decimal('3.6'), 0, 2666298), (56234, Decimal('1.571'), Decimal('4.65'), Decimal('3.9'), 0, 2666298), (56911, Decimal('1.7'), Decimal('4.2'), Decimal('3.15'), 0, 2666298)]

我将这个列表分成 3 个列表，odds1_list、odds2_list、odds3_list，并对它们进行计算。赔率示例1:

[Decimal('1.7'), Decimal('1.666'), Decimal('1.65'), Decimal('1.62'), Decimal('1.6'), Decimal('1.6'), Decimal('1.571'), Decimal('1.45')]

然后我需要识别此列表中的所有对 (x,y)，其中 (y/x > const)

Answer 1

如果列表已排序，那么对于每个 x，您可以只搜索列表中第一次出现的 const*x，以及该匹配项之后的所有项目:

import numpy

odds = numpy.arange(10.)
const = 2.5

for x in odds:
    idx = numpy.searchsorted(odds, const*x, side='right')
    for y in odds[idx:]:
        print (x,y)

运行给予

(0.0, 1.0)
(0.0, 2.0)
(0.0, 3.0)
(0.0, 4.0)
(0.0, 5.0)
(0.0, 6.0)
(0.0, 7.0)
(0.0, 8.0)
(0.0, 9.0)
(1.0, 3.0)
(1.0, 4.0)
(1.0, 5.0)
(1.0, 6.0)
(1.0, 7.0)
(1.0, 8.0)
(1.0, 9.0)
(2.0, 6.0)
(2.0, 7.0)
(2.0, 8.0)
(2.0, 9.0)
(3.0, 8.0)
(3.0, 9.0)