В принципе задача сама по себе проста.. Просто интересна работа с огромным текстовым файлом.. Пример: Есть некая база, текстовой документ №1, размером 1 ГБ. Есть второй текстовой документ №2, в нем допустим 100000 строк. Надо выяснить, есть ли дубли в первом текстовом документе из второго. Если нет - дописать их из второго в первый. Пока думаю сделать так: создать проекцию первого файла, получить на него указатель. По второму ("маленькому") ехать циклом построчно, и strstr() выяснять есть ли дубли в первом файле. Но мне кажется, что сама strstr будет работать очень медленно при таком огромном файле . Вобщем посоветуйте правильный (рациональный) алгоритм для подобных работ.
Есть реализация на делпфе (юзается бинарный поиск). Когда то хотел сделать свой антивирь) src Вообщем смотри там строка на вход функции должна подаваться в виде %xx формате. т.е. 464C414353 = FLACS
Бинарный алгоритм поиска юзается только на отсортированных данных, о том, что данные сортированы автор темы ничего не сказал. Problems? может скажете как вы это подразумевали? Не ищите подкола, я просто думал что прежде чем юзать бинарный поиск данные нужны отсортировать. Возможно что-то пропустил. 1) Отсортировать данные, подойдет любой алгоритм со сложность n*log(n) (quicksort, mergesort, heap sort), выберайте то что вам ближе. 2) Как написали в предыдущем сообщении - юзать бинарный поиск.
Данные надо отсортировать естестевнно, т.е. в том файле где будут проверяться строки, нужно привести все символы к нижнему или верхнему регистру. Потом заюзать код, что я дал приведя символу к тому же регистру, где будем проверять.
Не обязательно переводить в другой регистр. Достаточно, если как ключ взять первую букву и отсортировать. Алгоритм сортировки видет это не как буквы, а как числа, поэтому понятно что A по значению меньше чем a.
А что если в начале кешировать все строки, после чего уде можно отсортировать и юзать поиск по хранящемуся кэшу.MD5() например.
Такое пишетсо 5 мин Берешь открываешь 2 файла .. потом по строке с 1 гонишь по всех строках другого и делаешь что надо
Ага, пишется за 5 минут, а работает 100500 часов 100000 строк, и каждую из них нужно прогнать через n число строк в другом файле.
Всем спасибо за советы, в каком направлении подумать.. Буду разбираться с двоичным поиском , хотя пока сам механизм не знаю, но видимо он работает на "похожести" строк а не их точном соответствии? Кстати попробовал сейчас ради интереса алгоритм с strstr, результат на картинке Процессор был нагружен на моем стареньком компе на половину. Причем сама база пол ГБ. если интересно то исходник Code: #include <Windows.h> #include <fstream> #include <string> #include <time.h> int WINAPI WinMain(HINSTANCE hI, HINSTANCE hPInst, PSTR szCmdLine, int iCmdShow) { TCHAR *FName = "baza.txt"; HANDLE hFile = CreateFile(FName, GENERIC_WRITE | GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL); if (INVALID_HANDLE_VALUE == hFile) { MessageBox(0,"Не получилось открыть файл \"baza.txt\"","",MB_ICONERROR); return -1; } DWORD FileSize = GetFileSize(hFile, NULL); // узнаем размер HANDLE hFM = CreateFileMapping(hFile, NULL, PAGE_READWRITE, 0, 0, NULL); if (NULL == hFM) { MessageBox(0,"Не получилось создать проекцию файла","",MB_ICONERROR); CloseHandle(hFile); return -1; } PVOID pFile = MapViewOfFile(hFM, FILE_MAP_WRITE, 0, 0, 0); if (NULL == pFile) { MessageBox(0,"Не получилось создать проекцию на диске","",MB_ICONERROR); CloseHandle(hFM); CloseHandle(hFile); return -1; } PSTR pStr = (PSTR) pFile; pStr[FileSize / sizeof(CHAR)] = 0; // добавим в конец файла ноль std::ifstream inp; inp.open("substr.txt"); if(inp.fail()) { MessageBox(0,"Не получилось открыть \"substr.txt\"","",MB_ICONERROR); return -1; } std::string buf = ""; int s = 0; clock_t time; time = clock(); while(getline(inp,buf)) { if( NULL == strstr(pStr,buf.c_str())) { s++; if(s == 100) { time = clock() - time; char buf[50]; wsprintf(buf,"%u секунд работала программа, за это время проверено 100 строк.",time/CLOCKS_PER_SEC); MessageBox(0,buf,"",MB_ICONINFORMATION); break; } } } UnmapViewOfFile(pFile); CloseHandle(hFM); CloseHandle(hFile); return 0; } Были еще мысли считать "substr.txt" в массив. И вышеприведенный код исполнять в отдельном потоке, передавая каждому кусочек массива..
Посмотри тему: https://forum.antichat.ru/thread210854.html - "Truesort by ErrorNeo - программа для сортировки словарей"
Ничего не мешает, как и не мешает заюзать Hyper Threading если технология поддерживается производителем железа. Однако, так можно сделать при еденичном добавлении/проверки в файл. Если же файл не один, а несколько и часто добавляются новые в очередь на сравнение - то будет правильно вначале отсортировать основной(главный) файл с данными, после чего производить сравнение уже по отсортированному списку, бинарным поиском. Суммарное время если использовать второй вариант, будет намного меньше, нежели при использовании просто построчного сравнения.И с каждым новым добавленным для проверки/добавлением файлом, разница будет расти в пользу второго варианта. Уж если не прав, то поправтье.
