Сравнить два списка python: Как сравнить два списка в Python?

Содержание

сравнение содержимого двух списков python [duplicate]

Лучший способ сделать это — сортировка списков и их сравнение. (Использование Counter не будет работать с объектами, которые не являются хешируемыми.) Это просто для целых чисел:

sorted(a) == sorted(b)

Это становится немного сложнее с произвольными объектами. Если вам небезразличен идентификатор объекта, то есть, являются ли те же объекты в обоих списках, вы можете использовать функцию id() в качестве ключа сортировки.

sorted(a, key=id) == sorted(b, key==id)

(In Python 2.x вам действительно не нужен параметр key=, потому что вы можете сравнивать любой объект с любым объектом. Порядок произвольный, но стабильный, поэтому он отлично подходит для этой цели, неважно, какой порядок объектов в том числе, что упорядочение одинаково для обоих списков. В Python 3, однако, сравнение объектов разных типов запрещено во многих случаях — например, вы не можете сравнивать строки с целыми числами, поэтому, если у вас будет объекты разных типов, лучше всего использовать идентификатор объекта.)

Если вы хотите сравнить объекты в списке по значению , , с другой стороны, сначала вам нужно определить, что означает «значение» для объектов. Тогда вам понадобится какой-то способ предоставить это как ключ (и для Python 3, как согласованный тип). Один из возможных способов работы для множества произвольных объектов — сортировка по их repr(). Конечно, это может тратить много лишнего времени и блоков памяти repr() для больших списков и т. Д.

sorted(a, key=repr) == sorted(b, key==repr)

Если объекты все ваши собственные типы, вы можете определить __lt__() на них, чтобы объект знал, как сравнивать себя с другими. Затем вы можете просто отсортировать их и не беспокоиться о параметре key=. Конечно, вы также можете определить __hash__() и использовать Counter, который будет быстрее.

Сравнение двух списков-Python — python


Хорошо, у меня есть два списка, Список 1 и Список 2. Я хочу найти все элементы, которые находятся как в списке 1, так и в списке 2, и удалить их из списка 1. Первый способ, которым я думал об этом, — это цикл по Списку 1, а затем цикл по Списку 2, чтобы увидеть, находится ли он в списке 2, но это кажется медленным и неэффективным при масштабировании. Есть ли более эффективный способ сделать это?

Кроме того, эти списки будут упорядочены в алфавитном порядке (они являются строками), если это что-нибудь поможет.

Я использую python,но мне также интересно с точки зрения общего программирования.

list1 = ['bar','foo','hello','hi']
list2 = ['alpha','bar','hello','xam']

list1 станет ['foo','hi']

python list
Поделиться
Источник
Sam Creamer     07 февраля 2014 в 20:15

3 Ответа




6

В python, вы, вероятно, захотите использовать набор:

intersection = set(list1).intersection(list2)

Это вернет set , который разрушает Порядок (среди прочего), но вы всегда можете использовать этот набор для фильтрации list1 позже:

list1 = [x for x in list1 if x not in intersection]

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

set2 = set(list2)
list1 = [x for x in list1 if x not in set2]

Поделиться mgilson

    07 февраля 2014 в 20:16



4

Используйте set , чтобы получить разницу между ними:

list1 = ['bar','foo','hello','hi']
list2 = ['alpha','bar','hello','xam']

set1 = set(list1)
set2 = set(list2)
set1 - set2

Выходы:

set(['hi', 'foo'])

Как отмечает @chepner, с помощью set.difference, только первый должен быть преобразован в набор

set1.difference(list2)

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

set2 = set(list2)
[x for x in list1 if x not in set2]

Выходы:

['foo', 'hi']

Поделиться mhlester     07 февраля 2014 в 20:17



1

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

list1 = ['a', 'b', 'd', 'f', 'k']
list2 = ['c', 'd', 'i']
result = []

i1 = 0
i2 = 0
while i1 < len(list1) and i2 < len(list2):
    # invariants:
    #    list1[i1] not in list2[:i2], and
    #    result == (list1[:i1] with elements of list2[:i2] omitted)
    #
    if list1[i1] < list2[i2]:
        # By assumption, list1[i1] not in list2[:i2],
        # and because list2 is sorted, the true 'if' condition
        # implies that list1[i1] isn't in list2[i2:] either;
        # that is, it isn't in list2 at all.
        result.append(list1[i1])
        i1 += 1
    elif list1[i1] > list2[i2]:
        # can't decide membership of list1[i1] yet;
        # advance to next element of list2 and loop again
        i2 += 1
    else:
        # list1[i1] == list2[i2], so omit this element
        i1 += 1
        i2 += 1

# Add any remaining elements of list1 to tail of result
if i1 < len(list1):
    result.extend(list1[i1:])

