Эта статья возникла из личного публичного аккаунта:TechFlow, Оригинальность непроста, прошу внимания
Сегодняшняя статья знакомит с очень полезной библиотекой Python —heapq.
Полное написание heapq — очередь кучи, что означает очередь кучи. здеськуча и очередьВсе они являются структурами данных. Мы подробно расскажем о них в следующих статьях. Сегодня будет представлено только использование heapq. Если вы не понимаете принципов кучи и очереди, вы можете их игнорировать.
Прежде чем вводить использование, нам нужно знать определение приоритетной очереди.очередьКаждый должен быть с ней знаком, и это также очень простая и простая структура данных. Мы можем представить, что все элементы в очереди выстроены в ряд, новые элементы могут быть добавлены в очередь только с конца очереди, а элементы могут быть исключены из очереди только через начало очереди.Не могу выйти из очереди на полпути. Очередь приоритетов предназначена для установки приоритета для каждого элемента в очереди, так что элементы в очереди будутАвтоматически сортировать по приоритету, тот, у которого более высокий приоритет, указан первым.
Другими словами, heapq в Python — это библиотека, поддерживающая приоритетную очередь, и мы можем легко реализовать функцию приоритетной очереди, вызвав ее.
наибольший или наименьший элемент K
Давайте рассмотрим практическую задачу Предположим, что в данный момент у нас есть N случайных элементов, но нас интересуют только K наибольшего или K наименьшего элемента. Мы хотим извлечь эту часть из всего массива, что нам делать?
Эта проблема очень распространена на практике, и примеры можно привести вскользь. Например, пользователь вводит поисковый запрос, и мы находим много контента на основе поискового запроса пользователя. Мы хотим отфильтровать текст, который пользователь, скорее всего, нажмет, на основе алгоритма, а модель машинного обучения может дать каждому тексту прогнозируемый балл. После этого нам нужноВыберите K результатов с наивысшими баллами. Подобных сценариев много, и очень удобно использовать интерфейсы nlargest и nsmalest в библиотеке heapq.
Давайте посмотрим на пример:
import heapq
nums = [14, 20, 5, 28, 1, 21, 16, 22, 17, 28]
heapq.nlargest(3, nums)
# [28, 28, 22]
heapq.nsmallest(3, nums)
# [1, 5, 14]
nlargest и nsmalest из heapq принимают два параметра, первый параметр — K, то есть количество возвращаемых элементов, а второй параметр — входящий массив.
Вот вопрос, а что если элемент в нашем массиве является объектом? То, что должно быть сделано?
На самом деле, это также очень просто.Учащиеся, знакомые с пользовательской сортировкой ключевых слов Python, должны знать, что, как и сортировка, мы можем передатьанонимная функциявыполнить.
анонимная функция
Все мы знаем, что функцию в Python можно определить с помощью def. Функции, определенные с помощью def, имеют имена функций, поэтому они называютсяименованная функция. В дополнение к именованным функциям Python также поддерживает анонимные функции. Как следует из названия, это функция без имени функции. Другими словами, это то же самое, что и обычная функция в других отношениях, но без имени.
Новички могут задаться вопросом,Как вызвать функцию без имени?
Такое сомнение нормально, потому что вы привыкли к процессно-ориентированному программированию и не имеете глубокого понимания объектно-ориентированного программирования. Во многих языках высокого уровнявсе является объектом, класс, функция и int — все это объекты. Поскольку функции также являются объектами, функции, естественно, также могут использоваться для передачи, не только для передачи, но и для возврата. Это концепция функционального программирования, здесь мы не будем углубляться.
Конечно, можно передавать и обычные функции, и эффект тот же. Просто в программировании некоторые функции мы используем только один раз,Нет необходимости определять отдельную функцию, использование анонимных функций может быть очень удобным.
В качестве примера, скажем, у меня есть такая функция:
def operate(x, func):
return func(x)
Эта рабочая функция принимает два параметра, первый параметр — переменная x, второй параметр — переменная x.параметр является функцией. Он вызовет func внутри функции и вернет результат вызова func. Я хочу сделать это сейчас, я надеюсь судить, какую функцию следует использовать в соответствии с остатком от целого числа от x до 4. Если остаток до 4 равен 0, я хочу возвести его в квадрат, если остаток равен 2, я хочу возвести его в квадрат и так далее. Если мы будем следовать обычному методу, нам нужно реализовать 4 метода, а затем передавать их один за другим.
Это конечно возможно, но очень громоздко, если использовать анонимные функции, то можносильно упрощенныйКоличество кода:
def get_result(x):
if x % 4 == 0:
return operate(x, lambda x: x)
elif x % 4 == 1:
return operate(x, lambda x: x ** 2)
elif x % 4 == 2:
return operate(x, lambda x: x ** 3)
else:
return operate(x, lambda x: x ** 4)
В приведенном выше кодеМы определяем анонимную функцию с помощью ключевого слова lambda, что позволяет избежать ситуации, когда для передачи определены четыре функции. Конечно, есть более простые способы написать эту задачу, которую можно решить с помощью всего одной функции.
Давайте посмотрим на синтаксис lambda для определения анонимной функции.Первым является ключевое слово lambda, которое означает, что мы в настоящее время определяем анонимную функцию. После параметров этой анонимной функции мы используем только одну переменную x, поэтому нам нужно написать только один x. Если нам нужно использовать несколько параметров, разделенных запятыми, конечно, нельзя использовать никакие параметры. После записи параметров мы разделяем их двоеточиями, а возвращаемые результаты записываются после двоеточий.
Мы также можем присвоить переменной анонимную функцию, а затем вызвать ее как обычную функцию:
square = lambda x: x ** 2
print(square(3))
print(operate(3, square))
пользовательская сортировка
Возвращаясь к предыдущему содержимому, если мы хотим, чтобы heapq сортировал объект. Затем heapq не знает, какой параметр в объекте следует использовать в качестве критерия для сортировки, поэтому в настоящее время нам нужно использовать собственныйОпределите функцию для получения ключевого слова, передается в heapq, чтобы можно было выполнить сортировку.
Например, теперь у нас есть коллекция компьютеров, и мы хотим, чтобы heapq отсортировал их по цене:
laptops = [
{'name': 'ThinkPad', 'amount': 100, 'price': 91.1},
{'name': 'Mac', 'amount': 50, 'price': 543.22},
{'name': 'Surface', 'amount': 200, 'price': 21.09},
{'name': 'Alienware', 'amount': 35, 'price': 31.75},
{'name': 'Lenovo', 'amount': 45, 'price': 16.35},
{'name': 'Huawei', 'amount': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
При вызове nlargest и nsmallest мы передаем дополнительный ключ параметра, мы передаем анонимную функцию, и результат, который она возвращает, — это цена объекта, то есть мы хотим, чтобы heapq сортировался в соответствии с ценой объекта.
приоритетная очередь
Помимо возврата максимального и минимального числа K, heapq также реализует интерфейс приоритетной очереди. Мы можем напрямую вызвать метод heapq.heapify, ввести массив, а возвращаемый результат — это куча (эквивалент приоритетной очереди), созданная на основе этого массива.
Конечно, мы также можем начать с нуля и напрямую поддерживать кучу, вызывая push и pop из heapq. Далее будем самостоятельно реализовывать приоритетную очередь через heapq.Код очень простой.Я думаю каждый должен уметьнаучиться мгновенно.
Первая — это часть, которая реализует приоритетную очередь:
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index =0
def push(self, item, priority):
# 传入两个参数，一个是存放元素的数组，另一个是要存储的元素，这里是一个元组。
# 由于heap内部默认有小到大排，所以对priority取负数
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
Далее, давайте взглянем на фактическое приложение:
q = PriorityQueue()
q.push('lenovo', 1)
q.push('Mac', 5)
q.push('ThinkPad', 2)
q.push('Surface', 3)
q.pop()
# Mac
q.pop()
# Surface
На данный момент применение heapq было представлено, но на самом деле это не закончилось.
Нам нужно проанализировать сложность операций в heapq. Давайте пока пропустим часть с кучей. Давайте сначала посмотрим на nlargest и nsmalest. Я нашел эту библиотеку в githubисходный код, в аннотации метода автор пишет сложность метода, аПосле сортировки берем первые K накладных расходов:
def nlargest(n, iterable, key=None):
"""Find the n largest elements in a dataset.
Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
"""
Мы все знаем, что ожидаемая сложность сортировки
, если вы разбираетесь в куче, то будете знать, что сложность вставки элемента в кучу за раз составляет
. Если мы ограничим длину кучи до K, мы сможем сохранить K элементов только после вставки n раз. Сложность каждой вставки
, всего вставляется n раз, поэтому общая сложность равна
.
Если K меньше, накладные расходы могут быть немного меньше, чем при сортировке, но в ограниченной степени. Итак, есть ли способ как можно быстрее отфильтровать верхние K больших или верхние K маленьких элементов без сортировки?
Сначала я продам его здесь, и мы объясним это в следующей статье.
На сегодняшней статье все.Если вы чувствуете, что я что-то добился, обратите на это внимание.Ваши усилия очень важны для меня.
использованная литература
Python CookBook Version3
Википедия