Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Наконец, образовалась версия, которая не падает с out of memory на нашем максимальном тестовом файле 6.6 млн строк/1 ГБ. Правда, при отключенных 3-х фильтрах из 12 и дубликатах в выходном файле.

Алгоритм такой:

1. Проходимся по файлу, заполняем битовые массивы из предыдущего поста.
2. Проходимся по файлу, разбрасываем кандидатов в дубликаты по временным файлам. Общий размер 200М.
3. Для каждого временного файла
а) Проходимся по файлу, собираем строки в ассоциативный массив "ключ-массив строк"
б) Проходимся по массиву, отбрасываем недубликаты.
в) Пишем содержимое массива в выходной файл

Превышение памяти, если не отключать 3 самых потребляющих фильтра, наблюдается на этапе 3а. 5/6 на этапе 3б оказываются ложными дубликатами, надо увеличивать k. Битовые массивы по 48 мегабит, установленными оказывается примерно полтора мегабита из 48.

Целевое время тоже превышено пока - 30 минут вместо 10. Опасения об IO Boundness, понятно, не подтвердились - при работе на скорости винта всё заняло бы пару минут :)
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments