Требования
- огромный файл csv, размером несколько сотен ГБ
- каждая строка содержит несколько чисел
- программа должна извлечь несколько тысяч строк за запуск
- программа работает несколько раз с одним и тем же файлом, нужно извлекать только разные строки
Поскольку строки в файлах csv имеют переменную длину, вам придется прочитать весь файл, чтобы получить данные необходимых строк. Последовательное чтение всего файла все равно будет очень медленным - даже если вы максимально оптимизировали чтение файла. На самом деле хорошим индикатором является время выполнения w c -l, как уже упоминалось OP в вопросе.
Вместо этого следует оптимизировать на уровне алгоритмов c. Необходима однократная предварительная обработка данных, которая затем обеспечивает быстрый доступ к определенным строкам - без чтения всего файла.
Есть несколько возможных способов, например:
- Использование базы данных с индексом
- программа c создание индексного файла (ассоциация номеров строк со смещениями файлов)
- преобразование файла CSV в двоичный файл с фиксированным форматом
Тест OP показывает, что подход 1) привел к показателям 1,5 ТБ. Метод 2), создание небольшой программы, которая связывает номер строки со смещением файла, безусловно, также возможен. Наконец, подход 3 позволит вычислить смещение файла до номера строки без необходимости в отдельном индексном файле. Этот подход особенно полезен, если известно максимальное количество чисел в строке. В остальном подход 2 и подход 3 очень похожи.
Подход 3 более подробно объясняется ниже. Могут быть дополнительные требования, требующие незначительного изменения подхода, но для начала нужно следующее:
Необходима однократная предварительная обработка. Текстовые строки csv преобразуются в массивы int и используют фиксированный формат записи для хранения int в двоичном формате в отдельном файле. Чтобы затем прочитать конкретную строку n , вы можете просто вычислить смещение файла, например, с помощью line_nr * (sizeof(int) * MAX_NUMBERS_PER_LINE);. Наконец, с помощью fseeko(fp, offset, SEEK_SET); перейдите к этому смещению и прочтите MAX_NUMBERS_PER_LINE ints. Таким образом, вам нужно прочитать только те данные, которые вы действительно хотите обработать.
Это имеет не только то преимущество, что программа работает намного быстрее, но и требует очень мало оперативной памяти.
Тестовый пример
Создан тестовый файл с 3 000 000 000 строк. Каждая строка содержит до 10 случайных чисел типа int, разделенных запятой.
В данном случае получился файл csv с примерно 342 ГБ данных.
Быстрый тест с
time wc -l numbers.csv
дает
187.14s user 74.55s system 96% cpu 4:31.48 total
Это означает, что при использовании подхода последовательного чтения файлов всего потребуется не менее 4,5 минут.
Для однократной предварительной обработки Программа конвертера считывает каждую строку и сохраняет по 10 двоичных чисел в каждой строке. Преобразованный файл называется numbers_bin. Быстрый тест с доступом к данным 10000 случайно выбранных строк:
time demo numbers_bin
дает
0.03s user 0.20s system 5% cpu 4.105 total
Таким образом, вместо 4,5 минут для этого примера c требуется 4,1 секунды данные. Это более чем в 65 раз быстрее.
Исходный код
Этот подход может показаться более сложным, чем он есть на самом деле.
Начнем с программа-конвертер. Он читает файл csv и создает двоичный файл фиксированного формата.
Интересная часть происходит в функции pre_process: там строка читается в al oop с помощью 'getline', числа извлекаются с помощью ' strtok 'и' strtol 'и помещается в массив int, инициализированный с помощью 0. Наконец, этот массив записывается в выходной файл с помощью' fwrite '.
Ошибки во время преобразования приводят к сообщению на stderr и программе завершено.
convert. c
#include "data.h"
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <limits.h>
static void pre_process(FILE *in, FILE *out) {
int *block = get_buffer();
char *line = NULL;
size_t line_capp = 0;
while (getline(&line, &line_capp, in) > 0) {
line[strcspn(line, "\n")] = '\0';
memset(block, 0, sizeof(int) * MAX_ELEMENTS_PER_LINE);
char *token;
char *ptr = line;
int i = 0;
while ((token = strtok(ptr, ", ")) != NULL) {
if (i >= MAX_ELEMENTS_PER_LINE) {
fprintf(stderr, "too many elements in line");
exit(EXIT_FAILURE);
}
char *end_ptr;
errno = 0;
long val = strtol(token, &end_ptr, 10);
if (val > INT_MAX || val < INT_MIN || errno || *end_ptr != '\0' || end_ptr == token) {
fprintf(stderr, "value error with '%s'\n", token);
exit(EXIT_FAILURE);
}
ptr = NULL;
block[i] = (int) val;
i++;
}
fwrite(block, sizeof(int), MAX_ELEMENTS_PER_LINE, out);
}
free(block);
free(line);
}
static void one_off_pre_processing(const char *csv_in, const char *bin_out) {
FILE *in = get_file(csv_in, "rb");
FILE *out = get_file(bin_out, "wb");
pre_process(in, out);
fclose(in);
fclose(out);
}
int main(int argc, char *argv[]) {
if (argc != 3) {
fprintf(stderr, "usage: convert <in> <out>\n");
exit(EXIT_FAILURE);
}
one_off_pre_processing(argv[1], argv[2]);
return EXIT_SUCCESS;
}
Data.h
Используется несколько вспомогательных функций. Они более или менее говорят сами за себя.
#ifndef DATA_H
#define DATA_H
#include <stdio.h>
#include <stdint.h>
#define NUM_LINES 3000000000LL
#define MAX_ELEMENTS_PER_LINE 10
void read_data(FILE *fp, uint64_t line_nr, int *block);
FILE *get_file(const char *const file_name, char *mode);
int *get_buffer();
#endif //DATA_H
Data. c
#include "data.h"
#include <stdlib.h>
void read_data(FILE *fp, uint64_t line_nr, int *block) {
off_t offset = line_nr * (sizeof(int) * MAX_ELEMENTS_PER_LINE);
fseeko(fp, offset, SEEK_SET);
if(fread(block, sizeof(int), MAX_ELEMENTS_PER_LINE, fp) != MAX_ELEMENTS_PER_LINE) {
fprintf(stderr, "data read error for line %lld", line_nr);
exit(EXIT_FAILURE);
}
}
FILE *get_file(const char *const file_name, char *mode) {
FILE *fp;
if ((fp = fopen(file_name, mode)) == NULL) {
perror(file_name);
exit(EXIT_FAILURE);
}
return fp;
}
int *get_buffer() {
int *block = malloc(sizeof(int) * MAX_ELEMENTS_PER_LINE);
if(block == NULL) {
perror("malloc failed");
exit(EXIT_FAILURE);
}
return block;
}
demo. c
И, наконец, демонстрационная программа, которая читает данные для 10 000 случайно определенных строк.
Функция request_lines определяет 10 000 случайных строк. Строки сортируются с помощью qsort. Считываются данные для этих строк. Некоторые строки кода закомментированы. Если вы закомментируете их, прочитанные данные будут выведены в консоль отладки.
#include "data.h"
#include <stdlib.h>
#include <assert.h>
#include <sys/stat.h>
static int comp(const void *lhs, const void *rhs) {
uint64_t l = *((uint64_t *) lhs);
uint64_t r = *((uint64_t *) rhs);
if (l > r) return 1;
if (l < r) return -1;
return 0;
}
static uint64_t *request_lines(uint64_t num_lines, int num_request_lines) {
assert(num_lines < UINT32_MAX);
uint64_t *request_lines = malloc(sizeof(*request_lines) * num_request_lines);
for (int i = 0; i < num_request_lines; i++) {
request_lines[i] = arc4random_uniform(num_lines);
}
qsort(request_lines, num_request_lines, sizeof(*request_lines), comp);
return request_lines;
}
#define REQUEST_LINES 10000
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "usage: demo <file>\n");
exit(EXIT_FAILURE);
}
struct stat stat_buf;
if (stat(argv[1], &stat_buf) == -1) {
perror(argv[1]);
exit(EXIT_FAILURE);
}
uint64_t num_lines = stat_buf.st_size / (MAX_ELEMENTS_PER_LINE * sizeof(int));
FILE *bin = get_file(argv[1], "rb");
int *block = get_buffer();
uint64_t *requests = request_lines(num_lines, REQUEST_LINES);
for (int i = 0; i < REQUEST_LINES; i++) {
read_data(bin, requests[i], block);
//do sth with the data,
//uncomment the following lines to output the data to the console
// printf("%llu: ", requests[i]);
// for (int x = 0; x < MAX_ELEMENTS_PER_LINE; x++) {
// printf("'%d' ", block[x]);
// }
// printf("\n");
}
free(requests);
free(block);
fclose(bin);
return EXIT_SUCCESS;
}
Сводка
Этот подход обеспечивает гораздо более быстрые результаты, чем чтение всего файла последовательно (4 секунды вместо 4,5 минут на цикл для данных образца). Для этого также требуется очень мало оперативной памяти.
Предварительным условием является однократная предварительная обработка данных в двоичный формат. Это преобразование занимает довольно много времени, но данные для определенных строк могут быть впоследствии прочитаны очень быстро с помощью программы запросов.