lectura - guardar y leer datos en un archivo.txt en c

¿Cómo leo y analizo un archivo de texto con números, rápido(en C)?

Question

La última actualización: mi compañero de clase usa fread() para leer alrededor de un tercio de todo el archivo en una cadena, esto puede evitar la falta de memoria. Luego procese esta cadena, separe esta cadena en su estructura de datos. Tenga en cuenta que debe preocuparse por un problema: al final de esta cadena, estos últimos caracteres pueden no consistir en un número entero. Piense en una forma de detectar esta situación para poder conectar estos caracteres con los primeros caracteres de la siguiente cadena. Cada número corresponde a una variable diferente en su estructura de datos. Su estructura de datos debe ser muy simple porque cada vez que inserte sus datos en una estructura de datos, es muy lento. La mayor parte del tiempo se dedica a insertar datos en la estructura de datos. Por lo tanto, la forma más rápida de procesar estos datos es utilizar fread() para leer este archivo en una cadena, separar esta cadena en diferentes matrices unidimensionales. Por ejemplo (solo un ejemplo, no provino de mi proyecto), tengo un archivo de texto, como:

72 24 20
22 14 30
23 35 40
42 29 50
19 22 60
18 64 70
.
.
.

Cada fila es la información de una persona. La primera columna significa la edad de la persona, la segunda columna es su depósito, la segunda es la edad de su esposa. Luego usamos fread() para leer este archivo de texto en una cadena, luego uso un stroke() para separarlo (puedes usar una forma más rápida de separarlo). ¡No use la estructura de datos para almacenar los datos separados! Quiero decir, no hagas esto:

struct person
{
int age;
int deposit;
int wife_age;
};
struct person *my_data_store;
my_data_store=malloc(sizeof(struct person)*length_of_this_array);
//then insert separated data into my_data_store

¡No use la estructura de datos para almacenar datos! La forma más rápida de almacenar sus datos es la siguiente:

int *age;
int *deposit;
int *wife_age;
age=(int*)malloc(sizeof(int)*age_array_length);
deposit=(int*)malloc(sizeof(int)*deposit_array_length);
wife_age=(int*)malloc(sizeof(int)*wife_array_length);
// the value of age_array_length,deposit_array_length and wife_array_length will be known by using `wc -l`.You can use wc -l to get the value in your C program
// then you can insert separated data into these arrays when you use `stroke()` to separate them.

La segunda actualización: la mejor manera es usar freed() para leer parte del archivo en una cadena, luego separe esta cadena en su estructura de datos. Por cierto, no use ninguna función de biblioteca estándar que pueda formatear una cadena en un entero, eso es lento, como fscanf() or atoi() , deberíamos escribir nuestra propia función para transferir una cadena a n entero. No solo eso, sino que también debemos diseñar una estructura de datos más simple para almacenar estos datos. Por cierto, mi compañero de clase puede leer este archivo 1.7G en 7 segundos. Hay una manera de hacer esto. De esa manera es mucho mejor que usar multiproceso. No he visto su código, después de ver su código, actualizaré la tercera vez para decirle cómo podría hacerlo. Eso será dos meses después de que finalice nuestro curso.

Actualización: ¡Uso multihilo para resolver este problema! ¡Funciona! Aviso: no use clock () para calcular el tiempo cuando se usa multihilo, por eso pensé que el tiempo de ejecución aumenta.

Una cosa que quiero aclarar es que el tiempo de lectura del archivo sin almacenar el valor en mi estructura es de unos 20 segundos. El tiempo de almacenamiento del valor en mi estructura es de unos 60 segundos. La definición de "hora de leer el archivo" incluye la hora de leer todo el archivo y almacenar el valor en mi estructura. el momento de leer el archivo = escanear el archivo + almacenar el valor en mi estructura. Por lo tanto, ¿tiene algunas sugerencias para almacenar valor más rápido? (Por cierto, no tengo control sobre el archivo de entrada, es generado por nuestro profesor. Estoy tratando de usar multiproceso para resolver este problema, si funciona, le diré el resultado).

Tengo un archivo, su tamaño es 1.7G. Parece que:

1 1427826
1 1427827
1 1750238
1 2
2 3
2 4
3 5
3 6
10 7
11 794106
.
.

y su hijo en. Tiene unos diez millones de líneas en el archivo. Ahora necesito leer este archivo y almacenar estos números en mi estructura de datos en 15 segundos. He intentado usar freed() para leer todo el archivo y luego usar strtok() para separar cada número, pero todavía necesito 80 segundos. Si uso fscanf() , será más lento. ¿Cómo lo acelero? Tal vez no podamos hacerlo en menos de 15 segundos. Pero 80 segundos para leerlo es demasiado largo. ¿Cómo leerlo lo más rápido que podamos?

