Сравнение двух двумерных массивов - PullRequest
Новая
       6

Сравнение двух двумерных массивов

0 голосов
/ 26 августа 2018

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

В случае одномерного массива все легко: 

a = [1, 2]
b = [1, 2, 3]
newArray = list(set(b) - set(a))

newArray в этом случае будет [3]

Сложности в этом случае.Например, у меня есть: 

a = [[1, 2, 3], [1, 2, 5], [4, 6, 9]]
b = [[1, 2, 3], [1, 4, 5], [2, 6, 5]]

, и я хочу получить newArray = [[1, 4, 5], [2, 6, 5]], но если я попробую newArray = list(set(b) - set(a)), это приведет к ошибке 

TypeError: unhashable type: 'list'

Как я могу реализовать то же самоекак в случае одномерного массива?Длина массивов может быть разной.

Ответы [ 2 ]

0 голосов
/ 26 августа 2018

Вы должны преобразовать списки в формат, который можно хэшировать, например, tuple: 

>>> a = [[1, 2, 3], [1, 2, 5], [4, 6, 9]]
>>> b = [[1, 2, 3], [1, 4, 5], [2, 6, 5]]
>>> set(map(tuple, b)) - set(map(tuple, a))
set([(2, 6, 5), (1, 4, 5)])

Если результатом будет список списков, вы можете впоследствии преобразовать кортежи. 

>>> list(map(list, set(map(tuple, b)) - set(map(tuple, a))))
[[2, 6, 5], [1, 4, 5]]

Как и в вашем первоначальном подходе, он имеет сложность O (n + m), где n и m - длина списков, что делает его несколько быстрее, чем понимание вложенных списков, которое использует повторный поиск в списках., который имеет O (n) в отличие от поиска в наборах с O (1), но также имеет некоторые накладные расходы для преобразования в кортежи, создания наборов и т. д. На самом ли деле его на самом деле быстрее, иэто стоит более сложного кода, может зависеть от размера списков.

Если списки короткие, например, 10 элементов, понимание списка на самом деле немного быстрее, чем при использовании map и set и довольно немного быстрее, чем map и set и преобразование обратно в list: 

>>> a = [[randint(0, 3) for _ in range(3)] for _ in range(10)]
>>> b = [[randint(0, 3) for _ in range(3)] for _ in range(10)]
>>> %timeit [x for x in b if x not in a]
100000 loops, best of 3: 13.8 us per loop
>>> %timeit set(map(tuple, b)) - set(map(tuple, a))
100000 loops, best of 3: 14 us per loop
>>> %timeit list(map(list, set(map(tuple, b)) - set(map(tuple, a))))
10000 loops, best of 3: 21.8 us per loop

Если списки длиннее, скажем, 1000 элементов,затем использование set становится mucч быстрее. 

>>> a = [[randint(0, 10) for _ in range(3)] for _ in range(1000)]
>>> b = [[randint(0, 10) for _ in range(3)] for _ in range(1000)]
>>> %timeit [x for x in b if x not in a]
10 loops, best of 3: 82.5 ms per loop
>>> %timeit set(map(tuple, b)) - set(map(tuple, a))
1000 loops, best of 3: 1.16 ms per loop
>>> %timeit list(map(list, set(map(tuple, b)) - set(map(tuple, a))))
1000 loops, best of 3: 1.43 ms per loop
0 голосов
/ 26 августа 2018

Вы можете использовать понимание списка, чтобы перебирать b и возвращать списки, которых нет в a.Вот пример: 

a = [[1, 2, 3], [1, 2, 5], [4, 6, 9]]
b = [[1, 2, 3], [1, 4, 5], [2, 6, 5]]
new_array = [x for x in b if x not in a]

И new_array равно: 

[[1, 4, 5], [2, 6, 5]]
...