Списки: срезы и методы

Как работает Быстрая сортировка

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

Подумайте об этом на мгновение — как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку — случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.

Самый простой подход — просто выбрать первый (или последний) элемент. По иронии судьбы, это приводит к быстрой сортировке на уже отсортированных (или почти отсортированных) массивах.

Именно так большинство людей выбирают реализацию быстрой сортировки, и, так как это просто и этот способ выбора опоры является очень эффективной операцией, и это именно то, что мы будем делать.

Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

Цель состоит в том, чтобы переместить элементы так, чтобы все элементы, меньшие, чем опора, находились слева от него, а все более крупные элементы были справа от него. Меньшие и большие элементы не обязательно будут отсортированы, мы просто хотим, чтобы они находились на правильной стороне оси. Затем мы рекурсивно проходим левую и правую сторону оси.

Рассмотрим пошагово то, что мы планируем сделать, это поможет проиллюстрировать весь процесс. Пусть у нас будет следующий список.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

Выберем первый элемент как опору 29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

• Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
• Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
• Мы меняем местами low и high:

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

• Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
• Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
• Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44

Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона). И так далее.

Функции, которые когда-нибудь можно выучить

Следующие встроенные функции Python определённо не бесполезны, но они более специализированы.

Эти функции вам, возможно, будут нужны, но также есть шанс, что вы никогда не прибегнете к ним в своём коде.

• : возвращает итератор (список, набор и т. д.);
• : возвращает , если аргумент является вызываемым;
• and : вместо них рекомендуется использовать генератор-выражения;
• : округляет число;
• : эта функция выполняет деление без остатка () и операцию по модулю () одновременно;
• , и : служат для отображения чисел в виде строки в двоичной, восьмеричной или шестнадцатеричной форме;
• : возвращает абсолютное значение числа (аргумент может быть целым или числом с плавающей запятой, если аргумент является комплексным числом, его величина возвращается);
• ;
• .

Предварительное использование key в функции сортировки

До сих пор нашими ключевыми функциями были простые считыватели атрибутов, но они также могут вычислять значения для сортировки. Давайте взглянем на еще один пример. На этот раз мы определим класс Snake:

У нашей змеи есть имя, toxicity (токсичность, мерило того, насколько токсичен её яд) и agression (представленная в виде числа от 0 до 1, которое указывает на вероятность того, что змея нападет).

Теперь предположим, что мы можем подсчитать, насколько опасная змея, основываясь на показателях токсичности и агрессивности, и можем отсортировать список змей по степени их опасности:

Змеи отсортированы в ожидаемом нами порядке (несмотря на то, что гремучая змея (rattlesnake) более ядовита, чем кобра (kingCobra), уровень агрессивности кобры делает её более опасной).

Что такое списки?

Списки в Python — упорядоченные изменяемые коллекции объектов произвольных типов (почти как массив, но типы могут отличаться).

Чтобы использовать списки, их нужно создать. Создать список можно несколькими способами. Например, можно обработать любой итерируемый объект (например, строку) встроенной функцией list:

>>> list('список')

Список можно создать и при помощи литерала:

>>> s = []  # Пустой список
>>> l = 's', 'p', 'isok'], 2
>>> s
[]
>>> l
, 2]

Как видно из примера, список может содержать любое количество любых объектов (в том числе и вложенные списки), или не содержать ничего.

И еще один способ создать список — это генераторы списков. Генератор списков — способ построить новый список, применяя выражение к каждому элементу последовательности. Генераторы списков очень похожи на цикл for.

>>> c = c * 3 for c in 'list'
>>> c

Возможна и более сложная конструкция генератора списков:

>>> c = c * 3 for c in 'list' if c != 'i'
>>> c

>>> c = c + d for c in 'list' if c != 'i' for d in 'spam' if d != 'a'
>>> c

Python Tutorial

Python HOMEPython IntroPython Get StartedPython SyntaxPython CommentsPython Variables
Python Variables
Variable Names
Assign Multiple Values
Output Variables
Global Variables
Variable Exercises