Aquí es parte de mi código de lectura:

int Read_File(FILE *fd,int round)
{
clock_t start_read = clock();
int first,second;
first=0;
second=0;
fseek(fd,0,SEEK_END);
long int fileSize=ftell(fd);
fseek(fd,0,SEEK_SET);
char * buffer=(char *)malloc(sizeof(char)*fileSize);
char *string_first;
long int newFileSize=fread(buffer,1,fileSize,fd);
char *string_second;
while(string_first!=NULL)
{
first=atoi(string_first);
string_second=strtok(NULL," /t/n");
second=atoi(string_second);
string_first=strtok(NULL," /t/n");
max_num= first > max_num ? first : max_num ;
max_num= second > max_num ? second : max_num ;
root_level=first/NUM_OF_EACH_LEVEL;
leaf_addr=first%NUM_OF_EACH_LEVEL;
if(root_addr[root_level][leaf_addr].node_value!=first)
{
root_addr[root_level][leaf_addr].node_value=first;
root_addr[root_level][leaf_addr].head=(Neighbor *)malloc(sizeof(Neighbor));
root_addr[root_level][leaf_addr].tail=(Neighbor *)malloc(sizeof(Neighbor));
root_addr[root_level][leaf_addr].g_credit[0]=1;
root_addr[root_level][leaf_addr].head->neighbor_value=second;
root_addr[root_level][leaf_addr].head->next=NULL;
root_addr[root_level][leaf_addr].tail=root_addr[root_level][leaf_addr].head;
root_addr[root_level][leaf_addr].degree=1;
}
else
{
//insert its new neighbor
Neighbor *newNeighbor;
newNeighbor=(Neighbor*)malloc(sizeof(Neighbor));
newNeighbor->neighbor_value=second;
root_addr[root_level][leaf_addr].tail->next=newNeighbor;
root_addr[root_level][leaf_addr].tail=newNeighbor;
root_addr[root_level][leaf_addr].degree++;
}
root_level=second/NUM_OF_EACH_LEVEL;
leaf_addr=second%NUM_OF_EACH_LEVEL;
if(root_addr[root_level][leaf_addr].node_value!=second)
{
root_addr[root_level][leaf_addr].node_value=second;
root_addr[root_level][leaf_addr].head=(Neighbor *)malloc(sizeof(Neighbor));
root_addr[root_level][leaf_addr].tail=(Neighbor *)malloc(sizeof(Neighbor));
root_addr[root_level][leaf_addr].head->neighbor_value=first;
root_addr[root_level][leaf_addr].head->next=NULL;
root_addr[root_level][leaf_addr].tail=root_addr[root_level][leaf_addr].head;
root_addr[root_level][leaf_addr].degree=1;
root_addr[root_level][leaf_addr].g_credit[0]=1;
}
else
{
//insert its new neighbor
Neighbor *newNeighbor;
newNeighbor=(Neighbor*)malloc(sizeof(Neighbor));
newNeighbor->neighbor_value=first;
root_addr[root_level][leaf_addr].tail->next=newNeighbor;
root_addr[root_level][leaf_addr].tail=newNeighbor;
root_addr[root_level][leaf_addr].degree++;
}
}

Answer 1

Algunas sugerencias:

a) Considere la posibilidad de convertir (o preprocesar) el archivo en un formato binario; con el objetivo de minimizar el tamaño del archivo y también reducir drásticamente el costo de análisis. No conozco los rangos de sus valores, pero varias técnicas (por ejemplo, usar un bit para saber si el número es pequeño o grande y almacenar el número como un entero de 7 bits o un entero de 31 bits) podrían reducir a la mitad el archivo IO (y el doble de la velocidad de lectura del archivo desde el disco) y los costos de análisis de barras hasta casi nada. Nota: para lograr el máximo efecto, modificaría cualquier software que haya creado el archivo en primer lugar.

b) Leer el archivo completo en la memoria antes de analizarlo es un error. Duplica la cantidad de RAM requerida (y el costo de asignar / liberar) y tiene desventajas para los cachés de CPU. En su lugar, lea una pequeña cantidad del archivo (por ejemplo, 16 KiB) y procésela, luego lea la siguiente pieza y procésela, y así sucesivamente; para que estés constantemente reutilizando la misma pequeña memoria intermedia.

c) Usa el paralelismo para el archivo IO. No debería ser difícil leer la siguiente parte del archivo mientras está procesando la parte anterior del archivo (ya sea utilizando 2 subprocesos o utilizando IO asíncrona).

