linux - texto - terminal unix

Escoge al azar las líneas de un archivo sin sorberlo con Unix

Question

Tengo un archivo de 10 ^ 7 líneas, en el que quiero elegir 1/100 de líneas al azar del archivo. Este es el código AWK que tengo, pero absorbe todo el contenido del archivo de antemano. La memoria de mi PC no puede manejar tales sorbos. ¿Hay otro enfoque para hacerlo?

awk ''BEGIN{srand()}
!/^$/{ a[c++]=$0}
END {  
  for ( i=1;i<=c ;i++ )  { 
    num=int(rand() * c)
    if ( a[num] ) {
        print a[num]
        delete a[num]
        d++
    }
    if ( d == c/100 ) break
  }
 }'' file

Answer 1

El problema de cómo muestrear uniformemente N elementos de una población grande (de tamaño desconocido) se conoce como Muestreo de Yacimientos . (Si le gustan los problemas de algoritmos, dedique unos minutos a intentar resolverlos sin leer el algoritmo en Wikipedia).

Una búsqueda web para "Muestreo de yacimientos" encontrará muchas implementaciones. Here está el código de Perl y Python que implementa lo que desea, y here hay otro hilo de Desbordamiento de pila que lo analiza.

Answer 2

En este caso, el muestreo de yacimientos para obtener exactamente k valores es lo suficientemente trivial con awk que me sorprende que ninguna solución lo haya sugerido todavía. Tuve que resolver el mismo problema y escribí el siguiente programa awk para muestreo:

NR < k {
    reservoir[NR] = $0;
}
NR >= k {
    i = int(NR * rand());
    if (i < k) {
        reservoir[i] = $0;
    }
}
END {
    for (i in reservoir) {
        print reservoir[i];
    }
}

Luego, averiguar qué k se tiene que hacer por separado, por ejemplo, configurando awk -v ''k=int(''$(dc -e "$(cat FILE | wc -l) 0.01 * n")'')''

Answer 3

En lugar de esperar hasta el final para elegir al azar el 1% de las líneas, hazlo cada 100 líneas en "/ ^ $ /". De esta forma, solo tienes 100 líneas a la vez.

Answer 4

Escribí este código exacto en Gawk: estás de suerte. Es larga en parte porque conserva el orden de entrada. Probablemente hay mejoras de rendimiento que se pueden hacer.

Este algoritmo es correcto sin conocer el tamaño de entrada por adelantado. Publiqué una piedra Rosetta aquí al respecto. (No publiqué esta versión porque hace comparaciones innecesarias).

Tema original: Enviado para su revisión: muestreo aleatorio en awk.

# Waterman''s Algorithm R for random sampling
# by way of Knuth''s The Art of Computer Programming, volume 2

BEGIN {
    if (!n) {
        print "Usage: sample.awk -v n=[size]"
        exit
    }
    t = n
    srand()

}

NR <= n {
    pool[NR] = $0
    places[NR] = NR
    next

}

NR > n {
    t++
    M = int(rand()*t) + 1
    if (M <= n) {
        READ_NEXT_RECORD(M)
    }

}

END {
    if (NR < n) {
        print "sample.awk: Not enough records for sample" /
            > "/dev/stderr"
        exit
    }
    # gawk needs a numeric sort function
    # since it doesn''t have one, zero-pad and sort alphabetically
    pad = length(NR)
    for (i in pool) {
        new_index = sprintf("%0" pad "d", i)
        newpool[new_index] = pool[i]
    }
    x = asorti(newpool, ordered)
    for (i = 1; i <= x; i++)
        print newpool[ordered[i]]

}

function READ_NEXT_RECORD(idx) {
    rec = places[idx]
    delete pool[rec]
    pool[NR] = $0
    places[idx] = NR  
} 

Answer 5

Esto debería funcionar en la mayoría de las máquinas GNU / Linux.

$ shuf -n $(( $(wc -l < $file) / 100)) $file

Me sorprendería si el comando GNU shuf hiciera una gestión de memoria inapropiada.

Answer 6

No lo sé, pero hay una gran técnica para resolver una versión más general del problema que ha descrito, y en el caso general es mucho más rápido que la línea de retorno de línea si rand <0.01 enfoque, por lo que podría ser útil si tiene la intención de realizar tareas como las anteriores muchos (miles, millones) de veces. Se lo conoce como muestreo de yacimientos y esta página tiene una explicación bastante buena de una versión aplicable a su situación.

Answer 7

Podrías hacerlo en dos pasos:

• Ejecuta el archivo una vez, solo para contar cuántas líneas hay
• Seleccione al azar los números de línea de las líneas que desea imprimir, almacenándolos en una lista ordenada (o un conjunto)
• Ejecuta el archivo una vez más y selecciona las líneas en las posiciones seleccionadas

Ejemplo en python:

fn = ''/usr/share/dict/words''

from random import randint
from sys import stdout

count = 0
with open(fn) as f:
   for line in f:
      count += 1

selected = set()
while len(selected) < count//100:
   selected.add(randint(0, count-1))

index = 0
with open(fn) as f:
   for line in f:
      if index in selected:
          stdout.write(line)
      index += 1

Answer 8

Si el objetivo es simplemente evitar el agotamiento de la memoria, y el archivo es un archivo común, no es necesario implementar el muestreo del yacimiento. El número de líneas en el archivo se puede conocer si realiza dos pasadas en el archivo, una para obtener el número de líneas (como con wc -l ), una para seleccionar la muestra:

file=/some/file
awk -v percent=0.01 -v n="$(wc -l < "$file")" ''
  BEGIN {srand(); p = int(n * percent)}
  rand() * n-- < p {p--; print}'' < "$file"

Answer 9

Usaste awk, pero no sé si es obligatorio. Si no es así, aquí hay una manera trivial de hacer w / perl (y sin cargar todo el archivo en la memoria):

cat your_file.txt | perl -n -e ''print if (rand() < .01)''

(forma más simple, de los comentarios):

perl -ne ''print if (rand() < .01)'' your_file.txt 

Answer 10

si tiene tantas líneas, ¿está seguro de que quiere exactamente el 1% o una estimación estadística sería suficiente?

En ese segundo caso, solo aleatorice al 1% en cada línea ...

awk ''BEGIN {srand()} !/^$/ { if (rand() <= .01) print $0}''

Si desea la línea de encabezado más una muestra aleatoria de líneas después, use:

awk ''BEGIN {srand()} !/^$/ { if (rand() <= .01 || FNR==1) print $0}''