Упрощение алгоритмов и структур данных

В этой статье я объясню вам одну из проблем, с которой вы можете столкнуться при решении вопросов, касающихся структур данных и алгоритмов. Вам потребуются некоторые базовые знания структур данных, чтобы понять оптимизированное решение проблемы. Код в этой статье будет основан на 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 (с точки зрения непрофессионала, наименьшее значение) для одномерного случая? Это можно сделать двумя разными способами:

  1. Отсортируйте массив от наименьшего к наибольшему значению и выберите первое значение, или
  2. Просмотрите каждый элемент в массиве и запишите самый маленький, который вы видели. Это так же хорошо, как запомнить количество 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]

Если у вас есть какие-либо отзывы или что-то, чем вы хотите поделиться, не стесняйтесь оставлять комментарии 👇!