Python FInd Наибольшее число в последних элементах k

Учитывая массив целых чисел и целочисленное значение K моя задача - написать функцию, которая печатает на стандартном выходе наибольшее число для этого значения в массиве и прошлых записей K перед ним ,Python FInd Наибольшее число в последних элементах k

Пример ввода:

tps: 6, 9, 4, 7, 4, 1 
k: 3

Результат:

Мне сказали, что код, который я написал можно было бы сделать гораздо более эффективной для больших наборов данных. Как я могу сделать этот код наиболее эффективным?

def tweets_per_second(tps, k): 
    past = [tps[0]] 
    for t in tps[1:]: 
     past.append(t) 
     if len(past) > k: past = past[-k:] 
     print max(past)

источник

2015-01-09 kilojoules

Я не понимаю, как ваш ввод дает этот вывод. Почему вы получаете несколько '9' 'и' 7''? –

@Adam: для каждого члена массива он печатает максимальное значение прошлых членов K (включая текущий элемент). – Ani

Вы можете использовать максимальную кучу с точностью до k элементов (http: //en.wikipedia.орг/вики/Heap_ (data_structure)). Сложностью будет O (nlogk), и это оптимально, я считаю. – Jarlax

Вы можете добиться линейной временной сложности с использованием монотонной очереди (O (n) для любого значения k). Идея заключается в следующем:

Давайте сохраним знак пары (значение, положение). Первоначально он пуст.
Когда приходит новый элемент, сделайте следующее: в то время как положение переднего элемента выходит за допустимые пределы (меньше, чем i - K), поместите его. Хотя значение обратного элемента меньше, чем новое, поместите его. Наконец, нажмите пару (текущий элемент, его положение) на обратную сторону дека.
Ответ на текущую позицию - это передний элемент deque.

Каждый элемент добавляется к deque только один раз и удаляется не более одного раза. Таким образом, временная сложность линейна и не зависит от К. Это решение является оптимальным, так как просто чтение ввода - это O (n).

источник

2015-01-09 22:59:43 kraskevich

Это отличный ответ. Максимальный размер deque равен k + 1 вправо? Это также означает, что он может быть эффективно реализован с помощью кругового массива. –

@Anonymous Да, это k + 1. – kraskevich

@Anonymous True или использовать встроенный в Python '' deque' '(https://docs.python.org/2/library/collections.html#collections.deque) класс. – augurar

панда может сделать это довольно хорошо:

import pandas as pd 
df = pd.DataFrame(dict(data=[6, 9, 4, 7, 4, 1])) 
df['running_max'] = pd.expanding_max(df.data) 
df['rolling_max'] = pd.rolling_max(df.data, 3, min_periods=0) 


print df 
    data running_max rolling_max 
0  6   6   6 
1  9   9   9 
2  4   9   9 
3  7   9   9 
4  4   9   7 
5  1   9   7

источник

2015-01-09 22:43:14 acushner

Он просит алгоритм, а не инструмент. – augurar

он спрашивает, как сделать его эффективным для больших наборов данных, это хороший ответ для этого. – acushner

@acushner Я думаю, что интерпретация Аугурара. На вопрос помечен «алгоритм», который предполагает, что вопрос задает алгоритм, а не библиотечную функцию. –

Попробуйте использовать heap для достижения уменьшения сложности максимальной работы в от O(K) к O(logK) времени.

Добавить первую (-tps[i]) *, i in range(0,k) и выход (-heap[0]) каждый раз
для следующих номеров Nk вы должны добавить в куче tps[i] удалить tps[i-k] и печать (-heap[0])

В целом вы получите O (N log (K)), тогда как вы используете O (N * K). Это будет очень полезно, если K не мало.

* Поскольку реализация кучи имеет мин (кучи) в куче [0] в качестве инвариантной, если добавить -value-heap[0] станет max(heap), как вы хотите.

источник

2015-01-09 22:51:00 pankgeorg

Это лучше, но не оптимально, вы можете добиться амортизации O (1) сложности для этой операции. (См. [Ответ ILoveCoding] (http://stackoverflow.com/a/27870655/2572431)) – augurar

Python FInd Наибольшее число в последних элементах k

ответ

Смежные вопросы