Упрощение алгоритмов и структур данных
В этой статье я объясню вам одну из проблем, с которой вы можете столкнуться при решении вопросов, касающихся структур данных и алгоритмов. Вам потребуются некоторые базовые знания структур данных, чтобы понять оптимизированное решение проблемы. Код в этой статье будет основан на Python (обратите внимание, что Python имеет нулевой индекс)!
Сложность: ❤️️️❤️️💛
Ингредиент: приоритетная очередь (или куча)
В какой-то момент своей жизни вы могли столкнуться с вопросом о алгоритмах и структурах данных, который звучит примерно так:
Учитывая неупорядоченный (несортированный) массив координат и значение k, найдите k -ю ближайшую точку к началу координат. Указанные координаты могут быть в одномерном, двухмерном или трехмерном пространстве.
Например, если у вас есть массив 2D-координат,
[ (1,2), (1,0), (9,8), (6,8), (3,3) ]
а также учитывая значение k,
k = 3
Вы должны найти 3-й набор координат, ближайший к началу координат (0, 0). Давайте подойдем к этому шаг за шагом.
Грубая сила
Один из возможных вопросов, который вы можете задать себе, вместо k -го элемента, как мне получить 1-й элемент, ближайший к источнику (где k = 1)? Чтобы упростить задачу, что, если мне даны 1D координаты вместо 2D или 3D?
Например, учитывая следующий массив
[ 2, 3, 1, 5, 7, 6]
Как мне получить значение, наиболее близкое к исходному 0 (с точки зрения непрофессионала, наименьшее значение) для одномерного случая? Это можно сделать двумя разными способами:
- Отсортируйте массив от наименьшего к наибольшему значению и выберите первое значение, или
- Просмотрите каждый элемент в массиве и запишите самый маленький, который вы видели. Это так же хорошо, как запомнить количество k элементов, ближайших к исходному положению, и при необходимости заменить их.
Оба решения действительно работают! Но есть заметная разница в сложности времени выполнения и сложности пространства (см. Нотация Big O ).
Грубая сила - метод 1: сортировка
В первом методе все очень просто. Вы сортируете массив,
[ 1, 2, 3, 5, 6, 7]
И чтобы получить наименьший элемент (k = 1), просто получите элемент с индексом 0. А как насчет второго (k = 2) элемента? Это будет элемент с индексом 1.
Код (написанный как функция) будет выглядеть примерно так:
def kthClosestPoint(k: int, array: list): if k < 1: raise Exception('Invalid k') return sorted(array)[k-1]
В зависимости от алгоритма сортировки типичная сложность выполнения будет O (n log n). В отличие от приведенного выше кода, который получает новый отсортированный массив за капотом, который даст вам пространственную сложность O (n), если вы выполните сортировку на месте, у вас будет пространственная сложность O (1) вместо этого.
Но есть ли возможность дальнейшего улучшения этого метода с точки зрения сложности выполнения? Возможно нет.
Грубая сила - метод 2: запомнить количество элементов k
Теперь, вместо сортировки, что, если вы просто отслеживаете k количества элементов, ближайших к источнику?
Вернемся к тому же одномерному примеру и при k = 1,
[ 2, 3, 1, 5, 7, 6]
Вы будете брать каждый элемент в массиве один за другим и запоминать самые маленькие, которые вы видели до сих пор! Точно так же для k = 2 вы запомните только 2 наименьших из увиденных.
Теперь, если вы знакомы с очередью приоритетов или очередью кучи (я буду использовать heapq для Python), тогда вы поймете, что на самом деле вы можете использовать эту структуру данных для получения k самые маленькие элементы.
import heapq def kthClosestPoint(k: int, array: list): if k < 1: raise Exception('Invalid k') # Convert array into heap heapq.heapify(array) return heapq.nsmallest(k, array)
Если длина вашего массива (также известная как очередь кучи) n, при использовании этого метода вы получите худшую сложность времени выполнения O (n log n), поскольку нажатие а для извлечения элемента в кучу требуется O (log n). Сложность пространства составляет O (n), если вы дублируете массив или в этом примере кода, O (1), поскольку я делаю это на месте.
Оптимизация
Фактически вы можете еще больше улучшить сложность выполнения этого метода, ограничив очередь кучи k вместо всей длины массива n:
import heapq def kthClosestPoint(k: int, array: list): if k < 1: raise Exception('Invalid k') k_elements = [] for num in array: heappush(k_elements, -num) if len(k_elements) > k: heappop(k_elements) return [-num for num in k_elements]
Обратите внимание, что, поскольку heappop удаляет только самый маленький элемент, одна из возможностей состоит в том, чтобы инвертировать полярность элементов, т.е. положительные целые числа будут отрицательными, а отрицательные целые числа будут положительными. Это приведет к тому, что все большие целые числа будут казаться маленькими, поэтому из очереди кучи будут удалены только большие целые числа.
Типичная сложность выполнения будет O (n log k), так как вы будете загружать и загружать каждый отдельный элемент массива, в то время как длина очереди кучи не превышает k . Это так же плохо, как и худший сценарий!
Дальнейшая оптимизация
Можем ли мы улучшить это для типичного случая? Можем ли мы проверить, прежде чем делать это, вместо того, чтобы помещать каждый элемент в очередь кучи и удалять их? Да мы можем!
Если у нас уже есть очередь кучи размером k, мы должны взглянуть на «самый большой» элемент в очереди кучи и посмотреть, больше или меньше наш текущий элемент , перед тем, как мы вставим элемент. Если очередь кучи все еще меньше длины k, мы можем продолжать вставлять в нее элементы!
import heapq def kthClosestPoint(k: int, array: list): if k < 1: raise Exception('Invalid k') k_elements = [] for num in array: if len(k_elements) < k or k_elements[0] < -num: heappush(k_elements, -num) if len(k_elements) > k: heappop(k_elements) return [-num for num in k_elements]
Точно так же, если вы имеете дело с 2D или даже с 3D данными, вы можете изменить этот код, чтобы приспособить их, используя тот же самый метод.
Решение для 2D-данных
Предполагая, что у вас есть точки данных в массиве, который выглядит следующим образом:
[ (1, 2), (3, 5), (6, 7)]
Расстояние для каждой точки до начала координат (0, 0) просто выражается с помощью теоремы Пифагора в ее сокращенной форме:
distance = x**2 + y**2
Ничто не сравнится с внешним видом кода, поэтому, изменив предыдущий одномерный код:
import heapq def kthClosestPoint(k: int, array: list): if k < 1: raise Exception('Invalid k') k_elements = [] for x, y in array: dist = x**2, y**2 if len(k_elements) < k or k_elements[0][0] < -dist: heappush(k_elements, (-dist, x, y)) if len(k_elements) > k: heappop(k_elements) return [[x, y] for dist, x, y in k_elements]
Если у вас есть какие-либо отзывы или что-то, чем вы хотите поделиться, не стесняйтесь оставлять комментарии 👇!