manejo - ¿Cuál es la mejor manera de devolver una línea al azar en un archivo de texto usando C?

guardar y leer datos en un archivo.txt en c

Question

¿Cuál es la mejor manera de devolver una línea al azar en un archivo de texto usando C? Tiene que usar la biblioteca de E / S estándar ( <stdio.h> ) porque es para homebrew de Nintendo DS.

Aclaraciones:

• Usar un encabezado en el archivo para almacenar el número de líneas no funcionará para lo que quiero hacer.
• Quiero que sea lo más aleatorio posible (lo mejor es que cada línea tenga la misma probabilidad de ser elegida que cualquier otra línea).
• El archivo nunca cambiará mientras se ejecuta el programa. (Es el DS, por lo que no hay multitareas).

Answer 1

1. Obtenga la longitud del archivo.
2. Elija una posición aleatoria en el archivo.
3. Busque a esa posición.
4. Itera hacia adelante hasta que encuentre un carácter de nueva línea.
5. Si no encuentra un carácter de línea nueva, vuelva al principio.
6. Use gets () para leer la línea.

Answer 2

La respuesta de Mark es casi correcta a excepción de dos problemas:

1. Si una línea es más larga que la length - 1 caracteres (incluida la nueva línea), el ciclo while incrementará el count al menos dos veces para la misma línea: una para la primera length - 1 caracteres, otra para la siguiente length - 1 caracteres, etc. .
2. El cálculo del rand() * count de rand() * count puede causar un desbordamiento de enteros.

Para resolver el primer problema, puede invocar fgets en un búfer de la papelera hasta que devuelva NULL (lo que indica un error de E / S o EOF sin datos leídos) o el búfer de la papelera contiene una nueva línea:

