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

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

17 голосов
/ 24 мая 2019

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

Решение для кучи: 

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. Как это случилось? Теоретически все наоборот, не так ли?

Ответы [ 2 ]

26 голосов
/ 27 мая 2019

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

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

...

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

Итак, Big-O похож на:

enter image description here

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

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

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

enter image description here

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

enter image description here

Мы увидим, что на небольшом диапазоне 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 голосов
/ 02 июля 2019

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

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

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

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

...