Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Удаление дубликатов и удаление строк из файлов


Автор: lamber 26.1.2011, 19:48
Снова здравствуйте, стоит вот такая вот задача, все бы нечего если бы объёмы файлов ООочень большие от 10кк до 100кк записей. Нужно удалить дубликаты строк в файле, это первая задача, вторая задача сделать выборку из больших файлов по заданной строке, НО нужно удалить еще выбранные строки из файлов. Надеюсь на вашу помощь.

Автор: azesmcar 26.1.2011, 20:22
Цитата(lamber @  26.1.2011,  19:48 Найти цитируемый пост)
Нужно удалить дубликаты строк в файле

Читать построчно, подсчитать http://en.wikipedia.org/wiki/MD5 и хранить в каком нибудь контейнере типа std::set. Не повторяющиеся записать в другой файл. Все.

Цитата(lamber @  26.1.2011,  19:48 Найти цитируемый пост)
сделать выборку из больших файлов по заданной строке, НО нужно удалить еще выбранные строки из файлов

строки из файлов не удаляются, надо записать новый файл без этих строк.

Автор: lamber 26.1.2011, 22:01
2azesmcar
а зачем считать md5 :?

окей а как записать в тот же файл, перенести весь файл в оперативу а потом перезаписать или создавать временный файл оригинал удалять, а потом переименновывать временный :?

Автор: azesmcar 27.1.2011, 06:12
Цитата(lamber @  26.1.2011,  22:01 Найти цитируемый пост)
а зачем считать md5 :?

Для экономии памяти. MD5 в бинарном виде 16 байтов, в текстовом - 32. Теоретически твоя строка может состоять из сотни символов.

Цитата(lamber @  26.1.2011,  22:01 Найти цитируемый пост)
окей а как записать в тот же файл, перенести весь файл в оперативу а потом перезаписать или создавать временный файл оригинал удалять, а потом переименновывать временный :?

создавать временный файл оригинал удалять, а потом переименновывать временный smile 

Автор: lamber 27.1.2011, 17:24
отчитываюсь по результатам, использовал контейнер set удобная штука, но есть проблема может кто слышал про тулзу KeyWordKeeper.exe достаточно удобная штука, вот я решил сравнить работу своей проги использующей stl set просеяв строки на уникальность и её в итоге 244мб файл прога порезала всего на 14 метров, а моя прога укаратила его аж на 160мб, я конечно рад бы думать что у меня-то на самом деле как нужно, но реалии обвчно говрорят обратное, может есть какая-то не учтенная мною особенность контейнера.

2azesmcar я не реализовывал md5 от строки т.к. это сложновато для меня реализовать, ну а тянуть либу Crypto++ и разбираться  ней желания не было (хотя если выяснится что без этого ни как то я что поделаешь).

Автор: azesmcar 27.1.2011, 18:04
Цитата(lamber @  27.1.2011,  17:24 Найти цитируемый пост)
2azesmcar я не реализовывал md5 от строки т.к. это сложновато для меня реализовать, ну а тянуть либу Crypto++ и разбираться  ней желания не было (хотя если выяснится что без этого ни как то я что поделаешь). 

ты хранишь в set всю строку, оттого и такой расход памяти. А тянуть ничего не надо, в интернете полно реализаций md5, выбирай любую.
http://stackoverflow.com/questions/1220046/in-c-how-to-get-md5-hash-of-a-file

Автор: lamber 27.1.2011, 19:47
Столько сам файл занимает, я больше переживают за то почему при использовании set<string> столько якобы дубликатов удаляет. Прогоняя тот же файл софтом который на этом специализируется получаю совершенно разные результаты.

Автор: azesmcar 27.1.2011, 20:03
Цитата(lamber @  27.1.2011,  19:47 Найти цитируемый пост)
Столько сам файл занимает, я больше переживают за то почему при использовании set<string> столько якобы дубликатов удаляет. Прогоняя тот же файл софтом который на этом специализируется получаю совершенно разные результаты. 

покажи исходники, чего гадать?

