Есть текстовый файл с персональными данными (ФИО ДР ИНН и тд).

Необходимо найти всех двойников по критерию ФИО ДР.
Алгоритм нужен однопроходный.

Есть идея считать хэш (int), и сохранять строки с ФИО ДР в std::multimap<int, std::string > hash;

Проблема в том, что на гигобайтных входных данных это даст огромный расход памяти.

Есть идея получше?

Аноним 479 wrote:
> Есть идея получше?

Отсортировать строки внешней сортировкой,
потом пройтись по данным и выявить дубликаты за
один проход. Буде НЕ быстрее, но по памяти экономнее.

Собственно, не понятно, что ты хочешь -- быстро --
надо много памяти, мало памяти -- будет медленнее.

Здравствуйте, <Аноним>, Вы писали:

А>Есть идея считать хэш (int), и сохранять строки с ФИО ДР в std::multimap<int, std::string > hash;
А>Проблема в том, что на гигобайтных входных данных это даст огромный расход памяти.

А>Есть идея получше?

Только не multimap, а multiset< pair<hash_type,string_type> >

1) Загрузить файл в память сплошняком, и вместо string взять легковесный объект, умеющий выделять строку с заданного адреса. Экономим кучу (которая иначе будет мелко порублена и даст много накладных расходов).
2) Вместо string взять объект, умеющий читать строку с заданной позиции из файла.
3) Вынести дескриптор файла за скобки. Например, пусть только компаратор мультисета знает про файл: multiset< pair<hash,offset>, smart_comparator >.
Если двойников немного, то большой нагрузки на произвольный доступ к файлу не будет, да и ОС сгладит её (кэшированием). Главное — хороший хэш подобрать.

Если же файл не лезет в память, то, как уже сказали, — натравить внешнюю сортировку и исключить дубликаты.

Здравствуйте, Аноним, Вы писали:

А>Есть текстовый файл с персональными данными (ФИО ДР ИНН и тд).
А>Необходимо найти всех двойников по критерию ФИО ДР.

а с двойниками что сделать надо?
есди удалить, то man uniq

Здравствуйте, x905, Вы писали:

X>Здравствуйте, Аноним, Вы писали:

А>>Есть текстовый файл с персональными данными (ФИО ДР ИНН и тд).
А>>Необходимо найти всех двойников по критерию ФИО ДР.

X>а с двойниками что сделать надо?
X>есди удалить, то man uniq

Это ведь удаление только последовательно идущих повторов, разве нет?

Здравствуйте, <Аноним>, Вы писали:

А>Есть текстовый файл с персональными данными (ФИО ДР ИНН и тд).

А>Необходимо найти всех двойников по критерию ФИО ДР.
А>Алгоритм нужен однопроходный.

А>Есть идея считать хэш (int), и сохранять строки с ФИО ДР в std::multimap<int, std::string > hash;

А>Проблема в том, что на гигобайтных входных данных это даст огромный расход памяти.

А>Есть идея получше?

Так все-таки, их нужно подсчитать или найти?

Приветствую, _DAle_, вы писали:

DA> X>а с двойниками что сделать надо?
DA> X>есди удалить, то man uniq

DA> Это ведь удаление только последовательно идущих повторов, разве нет?
cat ... | sort -u или cat ... | sort | uniq

Здравствуйте, Sheridan, Вы писали:

S>Приветствую, _DAle_, вы писали:

DA>> X>а с двойниками что сделать надо?
DA>> X>есди удалить, то man uniq

DA>> Это ведь удаление только последовательно идущих повторов, разве нет?
S> cat ... | sort -u или cat ... | sort | uniq

Ты вообще вопрос читал? "Однопроходной алгоритм", "гигабайтные данные"...

Приветствую, _DAle_, вы писали:

DA> S> cat ... | sort -u или cat ... | sort | uniq
DA> Ты вообще вопрос читал? "Однопроходной алгоритм", "гигабайтные данные"...
а...
Ну тогда sort -u file > sortedfile

Здравствуйте, Аноним, Вы писали:
А>Есть текстовый файл с персональными данными (ФИО ДР ИНН и тд).

залить это в базу данных и
select ФИО, ДР, count(*) from ttt group by ФИО, ДР having count(*) > 1

Здравствуйте, _DAle_, Вы писали:

А>>>Есть текстовый файл с персональными данными (ФИО ДР ИНН и тд).
А>>>Необходимо найти всех двойников по критерию ФИО ДР.
X>>а с двойниками что сделать надо?
X>>есди удалить, то man uniq
_DA>Это ведь удаление только последовательно идущих повторов, разве нет?

да, и как сказали — использовать сначала sort
насчет однопроходности — а разве это возможно?
используя std::multimap ты сам не будеш повторно проходить по нему — за тебя это сделает std::multimap )

Здравствуйте, PPA, Вы писали:

PPA>Здравствуйте, Аноним, Вы писали:
А>>Есть текстовый файл с персональными данными (ФИО ДР ИНН и тд).

PPA>залить это в базу данных и
PPA>select ФИО, ДР, count(*) from ttt group by ФИО, ДР having count(*) > 1

Перейти на .NET и заюзать LINQ, срочно!

Здравствуйте, x905, Вы писали:

_DA>>Это ведь удаление только последовательно идущих повторов, разве нет?

X>да, и как сказали — использовать сначала sort
X>насчет однопроходности — а разве это возможно?

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

X>используя std::multimap ты сам не будеш повторно проходить по нему — за тебя это сделает std::multimap )