如何使用索引搜索加速嵌套 for 循环 PYTHON
How to speed up a nested for loop with index search PYTHON
我从订单簿中获取值作为这样的列表：
list1 = [...,'ethbtc', '0.077666', '10', '0.077680', '15',...]
----------------------^符号-----^值-----^数量--
此列表中大约有 100 个符号，每个符号有 40 个值。它们总是以相同的顺序排列。
如果我支付 100% 的余额，我想知道此时我的系统购买的最高价格是多少。
因此，如果我想以 0.077666 的价格购买 11 个 ETH，实际价格将是 0.077680，因为首价只有 10 个 ETH。
我不想得到平均值，因为目前已经太多了
我的代码有一个嵌套的 for 循环并遍历 2 个列表：
- coinlist = 其中列出了所有 100 个符号
symbollist = [ethbtc, eoseth,...]
- 名为
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 中的每三个条目是 ETH 中的数量，因此在列表中它将是 ['1', '1.5', '3', '4']
因此，如果我想出售我所有的 ETH（在本例中为 5.5），最大值将为“0.077710”
list1 包含 100 个符号，因此 'ethbtc' 前后还有其他数值数量和符号
预处理list1并将其存储在字典中。这意味着你只迭代 list1 一次而不是每次你的内部循环运行时。
price_dict = {'ethbtc': ['0.077666', '10', '0.077680', '15'], 'btceth': [...], ...}
不是遍历 a，而是遍历 range (Python 3) 或 xrange (Python 2)。这将使用迭代器而不是列表，并使您的代码更加灵活。
range(0, len(price_dict[symbol]), 2)
在你的情况下，我认为如果有固定的间隔，使用切片对象将有助于你的 '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
....
除了 user3080953 的回答之外，您还必须对数据进行预处理，不仅因为这样会更有效率，而且还因为它会帮助您处理复杂性。在这里，您同时做了两件事：解码列表和使用数据。先解码，再使用。
我认为目标格式应该是：
prices_and_quantities_by_symbol = {
'ethbtc': {
'prices':[0.077666, 0.077680, 0.077710, 0.078200],
'quantities':[1, 1.5, 3, 4]
},
'btceth': {
...
},
...}
现在，您只需要做：
for symbol, prices_and_quantities in prices_and_quantities_by_symbol.items(): # O(len(symbol_list))
total = 0
for p, q in zip(prices_and_quantities["prices"], prices_and_quantities["quantities"]): # O(len(quantities))
total += q # the running sum
if total >= my_current_balance:
yield symbol, p # this will yield the symbol and the associated max_value
break
如何获取目标格式的数据？只需遍历列表，如果找到一个符号，就开始存储值和数量，直到下一个符号：
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))
你有一个轻微但有趣的优化，特别是如果你的 quantities/values 列表很长。不存储数量，而是 运行 总数量：
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_value。代码变得更容易理解，因为 bisect.bisect_left(rts, my_current_balance) 将 return 第一个 运行 的索引 total >= 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))
将所有内容放入函数中（或者更好，class 的方法）：
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)
你可以看到，通过将问题分成两部分（解码和使用），代码变得更快并且（在我看来）更容易理解（我没有放评论，但它们应该在那里).
我从订单簿中获取值作为这样的列表：
list1 = [...,'ethbtc', '0.077666', '10', '0.077680', '15',...]
----------------------^符号-----^值-----^数量--
此列表中大约有 100 个符号，每个符号有 40 个值。它们总是以相同的顺序排列。
如果我支付 100% 的余额，我想知道此时我的系统购买的最高价格是多少。
因此，如果我想以 0.077666 的价格购买 11 个 ETH，实际价格将是 0.077680，因为首价只有 10 个 ETH。
我不想得到平均值，因为目前已经太多了
我的代码有一个嵌套的 for 循环并遍历 2 个列表：
- coinlist = 其中列出了所有 100 个符号
symbollist = [ethbtc, eoseth,...] - 名为
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 中的每三个条目是 ETH 中的数量，因此在列表中它将是 ['1', '1.5', '3', '4']
因此，如果我想出售我所有的 ETH（在本例中为 5.5），最大值将为“0.077710”
list1 包含 100 个符号，因此 'ethbtc' 前后还有其他数值数量和符号
预处理list1并将其存储在字典中。这意味着你只迭代 list1 一次而不是每次你的内部循环运行时。
price_dict = {'ethbtc': ['0.077666', '10', '0.077680', '15'], 'btceth': [...], ...}
不是遍历 a，而是遍历 range (Python 3) 或 xrange (Python 2)。这将使用迭代器而不是列表，并使您的代码更加灵活。
range(0, len(price_dict[symbol]), 2)
在你的情况下，我认为如果有固定的间隔，使用切片对象将有助于你的 '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
....
除了 user3080953 的回答之外，您还必须对数据进行预处理，不仅因为这样会更有效率，而且还因为它会帮助您处理复杂性。在这里，您同时做了两件事：解码列表和使用数据。先解码，再使用。
我认为目标格式应该是：
prices_and_quantities_by_symbol = {
'ethbtc': {
'prices':[0.077666, 0.077680, 0.077710, 0.078200],
'quantities':[1, 1.5, 3, 4]
},
'btceth': {
...
},
...}
现在，您只需要做：
for symbol, prices_and_quantities in prices_and_quantities_by_symbol.items(): # O(len(symbol_list))
total = 0
for p, q in zip(prices_and_quantities["prices"], prices_and_quantities["quantities"]): # O(len(quantities))
total += q # the running sum
if total >= my_current_balance:
yield symbol, p # this will yield the symbol and the associated max_value
break
如何获取目标格式的数据？只需遍历列表，如果找到一个符号，就开始存储值和数量，直到下一个符号：
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))
你有一个轻微但有趣的优化，特别是如果你的 quantities/values 列表很长。不存储数量，而是 运行 总数量：
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_value。代码变得更容易理解，因为 bisect.bisect_left(rts, my_current_balance) 将 return 第一个 运行 的索引 total >= 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))
将所有内容放入函数中（或者更好，class 的方法）：
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)
你可以看到，通过将问题分成两部分（解码和使用），代码变得更快并且（在我看来）更容易理解（我没有放评论，但它们应该在那里).