Поиск элемента в списке Python

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

Список (list) — тип данных, предназначенный для хранения набора или последовательности разных элементов.[1, 33, 6, 9] # литерал списка в Python

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

Как списки хранятся в памяти?

Базовая C-структура списков в Python (CPython) выглядит следующим образом:

typedef struct { PyObject_VAR_HEAD PyObject **ob_item; Py_ssize_t allocated; } PyListObject;

Когда мы создаём список, в памяти под него резервируется объект, состоящий из 3-х частей:

• PyObject_VAR_HEAD — заголовок;
• ob_item — массив указателей на элементы списка;
• allocated — количество выделенной памяти под элементы списка.

Объект списка хранит указатели на объекты, а не на сами объекты

Python размещает элементы списка в памяти, затем размещает указатели на эти элементы. Таким образом, список в Python — это массив указателей.

Видео

Как списки хранятся в памяти?

Как уже было сказано выше, список является изменяемым типом данных. При его создании в памяти резервируется область, которую можно условно назвать некоторым “контейнером”, в котором хранятся ссылки на другие элементы данных в памяти. В отличии от таких типов данных как число или строка, содержимое “контейнера” списка можно менять. Для того, чтобы лучше визуально представлять себе этот процесс взгляните на картинку ниже. Изначально был создан список содержащий ссылки на объекты 1 и 2, после операции a[1] = 3, вторая ссылка в списке стала указывать на объект 3.

Более подробно эти вопросы обсуждались в уроке 3 (Типы и модель данных).

Срезы

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

У них есть свой собственный синтаксис. Записывается срез так же, как обращение к элементу, используя индекс. Пример:

elements[START:STOP:STEP]

В этом случае берётся срез от номера start (включительно) до stop (не включая его), а step — это шаг. По умолчанию start и stop равны 0, step равен 1.

>>> elements = [0.1, 0.2, 1, 2, 3, 4, 0.3, 0.4] >>> int_elements = elements[2:6] # с 2-го элемента включительно по 6-й элемент >>> print(id(elements), id(int_elements)) # elements и int_elements - 2 разных списка 53219112 53183848 >>> print(elements) [0.1, 0.2, 1, 2, 3, 4, 0.3, 0.4] # срез не модифицирует исходный список >>> print(int_elements) [1, 2, 3, 4]

Преобразование списка в строку

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

Созданная подобным способом строка получает значение всех элементов списка.

Доступ к элементам

Мы можем получить доступ к элементам списка с помощью index. Значение индекса начинается с 0.

Если индекс не входит в диапазон, возникает IndexError.

Мы также можем передать отрицательное значение индекса. В этом случае элемент возвращается от конца к началу. Допустимый диапазон значений индекса — от -1 до — (длина).

Это полезно, когда нам нужен определенный элемент быстро, например, последний элемент, второй последний элемент и т. д.

Как проверить существует ли элемент?

Мы можем использовать оператор «in», чтобы проверить, присутствует ли элемент в списке или нет. Точно так же мы можем использовать оператор «not in».

С помощью лямбда функции

Еще один способ проверить, присутствует ли элемент — отфильтровать все, кроме этого элемента, точно так же, как просеять песок и проверить, остались ли в конце какие-нибудь раковины. Встроенный метод filter() принимает в качестве аргументов лямбда-функцию и список. Здесь мы можем использовать лямбда-функцию для проверки нашей строки «Bird» в списке animals.

Затем мы оборачиваем результаты в list(), так как метод filter() возвращает объект filter, а не результаты. Если мы упакуем объект filter в список, он будет содержать элементы, оставшиеся после фильтрации:

Вывод программы:

Сейчас этот подход не самый эффективный. Это довольно медленнее, чем предыдущие три подхода, которые мы использовали. Сам метод filter() эквивалентен функции генератора:

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

Методы для работы со списками

Начнем с метода append(), который добавляет элемент в конец списка:

