valores unicos una repite que metodos mas llenar listas lista encontrar elementos elemento comparar arreglos agregar python list sorting

unicos - metodos de listas en python



Argsorting valores en una lista de listas (4)

list.sort

Puede generar una lista de índices y luego llamar a list.sort con una key :

B = [(i, j) for i, x in enumerate(A) for j, _ in enumerate(x)] B.sort(key=lambda ix: A[ix[0]][ix[1]])

print(B) [(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]

Tenga en cuenta que en python-2.x, donde se admite el desempaquetado iterable en funciones, puede simplificar un poco la llamada de sort :

B.sort(key=lambda (i, j): A[i][j])

sorted

Esta es una alternativa a la versión anterior y genera dos listas (una en la memoria que se sorted luego funciona, para devolver otra copia).

B = sorted([ (i, j) for i, x in enumerate(A) for j, _ in enumerate(x) ], key=lambda ix: A[ix[0]][ix[1]] ) print(B) [(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]

Actuación

A petición popular, añadiendo algunos tiempos y una trama.

En el gráfico, vemos que llamar a list.sort es más eficiente que sorted . Esto se debe a que list.sort realiza una ordenación en el lugar, por lo que no existe una sobrecarga de tiempo / espacio a partir de la creación de una copia de los datos sorted .

Funciones

def cs1(A): B = [(i, j) for i, x in enumerate(A) for j, _ in enumerate(x)] B.sort(key=lambda ix: A[ix[0]][ix[1]]) return B def cs2(A): return sorted([ (i, j) for i, x in enumerate(A) for j, _ in enumerate(x) ], key=lambda ix: A[ix[0]][ix[1]] ) def rorydaulton(A): triplets = [(x, i, j) for i, row in enumerate(A) for j, x in enumerate(row)] pairs = [(i, j) for x, i, j in sorted(triplets)] return pairs def jpp(A): def _create_array(data): lens = np.array([len(i) for i in data]) mask = np.arange(lens.max()) < lens[:,None] out = np.full(mask.shape, max(map(max, data))+1, dtype=int) # Pad with max_value + 1 out[mask] = np.concatenate(data) return out def _apply_argsort(arr): return np.dstack(np.unravel_index(np.argsort(arr.ravel()), arr.shape))[0] return _apply_argsort(_create_array(A))[:sum(map(len, A))] def agngazer(A): idx = np.argsort(np.fromiter(chain(*A), dtype=np.int)) return np.array( tuple((i, j) for i, r in enumerate(A) for j, _ in enumerate(r)) )[idx]

Código de rendimiento de referencia

from timeit import timeit from itertools import chain import pandas as pd import numpy as np import matplotlib.pyplot as plt res = pd.DataFrame( index=[''cs1'', ''cs2'', ''rorydaulton'', ''jpp'', ''agngazer''], columns=[10, 50, 100, 500, 1000, 5000, 10000, 50000], dtype=float ) for f in res.index: for c in res.columns: l = [[1, 1, 3], [1, 2], [1, 1, 2, 4]] * c stmt = ''{}(l)''.format(f) setp = ''from __main__ import l, {}''.format(f) res.at[f, c] = timeit(stmt, setp, number=30) ax = res.div(res.min()).T.plot(loglog=True) ax.set_xlabel("N"); ax.set_ylabel("time (relative)"); plt.show();

Tengo una lista de listas A de longitud m . Cada lista de A contiene números positivos de {1, 2, ..., n} . El siguiente es un ejemplo, donde m = 3 y n = 4 .

A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]

Represento cada número x en A como un par (i, j) donde A[i][j] = x . Me gustaría ordenar los números en A en orden no decreciente; Romper los empates por el primer índice más bajo. Es decir, si A[i1][j1] == A[i2][j2] , entonces (i1, j1) aparece antes (i2, j2) iff i1 <= i2 .

En el ejemplo, me gustaría devolver los pares:

(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)

que representa los números ordenados

1, 1, 1, 1, 1, 2, 2, 3, 4

Lo que hice es un enfoque ingenuo que funciona de la siguiente manera:

  • Primero ordeno cada lista en A
  • Luego itero los números en {1, 2, ..., n} y la lista A y agrego los pares.

Código:

for i in range(m): A[i].sort() S = [] for x in range(1, n+1): for i in range(m): for j in range(len(A[i])): if A[i][j] == x: S.append((i, j))

Creo que este enfoque no es bueno. ¿Podemos hacerlo mejor?


Podría hacer trillizos de (x, i, j) , ordenarlos y luego extraer los índices (i, j) . Eso funciona porque los tripletes contienen toda la información necesaria para la clasificación y para su inclusión en la lista final, en el orden necesario para la clasificación. (Esto se denomina "Decora-clasifica-Decora-decora", relacionado con la transformada de Schwartz, desde Hat-tip a @Morgen por el nombre y la generalización y la motivación para que explique la generalidad de esta técnica). Esto podría combinarse en una sola declaración, pero lo dividí aquí para mayor claridad.

A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]] triplets = [(x, i, j) for i, row in enumerate(A) for j, x in enumerate(row)] pairs = [(i, j) for x, i, j in sorted(triplets)] print(pairs)

