La forma más rápida de determinar el rango de valores consecutivos más largo en una matriz 2D

El problema

supongamos que estamos trabajando con un gran conjunto de datos y por simplicidad usamos este más pequeño en esta pregunta:

dataset = [["PLANT", 4,11], ["PLANT", 4,12], ["PLANT", 34,4], ["PLANT", 6,5], ["PLANT", 54,45], ["ANIMAL", 5,76], ["ANIMAL", 7,33], ["Animal", 11,1]] 

y queremos averiguar qué columna tiene el rango más largo de valores consecutivos, ¿cuál sería la forma más rápida de averiguarlo, cuál es la mejor columna?

El enfoque ingenuo.

Descubrí que se puede ordenar rápidamente por cada columna con

 sortedDatasets = [] for i in range(1,len(dataset[0]): sortedDatasets.append(sorted(dataset,key=lambda x: x[i])) 

Pero aquí viene la parte de laggy: podríamos continuar desde aquí y hacer un for loop for para cada uno de los conjuntos de datos ordenados, y contar los elementos consecutivos, pero cuando se trata del procesamiento for loops Python es muy lento.

Ahora mi pregunta : ¿hay una manera más rápida que este enfoque ingenuo, tal vez incluso hay una función incorporada para estos contenedores 2D?


Actualizar:

Más precisamente, el significado de un rango puede ser descrito por este pseudo algoritmo – esto incluye incrementar si el current value == next value :

 if nextValue > current Value +1: {reset counter} else: {increment counter} 

Puedes hacer esto con una eficiencia razonable usando groupby . Lo haré por etapas, para que puedas ver cómo funciona.

 from itertools import groupby dataset = [ ["PLANT", 4, 11], ["PLANT", 4, 12], ["PLANT", 34, 4], ["PLANT", 6, 5], ["PLANT", 54, 45], ["ANIMAL", 5, 76], ["ANIMAL", 7, 33], ["ANIMAL", 11, 1], ] # Get numeric columns & sort them in-place sorted_columns = [sorted(col) for col in zip(*dataset)[1:]] print sorted_columns print # Check if tuple `t` consists of consecutive numbers keyfunc = lambda t: t[1] == t[0] + 1 # Search for runs of consecutive numbers in each column for col in sorted_columns: #Create tuples of adjacent pairs of numbers in this column pairs = zip(col, col[1:]) print pairs for k,g in groupby(pairs, key=keyfunc): print k, list(g) print 

salida

 [[4, 4, 5, 6, 7, 11, 34, 54], [1, 4, 5, 11, 12, 33, 45, 76]] [(4, 4), (4, 5), (5, 6), (6, 7), (7, 11), (11, 34), (34, 54)] False [(4, 4)] True [(4, 5), (5, 6), (6, 7)] False [(7, 11), (11, 34), (34, 54)] [(1, 4), (4, 5), (5, 11), (11, 12), (12, 33), (33, 45), (45, 76)] False [(1, 4)] True [(4, 5)] False [(5, 11)] True [(11, 12)] False [(12, 33), (33, 45), (45, 76)] 

Ahora, para atacar tu pregunta actual :

 from itertools import groupby dataset = [ ["PLANT", 4, 11], ["PLANT", 4, 12], ["PLANT", 34, 4], ["PLANT", 6, 5], ["PLANT", 54, 45], ["ANIMAL", 5, 76], ["ANIMAL", 7, 33], ["ANIMAL", 11, 1], ] # Get numeric columns & sort them in-place sorted_columns = [sorted(col) for col in zip(*dataset)[1:]] # Check if tuple `t` consists of consecutive numbers keyfunc = lambda t: t[1] == t[0] + 1 #Search for the longest run of consecutive numbers in each column runs = [] for i, col in enumerate(sorted_columns, 1): pairs = zip(col, col[1:]) m = max(len(list(g)) for k,g in groupby(pairs, key=keyfunc) if k) runs.append((m, i)) print runs #Print the highest run length found and the column it was found in print max(runs) 

salida

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

FWIW, esto se puede condensar en una sola línea. Es un poco más eficiente, ya que utiliza un par de expresiones generadoras en lugar de listas de comprensión, pero no es particularmente legible:

 print max((max(len(list(g)) for k,g in groupby(zip(col, col[1:]), key=lambda t: t[1] == t[0] + 1) if k), i) for i, col in enumerate((sorted(col) for col in zip(*dataset)[1:]), 1)) 

Actualizar

Podemos manejar su nueva definición de secuencia consecutiva haciendo algunos cambios menores.

En primer lugar, necesitamos una función clave que devuelva True si la diferencia entre un par de números adyacentes en una columna ordenada es <= 1.

 def keyfunc(t): return t[1] - t[0] <= 1 

Y en lugar de tomar la longitud de las secuencias que coinciden con esa función clave, ahora hacemos una aritmética simple para ver el tamaño del rango de valores en la secuencia.

 def runlen(seq): return 1 + seq[-1][1] - seq[0][0] 

Poniendolo todo junto:

 def keyfunc(t): return t[1] - t[0] <= 1 def runlen(seq): return 1 + seq[-1][1] - seq[0][0] # Get numeric columns & sort them in-place sorted_columns = [sorted(col) for col in zip(*dataset)[1:]] #Search for the longest run of consecutive numbers in each column runs = [] for i, col in enumerate(sorted_columns, 1): pairs = zip(col, col[1:]) m = max(runlen(list(g)) for k,g in groupby(pairs, key=keyfunc) if k) runs.append((m, i)) print runs #Print the highest run length found and the column it was found in print max(runs) 

Actualización 2

Como se señaló en los comentarios, max genera ValueError si su ValueError es una secuencia vacía. Una forma sencilla de manejar eso es envolver la llamada max en un bloque try..except . Esto es bastante eficiente si la excepción ocurre raramente, try..except que en realidad es más rápido que el equivalente if...else lógica cuando no se produce la excepción Así que podríamos hacer algo como esto:

 run = (runlen(list(g)) for k,g in groupby(pairs, key=keyfunc) if k) try: m = max(run) except ValueError: m = 0 runs.append((m, i)) 

Pero si esa excepción ocurre con bastante frecuencia, es mejor utilizar otro enfoque.

Aquí hay una nueva versión que usa una función de generador en toda regla, find_runs , en lugar de la expresión del generador. find_runs simplemente da sa cero antes de que comience a procesar los datos de la columna, por lo que max siempre tendrá al menos un valor para procesar. He runlen cálculo de runlen para ahorrar en la sobrecarga de una llamada de función adicional. Esta refactorización también facilita la comstackción de la lista de runs en una lista de comprensión.

 from itertools import groupby dataset = [ ["PLANT", 4, 11, 3], ["PLANT", 4, 12, 5], ["PLANT", 34, 4, 7], ["PLANT", 6, 5, 9], ["PLANT", 54, 45, 11], ["ANIMAL", 5, 76, 13], ["ANIMAL", 7, 33, 15], ["ANIMAL", 11, 1, 17], ] def keyfunc(t): return t[1] - t[0] <= 1 def find_runs(col): pairs = zip(col, col[1:]) #This stops `max` from choking if we don't find any runs yield 0 for k, g in groupby(pairs, key=keyfunc): if k: #Determine run length seq = list(g) yield 1 + seq[-1][1] - seq[0][0] # Get numeric columns & sort them in-place sorted_columns = [sorted(col) for col in zip(*dataset)[1:]] #Search for the longest run of consecutive numbers in each column runs = [(max(find_runs(col)), i) for i, col in enumerate(sorted_columns, 1)] print runs #Print the highest run length found and the column it was found in print max(runs) 

salida

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