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

Question

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

Решение кучи:

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]

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

Answer 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)

Answer 2

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

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

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

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