print(result)

Результат: ['a', 'b', 'f', 'k']

Поделиться BrianO     07 февраля 2014 в 21:36



Похожие вопросы:


Сравнение двух групп списков

Возможный Дубликат : Сравнение двух списков, в которых есть списки внутри них У меня есть класс автомобилей и класс моделей. Автомобиль имеет много свойств, таких как CarId и List<Models> ….


более сжатое сравнение двух списков?

Я хотел бы знать, есть ли общий способ в python сравнить элементы двух списков (например, элемент из списка 1 больше, чем элемент из списка 2) в более сжатом виде, чем это: t1 = [1,1,0] t2 = [2,2,1]…


Пересечение двух вложенных списков в Python

У меня проблема с вложенными списками. Я хочу вычислить длину пересечения двух вложенных списков с языком python. Мои списки составлены следующим образом: list1 = [[1,2], [2,3], [3,4]] list2 =…


Сравнение объектов из более чем 2 списков

Есть ли способ сравнить все комбинации 2-х элементов из более чем 2-х списков? Допустим, есть объект: class obj(): def __init__(): self.name = # some name self.number = random(10) def equals(obj):…


Сравнение 2 python списков до n-2 элементов

Сравнение двух списков python до n-2 элементов: list1 = [1,2,3,’a’,’b’] list2 = [1,2,3,’c’,’d’] list1 == list2 => True Исключая последние 2 элемента из 2-х списков, они одинаковы. Я могу сделать…


Сравнение двух списков в python

у меня есть такая веревочка : my_string = apple,orange,kiwi,mange который я разделил, чтобы сделать этот список: my_list_string = my_string.split(‘,’) и у меня есть второй список : my_list = [kiwi,…


Python сравнение двух списков

Привет, я хочу сравнить два списка, как это а=[1,2] б=10,20] compare (a, b) вернет True, если каждый элемент в a > соответствующий элемент в b так что сравнение ([1,2] > [3,4]) верно сравнение…


c#: сравнение двух списков и запись изменения значения

большинство ответов,которые я видел здесь, в основном охватывают проблему логического true / false при сравнении списков. Что меня интересует, так это сравнение двух списков и наблюдение за…


Сравнение двух списков на Python

Мне нужна помощь в сравнении двух списков и возврате индексов, которые не совпадают. a = [0, 1, 1, 0, 0, 0, 1, 0, 1] b = [0, 1, 1, 0, 1, 0, 1, 0, 0] индексы 4 и 8 не совпадают, и мне нужно вернуть…


Получить пересечение двух списков списков или пустой список

У меня есть два списка списков с одинаковой формой. list1 = [[1,2,3], [], [4,5], []] list2 = [[1,2], [7], [4,5], []] Мне нужен этот список списков: [[1,2], [], [4,5], []] Как я могу его получить?…

Слияние списков на python. Сравнение скорости / Хабр

Пусть у нас есть два списка (для простоты из целых чисел), каждый из которых отсортирован. Хотим объединить их в один список, который тоже должен быть отсортирован. Эта задача наверняка всем знакома, используется, например, при сортировке слиянием.

Способов реализации (особенно на python) достаточно много. Давайте разберем некоторые из них и сравним затрачиваемое время на разных входных данных.

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


Входные данные не меняются

Пусть есть два списка list1 и list2.

Начнем с самого простого алгоритма: обозначим метки за i и j и будем брать меньший из list1[i], list2[j] и увеличивать его метку на единицу, пока одна из меток не выйдет за границу списка.

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

Перейдем к коду:

def simple_merge(list1, list2):
    i, j = 0, 0
    res = []
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            res.append(list1[i])
            i += 1
        else:
            res.append(list2[j])
            j += 1
    res += list1[i:]
    res += list2[j:] 
    # один из list1[i:] и list2[j:] будет уже пустой, поэтому добавится только нужный остаток
    return res

Заметим, что в данном коде используется только перемещение вперед по списку. Поэтому будет достаточно работать с итераторами. Перепишем алгоритм с помощью итераторов.

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

def iter_merge(list1, list2):
    result, it1, it2 = [], iter(list1), iter(list2)
    el1 = next(it1, None)
    el2 = next(it2, None)
    while el1 is not None or el2 is not None:
        if el1 is None or (el2 is not None and el2 < el1):
            result.append(el2)
            el2 = next(it2, None)
        else:
            result.append(el1)
            el1 = next(it1, None)
    return result

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

def gen_merge_inner(it1, it2):
    el1 = next(it1, None)
    el2 = next(it2, None)
    while el1 is not None or el2 is not None:
        if el1 is None or (el2 is not None and el2 < el1):
            yield el2
            el2 = next(it2, None)
        else:
            yield el1
            el1 = next(it1, None)