Python Data TypesPython NumbersPython CastingPython Strings
Python Strings
Slicing Strings
Modify Strings
Concatenate Strings
Format Strings
Escape Characters
String Methods
String Exercises

Python BooleansPython OperatorsPython Lists
Python Lists
Access List Items
Change List Items
Add List Items
Remove List Items
Loop Lists
List Comprehension
Sort Lists
Copy Lists
Join Lists
List Methods
List Exercises

Python Tuples
Python Tuples
Access Tuples
Update Tuples
Unpack Tuples
Loop Tuples
Join Tuples
Tuple Methods
Tuple Exercises

Python Sets
Python Sets
Access Set Items
Add Set Items
Remove Set Items
Loop Sets
Join Sets
Set Methods
Set Exercises

Python Dictionaries
Python Dictionaries
Access Items
Change Items
Add Items
Remove Items
Loop Dictionaries
Copy Dictionaries
Nested Dictionaries
Dictionary Methods
Dictionary Exercise

Python If…ElsePython While LoopsPython For LoopsPython FunctionsPython LambdaPython ArraysPython Classes/ObjectsPython InheritancePython IteratorsPython ScopePython ModulesPython DatesPython MathPython JSONPython RegExPython PIPPython Try…ExceptPython User InputPython String Formatting

Потребление памяти при сортировке в Python

Рассмотрим подробнее наш Python скрипт:

Python

# memory_measurement/main.py

import random
import resource
import sys
import time

from sniffing import FunctionSniffingClass

def list_sort(arr):
return arr.sort()

def sorted_builtin(arr):
return sorted(arr)

if __name__ == «__main__»:
if len(sys.argv) != 2:
sys.exit(«Please run: python (sort|sorted)»)
elif sys.argv == «sorted»:
func = sorted_builtin
elif sys.argv == «sort»:
func = list_sort
else:
sys.exit(«Please run: python (sort|sorted)»)

# код теста Lib
arr =
mythread = FunctionSniffingClass(func, arr)
mythread.start()

used_mem = 0
max_memory = 0
memory_usage_refresh = .005 # Секунды

while(1):
time.sleep(memory_usage_refresh)
used_mem = (resource.getrusage(resource.RUSAGE_SELF).ru_maxrss)
if used_mem > max_memory:
max_memory = used_mem

# Проверяет, завершен ли вызов функции
if mythread.isShutdown():
# Уберите знак комментария, если вы хотите увидеть результат
# print(mythread.results)
break;

print(«\nMAX Memory Usage:», round(max_memory / (2 ** 20), 3), «MB»)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

# memory_measurement/main.py   importrandom importresource importsys importtime fromsniffing importFunctionSniffingClass deflist_sort(arr) returnarr.sort() defsorted_builtin(arr) returnsorted(arr) if__name__==»__main__» iflen(sys.argv)!=2 sys.exit(«Please run: python (sort|sorted)») elifsys.argv1==»sorted» func=sorted_builtin elifsys.argv1==»sort» func=list_sort else sys.exit(«Please run: python (sort|sorted)») # код теста Lib arr=random.randint(,50)forrinrange(1_000_000) mythread=FunctionSniffingClass(func,arr) mythread.start() used_mem= max_memory= memory_usage_refresh=.005# Секунды while(1) time.sleep(memory_usage_refresh) used_mem=(resource.getrusage(resource.RUSAGE_SELF).ru_maxrss) ifused_mem>max_memory max_memory=used_mem # Проверяет, завершен ли вызов функции ifmythread.isShutdown() # Уберите знак комментария, если вы хотите увидеть результат # print(mythread.results) break; print(«\nMAX Memory Usage:»,round(max_memory(2**20),3),»MB»)

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

Интересно, как все работает? Посмотрим!

Shell

$ python memory_measurement/main.py sort
Calling the Target Function…
Function Call Complete

MAX Memory Usage: 23.371 MB

$ python memory_measurement/main.py sorted
Calling the Target Function…
Function Call Complete

MAX Memory Usage: 30.879 MB

1 2 3 4 5 6 7 8 9 10 11