# Создаем список, состоящий из четных чисел от 0 до 8 включительно numbers = list(range(,10,2)) # Добавляем число 200 в конец списка numbers.append(200) numbers.append(1) numbers.append(2) numbers.append(3) print(numbers)

>>> [, 2, 4, 6, 8, 200, 1, 2, 3]

Мы можем передавать методу append() абсолютно любые значения:

all_types = [10, 3.14, ‘Python’, [‘I’, ‘am’, ‘list’]] all_types.append(1024) all_types.append(‘Hello world!’) all_types.append([1, 2, 3]) print(all_types)

>>> [10, 3.14, ‘Python’, [‘I’, ‘am’, ‘list’], 1024, ‘Hello world!’, [1, 2, 3]]

Метод append() отлично выпол­няет свою функцию. Но, что делать, если нам нужно добавить элемент в сере­дину списка? Это умеет метод insert(). Он добавляет элемент в список на произ­вольную позицию. insert() принимает в качестве первого аргу­мента позицию, на которую нужно вставить элемент, а вторым — сам элемент.

# Создадим список чисел от 0 до 9 numbers = list(range(10)) # Добавление элемента 999 на позицию с индексом 0 numbers.insert(, 999) print(numbers) # первый print numbers.insert(2, 1024) print(numbers) # второй print numbers.insert(5, ‘Засланная строка-шпион’) print(numbers) # третий print

>>> [999, , 1, 2, 3, 4, 5, 6, 7, 8, 9] # первый print >>> [999, , 1024, 1, 2, 3, 4, 5, 6, 7, 8, 9] # второй print >>> [999, , 1024, 1, 2, ‘Засланная строка-шпион’, 3, 4, 5, 6, 7, 8, 9] # третий print

Отлично! Добавлять элементы в список мы научи­лись, осталось понять, как их из него удалять. Метод pop() удаляет эле­мент из списка по его индексу:

numbers = list(range(10)) print(numbers) # 1 # Удаляем первый элемент numbers.pop() print(numbers) # 2 numbers.pop() print(numbers) # 3 numbers.pop(2) print(numbers) # 4 # Чтобы удалить последний элемент, вызовем метод pop без аргументов numbers.pop() print(numbers) # 5 numbers.pop() print(numbers) # 6

>>> [, 1, 2, 3, 4, 5, 6, 7, 8, 9] # 1 >>> [1, 2, 3, 4, 5, 6, 7, 8, 9] # 2 >>> [2, 3, 4, 5, 6, 7, 8, 9] # 3 >>> [2, 3, 5, 6, 7, 8, 9] # 4 >>> [2, 3, 5, 6, 7, 8] # 5 >>> [2, 3, 5, 6, 7] # 6

Теперь мы знаем, как удалять элемент из списка по его инде­ксу. Но что, если мы не знаем индекса элемента, но знаем его значение? Для такого случая у нас есть метод remove(), кото­рый удаляет пер­вый найденный по значению элемент в списке.

all_types = [10, ‘Python’, 10, 3.14, ‘Python’, [‘I’, ‘am’, ‘list’]] all_types.remove(3.14) print(all_types) # 1 all_types.remove(10) print(all_types) # 2 all_types.remove(‘Python’) print(all_types) # 3

>>> [10, ‘Python’, 10, ‘Python’, [‘I’, ‘am’, ‘list’]] # 1 >>> [‘Python’, 10, ‘Python’, [‘I’, ‘am’, ‘list’]] # 2 >>> [10, ‘Python’, [‘I’, ‘am’, ‘list’]] # 3

А сейчас немного посчитаем, посчитаем эле­менты списка с помощью метода count()

numbers = [100, 100, 100, 200, 200, 500, 500, 500, 500, 500, 999] print(numbers.count(100)) # 1 print(numbers.count(200)) # 2 print(numbers.count(500)) # 3 print(numbers.count(999)) # 4

>>> 3 # 1 >>> 2 # 2 >>> 5 # 3 >>> 1 # 4

В программировании, как и в жизни, проще работать с упоря­доченными дан­ными, в них легче ори­енти­ро­ваться и что-либо искать. Метод sort() сорти­рует список по воз­раста­нию значений его элементов.