def gen_merge(list1, list2):
    return list(gen_merge_inner(iter(list1), iter(list2))) # из генератора получаем список

Встроенные реализации

Рассмотрим еще несколько способов слияния через встроенные в python функции.


  • merge из heapq. Как говорит документация, эта функция делает именно то, что мы хотим, и больше: объединяет несколько итерируемых объекта, можно задать ключ, можно сортировать в обратном порядке.

    Тогда нам нужно просто импортировать и использовать:

    from heapq import merge
    
    def heapq_merge(list1, list2):
    return list(merge(list1, list2)) # тоже возвращает генератор

  • Counter из collections. Counter умеет считать количество вхождений каждого из элементов, выдавать их в тех количествах, в которых они входят, и еще несколько полезных вещей, которые сейчас не нужны (например, несколько самых часто встречающихся элементов).

    Воспользуемся gen_merge_inner для слияния элементов Counter(list1) и Counter(list2):

    def counter_merge(list1, list2):
    return list(gen_merge_inner(Counter(list1).elements(), Counter(list2).elements()))

  • И, наконец, просто сортировка. Объединяем и сортируем заново.

    def sort_merge(list1, list2):
    return sorted(list1 + list2)


Если можно менять исходные списки

Предположим, что после слияния старые списки больше не нужны (как обычно и случается). Тогда можно написать еще один способ. Будем как и раньше сравнивать нулевые элементы списков и вызывать pop(0) у списка с меньшим, пока один из списков не закончится.

def pop_merge(list1, list2):
    result = []
    while list1 and list2:
        result.append((list1 if list1[0] < list2[0] else list2).pop(0))
    return result + list1 + list2

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

def reverse_pop_merge(list1, list2):
    result = []
    while list1 and list2:
        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))
    return (result + list1[-1::-1] + list2[-1::-1])[-1::-1]

Сравнение

Пора перейти к самому интересному.
Составим список функций, которые будем сравнивать:


  • simple_merge
  • iter_merge
  • gen_merge
  • heapq_merge
  • counter_merge
  • sort_merge
  • pop_merge
  • reverse_pop_merge

Будем измерять время работы с помощью модуля timeit. Код можно посмотреть здесь.

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


Тест первый

Проведем общий тест, размеры от до , элементы от до .

Отдельно сравним pop и reverse_pop:

pop_merge тратит колоссально больше времени в общем случае, как и ожидалось.

Не будем учитывать здесь огромный pop_merge, чтобы лучше видеть разницу между другими:

reverse_pop_merge показал себя относительно неплохо по сравнению с ручной реализацией и heapq_merge.

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


Тест второй, сравнимые размеры

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

Как уже можно видеть pop_merge при небольшом размере списков еще ведет себя как heapq_merge, а дальше обгоняет всех.


Тест третий, один маленький, второй большой

Размер первого равен , размер второго .

В самом начале (на очень маленьких списках) reverse_pop_merge обгоняет всех, кроме sort_merge, но на чуть больших все выходит на стандартные позиции.


Тест четвертый, много повторных

Размеры фиксированы, а количество элементов увеличивается на , начиная с .

Как видно, на достаточно малых количествах counter_merge оказывается быстрее reverse_pop_merge и heapq_merge, но потом он отстает.


Итоги

Абсолютным победителем оказался sort_merge! Гораздо быстрее просто отсортировать список заново, чем использовать вроде бы линейные от длины списков функции.

На втором месте в подавляющем большинстве случаев идет gen_merge, за ним следует iter_merge.

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


P.S.

Код, тесты, jupyter notebook c графиками можно найти на gitlab.

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

Сравнения двух больших списков в Python

у меня есть один список, который содержит около 400 слов. И еще один список списков, в котором каждый список содержит около 150 000 слов. В этом списке 20 таких списков.

теперь я хочу посмотреть, сколько из этих 400 слов появляется во всех этих 150 000 слов списка. Я также хочу знать слово из этого 400 слов, сколько раз в списке 150k слов, какие из этих слов встречаются больше всего, сколько раз и т. д.

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

for one_list in list_of_150kwords:
    for key in 400_words:
        for word in one_list:
            if key == word:
                # count this word
                # do other stuff

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

list_of_150kwords = numpy.array(list_of_150kwords)
...

но я все еще нахожу его очень медленным. Есть другое решение? Или любая библиотека?

4 ответов


Это звучит как хорошая возможность для использования set:

set_of_150kwords = set(list_of_150kwords)
one_set = set(one_list)

len(one_set & set_of_150kwords) # set intersection is &
=> number of elements common to both sets

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Theme: Overlay by Kaira Extra Text
Cape Town, South Africa