Encontrar n mayores diferencias entre dos listas

Question

Tengo dos listas old y new, con el mismo número de elementos.

Estoy tratando de escribir una función eficiente que tome n Como parámetro, compara los elementos de dos listas en las mismas ubicaciones (por índice), encuentra n mayores diferencias y devuelven los índices de aquellos n elementos.

Estaba pensando que esto se resolvería mejor por un diccionario de valor sorteado, pero uno no está disponible en Python (y no conozco ninguna biblioteca que lo ofrezca). ¿Quizás hay una mejor solución?

Answer 1

Siempre que pienses "n más grande", pensar 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)]

Esto encontrará los elementos X más grandes en el tiempo O (n log x), donde n es el número total de elementos en la lista; La clasificación lo hace en o (n log n) tiempo.

Simplemente se me ocurrió que lo anterior en realidad no hace lo que usted pidió. ¡Quieres un índice! Todavía muy fácil. También usaré abs Aquí en caso de que desee el valor absoluto de la diferencia:

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

Suponiendo que el número de elementos en las listas no sea enorme, solo podría diferirlos todos, clasificarlos y elegir el primero n:

print sorted((abs(x-y) for x,y in zip(old, new)), reverse=True)[:n]

Esto sería O(k log k) dónde k es la longitud de sus listas originales.

Si n es significativamente más pequeño que k, la mejor idea sería usar el nlargest función proporcionada por el heapq módulo:

import heapq
print heapq.nlargest(n, (abs(x-y) for x,y in zip(old, new))

Esto será O(k log n) en vez de O(k log k) que puede ser significativo para k >> n. Además, si sus listas son realmente grandes, probablemente estaría mejor usando itertools.izip en lugar del regular zip función.

Answer 3

De tu pregunta creo que esto es lo que quieres:

En diferencia.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)

Ejecución:

[avasal@avasal ]# python difference.py 
Enter value of n:4
largest diff:  116
index of values: 2
[avasal@avasal]#

Si esto no es lo que quieres, considera elaborar la pregunta poco más.

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 Viene a mano para tareas repetitivas. De starmap conversos tuples a *args. Para referencia. With max función podrá obtener el resultado deseado. index La función ayudará a encontrar la posición.

l.index(max(l)

>>> l.index(max(l))
6: 2

Answer 5

Aquí hay una solución pirateada en numpy (Descargo de responsabilidad, soy un novato en Numpy, por lo que puede haber formas aún más hábiles de hacer esto). No combiné ninguno de los pasos, por lo que está muy claro qué estaba haciendo cada paso. El valor final es una lista de los índices de las listas originales en orden del Delta más alto. Elegir la parte superior n es simplemente sorted_inds[:n] y recuperar los valores de cada lista o de la lista delta es trivial.

No sé cómo se compara en el rendimiento con las otras soluciones y obviamente no se mostrará con un conjunto de datos tan pequeño, pero podría valer la pena probar con su conjunto de datos real, ya que mi entendimiento es que Numpy es muy rápido Para operaciones de matriz numérica.

Código

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

Producción

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]