numbers = [100, 2, 11, 9, 3, 1024, 567, 78] numbers.sort() print(numbers) # 1 fruits = [‘Orange’, ‘Grape’, ‘Peach’, ‘Banan’, ‘Apple’] fruits.sort() print(fruits) # 2

>>> [2, 3, 9, 11, 78, 100, 567, 1024] # 1 >>> [‘Apple’, ‘Banan’, ‘Grape’, ‘Orange’, ‘Peach’] # 2

Мы можем изменять порядок сортировки с помощью пара­метра reverse. По умол­чанию этот параметр равен False

fruits = [‘Orange’, ‘Grape’, ‘Peach’, ‘Banan’, ‘Apple’] fruits.sort() print(fruits) # 1 fruits.sort(reverse=True) print(fruits) # 2

>>> [‘Apple’, ‘Banan’, ‘Grape’, ‘Orange’, ‘Peach’] # 1 >>> [‘Peach’, ‘Orange’, ‘Grape’, ‘Banan’, ‘Apple’] # 2

Иногда нам нужно перевернуть список, не спраши­вайте меня зачем… Для этого в самом лучшем языке прог­рам­миро­вания на этой планете JavaScr..­Python есть метод reverse():

numbers = [100, 2, 11, 9, 3, 1024, 567, 78] numbers.reverse() print(numbers) # 1 fruits = [‘Orange’, ‘Grape’, ‘Peach’, ‘Banan’, ‘Apple’] fruits.reverse() print(fruits) # 2

>>> [78, 567, 1024, 3, 9, 11, 2, 100] # 1 >>> [‘Apple’, ‘Banan’, ‘Peach’, ‘Grape’, ‘Orange’] # 2

Допустим, у нас есть два списка и нам нужно их объединить. Програм­мисты на C++ cразу же кинулись писать циклы for, но мы пишем на python, а в python у спис­ков есть полез­ный метод extend(). Этот метод вызы­вается для одного списка, а в качестве аргу­мента ему пере­дается другой список, extend() запи­сывает в конец первого из них начало вто­рого:

fruits = [‘Banana’, ‘Apple’, ‘Grape’] vegetables = [‘Tomato’, ‘Cucumber’, ‘Potato’, ‘Carrot’] fruits.extend(vegetables) print(fruits)

>>> [‘Banana’, ‘Apple’, ‘Grape’, ‘Tomato’, ‘Cucumber’, ‘Potato’, ‘Carrot’]

В природе существует специ­аль­ный метод для очистки списка — clear()

fruits = [‘Banana’, ‘Apple’, ‘Grape’] vegetables = [‘Tomato’, ‘Cucumber’, ‘Potato’, ‘Carrot’] fruits.clear() vegetables.clear() print(fruits) print(vegetables)

>>> [] >>> []

Осталось совсем чуть-чуть всего лишь пара мето­дов, так что делаем последний рывок! Метод index() возв­ращает индекс эле­мента. Рабо­тает это так: вы пере­даете в качестве аргу­мента в index() значение элемента, а метод возв­ращает его индекс:

fruits = [‘Banana’, ‘Apple’, ‘Grape’] print(fruits.index(‘Apple’)) print(fruits.index(‘Banana’)) print(fruits.index(‘Grape’))

>>> 1 >>> >>> 2

Финишная прямая! Метод copy(), только не падайте, копирует список и возвра­щает его брата-близнеца. Вообще, копи­ро­вание списков — это тема доста­точно инте­ресная, давай­те рас­смотрим её по-подробнее.

Во-первых, если мы просто прис­воим уже сущест­вующий список новой пере­менной, то на первый взгляд всё выглядит неплохо:

fruits = [‘Banana’, ‘Apple’, ‘Grape’] new_fruits = fruits print(fruits) print(new_fruits)

>>> [‘Banana’, ‘Apple’, ‘Grape’] >>> [‘Banana’, ‘Apple’, ‘Grape’]

