В дополнение к ответу от пользователя 3080953 вам необходимо предварительно обработать данные не только потому, что это будет более эффективно, но и потому, что это поможет вам справиться со сложностью.Здесь вы делаете две вещи одновременно: расшифровываете свой список и используете данные.Сначала декодируйте, затем используйте.
Целевой формат должен быть, по моему мнению:
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))
У вас есть небольшая, но интересная оптимизация, особенно если ваш список величин / значенийдлинныеСохраняйте не количество, а текущую сумму:
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': {
...
},
...}
Теперь вы можете очень быстро найти значение max_value, используя bisect.Код становится более простым для понимания, поскольку 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)
Вы можете увидеть, как, разделив задачу на две части (декодировать и использовать)код становится быстрее и (на мой взгляд) легче для понимания (я не размещал комментарии, но они должны быть там).