software2

Rebanar una lista uniformemente con Python

2017-05-14Comentarios

Sliced Python

He aquí un problema que se me ocurrió contra recientemente.

La tarea consistía en picar una lista en exactamente n uniformemente slized trozos. Para darle un poco más de contexto, supongamos que queremos dividir una lista de trabajos por igual entre los n de los trabajadores, donde n puede ser el número de núcleos de CPU disponibles.

Podemos construir el resultado repetidamente rebanar la entrada:

def chunk(xs, n): ""Dividir la lista, xs, en n trozos"' L = len(xs) afirmar 0 < n <= L s = L//n volver [xs[p:p+s] de p en el intervalo(0, L, s)] 

Esto se ve prometedor

>>> chunk('abcdefghi', 3)
['abc', 'def', 'ghi'] 

pero, si el tamaño de la lista no es un múltiplo exacto de n, el resultado no contiene exactamente ntrozos.

>>> chunk('abcde', 3)
['a', 'b', 'c', 'd', 'e']
>>> chunk('abcdefgh', 3)
['ab', 'cd', 'ef', 'gh']
>>> chunk('abcdefghij', 3)
['abc', 'def', 'ghi', 'j'] 

(Por cierto, estoy usando cadenas en lugar de las listas en los ejemplos. El código funciona igual de bien para ambos tipos, y las cadenas de hacer un poco más fácil ver lo que está pasando.)

Una forma de solucionar el problema es el grupo de la final trozos juntos.

def chunk(xs, n): ""Dividir la lista, xs, en n trozos"' L = len(xs) afirmar 0 < n <= L s, r = divmod(L, n) trozos = [xs[p:p+s] de p en el intervalo(0, L, s)] trozos[n-1:] = [xs[-r-s:]] volver trozos 

Ahora tenemos exactamente n trozos, pero no puede ser de tamaño uniforme, ya que el último fragmento se pone collar con cualquier excedente.

>>> chunk('abcde', 3)
['a', 'b', 'cde']
>>> chunk('abcdefgh', 3)
['ab', 'cd', 'efgh']
>>> chunk('abcdefghij', 3)
['abc', 'def', 'ghij'] 

¿Qué significa “de tamaño uniforme” realmente significa? A grandes rasgos, queremos que la resultante trozos como estrechamente tamaño como sea posible.

Más precisamente, si el resultado de dividir la longitud de la lista L por el número de fragmentos n da una talla s con el resto r, entonces la función debe devolver r trozos de tamaño s+1 y n-r trozos de tamaño s. Hay elija(n, r) maneras de hacer esto. He aquí una solución que pone a los largos trozos de la parte frontal de los resultados.

def chunk(xs, n): ""Dividir la lista, xs, en n trozos de tamaño uniforme"' L = len(xs) afirmar 0 < n <= L s, r = divmod(L, n) t = s + 1 retorno ([xs[p:p+t] para p en el intervalo(0, r*t, t)] + [xs[p:p+s] para p en el rango(r*t, L, s)]) 

Aquí está una segunda aplicación, esta vez utilizando itertools. El encadenamiento de r copias de s+1 y n-r copias de s nos da el n pedazo de ancho. La acumulación de los anchos nos da la lista de las compensaciones para cortar — a pesar de la nota que debemos anteponer un inicial de 0. Ahora podemos formar un (a esto, el próximo par de iteradores sobre los desplazamientos, y el resultado es la acumulación de repetidos (comienzo, final), rebanadas tomado de la lista original.

de itertools de importación se acumulan, la cadena, la repetición, el tee def chunk(xs, n): afirmar n > 0 L = len(xs) s, r = divmod(L, n) anchos = cadena(repetir(s+1, r), repetir(s, n-r)) compensaciones = acumulan(de la cadena((0,), anchos)) b, e = tee(offsets)
siguiente(e) volver [xs[s] de s en el mapa(slice, b, e)] 

Esta versión no algo razonable en el caso de que el número de cortes, n, supera la longitud de la lista.

>>> chunk('ab', 5)
['a', 'b', ", ", "] 

Por último, algunas de las pruebas.

def test_chunk(): afirmar pedazo(", 1) == ["] afirmar chunk('ab', 2) == ['a', 'b'] afirmar chunk('abc', 2) == ['ab', 'c'] xs = list(range(8)) afirmar chunk(xs, 2) == [[0, 1, 2, 3], [4, 5, 6, 7]] afirmar chunk(xs, 3) == [[0, 1, 2], [3, 4, 5], [6, 7]] afirmar chunk(xs, 5) == [[0, 1], [2, 3], [4, 5], [6], [7]] rs = rango(1000000) afirmar chunk(rs, 2) == [rango(500000), rango(500000, 1000000)] 

Software almacen de Cea Ordenadores

Comentarios desactivados en Rebanar una lista uniformemente con Python