$python memory_measurementmain.pysort Calling the Target Function… FunctionCall Complete MAX Memory Usage23.371MB $python memory_measurementmain.pysorted Calling the Target Function… FunctionCall Complete MAX Memory Usage30.879MB

Как видите, функция потребляет примерно на 32% больше памяти, чем метод . Этого следовало ожидать, так как последний вариант изменяет список на месте, тогда как первый всегда создают отдельный список.

Key Functions¶

Both and have a key parameter to specify a
function (or other callable) to be called on each list element prior to making
comparisons.

For example, here’s a case-insensitive string comparison:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)

The value of the key parameter should be a function (or other callable) that
takes a single argument and returns a key to use for sorting purposes. This
technique is fast because the key function is called exactly once for each
input record.

A common pattern is to sort complex objects using some of the object’s indices
as keys. For example:

>>> student_tuples = 
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... 
>>> sorted(student_tuples, key=lambda student student2])   # sort by age

The same technique works for objects with named attributes. For example:

>>> class Student
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

Старый способ использования параметра cmp

Многие конструкции, приведенные в этом HOWTO, предполагают Python 2.4 или новее. До этого не было встроенных функций и c аргументами ключевых слов. Вместо этого все версии Py2.x поддерживали параметр для обработки заданных пользователем функций сравнения.

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

В Py2.x сортировка допускает необязательную функцию, которая может быть вызвана для сравнения. Эта функция должна принимать два аргумента для сравнения, а затем возвращать отрицательное значение для «меньше», возвращать ноль, если они равны, или возвращать положительное значение для «больше». Например, мы можем:

>>> def numeric_compare(x, y):
...    return x - y

>>> sorted(, cmp=numeric_compare) 

Или вы можете изменить порядок сравнения:

>>> def reverse_numeric(x, y):
...    return y - x

>>> sorted(, cmp=reverse_numeric) 

При переносе кода с Python 2.x на 3.x может возникнуть ситуация, когда у вас есть пользователь, предоставляющий функцию сравнения, и вам нужно преобразовать ее в ключевую функцию. Следующая оболочка упрощает это:

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj)  0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) = 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

Чтобы преобразовать в ключевую функцию, просто оберните старую функцию сравнения:

>>> sorted(, key=cmp_to_key(reverse_numeric))

В Python 3.2 функция была добавлена ​​в модуль в стандартной библиотеке.

Старый способ с использованием параметра cmp

Многие из приведённых здесь примеров подразумевают использование Python версии 2.4 и выше. До этой версии не было функции , а не принимал ключевых аргументов. Вместо этого все версии Python 2.x поддерживали параметр для обработки пользовательских функций сравнения.

В Python 3.0 от этого параметра полностью избавились в целях упрощения языка и разрешения конфликта между операторами сравнения и методами .

В Python 2.x в можно было передать функцию, которая использовалась бы для сравнения элементов. Она должна принимать два аргумента и возвращать отрицательное значение для случая «меньше чем», положительное — для «больше чем» и ноль, если они равны. Например:

Можно сравнивать в обратном порядке:

При портировании кода с версии 2.x на 3.x может возникнуть ситуация, когда нужно преобразовать пользовательскую функцию для сравнения в функцию-ключ. Следующая обёртка упрощает эту задачу:

Чтобы произвести преобразование, просто оберните старую функцию:

В Python 2.7 функция была добавлена в модуль functools.

Основы сортировки

Сделать обычную сортировку по возрастанию очень просто — достаточно вызвать функцию , которая вернёт новый отсортированный список:

Также можно использовать метод списков , который изменяет исходный список (и возвращает во избежание путаницы). Обычно это не так удобно, как использование , но если вам не нужен исходный список, то так будет немного эффективнее:

Прим.перев. В Python вернуть и не вернуть ничего — одно и то же.

Ещё одно отличие заключается в том, что метод определён только для списков, в то время как работает со всеми итерируемыми объектами:

Прим.перев. При итерировании по словарю Python возвращает его ключи. Если вам нужны их значения или пары «ключ-значение», используйте методы и соответственно.

Прочее

