Недавно я провалил задачу кодирования, которая связана со сложностью времени.Я занимался этим в свое свободное время, но все еще не могу заставить его работать быстро для больших списков.Сначала я переосмыслил проблему, реорганизовал ее и т. Д., Сделал некоторые дополнительные улучшения, попытался использовать pandas (что оказалось намного медленнее) и т. Д.
Iмне интересно узнать, какие методы я мог бы использовать для повышения скорости выполнения этого кода.
Ввод: список с максимальным размером 10**6, содержащий несортированные целые числа в range(1,10**5).
Задача состоит в том, чтобы вычислить «общую цену» из этой произвольной конструкции и вернуть «общую цену» и упорядоченный список индексов , представляющих те элементы, которыеесли не со скидкой.
Цена товара по индексу i снижается на следующий меньший / меньший элемент .Если в items[i+1:] нет меньших значений, цена товара не дисконтируется (или вы можете считать, что она дисконтирована 0).
Пример ввода: items = [5, 3, 4, 1, 5]
Пример вывода: 13, [3, 4]
Здесь items[0] дисконтируется items[1], items[1] дисконтируется items[3], items[2] дисконтируетсяitems[3], items[3] и items[4] не обесцениваются.
Таким образом, общая цена составляет 13, определяемая как (5-3) + (3-1) + (4-1) + (1-0) + (5-0)
У меня есть функция, которая решает эту проблему довольно быстро в большинстве случаев, но по мере приближения к максимумуразмер списка, это занимает гораздо больше времени.Например, список длиной 50000 обрабатывается за <1 секунду.Список длиной 100К обрабатывается за <3 секунды.Список длиной 200К занимает <10 секунд, а 400К занимает около 50 секунд.<strong> Работа с миллионом элементов занимает ~ 1000 + секунд.
Для тестирования я создаю большой список примерно так, а затем передаю его (или его фрагменты) функциям, например:
data = list(np.array(np.random.randint(1,10**5,(10**6)), dtype='int64'))
total, full_price = get_total(data[:100000])
Вот более быстрая, не pandas функция:
def get_total(data):
init_total = sum(data)
items = data[:]
size = len(items)
discount = [get_discount(items.pop(0),items) for i in range(size)]
full = [i for (i,v) in enumerate(discount) if v == 0]
total = init_total - sum(discount)
return total, full, None
def get_discount(this, _items):
next_lowest_index, discount = next(((x,val) for x, val in enumerate(_items) if val < this), (np.NaN, 0))
return discount
Я упоминал, что я тоже пробовал pandas, но этот код много медленнее даже в небольших списках (n = 1000).Я попытался отсортировать его по значению:
def frame_total(data):
if type(data) == list:
data = pd.DataFrame(data)
data = data[:].sort_values(0, 'index')
df = pd.DataFrame({ 'val':data[0],
'discount': [0] * data.shape[0]
}, dtype='int')
df.discount = [next(iter(df.loc[(df.index > i) & (df.val < row.val)].sort_index().val),0)
for i,row in df.iterrows()]
total = data.sum() - df.discount.sum()
full_indices = list(df[df.discount == 0].sort_index().index)
return total, full_indices, None
И другой, который не сортирует входные данные, который не заметно быстрее:
def frame2(data):
if type(data) == list:
data = pd.DataFrame(data)
data = data[:]
df = pd.DataFrame({ 'val':data[0],
'discount': [0] * data.shape[0]
}, dtype='int')
df.discount = [next(iter(df.val[i+1:].loc[df.val < row.val]),0) for i,row in df.iterrows()]
total = data.sum() - df.discount.sum()
full_indices = list(df[df.discount == 0].index)
return total, full_indices, None
Обратите внимание, что полные цены более вероятнысуществовать ближе к концу списка (при увеличении i вероятность того, что любое значение <<code>items[i] существует в items[i+1:], уменьшается).Я чувствую, что это важно, но я не могу понять, как это использовать.
def get_next_smallest(data,default=0):
"""
returns the discounted value for all items in a list
discounted value is the next smaller item in the list, e.g.:
for any n, the next smallest item is the first item in data[n+1:] < data[n]
provides O(n) complexity solution.
"""
discounts=[default for i in data] # stores the corresponding next smaller value
stack = [] # initialize our empty stack
for i, this in enumerate(data):
while len(stack) > 0 and this < data[stack[-1]]:
discounts[stack.pop()] = this
stack.append(i)
return discounts
def get_total(data):
init_total = sum(data)
default = 0 # should be a value that will NOT be present in the data, like 0 or -1
discounts = get_next_smallest(data, default)
full = [i for i,v in enumerate(discounts) if v == default]
total = init_total - sum(discounts)
return total, full