Aquí está el resultado impreso:

[(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]


Por diversión, aquí hay un método a través de la biblioteca de numpy . El rendimiento es aproximadamente un 10% más lento que la solución de @ coldspeed debido al costoso paso del relleno.

Créditos : Para esta solución, he adaptado la receta array-from-jagged-list @Divakar, y he copiado textualmente la solución de argsort multidimensional de @ AshwiniChaudhary.

import numpy as np A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]] def create_array(data): """Convert jagged list to numpy array; pad with max_value + 1""" lens = np.array([len(i) for i in data]) mask = np.arange(lens.max()) < lens[:,None] out = np.full(mask.shape, max(map(max, data))+1, dtype=int) # Pad with max_value + 1 out[mask] = np.concatenate(data) return out def apply_argsort(arr): """Flatten, argsort, extract indices, then stack into a single array""" return np.dstack(np.unravel_index(np.argsort(arr.ravel()), arr.shape))[0] # limit only to number of elements in A res = apply_argsort(create_array(A))[:sum(map(len, A))] print(res) [[0 0] [0 1] [1 0] [2 0] [2 1] [1 1] [2 2] [0 2] [2 3]]


Solo porque @jpp se divierte:

from itertools import chain import numpy as np def agn(A): idx = np.argsort(np.fromiter(chain(*A), dtype=np.int)) return np.array(tuple((i, j) for i, r in enumerate(A) for j, _ in enumerate(r)))[idx]

Pruebas de tiempo:

Prueba 1:

Comparación contra el método más rápido de @coldspeed:

In [1]: import numpy as np In [2]: print(np.__version__) 1.13.3 In [3]: from itertools import chain In [4]: import sys In [5]: print(sys.version) 3.5.5 |Anaconda, Inc.| (default, Mar 12 2018, 16:25:05) [GCC 4.2.1 Compatible Clang 4.0.1 (tags/RELEASE_401/final)] In [6]: A = [[1],[0, 0, 0, 1, 1, 3], [1, 2], [1, 1, 2, 4]] * 10000 In [7]: %timeit np.array(tuple((i, j) for i, r in enumerate(A) for j, _ in enumerate(r)))[np.argsort(np.fromit ...: er(chain(*A), dtype=np.int))] 89.4 ms ± 718 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [8]: %timeit B = [(i, j) for i, x in enumerate(A) for j, _ in enumerate(x)]; B.sort(key=lambda ix: A[ix[0]] ...: [ix[1]]) 93.5 ms ± 1.65 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Prueba 2a:

Esta prueba utiliza una gran matriz A generada aleatoriamente (cada lista secundaria se ordena porque así es como parece ser la lista OP):

In [20]: A = [sorted([random.randint(1, 100) for _ in range(random.randint(1,1000))]) for _ in range(10000)] In [21]: def agn(A): ...: idx = np.argsort(np.fromiter(chain(*A), dtype=np.int)) ...: return np.array(tuple((i, j) for i, r in enumerate(A) for j, _ in enumerate(r)))[idx] ...: In [22]: %timeit agn(A) 3.1 s ± 62.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [23]: %timeit cs1(A) 3.2 s ± 89.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Prueba 2.b

Similar a la prueba 2.b pero con una matriz sin clasificar A :

In [25]: A = [[random.randint(1, 100) for _ in range(random.randint(1,1000))] for _ in range(10000)] In [26]: %timeit cs1(A) 4.24 s ± 215 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [27]: %timeit agn(A) 3.44 s ± 49.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)