Автор: lamber 28.1.2011, 11:53
Код

    int count=0;
    strcpy(result.filename,filename);    
    string line;
    string temp;
    char outname[256];
    char buff[1024];
    string buffer;
    set<string> setbuffer;
    buffer=GetFileName(filename);
    sprintf(outname,"parsed_%s",buffer.c_str());
    size_t nPos;
    buffer.clear();
    ifstream infile(filename,ios_base::in);
    while (getline(infile, line,'\r'))
  {
      count++;
      result.lines++;
      nPos=line.find(":");      
      if(nPos!=string::npos)
      {
          temp=explode(line);
          setbuffer.insert(temp+'\n');

      }else
          setbuffer.insert(temp+'\n');
      if(count>204800)
      {
          count=0;
          wsprintfA(buff,"file parsed:%s\nlines parsed: %d",result.filename,result.lines);
          SetWindowTextA(GetDlgItem(thwnd,IDTEXT),buff);
      }
    
  }
          if(setbuffer.size()>0)
          {
          SaveToFile("blackhole.txt",setbuffer);
          wsprintfA(buff,"file parsed:%s\nlines parsed: %d",result.filename,result.lines);
          SetWindowTextA(GetDlgItem(thwnd,IDTEXT),buff);
          setbuffer.clear();
          }         
          return result;
}

Автор: azesmcar 28.1.2011, 13:45
lamber

Как все запутанно smile 
Код

std::string md5(const std::string& line)
{
    return /* md5 implementation goes here */ line;
}

int main()
{
    std::ifstream inp("d:\\1.txt");
    std::ofstream out("d:\\2.txt");

    std::set<std::string> lines;

    for (std::string temp; std::getline(inp, temp);)
    {
        if (lines.insert(md5(temp)).second)
        {
            out << temp << '\n';
        }
    }
    out.close();
    inp.close();
}

Автор: jonie 29.1.2011, 13:00
azesmcar, md5 слишком круто имхо для решения подобной задачи... кроме того даже она не обеспечивает истинности сравнения строк... тогда уж имхо хранить {хеш, длина, начальное смещение} и проверять соотвественно сначала хеш на уникальность, потом длину, потом побайтам ...

Автор: azesmcar 29.1.2011, 17:15
Цитата(jonie @  29.1.2011,  13:00 Найти цитируемый пост)
md5 слишком круто имхо для решения подобной задачи

В каком смысле крут? В принципе можно и что нибудь попроще, но md5 дает хорошое распределение.

Цитата(jonie @  29.1.2011,  13:00 Найти цитируемый пост)
кроме того даже она не обеспечивает истинности сравнения строк

 smile 
этого не может обеспечить ни один хэш, тем не менее для более менее коротких строк md5 достаточно уникален, чтобы на него можно было положиться во многих ситуациях.

Цитата(jonie @  29.1.2011,  13:00 Найти цитируемый пост)
тогда уж имхо хранить {хеш, длина, начальное смещение} и проверять соотвественно сначала хеш на уникальность, потом длину, потом побайтам ... 

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

Автор: jonie 29.1.2011, 19:07
Цитата(azesmcar @  29.1.2011,  17:15 Найти цитируемый пост)

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

не то чтобы сильно замедлит, если заменить md5 на что-то более быстрое. http://code.google.com/p/google-sparsehash/ вот какой-то хеш, говорят неплох по скорости...

Автор: azesmcar 29.1.2011, 19:11
Цитата(jonie @  29.1.2011,  19:07 Найти цитируемый пост)
не то чтобы сильно замедлит, если заменить md5 на что-то более быстрое. http://code.google.com/p/google-sparsehash/ вот какой-то хеш, говорят неплох по скорости...

Ну замедление будет не за счет хеша, а за счет повторного чтения и сравнения самих строк. Поскольку этот процесс будет происходить только для повторов, то это будет скорее чувствоваться при большом множестве повторений.
Цитата(jonie @  29.1.2011,  19:07 Найти цитируемый пост)
вот какой-то хеш, говорят неплох по скорости...

А есть какие-то про распределение (distribution), я что-то ничего не нашел.

Автор: sQu1rr 30.1.2011, 01:51
Цитата(azesmcar @  29.1.2011,  17:15 Найти цитируемый пост)

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

Если такой случай один на миллион то и замедлится процесс в одну миллионную раза smile

Автор: azesmcar 30.1.2011, 07:07
Цитата(sQu1rr @  30.1.2011,  01:51 Найти цитируемый пост)
Если такой случай один на миллион то и замедлится процесс в одну миллионную раза  

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)