d) Asigne previamente memoria para las estructuras "vecinas" y elimine la mayoría de las llamadas malloc() de su bucle. El mejor caso posible es usar una matriz asignada estáticamente como un grupo, por ejemplo, Neighbor myPool[MAX_NEIGHBORS]; donde malloc() puede reemplazarse con &myPool[nextEntry++]; . Esto reduce / elimina la sobrecarga de malloc() al mismo tiempo que mejora la localidad de caché para los datos en sí.

e) Usa el paralelismo para almacenar valores. Por ejemplo, podría tener varios subprocesos en los que el primer subproceso controla todos los casos donde root_level % NUM_THREADS == 0 , el segundo subproceso controla todos los casos donde root_level % NUM_THREADS == 1 , etc.

Con todo lo anterior (suponiendo una CPU moderna de 4 núcleos), creo que puede reducir el tiempo total (para leer y almacenar) a menos de 15 segundos.

Answer 2

En primer lugar, ¿cuál es su hardware de disco ? Es probable que una sola unidad SATA se complete a 100 MB / s. Y probablemente más como 50-70 MB / seg. Si ya está moviendo los datos de la (s) unidad (es) lo más rápido posible, todo el ajuste de software que haga se perderá.

Si su hardware puede soportar la lectura más rápido? Primero, su patrón de lectura (leer el archivo completo en la memoria una vez) es el caso de uso perfecto para IO directo. Abra su archivo usando open( "/file/name", O_RDONLY | O_DIRECT ); . Lea los buffers alineados con la página (vea la página del valloc() de valloc() ) en fragmentos de tamaño de página. El uso directo de IO hará que sus datos eviten el almacenamiento en búfer doble en el caché de la página del kernel, lo que no sirve para nada cuando se leen tantos datos rápidamente y no se vuelven a leer las mismas páginas de datos una y otra vez.

Si está ejecutando un verdadero sistema de archivos de alto rendimiento, puede leer de forma asíncrona y probablemente más rápido con lio_listio () o aio_read (). O simplemente puede usar varios subprocesos para leer, y usar pread() para que no pierda tiempo buscando, y porque al leer utilizando varios subprocesos, una búsqueda en un archivo abierto afecta a todos los subprocesos que intentan leer desde el archivo.

Y no intente leer rápidamente en un trozo de memoria recién malloc''d: memset () primero. Debido a que los sistemas de disco realmente rápidos pueden bombear datos a la CPU más rápido que el administrador de memoria virtual puede crear páginas virtuales para un proceso.

Answer 3

Hay varias posibilidades. Tendrás que experimentar.

• Aprovecha lo que tu OS te da. Si Windows, echa un vistazo a io superpuesto . Esto permite que su cálculo continúe analizando un búfer lleno de datos, mientras que el kernel de Windows llena otro. Luego cambia los buffers y continúa. Esto está relacionado con lo que sugirió @Neal, pero tiene menos sobrecarga para el almacenamiento en búfer. Windows está depositando datos directamente en su búfer a través del canal DMA. Sin copiar. Si Linux, echa un vistazo a los archivos de memoria asignados . Aquí, el sistema operativo está utilizando el hardware de memoria virtual para hacer más o menos lo que Windows hace con la superposición.

• Codifique su propia conversión de enteros. Es probable que esto sea un poco más rápido que hacer una llamada clib por entero.

Aquí está el código de ejemplo. Quieres limitar absolutamente el número de comparaciones.

// Process one input buffer.
*end_buf = '' ''; // add a sentinel at the end of the buffer
for (char *p = buf; p < end_buf; p++) {
// somewhat unsafe (but fast) reliance on unsigned wrapping
unsigned val = *p - ''0'';
if (val <= 9) {
// Found start of integer.
for (;;) {
unsigned digit_val = *p - ''0'';
if (digit_val > 9) break;
val = 10 * val + digit_val;
p++;
}
... do something with val
}
}

• No llame a malloc una vez por registro. Debes asignar bloques de muchas estructuras a la vez.

• Experimentar con tamaños de tampones.

• Aumentar las optimizaciones del compilador. Este es el tipo de código que se beneficia enormemente de la excelente generación de código.

Answer 4

Mi sugerencia sería formar una tubería de procesamiento y enhebrarla. Leer el archivo es una tarea enlazada de E / S y analizarla está enlazado a la CPU. Se pueden hacer al mismo tiempo en paralelo.

Answer 5

Sí, las funciones de conversión de biblioteca estándar son sorprendentemente lentas.

Si la portabilidad no es un problema, asignaría el archivo a la memoria. Luego, se podría usar algo como el siguiente código C99 (no probado) para analizar todo el mapa de memoria:

