如何使用索引搜索PYTHON来加快嵌套for循环的速度

Question

我从订单簿中获取值，如下所示：

list1 = [...,'ethbtc', '0.077666', '10', '0.077680', '15',...]
------------------------^符号-----^价值---^数量--

这个列表中大约有100个符号，每个符号有40个值。它们总是处于同一顺序。
我想知道，如果我支付余额的100%，我的系统在这一刻购买的最高价格是多少。在

因此，如果我想以0.077666的价格购买11以太币，那么实际价格应该是0.077680，因为第一个价格只有10个以太币。
我不想得到平均值，因为那将是目前太多

我的代码有一个嵌套的for循环，并循环两个列表：

1. coinlist=所有100个符号都是这样列出的symbollist = [ethbtc, eoseth,...]
2. 名为a的索引列表，因为值和数量总是在同一位置
   a = ['1', '3', '5', ...]

我的代码：

for symbolnow in symbollist:
sumlist = []
    for i in a:
        quantity = float(list1[list1.index(symbolnow) + (i+1)] if symbolnow in list1 else 0)
        sumlist.append(quantity)
        if sum(sumlist) > mycurrentbalance:
            maxvalue = float(list1[list1.index(symbolnow) + i] if symbolnow in list1 else -1)
            break
        else:
            maxvalue = -1

那么这段代码是做什么的：
1） 循环遍历符号列表中的每个符号
2） 对于找到的每个符号，我都会查找可用数量
3） 如果我的余额（即10 ETH）小于qty，则循环中断
4） 如果没有，则继续搜索和汇总汇总列表中的每个数量，直到有足够的数量为止。在

代码按预期工作，但没有那么快。正如预期的那样，list1.index需要很长时间才能执行。。在

问题
一个更快的代码是如何工作的。在这种情况下，列表理解更好吗？甚至是正则表达式？我的代码很难看吗？在

提前谢谢你！在

编辑：
为了澄清输入和期望输出，示例：

list1 = [...,'ethbtc', '0.077666', '1', '0.077680', '1.5', '0.077710', '3', '0.078200', '4',...]
mycurrentbalance = 5.5<；--余额以ETH为单位
list1中每三个条目都是以太币的数量，因此在列表中它将是['1', '1.5', '3', '4']

所以如果我想卖掉我所有的ETH（在这个例子中是5.5），最大值应该是'0.077710'

list1包含100个符号，因此在'ethbtc'之前和之后还有其他值、数量和符号

Answer 1

除了用户3080953给出的答案外，您还必须对数据进行预处理，这不仅是因为这样会更有效，而且还因为它将帮助您处理复杂性。在这里，您同时做两件事：解码列表和使用数据。先解码，再使用。在

我认为，目标格式应该是：

prices_and_quantities_by_symbol = {
    'ethbtc': {
        'prices':[0.077666, 0.077680, 0.077710, 0.078200], 
        'quantities':[1, 1.5, 3, 4]
    }, 
    'btceth': {
        ...
    }, 
...}

现在，你只需：

^{pr2}$

如何获取目标格式的数据？只需迭代列表，如果找到符号，则开始存储值和数量，直到下一个符号：

prices_and_quantities_by_symbol = {}
symbol_set = (symbol_list) # O(len(symbol_list))
for i, v in enumerate(list1): # O(len(list1))
    if v in symbol_set:  # amortized O(1) lookup
        current_prices = []
        current_quantities = []
        current_start = i+1
        prices_and_quantities_by_symbol[v] = {
            'prices':current_prices, 
            'quantities':current_quantities
        }
    else: # a value or a quantity
        (current_prices if (i-current_start)%2==0 else current_quantities).append(float(v))

您有一个轻微但有趣的优化，特别是如果您的数量/值列表很长。不要存储数量，而是存储总数量：

prices_and_running_total_by_symbol = {
    'ethbtc': {
        'prices':[0.077666, 0.077680, 0.077710, 0.078200], 
        'running_total':[1, 2.5, 5.5, 9.5]
    }, 
    'btceth': {
        ...
    }, 
...}

现在，您可以使用bisect快速找到您的max_值。代码变得更容易理解，因为bisect.bisect_left(rts, my_current_balance)将返回第一次运行的总计>= my_current_balance的索引：

for symbol, prices_and_running_totals in prices_and_running_totals_by_symbol.items(): # O(len(symbol_list))
    ps = prices_and_running_totals["prices"]
    rts = prices_and_running_totals["running_total"]
    i = bisect.bisect_left(rts, my_current_balance) # O(log(len(rts)))
    yield symbol, ps[i] # this will yield the symbol and the associated max_value

要建立运行总数，您必须以不同的方式处理价格和数量：

# O(len(list1))
...
if v in symbol_set:  # amortized O(1) lookup*
    ...
elif (i-current_start)%2==0:
    current_prices.append(float(v))
else:
    current_running_totals.append((current_running_totals[-1] if current_running_totals else 0.0) + float(v))

将所有内容放入函数中（或者更好地说，类的方法）：

prices_and_running_totals_by_symbol = process_data(list1)
for symbol, max_value in symbols_max_values(prices_and_running_totals_by_symbol, my_current_balance):
    print(symbol, max_value)

你可以看到，通过将问题分成两部分（解码和使用），代码变得更快（在我看来）更容易理解（我没有发表评论，但它们应该在那里）。在

Answer 2

预处理list1并将其存储在dict中。这意味着您只需在list1上迭代一次，而不是每次内部循环运行时。在

price_dict = {'ethbtc': ['0.077666', '10', '0.077680', '15'], 'btceth': [...], ...}

不要迭代a，而是迭代range（python3）或{}（python2）。这将使用迭代器而不是列表，从而使代码更加灵活。在

^{pr2}$

Answer 3

在您的例子中，如果有固定的间隔，我认为使用slice对象将有助于您的“a”循环。您可以将列表切片保存到一个对象，如下所示（还有1个或2个其他提示）。我同意上面的用户，如果你有机会预处理输入的数据，那么你真的必须。为此，我建议使用pandas库，因为它非常快，但是字典也允许散列值。在

input_data = ['ethbtc', '0.0776666', '10', '0.077680', '15']  # Give your variables meaningful names

length = 20 # a variable to store how long a list of values is for a particular symbol.

for symbol in symbollist: # Use meaningful names if loops too
    start = input_data.index(symbol)  # break up longer lines
    # Some exception handling here
    indxs = slice(start: start+length:2) # python lets you create slice objects
    quantities = [float(number) for number in input_data[indxs]]

    if sum(quantities) > mycurrentbalance:
        # Whatever code here
        ....