у меня есть список многих несортированных чисел, например:
N=1000000
x = [random.randint(0,N) for i in range(N)]
Я хочу только верхние k минимальных значений, в настоящее время это мой подход
def f1(x,k): # O(nlogn)
return sorted(x)[:k]
Это выполняет много избыточных операций, так как мы также сортируем оставшиеся Nk-элементы. Перечисление также не работает:
def f2(x,k): # O(nlogn)
y = []
for idx,val in enumerate( sorted(x) ):
if idx == k: break
y.append(val)
return y
Проверка перечисления не помогает:
if 1 : ## Time taken = 0.6364126205444336
st1 = time.time()
y = f1(x,3)
et1 = time.time()
print('Time taken = ', et1-st1)
if 1 : ## Time taken = 0.6330435276031494
st2 = time.time()
y = f2(x,3)
et2 = time.time()
print('Time taken = ', et2-st2)
Возможно, мне нужен генератор, который постоянно возвращает следующий минимум списка, и с момента получения следующий минимум должен быть O(1) операция, функция f3() должна быть просто O(k) верно? Какая функция GENERATOR будет работать лучше в этом случае?
def f3(x,k): # O(k)
y = []
for idx,val in enumerate( GENERATOR ):
if idx == k: break
y.append(val)
return y
РЕДАКТИРОВАТЬ 1 :
Анализ, показанный здесь, неверен, пожалуйста, проигнорируйте и перепрыгните в Редактировать 3
Самая низкая граница возможна: с точки зрения сложности времени, я думаю, что это нижняя граница, достижимая, но так как она будет увеличивать исходный список, это n ' t решение моей проблемы.
def f3(x,k): # O(k) Time
y = []
idx=0
while idx<k:
curr_min = min(x)
x.remove(curr_min) # This removes from the original list
y.append(curr_min)
idx += 1
return y
if 1 : ## Time taken = 0.07096505165100098
st3 = time.time()
y = f3(x,3)
et3 = time.time()
print('Time taken = ', et3-st3)
O (N) Время | O (N) Хранение: лучшее решение на данный момент, однако для него требуется копия исходного списка, следовательно, в результате O(N) времени и хранилища, с итератором, который получает следующий минимум, для k раз, будет O(1) хранилища и O(k) время.
def f3(x,k): # O(N) Time | O(N) Storage
y = []
idx=0
while idx<k:
curr_min = min(x)
x.remove(curr_min)
y.append(curr_min)
idx += 1
return y
if 1 : ## Time taken = 0.0814204216003418
st3 = time.time()
y = f3(x,3)
et3 = time.time()
print('Time taken = ', et3-st3)
РЕДАКТИРОВАТЬ 2 :
Спасибо за указание на мои вышеуказанные ошибки, получение минимального списка должно быть O(n), а не O(1).
РЕДАКТИРОВАТЬ 3 :
Вот полный сценарий анализа после использования рекомендуемого решения. Теперь это вызывает больше вопросов
1) Построение x в виде кучи с использованием heapq.heappush медленнее, чем использование list.append x для списка, а затем heapq.heapify it?
2) heapq.nsmallest замедляется, если x уже является кучей?
3) Текущий вывод: не heapq.heapify текущий список, затем используйте heapq.nsmallest.
import time, random, heapq
import numpy as np
class Timer:
def __init__(self, description):
self.description = description
def __enter__(self):
self.start = time.perf_counter()
return self
def __exit__(self, *args):
end = time.perf_counter()
print(f"The time for '{self.description}' took: {end - self.start}.")
def f3(x,k):
y = []
idx=0
while idx<k:
curr_min = min(x)
x.remove(curr_min)
y.append(curr_min)
idx += 1
return y
def f_sort(x, k):
y = []
for idx,val in enumerate( sorted(x) ):
if idx == k: break
y.append(val)
return y
def f_heapify_pop(x, k):
heapq.heapify(x)
return [heapq.heappop(x) for _ in range(k)]
def f_heap_pop(x, k):
return [heapq.heappop(x) for _ in range(k)]
def f_heap_nsmallest(x, k):
return heapq.nsmallest(k, x)
def f_np_partition(x, k):
return np.partition(x, k)[:k]
if True : ## Constructing list vs heap
N=1000000
# N= 500000
x_main = [random.randint(0,N) for i in range(N)]
with Timer('constructing list') as t:
x=[]
for curr_val in x_main:
x.append(curr_val)
with Timer('constructing heap') as t:
x_heap=[]
for curr_val in x_main:
heapq.heappush(x_heap, curr_val)
with Timer('heapify x from a list') as t:
x_heapify=[]
for curr_val in x_main:
x_heapify.append(curr_val)
heapq.heapify(x_heapify)
with Timer('x list to numpy') as t:
x_np = np.array(x)
"""
N=1000000
The time for 'constructing list' took: 0.2717265225946903.
The time for 'constructing heap' took: 0.45691753178834915.
The time for 'heapify x from a list' took: 0.4259336367249489.
The time for 'x list to numpy' took: 0.14815033599734306.
"""
if True : ## Performing experiments on list vs heap
TRIALS = 10
## Experiments on x as list :
with Timer('f3') as t:
for _ in range(TRIALS):
y = f3(x.copy(), 30)
print(y)
with Timer('f_sort') as t:
for _ in range(TRIALS):
y = f_sort(x.copy(), 30)
print(y)
with Timer('f_np_partition on x') as t:
for _ in range(TRIALS):
y = f_np_partition(x.copy(), 30)
print(y)
## Experiments on x as list, but converted to heap in place :
with Timer('f_heapify_pop on x') as t:
for _ in range(TRIALS):
y = f_heapify_pop(x.copy(), 30)
print(y)
with Timer('f_heap_nsmallest on x') as t:
for _ in range(TRIALS):
y = f_heap_nsmallest(x.copy(), 30)
print(y)
## Experiments on x_heap as heap :
with Timer('f_heap_pop on x_heap') as t:
for _ in range(TRIALS):
y = f_heap_pop(x_heap.copy(), 30)
print(y)
with Timer('f_heap_nsmallest on x_heap') as t:
for _ in range(TRIALS):
y = f_heap_nsmallest(x_heap.copy(), 30)
print(y)
## Experiments on x_np as numpy array :
with Timer('f_np_partition on x_np') as t:
for _ in range(TRIALS):
y = f_np_partition(x_np.copy(), 30)
print(y)
#
"""
Experiments on x as list :
[0, 1, 1, 4, 5, 5, 5, 6, 6, 7, 7, 7, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 18, 18, 19, 19, 21, 22, 24, 25]
The time for 'f3' took: 10.180440502241254.
[0, 1, 1, 4, 5, 5, 5, 6, 6, 7, 7, 7, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 18, 18, 19, 19, 21, 22, 24, 25]
The time for 'f_sort' took: 9.054768254980445.
[ 1 5 5 1 0 4 5 6 7 6 7 7 12 12 11 13 11 12 13 18 10 14 10 18 19 19 21 22 24 25]
The time for 'f_np_partition on x' took: 1.2620676811784506.
Experiments on x as list, but converted to heap in place :
[0, 1, 1, 4, 5, 5, 5, 6, 6, 7, 7, 7, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 18, 18, 19, 19, 21, 22, 24, 25]
The time for 'f_heapify_pop on x' took: 0.8628390356898308.
[0, 1, 1, 4, 5, 5, 5, 6, 6, 7, 7, 7, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 18, 18, 19, 19, 21, 22, 24, 25]
The time for 'f_heap_nsmallest on x' took: 0.5187360178679228.
Experiments on x_heap as heap :
[0, 1, 1, 4, 5, 5, 5, 6, 6, 7, 7, 7, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 18, 18, 19, 19, 21, 22, 24, 25]
The time for 'f_heap_pop on x_heap' took: 0.2054140530526638.
[0, 1, 1, 4, 5, 5, 5, 6, 6, 7, 7, 7, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 18, 18, 19, 19, 21, 22, 24, 25]
The time for 'f_heap_nsmallest on x_heap' took: 0.6638103127479553.
[ 1 5 5 1 0 4 5 6 7 6 7 7 12 12 11 13 11 12 13 18 10 14 10 18 19 19 21 22 24 25]
The time for 'f_np_partition on x_np' took: 0.2107151597738266.
"""