#include <stdlib.h>
#include <errno.h>
struct pair {
unsigned long key;
unsigned long value;
};
typedef struct {
size_t size; /* Maximum number of items */
size_t used; /* Number of items used */
struct pair item[];
} items;
/* Initial number of items to allocate for */
#ifndef ITEM_ALLOC_SIZE
#define ITEM_ALLOC_SIZE 8388608
#endif
/* Adjustment to new size (parameter is old number of items) */
#ifndef ITEM_REALLOC_SIZE
#define ITEM_REALLOC_SIZE(from) (((from) | 1048575) + 1048577)
#endif
items *parse_items(const void *const data, const size_t length)
{
const unsigned char *ptr = (const unsigned char *)data;
const unsigned char *const end = (const unsigned char *)data + length;
items *result;
size_t size = ITEMS_ALLOC_SIZE;
size_t used = 0;
unsigned long val1, val2;
result = malloc(sizeof (items) + size * sizeof (struct pair));
if (!result) {
errno = ENOMEM;
return NULL;
}
while (ptr < end) {
/* Skip newlines and whitespace. */
while (ptr < end && (*ptr == ''/0'' || *ptr == ''/t'' ||
*ptr == ''/n'' || *ptr == ''/v'' ||
*ptr == ''/f'' || *ptr == ''/r'' ||
*ptr == '' ''))
ptr++;
/* End of data? */
if (ptr >= end)
break;
/* Parse first number. */
if (*ptr >= ''0'' && *ptr <= ''9'')
val1 = *(ptr++) - ''0'';
else {
free(result);
errno = ECOMM; /* Bad data! */
return NULL;
}
while (ptr < end && *ptr >= ''0'' && *ptr <= ''9'') {
const unsigned long old = val1;
val1 = 10UL * val1 + (*(ptr++) - ''0'');
if (val1 < old) {
free(result);
errno = EDOM; /* Overflow! */
return NULL;
}
}
/* Skip whitespace. */
while (ptr < end && (*ptr == ''/t'' || *ptr == ''/v''
*ptr == ''/f'' || *ptr == '' ''))
ptr++;
if (ptr >= end) {
free(result);
errno = ECOMM; /* Bad data! */
return NULL;
}
/* Parse second number. */
if (*ptr >= ''0'' && *ptr <= ''9'')
val2 = *(ptr++) - ''0'';
else {
free(result);
errno = ECOMM; /* Bad data! */
return NULL;
}
while (ptr < end && *ptr >= ''0'' && *ptr <= ''9'') {
const unsigned long old = val2;
val1 = 10UL * val2 + (*(ptr++) - ''0'');
if (val2 < old) {
free(result);
errno = EDOM; /* Overflow! */
return NULL;
}
}
if (ptr < end) {
/* Error unless whitespace or newline. */
if (*ptr != ''/0'' && *ptr != ''/t'' && *ptr != ''/n'' &&
*ptr != ''/v'' && *ptr != ''/f'' && *ptr != ''/r'' &&
*ptr != '' '') {
free(result);
errno = ECOMM; /* Bad data! */
return NULL;
}
/* Skip the rest of this line. */
while (ptr < end && *ptr != ''/n'' && *ptr != ''/r'')
ptr++;
}
/* Need to grow result? */
if (used >= size) {
items *const old = result;
size = ITEMS_REALLOC_SIZE(used);
result = realloc(result, sizeof (items) + size * sizeof (struct pair));
if (!result) {
free(old);
errno = ENOMEM;
return NULL;
}
}
result->items[used].key = val1;
result->items[used].value = val2;
used++;
}
/* Note: we could reallocate result here,
* if memory use is an issue.
*/
result->size = size;
result->used = used;
errno = 0;
return result;
}

He utilizado un enfoque similar para cargar datos moleculares para visualización. Dichos datos contienen valores de punto flotante, pero la precisión suele ser solo de unos siete dígitos significativos, no se necesitan cálculos de multiprecisión. Una rutina personalizada para analizar dichos datos supera las funciones estándar en al menos un orden de magnitud en velocidad.

Al menos el kernel de Linux es bastante bueno para observar los patrones de acceso a la memoria / archivos; el uso de madvise() también ayuda.

Si no puede usar un mapa de memoria, entonces la función de análisis sería un poco diferente: se agregaría a un resultado existente, y si la línea final en el búfer es parcial, lo indicaría (y el número de caracteres no analizados) , para que la persona que llama pueda memmove() el búfer, leer más datos y continuar el análisis. (Utilice direcciones alineadas de 16 bytes para leer nuevos datos, para maximizar las velocidades de copia. No necesariamente tiene que mover los datos no leídos al inicio exacto del búfer, vea; simplemente mantenga la posición actual en los datos del búfer).

Preguntas?