Но есть одно маленькое «НО»:

fruits = [‘Banana’, ‘Apple’, ‘Grape’] new_fruits = fruits fruits.pop() print(fruits) print(new_fruits)

# Внезапно, из списка new_fruits исчез последний элемент >>> [‘Banana’, ‘Apple’] >>> [‘Banana’, ‘Apple’]

При прямом присваивании спис­ков копи­рования не проис­ходит. Обе пере­менные начи­нают ссылаться на один и тот же список! То есть если мы изме­ним один из них, то изме­нится и другой. Что же тогда делать? Пользоваться методом copy(), конечно:

fruits = [‘Banana’, ‘Apple’, ‘Grape’] new_fruits = fruits.copy() fruits.pop() print(fruits) print(new_fruits)

>>> [‘Banana’, ‘Apple’] >>> [‘Banana’, ‘Apple’, ‘Grape’]

Отлично! Но что если у нас список в списке? Скопируется ли внутренний список с помощью метода copy() — нет:

fruits = [‘Banana’, ‘Apple’, ‘Grape’, [‘Orange’,‘Peach’]] new_fruits = fruits.copy() fruits[-1].pop() print(fruits) # 1 print(new_fruits) # 2

>>> [‘Banana’, ‘Apple’, ‘Grape’, [‘Orange’]] # 1 >>> [‘Banana’, ‘Apple’, ‘Grape’, [‘Orange’]] # 2

List Comprehensions как обработчик списков

В языке Python есть две очень мощные функции для работы с коллекциями: map и filter. Они позволяют использовать функциональный стиль программирования, не прибегая к помощи циклов, для работы с такими типами как list, tuple, set, dict и т.п. Списковое включение позволяет обойтись без этих функций. Приведем несколько примеров для того, чтобы понять о чем идет речь.

Пример с заменой функции map.

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

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

В данном случае применена lambda-функция, о том, что это такое и как ее использовать можете прочитать здесь.

Через списковое включение эта задача будет решена так:

Пример с заменой функции filter.

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

Решим эту задачу с использованием filter:

Решение через списковое включение:

Расширение списка

Имея необходимость объединить два разных набора данных, представленных в виде списков, стоит воспользоваться методом extend. Выполнив его вызов для одного из объектов и записав в качестве аргумента другой объект, произойдет их слияние в одно целое.

Таким образом, элементы второго списка будут автоматически записаны в конец первого.

Создание списка с помощью list()

Переходим к способам создания списка. Самый простой из них был приведен выше. Еще раз для закрепления:

smiles = [‘(ಠ_ಠ)’, ‘(￣﹃￣)’, ‘( ͡° ͜ʖ ͡°)’, ‘(╮°-°)╮’]

А есть еще способы? Да, есть. Один из них — создание списка с помощью функции list() В неё мы можем передать любой итерируемый объект (да-да, тот самый по которому можно запустить цикл (• ᵕ •) )

Рассмотрим несколько примеров:

letters = list(‘abcdef’) numbers = list(range(10)) even_numbers = list(range(, 10, 2)) print(letters) print(numbers) print(even_numbers)