Для сортировки с учётом языка используйте в качестве ключевой функции или в качестве функции сравнения.

Параметр всё ещё сохраняет стабильность сортировки. Что интересно, этот эффект можно сымитировать без параметра, использовав встроенную функцию дважды:

Чтобы создать стандартный порядок сортировки для класса, просто добавьте реализацию соответствующих методов сравнения:

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

Функциям-ключам не нужен доступ к внутренним данным сортируемых объектов. Они также могут осуществлять доступ к внешним ресурсам. Например, если оценки ученика хранятся в словаре, их можно использовать для сортировки отдельного списка с именами учеников:

Поддержание порядка сортировки

В стандартной библиотеке Python нет модулей, аналогичных типам данных C++ вроде и . Это осознанное решение Гвидо и других для сохранения «единственного очевидного способа сделать это». Python делегирует эту задачу сторонним библиотекам, доступным в Python Package Index. Эти библиотеки используют различные методы для сохранения типов , и в отсортированном порядке. Поддержание порядка с помощью специальной структуры данных может помочь избежать очень медленного поведения (квадратичного времени выполнения) при наивном подходе с редактированием и постоянной пересортировкой данных. Вот некоторые из модулей, реализующих эти типы данных:

• SortedContainers — реализация сортированных типов , и на чистом Python, по скорости не уступает реализациям на Си. Тестирование включает 100% покрытие кода и многие часы стресс-тестирования. В документации можно найти полный справочник по API, сравнение производительности и руководства по внесению своего вклада.
• rbtree — быстрая реализация на Си для типов и . Реализация использует структуру данных, известную как красно-чёрное дерево.
• treap — сортированный . В реализации используется Декартово дерево, а производительность улучшена с помощью Cython.
• bintrees — несколько реализаций типов и на основе деревьев на Си. Самые быстрые основаны на АВЛ и красно-чёрных деревьях. Расширяет общепринятый API для предоставления операций множеств для словарей.
• banyan — быстрая реализация и на Си.
• skiplistcollections — реализация на чистом Python, основанная на списках с пропусками, предлагает ограниченный API для типов и .
• blist — предоставляет сортированные типы , и , основанные на типе данных «blist», реализация на Б-деревьях. Написано на Python и Си.

Стабильность сортировки и сложные сортировки

Сортировки гарантированно . Это означает, что когда несколько записей имеют один и тот же ключ, их исходный порядок сохраняется.

>>> data = 
>>> sorted(data, key=itemgetter(0))

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

Например, чтобы отсортировать данные учащиеся по убыванию класса, а затем по возрастанию возраста, сделать возраст своего рода первым, а затем сортировать снова используя класс:

Это замечательное свойство позволяет создавать сложные сортировки в несколько этапов. Например, чтобы отсортировать данные учащиеся по убыванию класса, а затем по возрастанию возраста, сделать возраст своего рода первым, а затем сортировать снова используя класс:

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending

Можно абстрагировать все это в функцию-оболочку, которая может принимать список и кортежи поля и упорядочивать их за нескольких проходах.

>>> def multisort(xs, specs):
...    for key, reverse in reversed(specs):
...        xs.sort(key=attrgetter(key), reverse=reverse)
...    return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))

Как перебрать значения списка в Python?

Python позволяет использовать цикла for со списками:

Индекс текущего элемента в цикле можно получить используя функцию enumerate:

Так же, можно проходить по списку используя функцию range. Range генерирует ряд чисел в рамках заданного диапазона, соответственно началом диапазона является число 0 (индекс первого элемента), а концом индекс последнего элемента. Len возвращает длину списка, так как индекс первого элемента является нулем, вычитать из длины списка единицу не нужно, индекс последнего элемента будет соответствовать длине списка:

Ранее отмечалось, что списки являются изменяемой (или иммютабельной, от англ. immutable) структурой данных. Это означает, что если изменить список во время итерации, мы можем получить неожиданные результаты, например:

В примере мы удалили первый элемент на первой итерации изменив список, что привело к пропуску bar. На второй итерации, baz стал вторым элементом списка.

