Почему куча медленнее, чем сортировка для K ближайших точек к началу координат?

Задача кодирования здесь

Кучное решение:

import heapq
class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        return heapq.nsmallest(K, points, key = lambda P: P[0]**2 + P[1]**2)

Сортировка решения:

class Solution(object):
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        points.sort(key = lambda P: P[0]**2 + P[1]**2)
        return points[:K]

Согласно приведенному здесь объяснению, Python heapq.nsmallest - это O (n log (t)), а Python List.sort() - это O (n log (n)). Тем не менее, мои результаты показывают, что сортировка выполняется быстрее, чем heapq. Как это случилось? Теоретически, наоборот?

Ответ 1

Давайте выберем определение обозначения Big-O из Википедии:

Нотация Big O - это математическая нотация, которая описывает ограничивающее поведение функции, когда аргумент стремится к определенному значению или бесконечности.

...

В информатике большие обозначения O используются для классификации алгоритмов в зависимости от того, как растут их требования к времени выполнения или пространству с ростом размера входных данных.

Так что Big-O похож на:

Поэтому, когда вы сравниваете два алгоритма для небольших диапазонов/чисел, вы не можете сильно полагаться на Big-O. Давайте проанализируем пример:

У нас есть два алгоритма: первый O (1) и работает ровно 10000 тиков, а второй O (n ^ 2). Таким образом, в диапазоне 1 ~ 100 секунда будет быстрее первой (100^2 == 10000 поэтому (x<100)^2 < 10000). Но из 100 второй алгоритм будет медленнее, чем первый.

Подобное поведение есть в ваших функциях. Я рассчитал их с различной длиной ввода и построил временные графики. Вот время для ваших функций на больших числах (желтый - это sort, синий - это heap):

Вы можете видеть, что sort занимает больше времени, чем heap, и время увеличивается быстрее, чем heap's. Но если мы посмотрим ближе на более низкий диапазон:

Мы увидим, что на небольшом диапазоне sort выполняется быстрее, чем в heap ! Похоже, heap имеет "по умолчанию" потребление времени. Поэтому нет ничего плохого в том, что алгоритм с худшим Big-O работает быстрее, чем алгоритм с лучшим Big-O. Это просто означает, что их использование диапазона слишком мало для лучшего алгоритма, чтобы быть быстрее, чем худший.

Вот временной код для первого сюжета:

import timeit
import matplotlib.pyplot as plt

s = """
import heapq
def k_heap(points, K):
    return heapq.nsmallest(K, points, key = lambda P: P[0]**2 + P[1]**2)

def k_sort(points, K):
    points.sort(key = lambda P: P[0]**2 + P[1]**2)
    return points[:K]
"""

random.seed(1)
points = [(random.random(), random.random()) for _ in range(1000000)]
r = list(range(11, 500000, 50000))
heap_times = []
sort_times = []
for i in r:
    heap_times.append(timeit.timeit('k_heap({}, 10)'.format(points[:i]), setup=s, number=1))
    sort_times.append(timeit.timeit('k_sort({}, 10)'.format(points[:i]), setup=s, number=1))

fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
#plt.plot(left, 0, marker='.')
plt.plot(r, heap_times, marker='o')
plt.plot(r, sort_times, marker='D')
plt.show()

Для второго сюжета заменить:

r = list(range(11, 500000, 50000))  -> r = list(range(11, 200))
plt.plot(r, heap_times, marker='o') -> plt.plot(r, heap_times)
plt.plot(r, sort_times, marker='D') -> plt.plot(r, sort_times)

Ответ 2

Это из-за реализации. Модуль heapq реализован на python. Функция list.sort использует реализацию алгоритма Timsort на языке C.

Мои тесты показывают, что подход на основе кучи медленнее, чем метод сортировки, и разница увеличивается только для больших N.

_{Код бенчмаркинга (сделан с perfplot)}

Ответ 3

Кажется, что heapq не реализует самый маленький алгоритм кучи... Из документации:

heapq.nsmallest(n, повторяемый, ключ = нет):

Вернуть список с n наименьшими элементами из набора данных, определенных с помощью iterable. Ключ, если он указан, определяет функцию с одним аргументом, которая используется для извлечения ключа сравнения из каждого элемента в итерируемом (например, key = str.lower). Эквивалентно: sorted (итерируемый, ключ = ключ) [: n].

Но вы можете сделать это самостоятельно:

import heapq
import numpy as np

N = 1_000_000
points=np.random.rand(N,2)
lpoints= [tuple(x) for x in points]

def nsmallest(lpoints,n):
    heap=[(x*x+y*y,x,y) for (x,y) in lpoints]
    heapq.heapify(heap) # build the heap,  O(N)
    res=[]
    for _ in range(n):
        d,x,y =heapq.heappop(heap)   # O(log(N))  
        res.append((x,y))
    return res

Это подтверждает превосходство k-наименьшего алгоритма кучи с большим N и небольшим n:

>>> sorted(lpoints,key = lambda P: P[0]**2 + P[1]**2)[:10] == nsmallest(lpoints,10)
True

>>> %timeit nsmallest(lpoints,10)
299 ms ± 940 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit sorted(lpoints,key = lambda P: P[0]**2 + P[1]**2)[:10]
945 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Ответ 4

Как уже говорилось, быстрая реализация сортировки с использованием tim sort в python является одним из факторов. Другим фактором здесь является то, что операции с кучей не так удобны для кэша, как сортировка слиянием и сортировка вставкой (сортировка tim является гибридом этих двух).

Операции с кучей обращаются к данным, хранящимся в удаленных индексах.

Python использует 0-индексированный массив для реализации своей библиотеки кучи. Таким образом, для значения kth индексы его дочерних узлов равны k * 2 + 1 и k * 2 + 2.

Каждый раз, когда вы выполняете операции перколирования вверх/вниз после добавления/удаления элемента в/из кучи, он пытается получить доступ к родительским/дочерним узлам, которые находятся далеко от текущего индекса. Это не подходит для кэша. По этой же причине сортировка в куче обычно выполняется медленнее, чем в быстрой, хотя асимптотически они одинаковы.