>>> [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’ >>> [, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> [, 2, 4, 6, 8]

Поиск Фибоначчи

Поиск Фибоначчи — это еще один алгоритм «разделяй и властвуй», который имеет сходство как с бинарным поиском, так и с jump search. Он получил свое название потому, что использует числа Фибоначчи для вычисления размера блока или диапазона поиска на каждом шаге.

Числа Фибоначчи  — это последовательность чисел 0, 1, 1, 2, 3, 5, 8, 13, 21 …, где каждый элемент является суммой двух предыдущих чисел.

Алгоритм работает с тремя числами Фибоначчи одновременно. Давайте назовем эти три числа fibM, fibM_minus_1 и fibM_minus_2. Где fibM_minus_1 и fibM_minus_2 — это два числа, предшествующих fibM в последовательности:

fibM = fibM_minus_1 + fibM_minus_2

Мы инициализируем значения 0, 1, 1 или первые три числа в последовательности Фибоначчи. Это поможет нам избежать  IndexError в случае, когда наш массив lys содержит очень маленькое количество элементов.

Затем мы выбираем наименьшее число последовательности Фибоначчи, которое больше или равно числу элементов в нашем массиве lys, в качестве значения fibM. А два числа Фибоначчи непосредственно перед ним — в качестве значений fibM_minus_1 и fibM_minus_2. Пока в массиве есть элементы и значение fibM больше единицы, мы:

• Сравниваем val со значением блока в диапазоне до fibM_minus_2 и возвращаем индекс элемента, если он совпадает.
• Если значение больше, чем элемент, который мы в данный момент просматриваем, мы перемещаем значения fibM, fibM_minus_1 и fibM_minus_2 на два шага вниз в последовательности Фибоначчи и меняем индекс на индекс элемента.
• Если значение меньше, чем элемент, который мы в данный момент просматриваем, мы перемещаем значения fibM, fibM_minus_1 и fibM_minus_2 на один шаг вниз в последовательности Фибоначчи.

Давайте посмотрим на реализацию этого алгоритма на Python:

Используем функцию FibonacciSearch для вычисления:

Давайте посмотрим на пошаговый процесс поиска:

• Присваиваем переменной fibM наименьшее число Фибоначчи, которое больше или равно длине списка. В данном случае наименьшее число Фибоначчи, отвечающее нашим требованиям, равно 13.
• Значения присваиваются следующим образом:

           fibM = 13

           fibM_minus_1 = 8

           fibM_minus_2 = 5

           index = -1

• Далее мы проверяем элемент lys[4], где 4 — это минимум из двух значений — index + fibM_minus_2 (-1+5) и длина массива минус 1 (11-1). Поскольку значение lys[4] равно 5, что меньше искомого значения, мы перемещаем числа Фибоначчи на один шаг вниз в последовательности, получая следующие значения:

           fibM = 8

           fibM_minus_1 = 5

           fibM_minus_2 = 3

           index = 4

• Далее мы проверяем элемент lys[7], где 7 — это минимум из двух значений: index + fibM_minus_2 (4 + 3) и длина массива минус 1 (11-1). Поскольку значение lys[7] равно 8, что больше искомого значения, мы перемещаем числа Фибоначчи на два шага вниз в последовательности, получая следующие значения: 

           fibM = 3

           fibM_minus_1 = 2

           fibM_minus_2 = 1

           index = 4

• Затем мы проверяем элемент lys[5], где 5 — это минимум из двух значений: index + fibM_minus_2 (4+1) и длина массива минус 1 (11-1) . Значение lys[5] равно 6, и это наше искомое значение!

Получаем ожидаемый результат:

Временная сложность поиска Фибоначчи равна O(log n). Она такая же, как и у бинарного поиска. Это означает, что алгоритм в большинстве случаев работает быстрее, чем линейный поиск и jump search.

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

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

Таблица «методы списков»

Метод	Что делает
list.append(x)	Добавляет элемент в конец списка
list.extend(L)	Расширяет список list, добавляя в конец все элементы списка L
list.insert(i, x)	Вставляет на i-ый элемент значение x
list.remove(x)	Удаляет первый элемент в списке, имеющий значение x. ValueError, если такого элемента не существует
list.pop([i])	Удаляет i-ый элемент и возвращает его. Если индекс не указан, удаляется последний элемент
list.index(x, [start [, end]])	Возвращает положение первого элемента со значением x (при этом поиск ведется от start до end)
list.count(x)	Возвращает количество элементов со значением x
list.sort([key=функция])	Сортирует список на основе функции
list.reverse()	Разворачивает список
list.copy()	Поверхностная копия списка
list.clear()	Очищает список

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

И, напоследок, примеры работы со списками:

Изредка, для увеличения производительности, списки заменяют гораздо менее гибкими массивами (хотя в таких случаях обычно используют сторонние библиотеки, например NumPy).

Теги