Наши пользователи имеют разные уровни знаний и опыта в области кодирования, поэтому я часто вижу стандартные и более очевидные подходы к решению задач. Но время от времени я сталкиваюсь с такими уникальными и необычными решениями, что они заставляют меня вновь изучать неведомые ранее тонкости языка.
В этой статье я хочу рассмотреть некоторые решения одной из очень простых задач, которые, на мой взгляд, являются самыми интересными. Миссия требует от Вас написать функцию, которая будет определять, имеют ли все элементы массива одинаковое значение.
1. Одно из первых решений, которое приходит в голову — сравнить длину списка исходных элементов с тем, сколько раз первый элемент входит в список. Если эти значения равны, значит список состоит из одинаковых элементов. Также присутствует проверка того, является ли список пустым, так как в этом случае также необходимо вернуть True.
def all_the_same(elements):
if len(elements) < 1:
return True
return len(elements) == elements.count(elements[0])
Либо более сокращенный вариант:
def all_the_same(elements):
return len(elements) < 1 or len(elements) == elements.count(elements[0])
2. В этом решении использовалась полезная особенность Python — возможность сравнивать списки всего лишь с помощью оператора сравнения — ‘==’ (в отличии от некоторых других языков программирования, где это сделать не так просто). Рассмотрим, как это работает:
>>> [1, 1, 1] == [1, 1, 1]
True
>>> [1, 1, 0] == [0, 1, 1]
False
Другая особенность языка в том, что он предоставляет возможность умножать list на число и результатом этой операции будет list в котором все элементы скопированы указанное количество раз. Давайте я покажу вам несколько примеров:
>>> [1] * 3
[1, 1, 1]
>>> [1] * 5
[1, 1, 1, 1, 1]
>>> [1] * 0
[]
>>> [1, 2] * 3
[1, 2, 1, 2, 1, 2]
Таким образом можно прийти к простому решению — если умножить массив из одного первого элемента из исходного массива на длину этого исходного массива, то должен опять получиться исходных массив, если все элементы этого массива одинаковые.
def all_the_same(elements):
if not elements:
return True
return [elements[0]] * len(elements) == elements
Как и в предыдущем случае, можно укоротить это решение:
def all_the_same(elements):
return not elements or [elements[0]] * len(elements) == elements
3. В этом решении использовалась стандартная функция set(). Эта функция преобразовывает объект в set в котором, по определению, все элементы должны быть уникальными. Это выглядит так:
>>> elements = [1, 2, 5, 1, 5, 3, 2]
>>> set(elements)
{1, 2, 3, 5}
Если в итоге полученный set будет состоять из 1 или 0 элементов — значит в исходном списке все элементы были одинаковы или же он был пуст. Решение может выглядеть так:
def all_the_same(elements):
return len(set(elements)) in (0, 1)
или так:
def all_the_same(elements):
return len(set(elements)) <= 1
Подобный подход можно использовать с помощью модуля NumPy, в котором есть функция unique(), работающая следующим образом:
>>> from numpy import unique
>>> a = [1, 2, 1, 2, 3, 1, 1, 1, 1]
>>> unique(a)
[1 2 3]
Как видите, её работа весьма схожа с работой set(), только в этом случае не
меняется тип объекта — список остается списком. Решение с помощью этой функции выглядит так:
from numpy import unique
def all_the_same(elements):
return len(unique(elements)) <= 1
4. Вот пример весьма оригинального решения, в котором, к тому же, обыгрывается название данной задачи с помощью стандартной функции Python — all(). Функция all() вернет True, если все элементы переданного списка будут True. Например:
>>> all([1, 2, 0, True])
False
#(0 не true)
>>> all([1, 2, None, True])
False
#(None не true)
>>> all([1, 2, False, True])
False
>>> all([1, 2, 0.1, True])
True
Сперва переменной first присваивается значение первого элемента списка, а rest — список всех остальных элементов, кроме первого. Затем в кортеж the_same добавляются значения True or False в зависимости от того, равен ли очередной элемент списка rest первому элементу исходного списка. После этого функция all() вернет True, если the_same будет состоять только из элементов ‘True’, и False, если в кортеже будет хотя бы один элемент ‘False’.
def all_the_same(elements):
try:
first, *rest = elements
except ValueError:
return True
the_same = (x == first for x in rest)
return all(the_same)
Исключение ValueError будет вызвано только в том случае, если массив пуст. Но мы можем сделать более привычную нам проверку:
def all_the_same(elements):
if not elements:
return True
first, *rest = elements
the_same = (x == first for x in rest)
return all(the_same)
5. Следующее решение очень похоже на предыдущее. В нем есть лишь небольшая поправка — первый и остальные элементы из исходного списка разделяются с помощью итератора. Функция iter() создает итератор из переданного списка, а функция next() берет из него следующий элемент (т.е. первый — при первом вызове). Если вывести с помощью print элементы, входящие в el и first, мы увидим следующее:
>>> el = iter([1, 2, 3])
>>> first = next(el, None)
>>> print(first)
1
>>> for i in el:
>>> print(i)
2
3
В остальном, это решение похоже на предыдущее, за исключением того, что у нас отпадает необходимость в проверке — является ли список пустым или нет.
def all_the_same(elements):
el = iter(elements)
first = next(el, None)
return all(element == first for element in el)
6. Одним из креативных подходов к решению этой задачи является перестановка элементов. Мы меняем элементы местами и проверяем, что список из-за этого не изменился. Это говорит нам о том, что все элементы в списке — одинаковые. Вот пару примеров такого подхода:
def all_the_same(elements):
return elements[1:] == elements[:-1]
и
def all_the_same(elements):
return elements == elements[1:] + elements[:1]
Стоит также обратить внимание, что сравнивать массивы можно и поэлементно, используя функцию zip(). Рассмотрим это на примере следующих решений.
7. Функция zip() объединяет каждый i-ый элемент одного объекта с i-ым элементом остальных до тех пор, пока не закончится самый короткий объект.
>>> x = [1, 2, 3]
>>> y = [10, 11]
>>> list(zip(x, y))
[(1, 10), (2, 11)]
Как видите, несмотря на то, что x состоит из трех элементов, были использованы только два, так как самый короткий объект — в данном случае y — состоит всего из 2-х элементов.
Приведенное ниже решение работает следующим образом: сперва создается второй список (elements[1:]), который равен исходному списку, но без первого элемента. Затем поочередно сравниваются элементы из этих двух списков и в результате каждого такого сравнения мы получаем True или False. После чего функция all() возвращает результат обработки этого набора True и False.
def all_the_same(elements):
return all(x == y for x, y in zip(elements, elements[1:]))
Предположим, наш исходный список elements = [2, 2, 2, 3]. Тогда с помощью zip(), мы объединим полный список ([2, 2, 2, 3]) и список без первого элемента ([2, 2, 3]) таким образом: [(2, 2), (2, 2), (2, 3)], сравнения элементов между собой передадут в функцию all() набор [True, True, False] и в результате мы получим False, что является правильным ответом, так как в исходном списке не все элементы одинаковы.
8. Весьма любопытным оказалось следующее решение. В нем использовался итератор groupby(), который работает таким образом — сравнивает каждый i-ый элемент с (i-1)-ым и если элементы равны — двигается дальше, а если не равны — оставляет в итоговом списке элемент (i-1) и продолжает сравнение со следующего элемента. На практике это выглядит так:
>>> from itertools import groupby
>>> elements = [1, 1, 1, 2, 1, 1, 1, 2]
>>> for key, group in groupby(elements):
>>> print(key)
1
2
1
2
Как видите, остались только те элементы, которые отличаются от элемента на следующей позиции (elements[0], elements[1], elements[4] и elements[5] были исключены).
В данном решении функция с помощью итератора groupby() добавляет в список единицу (1) каждый раз, когда следующий элемент исходного списка отличается от предыдущего. Таким образом, если в исходном списке 0 элементов или все элементы равны, сумма (sum(1 for _ in groupby(elements))) будет равна 0 или 1 — то есть в любом случае меньше 2, что и указано в решении.
from itertools import groupby
def all_the_same(elements):
return sum(1 for _ in groupby(elements)) < 2
9. Еще одно креативное решение, в котором используется один из стандартных модулей Python — collections. Counter создает словарь, куда заносит информацию о количестве каждого элемента в исходном списке. Давайте посмотрим, как это работает:
>>> from collections import Counter
>>> a = [1, 1, 1, 2, 2, 3]
>>> Counter(a)
Counter({1: 3, 2: 2, 3: 1})
Соответственно, если длина этого словаря будет 2 и больше — в исходном списке как минимум 2 разных элемента и не все элементы одинаковы.
def all_the_same(elements):
from collections import Counter
return not len(list(Counter(elements))) > 1
10. Данное решение построено на такой же логике, как и решение №7, но используются функции eq() и starmap(). Разберемся, как они работают:
>>> from operator import eq
>>> eq(1, 2)
False
По сути, функция eq() делает то же, что и “==” — сравнивает два объекта и возвращает True, если они равны и False в ином случае (eq — сокращенно от equivalent). Однако, обратите внимание, что функция — это объект и она может быть, к примеру, передана в качестве аргумента для другой функции, что и было сделано в описанном далее решении.
Функция starmap() создает итератор, который применяет другую функцию к списку объектов. Используется тогда, когда объекты уже сгруппированы в кортежи. Например:
>>> import math
>>> from itertools import starmap
>>> list(starmap(math.pow, [(1, 2), (3, 4)]))
[1.0, 81.0]
Как вы видите, указанная один раз функция math.pow(), благодаря функции starmap() была применена дважды — к обоим наборам объектов (1**2 = 1.0, 3**4 = 81.0)
Упрощенно функцию starmap() для данного примера можно представить в виде цикла:
import math
elements = [(1, 2), (3, 4)]
result = []
for i in elements:
result.append(math.pow(i[0], i[1]))
Решение с использованием описанных ранее функций выглядит так:
from operator import eq
from itertools import starmap
def all_the_same(elements):
return all(starmap(eq, zip(elements, elements[1:])))
Заключение
Итак, мы рассмотрели некоторые смекалистые решения, которые относятся к одной из самых простых головоломок. При всем желании, я даже понятия не имею, как начать описывать то количество уникальных подходов, которые применяют наши пользователи для решения других интересных и более сложных задач. Надеюсь, Вы получили такое же удовольствие от прочтения этой статьи, что и я во время ее написания. Я с нетерпением жду Ваших отзывов. Было ли это полезно для Вас? Как бы Вы решили эту задачу?
Перевод статьи “Determining if all Elements in a List are the Same in Python”, опубликованной на блоге “The Mouse Vs. The Python”.
Комментарии (22)
Ivanq
11.05.2018 18:32> 6. Одним из креативных подходов к решению этой задачи является перестановка элементов. Мы меняем элементы местами и проверяем, что список из-за этого не изменился. Это говорит нам о том, что все элементы в списке — одинаковые. Вот пару примеров такого подхода:
Палиндромы? Не, не слышали.DinoL
11.05.2018 18:53+2Палиндромы также верно определятся приведённой функцией. Всё, что там «переставляется» — первый элемент в конец списка. Сравнение
— это просто другой способ написать «второй элемент равен первому, третий — второму, ..., последний — предпоследнему».elements[1:] == elements[:-1]
maslyaev
11.05.2018 19:03>>> elements = [1, 2, 1] # палиндром >>> elements[1:] [2, 1] >>> elements[:-1] [1, 2] >>> elements[1:] == elements[:-1] False
IIvana
12.05.2018 00:46О, паралимпиада, люблю ) Кот претендует на медаль в номинации "уникального и необычного" ) Питон не знаю, но алгоритм тривиально пишется на любом языке, напишу на сях )
bool f (int *m, int b, int e) { int c=(b+e)/2; return b>=e ? true : b+1==e ? m[b]==m[e] : f(m,b,c) && f(m,c,e); }
А вообще надо вводить новый моноидальный тип и решать эту задачу как свертку структуры по моноиду. Ибо в таком случае умный компилятор сумеет сам распараллелить процесс на нужное число потоков/ядер и порвать по бенчмаркам все предложенное.
Wesha
12.05.2018 03:36return len(elements) == elements.count(elements[0])
Вот и выросло поколение, которое считает все оперцации атомарными, и не в курсе, что внутрях у неё
думатель и неонкадофигиллион циклов.
Пройтись по списку в цикле c "return false if (elem[i] != elem[0]); return true if (достигнут последний элемент)"? Нет, не слышали.
TheShock
12.05.2018 03:53дофигиллион циклов
А вы, видимо, не слышали об O-нотации. Оба решения — линейны и ваше решение всего, в среднем, в два раза быстрее. А если count написан на каком-нибудь более быстром языке, то и вовсе может оказать, что ваше предложение медленнее.
VaalKIA
12.05.2018 09:25+2Не программировал на Питоне, но у ЯВУ, в которых радеют за выразительность, как правило, есть проблема в том, что все операторы написаны не на самом языке и поэтому быстрые, а сам язык — медленный. Получается такая штука: если есть какой-то специальный оператор, пусть и молотящий в 10 раз больше действий, чем надо, то он всегда на порядок будет быстрей, чем его же реализация на этом языке в модификации с уменьшенным количеством действий. Получается довольно извращённое программирование, когда микроскопами гвозди забивают и можно сделать это сотней способов, а вот, правильный и красивый алгоритм, это будет медленно. Надеюсь меня не заминусуют в хлам, это моё личное мнение.
khim
12.05.2018 20:26Это не ваше личное мнение, это квинтэессенция питона и есть. Самая распространённая реализация — это интерпретатор, который примерно на два-три порядка медленнее, чем реализация того же, но не на самом питоне.
А дальше — всё, как вы сказали.Zibx
12.05.2018 22:10Минутка занудства
Два-три порядка пережить можно, избегать следует именно увеличения сложности.
1 > log(N) > N > N log(N) > N2 > N[3-x] > !N
Решения с аллокацией дополнительного массива в рамках этой задачи заставляют закипать что-то глубоко внутри меня.
Если бы оно было записано не на языке программирования, а именно как математическая демонстрация множественности решений — вообще никаких вопросов бы не возникло.
khim
12.05.2018 23:56Два-три порядка пережить можно, избегать следует именно увеличения сложности.
Ну и где вы увидели в этой задаче «увеличение сложности»? Исходный массив — занимает O(N). Если мы в процессе работы не порождаем больше конечного числа массивов, то мы никакого «увеличения сложности», в общем, не получаем. Массивы временные, будут удалены сразу же.
1 > log(N) > N > N log(N) > N2 > N[3-x] > !N
Решения с аллокацией дополнительного массива в рамках этой задачи заставляют закипать что-то глубоко внутри меня.
Тем не менее для python'а — это нормально. Ибо там и просто массив целых будет занимать на порядок больше памяти, чем в C.
Если вы не хотите, чтобы аллокации производились «на каждый чих» — зачем вы вообще с этим языком связались?
Если бы оно было записано не на языке программирования, а именно как математическая демонстрация множественности решений — вообще никаких вопросов бы не возникло.
Ну это уже совсем другая история. Там можно и с сортировкой в N! мириться. А в обычной жизни — если вы выбрали python, то значит на константу — вам наплевать (хотя про bigO забывать не стоит).
elements[1:] == elements[:-1]
кажется самым разумным выражением идеи…
worldmind
13.05.2018 13:26Честно говоря ИМХО в питоне важнее найти не много способов, а один, но самый выразительный, в данном случае самым привлекательным выглядит вариант с unique
dopusteam
Жаль нет сравнения памяти/времени, необходимых для каждого способа
khim
А смысл? Если вам важно сколько времени и памяти уходит на всё это, то лучше использовать не Python, а что-нибудь другое.
Python — это для случаев, когда в первую очередь важна читаемость…
dopusteam
Следуя Вашей логике код на питоне никогда не стоит оптимизировать
khim
Стоит, но исключительно с точки зрения читабельности. На питоне вообще не нужно писать кусков кода, занимающих сколько-нибудь осмысленное время и требующих заметное количество памяти. Для это другие языки есть.
Daniyar94
Я сначала тоже подумал про время. Но математически нельзя сделать подобную проверку не пройтись по всем элементам, так что кажется все эти подходы в лучшем случае все равно дают O(n). Поправьте если сморозил глупость
VaalKIA
Почему это нельзя не пройтись, при первом же отличном элементе заканчивать проход, так что полный проход будет только в худшем случае.
amberovsky
В лучшем случае О(1), амортизированное время всё равно O(n)
VaalKIA
del
Daniyar94
Я об этом и говорю O(x) означает всегда худшее.