найти n самых больших различий между двумя списками

Question

У меня есть два списка old и new, с одинаковым количеством элементов.

Я пытаюсь написать эффективную функцию, которая принимает n в качестве параметра, сравнивает элементы двух списков в тех же местах (по индексу), находит n самые большие различия и возвращает индексы этих n элементов.

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

Answer 1

Всякий раз, когда вы думаете, " 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]

Answer 2

Если предположить, что количество элементов в списках невелико, вы можете просто различать их все, отсортировать и выбрать первое 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.

Answer 3

Вот решение, взломанное вместе в numpy (отказ от ответственности, я новичок в numpy, поэтому могут быть даже более изощренные способы сделать это). Я не совмещал ни одного из шагов, поэтому очень ясно, что делал каждый шаг. Конечное значение представляет собой список индексов исходных списков в порядке наивысшей дельты. Выбор верхнего n - это просто sorted_inds[:n], а извлечение значений из каждого списка или из дельта-списка тривиально.

Я не знаю, как он сравнивается по производительности с другими решениями, и он, очевидно, не будет отображаться с таким небольшим набором данных, но, возможно, стоит проверить его с вашим реальным набором данных, так как я понимаю, что 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]

Answer 4

>>> 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

Answer 5

От вашего вопроса я думаю, что это то, что вы хотите:

In diff.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]#

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