count = 0;
while (fgets(line, length, stream) != NULL)
{
char *p = strchr(line, ''/n'');
if (p != NULL) {
assert(*p == ''/n'');
*p = ''/0''; // trim the newline
}
else { // haven''t reached EOL yet. Read & discard the rest of the line.
#define TRASH_LENGTH 1024
char trash[TRASH_LENGTH];
while((p = fgets(trash, TRASH_LENGTH, stream)) != NULL) {
if ((p = strchr(trash, ''/n'')) != NULL) // reached EOL
break;
}
}
assert(strchr(line, ''/n'') == NULL); // `line` does not contain a newline
count++;
// ...

El segundo problema se puede resolver con la sugerencia de @tvanfosson si la aritmética de coma flotante no está disponible:

int one_chance_in(size_t n)
{
if (rand() % n == 0) // `rand` returns an integer in [0, `RAND_MAX`]
return 1;
else
return 0;
}

Pero tenga en cuenta que rand() % n no es una variable aleatoria uniforme y discreta, incluso si se supone que rand() es uno porque la probabilidad de que rand() % n == 0 puede ser tanto como 1 / RAND_MAX mayor que la deseada probabilidad 1 / n . En mi máquina, RAND_MAX es 2147483647, por lo que la diferencia es 4.66 × 10 ^-10 , pero el estándar C solo requiere que RAND_MAX sea ​​al menos 32767 (diferencia de 3.05 × 10 ^-5 ).

Además, si alguien se pregunta por qué funciona este esquema (como yo), podría ser útil trabajar en el cálculo de la probabilidad de que la primera línea permanezca en keptline si hay m lines y generalize: en la primera iteración del ciclo , la probabilidad de que la primera línea se copie a keptline es 1/1. En la segunda iteración del ciclo, la probabilidad de que la segunda línea no sobrescriba la primera línea es 1/2. En la tercera iteración, la probabilidad de que la tercera línea no sobrescriba la primera línea es 2/3. Continuando, la probabilidad de que la última línea no sobrescriba la primera línea es ( m - 1) / m . Por lo tanto, la probabilidad de que la primera línea permanezca en keptline después de iterar sobre todas las líneas es:

1/1 × 1/2 × 2/3 × 3/4 × ... × ( m - 2) / ( m - 1) × ( m - 1) / m = 1 / m

La probabilidad de que la segunda línea permanezca en keptline es:

1/2 × 2/3 × 3/4 × ... × ( m - 2) / ( m - 1) × ( m - 1) / m = 1 / m

La probabilidad de que la tercera línea permanezca en keptline es:

1/3 × 3/4 × ... × ( m - 2) / ( m - 1) × ( m - 1) / m = 1 / m

Etc. Son todos 1 / m .

Answer 3

Lea cada línea y use un número aleatorio para elegir si desea mantener esa línea o ignorarla. Para la primera línea, quiere probabilidades de 1: 1 para mantener; por el segundo, quiere probabilidades de 1: 2, etc.

count = 0;
while (fgets(line, length, stream) != NULL)
{
count++;
if ((rand() * count) / RAND_MAX == 0)
strcpy(keptline, line);
}

No he verificado que tenga las cualidades aleatorias adecuadas, pero parece correcto a primera vista.

Se ha señalado que el desbordamiento de enteros se convertiría rápidamente en un problema con la forma en que se codifica la comparación, y yo mismo había llegado a la misma conclusión de forma independiente. Probablemente haya muchas maneras de arreglarlo, pero este es el primero que se me ocurre:

if ((rand() / (float)RAND_MAX) <= (1.0 / count)) 

Answer 4

Solo una nota rápida sobre la forma en que Mark Ransom evita el desbordamiento de enteros: el DS no tiene FPU, por lo que la división de coma flotante será emulada en el software y muy lenta. Deberá evitar que el encasillado / promoción flote o se duplique a toda costa, si la velocidad es una preocupación.

Aquí hay una forma diferente de evitar el desbordamiento de enteros que evita cualquier punto flotante matemático:

if(rand() <= RAND_MAX / count)

Las probabilidades pueden estar ligeramente sesgadas debido a la división de enteros, pero esto ciertamente debería correr mucho más rápido en un DS.

Answer 5

Tengo una solución alternativa. Dado que la plataforma es el DS, probablemente no desee intentar mantener el archivo en la memoria. Esto lee el archivo dos veces. Una vez para contar las líneas y la segunda vez para encontrar la línea que quiere. Esto funcionaría más lento que las otras soluciones sugeridas hasta el momento, pero apenas utiliza memoria. Incluso lo escribí en C para ti (omití el manejo de errores):

main(int argc, char **argv)
{
FILE *f;
int nLines = 0;
char line[1024];
int randLine;
int i;
srand(time(0));
f = fopen(argv[1], "r");
/* 1st pass - count the lines. */
while(!feof(f))
{
fgets(line, 1024, f);
nLines++;
}
randLine = rand() % nLines;
printf("Chose %d of %d lines/n", randLine, nLines);
/* 2nd pass - find the line we want. */
fseek(f, 0, SEEK_SET);
for(i = 0; !feof(f) && i <= randLine; i++)
fgets(line, 1024, f);
printf("%s", line);
}

ACTUALIZACIÓN: Ups, debería haber leído la respuesta de Brian R. Bondy antes de publicar esto, pero estaba obsesionada con escribir el código y no me di cuenta. Esto es casi lo mismo, excepto que no almacena las posiciones de línea en una matriz. Podrías hacerlo de cualquier manera dependiendo de qué tan grande sea el archivo y si la velocidad es más importante que guardar la memoria.

Answer 6

Todo lo que necesita hacer es generar un número aleatorio sin escala por línea, mientras mantiene el valor máximo para todos los números aleatorios que genere. Siempre que actualice el valor máximo, sobrescribirá la línea seleccionada con la línea actual.

Al final, obtiene la línea asociada con el número más alto de rand () escupido, que debería ser igualmente probable entre todas sus líneas.

Answer 7

Use una combinación del desplazamiento aleatorio de Adam en el enfoque de archivo y el enfoque de probabilidad de Mark. El método de Adam puede llevarte aleatoriamente a una sección del archivo. Luego usa el enfoque de Mark para evitar preferir las cadenas más grandes. El algoritmo de Mark preferirá las primeras cadenas de donde quiera que empiece,

Answer 8

Este método es bueno porque:

i) Puedes seguir generando líneas aleatorias sin grandes costos

ii) Solo tiene que leer el archivo un total de 1 vez + 1 línea a la vez por línea aleatoria que desee. El exceso de datos de lectura solo es igual al tamaño del archivo.

iii) Da a cada línea una oportunidad justa sin importar su posición en el archivo.

iv) Le da a cada línea una oportunidad justa sin importar su longitud en el archivo.

La sugerencia:

Yo sugeriría un algoritmo de 2 pasos. Bueno, realmente es un paso + N líneas. Donde N es el número de líneas aleatorias que desea.

El primer pase que usaría para calcular cuántas líneas y las posiciones de inicio de cada línea.

A continuación, tome un número aleatorio de 0 a la cantidad de líneas menos 1. Use ese número aleatorio, que es su índice de línea, obtenga la posición de inicio para ese índice de línea. Busque a esa posición.

A continuación, solo necesita 1 lectura más y conoce el tamaño exacto. (hasta el índice de inicio de la línea siguiente)

Cómo almacenar el número de líneas y el índice de cada línea:

Para almacenar el número de líneas, obviamente puede simplemente usar un int.

Si puede usar un vector, puede agregar cada índice de línea al vector. Si no, puedes crear una matriz de entradas con la cantidad máxima de líneas que crees que habrá. Luego indice en esa matriz.

Otras respuestas:

Otra respuesta mencionó que puede elegir un número aleatorio de 1 al tamaño del archivo y luego usar la línea nueva más cercana. Pero esto no funcionará Por ejemplo, puede tener 1 línea que es realmente larga y las otras que no son tan largas. En ese caso, tendrías una distribución desigual.