Алгоритм быстрой сортировки

Этот алгоритм также использует разделяй и стратегию завоюйте, но использует подход сверху вниз вместо первого разделения массива вокруг шарнирного элемента (здесь, мы всегда выбираем последний элемент массива будут стержень).

Таким образом гарантируется, что после каждого шага точка поворота находится в назначенной позиции в окончательном отсортированном массиве.

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

def quicksort(a, arr_type):
    def do_partition(a, arr_type, start, end):
        # Performs the partitioning of the subarray a
        
        # We choose the last element as the pivot
        pivot_idx = end
        pivot = a

        # Keep an index for the first partition
        # subarray (elements lesser than the pivot element)
        idx = start - 1

        def increment_and_swap(j):
            nonlocal idx
            idx += 1
            a, a = a, a

         < pivot]
        
        # Finally, we need to swap the pivot (a with a)
        # since we have reached the position of the pivot in the actual
        # sorted array
        a, a = a, a

        # Return the final updated position of the pivot
        # after partitioning
        return idx+1

    def quicksort_helper(a, arr_type, start, end):
        if start < end:
            # Do the partitioning first and then go via
            # a top down divide and conquer, as opposed
            # to the bottom up mergesort
            pivot_idx = do_partition(a, arr_type, start, end)
            quicksort_helper(a, arr_type, start, pivot_idx-1)
            quicksort_helper(a, arr_type, pivot_idx+1, end)

    quicksort_helper(a, arr_type, 0, len(a)-1)

Здесь метод выполняет шаг подхода Divide and Conquer, в то время метод разделяет массив вокруг точки поворота и возвращает позицию точки поворота, вокруг которой мы продолжаем рекурсивно разбивать подмассив до и после точки поворота, пока не будет весь массив отсортирован.

Прецедент:

b = array.array('i', )
print('Before QuickSort ->', b)
quicksort(b, 'i')
print('After QuickSort ->', b)

Вывод:

Before QuickSort -> array('i', )
After QuickSort -> array('i', )

Алгоритм MergeSort

Алгоритм использует восходящий подход Divide and Conquer, сначала разделяя исходный массив на подмассивы, а затем объединяя индивидуально отсортированные подмассивы, чтобы получить окончательный отсортированный массив.

В приведенном ниже фрагменте кода метод выполняет фактическое разделение на подмассивы, а метод perform_merge() объединяет два ранее отсортированных массива в новый отсортированный.

import array

def mergesort(a, arr_type):
    def perform_merge(a, arr_type, start, mid, end):
        # Merges two previously sorted arrays
        # a and a
        tmp = array.array(arr_type, )
        def compare(tmp, i, j):
            if tmp <= tmp:
                i += 1
                return tmp
            else:
                j += 1
                return tmp
        i = start
        j = mid + 1
        curr = start
        while i<=mid or j<=end:
            if i<=mid and j<=end:
                if tmp <= tmp:
                    a = tmp
                    i += 1
                else:
                    a = tmp
                    j += 1
            elif i==mid+1 and j<=end:
                a = tmp
                j += 1
            elif j == end+1 and i<=mid:
                a = tmp
                i += 1
            elif i > mid and j > end:
                break
            curr += 1


    def mergesort_helper(a, arr_type, start, end):
        # Divides the array into two parts
        # recursively and merges the subarrays
        # in a bottom up fashion, sorting them
        # via Divide and Conquer
        if start < end:
            mergesort_helper(a, arr_type, start, (end + start)//2)
            mergesort_helper(a, arr_type, (end + start)//2 + 1, end)
            perform_merge(a, arr_type, start, (start + end)//2, end)


    # Sorts the array using mergesort_helper
    mergesort_helper(a, arr_type, 0, len(a)-1)

Прецедент:

a = array.array('i', )
print('Before MergeSort ->', a)
mergesort(a, 'i')
print('After MergeSort ->', a)

Вывод:

Before MergeSort -> array('i', )
After MergeSort -> array('i', )

Красивый Питон — часть 4. Словари в Python.

• 3.05.2016
• Python
• идиомы python

Это четвертый пост об идиомах в Питона. Теперь пришло время узнать, что же такое словари в Python. Вы наверняка знаете, что это такая структура данных, тип которой обычно обозначают как dict. Пост же несколько подробнее расскажет о словарях: о том, как их перебирать или получать значение по ключу.

Работа со словарями Python

Вообще, словарями в Python называют коллекции произвольных объектов с доступом по ключу. При этом коллекции неупорядоченные. По-другому словари можно называть ассоциативными массивами или хеш-таблицами. Словарь может выглядеть, например, так:

dict = {'ключ1': 1, 'ключ2': 2}

Конечно же, существует куча способов работы со словарями, и все они не поместятся в этот пост. Но некоторые полезные идиомы, пожалуй, стоит упомянуть.

Цикл по ключам словаря Python

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

Наверняка вы будете часто использовать такую операцию, поэтому стоит обратить внимание на правильный и красивый способ ее выполнения

#Не перебирайте ключи так
for k in dic.keys():
    print(k)
    
#Делайте это так
for k in dic:
    print(k)

Как видите. для цикла по ключам словаря не нужно использовать метод dictionary.keys(). Все что нужно — это ссылка на словарь.

Цикл по паре ключ-значение Python

Еще одна нужная операция, которая почти всегда требуется при работе со словарями — это цикл по паре ключ:значение. Конечно же, в Python есть несколько быстрых и простых способ построить такой цикл.

#цикл можно построить так
for k in dic:
    print(k)
    print(dic)

#или вот так
for k, val in dic.items():
    print(k)
    print(val)

В примере показано два способа перебора пар ключ-значение в словаре. Первый перебирает ключи словаря, а значения извлекает по ключу. Второй пример пробегает по словарю, распаковывая ключи и значения в две переменные.

Использование dictionary.get() для получения значений

Если нужно получить значение по ключу, но при этом неизвестно, существует такой ключ или нет — используйте метод dictionary.get().

#Использование get() для получения значения
val = dic.get('key1', 'na')

Если ключ «key1» существует в словаре dic, то переменной будет присвоено значение в соответствии с ключом. В противном случае переменная получит значение второго аргумента функции get().

Удаление элементов из словаря Python по критериям

Вероятно, если бы перед вами встала такая задача, то в мыслях сразу бы возникли циклы и условные операторы. Но в Питоне все это не требуется! Смотрите:

#Удаление элементов из словаря по критериям
dic = {k : dic for k in dic if not len(k) < 5}

Синтаксис очень простой:  {ключ : значение for ключ in словарь }. Пример выше создаст новый словарь, которые содержит все пары ключ-значение, в которых ключ имеет длину менее 5.

Объединение двух списков в словарь

Например, у вас есть список имен и список фамилий. Но вы хотите иметь словарь из пар фамилия-имя. Что делать в такой ситуации? Объединять списки в словарь, конечно же!

#Объединение двух списков в словарь
f_names = 
l_names = 
names = dict(zip(f_names, l_names))

Эта идиома принимает на вход два списка: f_names и l_names, а затем формирует из них словарь из пар фамилия-имя. Это быстро и просто, как и в других идиомах Python. Если вас заинтересует метод zip() — почитайте о нем подробнее в документации.

Сортировка с использованием функции attrgetter

В этот раз, возвращаемый список отсортирован по возрасту, как мы и ожидали. Фактически, сортировка по определенному атрибуту объекта это простая задача Python, которую может выполнить стандартная библиотека, благодаря функции, которая может генерировать функции ключей для вас:

Результат вызова attrgetter() – это функция, схожая с предыдущими двумя, которые мы только что рассмотрели. Мы определяем имя атрибута для выборки, после чего attrgetter генерирует функцию, которая принимает объект и возвращает определенный атрибут из этого объекта.

Таким образом, attrgetter(name) возвращает функцию, которая ведет себя также как и определенная раннее нашей функцией byName_key():

Функция attrgetter(age) возвращает функцию, которая ведет себя также как и определенная раннее нашей функцией byAge_key():