[Алгоритм]из одного файла удалить все строки, которые есть в другом файле.

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by enigma, 3 Mar 2012.

  1. enigma

    enigma Member

    Joined:
    10 Jul 2011
    Messages:
    82
    Likes Received:
    14
    Reputations:
    7
    В принципе задача сама по себе проста..

    Просто интересна работа с огромным текстовым файлом..

    Пример: Есть некая база, текстовой документ №1, размером 1 ГБ.
    Есть второй текстовой документ №2, в нем допустим 100000 строк.
    Надо выяснить, есть ли дубли в первом текстовом документе из второго. Если нет - дописать их из второго в первый.


    Пока думаю сделать так: создать проекцию первого файла, получить на него указатель.
    По второму ("маленькому") ехать циклом построчно, и strstr() выяснять есть ли дубли в первом файле.
    Но мне кажется, что сама strstr будет работать очень медленно при таком огромном файле :).

    Вобщем посоветуйте правильный (рациональный) алгоритм для подобных работ.
     
  2. Problems?

    Problems? Member

    Joined:
    13 Jan 2011
    Messages:
    14
    Likes Received:
    9
    Reputations:
    5
    Есть реализация на делпфе (юзается бинарный поиск). Когда то хотел сделать свой антивирь)

    src

    Вообщем смотри там строка на вход функции должна подаваться в виде %xx формате.
    т.е. 464C414353 = FLACS
     
    1 person likes this.
  3. R0nin

    R0nin Member

    Joined:
    11 Jul 2010
    Messages:
    262
    Likes Received:
    24
    Reputations:
    8

    Бинарный алгоритм поиска юзается только на отсортированных данных, о том, что данные сортированы автор темы ничего не сказал.
    Problems? может скажете как вы это подразумевали? Не ищите подкола, я просто думал что прежде чем юзать бинарный поиск данные нужны отсортировать. Возможно что-то пропустил.

    1) Отсортировать данные, подойдет любой алгоритм со сложность n*log(n) (quicksort, mergesort, heap sort), выберайте то что вам ближе.
    2) Как написали в предыдущем сообщении - юзать бинарный поиск.
     
    #3 R0nin, 3 Mar 2012
    Last edited: 3 Mar 2012
  4. Problems?

    Problems? Member

    Joined:
    13 Jan 2011
    Messages:
    14
    Likes Received:
    9
    Reputations:
    5
    Данные надо отсортировать естестевнно, т.е. в том файле где будут проверяться строки, нужно привести все символы к нижнему или верхнему регистру. Потом заюзать код, что я дал приведя символу к тому же регистру, где будем проверять.
     
  5. R0nin

    R0nin Member

    Joined:
    11 Jul 2010
    Messages:
    262
    Likes Received:
    24
    Reputations:
    8
    Не обязательно переводить в другой регистр. Достаточно, если как ключ взять первую букву и отсортировать. Алгоритм сортировки видет это не как буквы, а как числа, поэтому понятно что A по значению меньше чем a.
     
    #5 R0nin, 3 Mar 2012
    Last edited: 3 Mar 2012
  6. Spot

    Spot Elder - Старейшина

    Joined:
    1 Mar 2007
    Messages:
    466
    Likes Received:
    38
    Reputations:
    1
    А что если в начале кешировать все строки, после чего уде можно отсортировать и юзать поиск по хранящемуся кэшу.MD5() например.
     
  7. ShyRka_coder

    ShyRka_coder Member

    Joined:
    27 Jul 2010
    Messages:
    158
    Likes Received:
    7
    Reputations:
    5
    Такое пишетсо 5 мин :) Берешь открываешь 2 файла .. потом по строке с 1 гонишь по всех строках другого :) и делаешь что надо :)
     
  8. SHiNiGaMi

    SHiNiGaMi Banned

    Joined:
    3 Jan 2010
    Messages:
    389
    Likes Received:
    55
    Reputations:
    15
    ShyRka_coder учитывая размеры файлов ТС'а, твой алгоритм закончится как раз к пенсии
     
    1 person likes this.
  9. Spot

    Spot Elder - Старейшина

    Joined:
    1 Mar 2007
    Messages:
    466
    Likes Received:
    38
    Reputations:
    1
    Ага, пишется за 5 минут, а работает 100500 часов:)
    100000 строк, и каждую из них нужно прогнать через n число строк в другом файле.
     
  10. ShyRka_coder

    ShyRka_coder Member

    Joined:
    27 Jul 2010
    Messages:
    158
    Likes Received:
    7
    Reputations:
    5
    умм.. промахалсо с размером :) тогда даже хз что посоветовать ..
     
  11. _nic

    _nic Elder - Старейшина

    Joined:
    5 May 2006
    Messages:
    654
    Likes Received:
    54
    Reputations:
    3
    Что мешает поделить файл на куски, под число ядер процессора?
     
    1 person likes this.
  12. enigma

    enigma Member

    Joined:
    10 Jul 2011
    Messages:
    82
    Likes Received:
    14
    Reputations:
    7
    Всем спасибо за советы, в каком направлении подумать.. Буду разбираться с двоичным поиском :) ,
    хотя пока сам механизм не знаю, но видимо он работает на "похожести" строк а не их точном соответствии?


    Кстати попробовал сейчас ради интереса алгоритм с strstr, результат на картинке

    [​IMG]

    Процессор был нагружен на моем стареньком компе на половину. Причем сама база пол ГБ.

    если интересно то исходник
    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" в массив. И вышеприведенный код исполнять в отдельном потоке, передавая каждому кусочек массива..
     
  13. M_script

    M_script Members of Antichat

    Joined:
    4 Nov 2004
    Messages:
    2,671
    Likes Received:
    1,269
    Reputations:
    1,557
    Посмотри тему:
    https://forum.antichat.ru/thread210854.html - "Truesort by ErrorNeo - программа для сортировки словарей"
     
    1 person likes this.
  14. Spot

    Spot Elder - Старейшина

    Joined:
    1 Mar 2007
    Messages:
    466
    Likes Received:
    38
    Reputations:
    1
    Ничего не мешает, как и не мешает заюзать Hyper Threading если технология поддерживается производителем железа. Однако, так можно сделать при еденичном добавлении/проверки в файл. Если же файл не один, а несколько и часто добавляются новые в очередь на сравнение - то будет правильно вначале отсортировать основной(главный) файл с данными, после чего производить сравнение уже по отсортированному списку, бинарным поиском.

    Суммарное время если использовать второй вариант, будет намного меньше, нежели при использовании просто построчного сравнения.И с каждым новым добавленным для проверки/добавлением файлом, разница будет расти в пользу второго варианта.

    Уж если не прав, то поправтье.
     
Loading...