		*Últimos Cambios*
	Blog personal: El hilo del laberinto

Elegir N líneas al azar de un fichero

Última Actualización: 2 de noviembre de 2011

A veces tenemos que elegir N líneas al azar de un fichero. Por ejemplo, queremos elegir al azar la frase del día, o elegir una palabra de un diccionario de forma aleatoria.

La elección habitual sería leer todo el fichero en memoria y elegir una línea al azar. Pero si el fichero es muy grande es un desperdicio de memoria o, incluso, una imposibilidad si supera nuestra memoria RAM.

Trabajando con ficheros físicos, y suponiendo que estadísticamente todas las líneas tienen un tamaño comparable, podemos hacer un "seek" aleatorio en el fichero y retroceder luego carácter a carácter hasta llegar al inicio de la línea o al principio del fichero. Pero esta operación requiere conocer el tamaño del fichero y tiene problemas con codificaciones de longitud variable tipo UTF-8, ficheros comprimidos, etc. Tampoco se puede usar si no conocemos el tamaño de los datos, si el tamaño de las líneas es muy dispar o si no podemos hacer "seek" (por ejemplo, porque los datos nos están llegando por una conexión TCP). Puede ser que nos estén llegando líneas y no sepamos dónde está el final... hasta que justo llegamos a él.

Lo que queremos es un algoritmo genérico que lea el fichero una sola vez, y que nos proporcione N líneas aleatorias del mismo, sin consumir apenas memoria.

El algoritmo para N=1

Por sencillez, supongamos que N=1. Es decir, queremos una línea al azar del fichero. El algoritmo es el siguiente:

Leemos la primera línea y la almacenamos en memoria.
Leemos la segunda línea y reemplazamos la línea en memoria con una probabilidad del 50%.
...
Leemos la línea "i" y reemplazamos la que tenemos en memoria con una probabilidad 1/i.
Completado el fichero, imprimimos la línea almacenada en memoria.

Este algoritmo cumple lo que queremos: lee el fichero una sola vez y solo necesita recordar una línea. Falta demostrar que es correcto. Hagámoslo por inducción:

Si el fichero solo contiene una línea, el algoritmo la mostrará. Como debe ser.
Si el fichero contiene dos líneas, el algoritmo mostrará una u otra con una probabilidad del 50%. Como debe ser.
Supongamos que el algoritmo proporciona realmente una línea aleatoria de un fichero de L líneas. Es decir, que la probabilidad de cada línea es de 1/L. Sabemos que eso se cumple para el caso de L=1 y L=2, al menos.
Si el algoritmo tiene L+1 líneas, la probabilidad de que se muestre la última línea será de 1/(L+1), y la probabilidad de que se muestre una de las líneas anteriores será L/(L+1). Hay L líneas anteriores y aceptamos el punto anterior, la probabilidad de mostrar cada una de ellas será 1/(L+1). Es decir, si tenemos L+1 líneas, la probabilidad de mostrar una concreta de ellas será de 1/(L+1), como debe ser.
Es decir, como el algoritmo se cumple para el caso L=1 y L=2, se cumple también para L=3. Y, por tanto, también para L=4, así que también para L=5... Demostración por inducción :-).

El programa en sí es trivial: (código Python compatible con Python 3 y versiones recientes de Python 2)

import random, sys

for i, l in enumerate(sys.stdin, start=1) :
    if random.randrange(0, i) == 0 :
        linea = l

print(linea.strip())

El algoritmo para un N general

Leemos las primeras N líneas, y las conservamos en memoria.
Al leer la línea "i", nos la quedamos con probabilidad N/i. Elegimos al azar una de las N líneas almacenadas y la reemplazamos por la línea nueva.
Imprimimos el resultado. Si queremos que el orden de impresión sea aleatorio, desordenamos las N líneas almacenadas primero.

La demostración por inducción es fácil:

Si el fichero tiene N líneas, L=N, es resultado es obviamente correcto.
Si el fichero tiene N+1 líneas, L=N+1, la última línea aparecerá con una probabilidad de N/(N+1), que es correcto. Esa línea ha reemplazado una de las N primeras líneas, con probabilidad 1/N. Es decir, la probabilidad de que una de las N primeras líneas sea descartada es de (N/(N+1))*(1/N) = 1/(N+1). Por lo tanto la probabilidad que dicha línea no sea descartada y se mantenga en el listado final es de 1-(1/(N+1)) = ((N+1)-1)/(N+1) = N/(N+1). Por tanto, con L=N+1, el algoritmo funciona.
Supongamos ahora que el algoritmo funciona para un L dado. Es decir, que la probabilidad de que una línea concreta del fichero aparezca en la salida es de N/L. Ya probamos que eso se cumple para L=N+1.
Si tenemos L+1 líneas, la nueva línea será elegida con probabilidad N/(L+1), siguiendo el algoritmo. Ese valor es correcto. Con las otras líneas almacenadas, dando por bueno el paso anterior, representan al resto del fichero con una probabilidad N/L. Que una línea concreta sea reemplazada tiene una probabilidad de (N/(L+1))*(1/N) = 1/(L+1). Por tanto que no sea reemplazada tiene una probabilidad de 1-(1/L+1)) = ((L+1)-1)/(L+1) = L/(L+1). Pero esa línea almacenada que se conserva a su vez es una línea aleatoria del fichero, con probabilidad N/L, así la probabilidad de que esa línea concreta del fichero aparezca en la salida es el producto de que haya sido elegida cuando teníamos L líneas (N/L) y que no haya sido sustituida en el paso L+1. Es decir (N/L)*(L/L+1) = N/(L+1).
Es decir, si algoritmo es correcto para L líneas, es correcto para L+1 líneas, y hemos probado que es correcto para L=N+1, así que hemos terminado la demostración por inducción.

El programa literal queda un poco feucho, requiere dos números aleatorios. Podemos solucionar este hecho generando un número al azar "p" entre 0 y L, y utilizarlo tanto para decidir si quedarnos con la línea nueva (la probabilidad N/L sería la probabilidad de que p<N) como para elegir el elemento a reemplazar (directamente el elemento "p", ya que en este caso sabemos que 0<=p<N).

La cosa queda algo así: (código compatible con Python 3 y Python 2 recientes)

import random, sys

NUM_ELEMENTOS = 10
lineas = [sys.stdin.readline() for i in xrange(NUM_ELEMENTOS)]

for i, l in enumerate(sys.stdin, start=NUM_ELEMENTOS+1) :
    r = random.randrange(0, i)
    if r < NUM_ELEMENTOS :
        lineas[r] = l

for i in lineas :
    print(i.strip())

Notas finales

Analizando el problema y buscando información por Internet sobre el mismo, me encuentro que se llama "reservoir sampling". El código de ejemplo en la Wikipedia es clavado al mío.

Si realmente estamos trabajando con ficheros físicos en ASCII o LATIN-1 o similares, podemos usar la sugerencia inicial de "seek". La operación es instantánea, comparado con leerse el fichero entero. Las líneas tienen que tener un tamaño comparable, porque sino las más largas tendrán una probabilidad mayor de aparecer. Una posibilidad estadística es hacer "seek"s al azar en el fichero, hasta que caemos sobre un LineFeed (en Unix) o en el offset 0 del fichero, y leemos la línea siguiente.

Aquí todas las líneas serían equiprobables, independientemente de su longitud, a costa de hacer una media de "X" seeks, donde "X" es el tamaño medio de una línea. Hacer 50 "seek"s es costoso, pero menos que leer un fichero de 10 gigabytes :). Por supuesto. esto no nos sirve si los datos no están en un fichero, sino que nos van llegando y no sabemos dónde está el final hasta que llegamos a él.

Historia

02/nov/11: Primera versión de este documento

Más información sobre los OpenBadges

Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS