Поиск самых больших различий между двумя списками
-
27-10-2019 - |
Вопрос
У меня есть два списка old
а также new
, с тем же количеством элементов.
Я пытаюсь написать эффективную функцию, которая занимает n
В качестве параметра сравнивает элементы двух списков в одних и тех же местах (по индексу), находит n
самые большие различия и возвращает индексы этих n
элементы.
Я думал, что это лучше всего решить словарем, содержащим ценность, но один не доступно В Python (и я не знаю ни о каких библиотеках, которые это предлагают). Возможно, есть лучшее решение?
Решение
Всякий раз, когда ты думаешь "n самый большой", считать heapq
.
>>> import heapq
>>> import random
>>> l1 = [random.randrange(100) for _ in range(100)]
>>> l2 = [random.randrange(100) for _ in range(100)]
>>> heapq.nlargest(10, (((a - b), a, b) for a, b in zip(l1, l2)))
[(78, 99, 21), (75, 86, 11), (69, 90, 21), (69, 70, 1), (60, 86, 26), (55, 95, 40), (52, 56, 4), (48, 98, 50), (46, 80, 34), (44, 81, 37)]
Это найдет X самые большие элементы в O (n log x), где n - это общее количество элементов в списке; Сортировка делает это во время O (n log n).
Мне просто пришло в голову, что вышесказанное на самом деле не делает то, о чем вы просили. Вы хотите индекс! Все еще очень легко. Я также буду использовать abs
Здесь, если вы хотите абсолютное значение разницы:
>>> heapq.nlargest(10, xrange(len(l1)), key=lambda i: abs(l1[i] - l2[i]))
[91, 3, 14, 27, 46, 67, 59, 39, 65, 36]
Другие советы
Предполагая, что количество элементов в списках не огромно, вы можете просто отличить их всех, сортировать и выбрать первое n
:
print sorted((abs(x-y) for x,y in zip(old, new)), reverse=True)[:n]
Это было бы O(k log k)
куда k
это длина ваших исходных списков.
Если n
значительно меньше, чем k
, лучшая идея - использовать nlargest
функция, предоставленная heapq
модуль:
import heapq
print heapq.nlargest(n, (abs(x-y) for x,y in zip(old, new))
Это будет O(k log n)
вместо O(k log k)
что может быть значительным для k >> n
. Анкет Кроме того, если ваши списки действительно большие, вам, вероятно, будет лучше использовать itertools.izip
вместо обычного zip
функция
Из вашего вопроса я думаю, что это то, что вы хотите:
В разнице.py
l1 = [15,2,123,4,50]
l2 = [9,8,7,6,5]
l3 = zip(l1, l2)
def f(n):
diff_val = 0
index_val = 0
l4 = l3[:n]
for x,y in l4:
if diff_val < abs(x-y):
diff_val = abs(x-y)
elem = (x, y)
index_val = l3.index(elem)
print "largest diff: ", diff_val
print "index of values:", index_val
n = input("Enter value of n:")
f(n)
Исполнение:
[avasal@avasal ]# python difference.py
Enter value of n:4
largest diff: 116
index of values: 2
[avasal@avasal]#
Если это не то, что вы хотите, рассмотрите вопрос о том, чтобы уточнить вопрос немного больше ..
>>> l = []
... for i in itertools.starmap(lambda x, y: abs(x-y), itertools.izip([1,2,3], [100,102,330])):
... l.append(i)
>>> l
5: [99, 100, 327]
itertools
пригодится для повторяющихся задач. Из starmap
конверты tuples
к *args
. Анкет За ссылка. With max
Функция вы сможете получить желаемый результат. index
Функция поможет найти позицию.
l.index(max(l)
>>> l.index(max(l))
6: 2
Вот решение, взломанное в Numpy (Отказ от ответственности, я новичок в Numpy, так что могут быть даже более гладкие способы сделать это). Я не сочетал ни одного из шагов, поэтому совершенно ясно, что делал каждый шаг. Окончательное значение - это список индексов исходных списков в порядке самой высокой дельты. Выбор верхнего n просто sorted_inds[:n]
и извлечение значений из каждого списка или из списка Delta тривиально.
Я не знаю, как это сравнивается с производительностью с другими решениями, и, очевидно, не будет отображаться с таким небольшим набором данных, но, возможно, стоит провести тестирование с вашим реальным набором данных, так как я понимаю, что Numpy очень быстро очень быстро Для численных операций массива.
Код
import numpy
list1 = numpy.array([1, 2, 3, 4, 5, 6, 7, 8, 9])
list2 = numpy.array([9, 8, 7, 6, 5, 4, 3, 2, 1])
#Caculate the delta between the two lists
delta = numpy.abs(numpy.subtract(list1, list2))
print('Delta: '.ljust(20) + str(delta))
#Get a list of the indexes of the sorted order delta
sorted_ind = numpy.argsort(delta)
print('Sorted indexes: '.ljust(20) + str(sorted_ind))
#reverse sort
sorted_ind = sorted_ind[::-1]
print('Reverse sort: '.ljust(20) + str(sorted_ind))
Выход
Delta: [8 6 4 2 0 2 4 6 8]
Sorted indexes: [4 3 5 2 6 1 7 0 8]
Reverse sort: [8 0 7 1 6 2 5 3 4]