Как получить большой файл

Question

Я работаю над приложением, в котором мне нужно сравнить 10^8 записей (буквенно-цифровые записи). Чтобы получить записи из файла (размер файла составляет 1,5 ГБ), а затем для их сравнения, мне нужно потратить менее 5 минут. Итак, что было бы эффективным способом сделать это, поскольку только время получения превышает 5 минут. И мне нужно работать только с файлом. пожалуйста, предложите выход. Я работаю над окнами с 3 ГБ оперативной памяти n 100 Гб жесткого диска.

Answer 1

• Прочтите часть файла, отсортируйте ее, напишите во временный файл.
• Объединить полученные файлы.

Answer 2

Если время поиска превышает 5 минут, кажется, что вам нужно посмотреть, как вы читаете этот файл. Одна вещь, которая вызвала плохую производительность для меня, заключается в том, что реализация C иногда использует поточные операции ввода-вывода по умолчанию, и вы можете получить некоторую скорость с помощью небезопасного ввода-вывода.

На каком компьютере это будет работать? Многие компьютеры в настоящее время имеют несколько гигабайт памяти, поэтому, возможно, это будет просто читать все это в памяти, а затем сортировать там (например, с помощью qsort)?

Answer 3

Обработка ошибок и заголовок не включены. Вам необходимо предоставить DataType и cmpfunc, образцы предоставлены. Вы должны быть в состоянии вывести основные разработки этого фрагмента:

#include <sys/mman.h> 
#include <sys/types.h> 
#include <sys/stat.h> 
#include <fcntl.h> 
#include <stdlib.h> 
#include <unistd.h> 

typedef char DataType; // is this alphanumeric? 
int cmpfunc(char const *left, char const *right) 
{ 
    return *right - *left; 
} 

int main(int argc, char **argv) 
{ 
    int fd = open(argv[1], O_RDWR|O_LARGEFILE); 
    if (fd == -1) 
     return 1; 
    struct stat st; 
    if (fstat(fd, &st) != 0) 
     return 1; 
    DataType *data = mmap(NULL, st.st_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); 
    if (!data) 
     return 1; 
    qsort(data, st.st_size/sizeof(*data), cmpfunc); 
    if (0 != msync(data, st.st_size, MS_SYNC)) 
     return 1; 
    if (-1 == munmap(data, st.st_size)) 
     return 1; 
    if (0 != close(fd)) 
     return 1; 
    return 0;  
} 

Я не могу себе представить, вы можете получить гораздо быстрее, чем это. Убедитесь, что у вас достаточно адресного пространства виртуальной памяти (1,5 ГБ подталкивает его, но, вероятно, просто работает на 32-битной Linux, вы сможете управлять этим на любой 64-битной ОС). Обратите внимание, что этот код «ограничен» для работы в POSIX-совместимой системе.

С точки зрения C и эффективности этот подход ставит всю операцию в руки ОС и отличный алгоритм qsort.