Привед други!

Как всегда. Илья. Сова. Дима-Т. И все-все.

В продолжение темы Работа с большими данными

Автор затих и топик не имеет продолжения. Я решил что зря.
Тема хорошая и ее стоит возобновить. Значит так.

Дано: текстовый файл большого размера. Для простоты в 2-4 раза превышающий
объем оперативной памяти.

Найти: список уникальных строк из этого файла. Время поиска должно быть минимально
настолько, насколько это возможно.

Ограничения:

1. Будем считать что максимальная длина строки - 64 килобайта. Просто договоримся что исходные данные таковы.
Так будет проще.
2. Кодировка ASCII. 1 байт на символ. Семантика символов 127-255 - на наше усмотрение.
3. Алгоритмы и структуры данных - любые. Все что есть.
4. Сторонние библиотеки юзать можно. Главное чтоб были в наличии исходники и чтоб мы поняли
суть алгоритма.
5. Базы данных - не используем.
6. Сортировка уникальных в данных в результате нас не интересует. То есть мы не ставим такой задачи.
Главное - сделать уникальность.

Пример usecase:


Результат - файл с уникальным набором строк.

Go! Go!

Хардкод приветствуется! С/С++ Moar хардкода! Можно и ассемблер.

P.S. Я еще не написал ни строчки кода по сабж. Пока только мысли Поэтому go-go!

Примечание №1 Можно многократно сканировать исходный текстовый файл для достижения
полезного эффекта. Собирать статистику. Делать какие-то примерные оценки или прикидывать
размеры. Главное - чтоб общее время работы алгоритма было минимально.

Ссылок на тестовые данные я подкину позже. В крайнем случае - сгенерю. Не вижу проблемы.

Siemargl, это грубо. К чему так?

Siemargl, ты уверен что твой метод сработает?

Siemargl, worst case?

Задним числом я поредактировал тему. Добавил важное ограничение
касающееся минимизации времени работы.

UP! Чо-как?

ИзопропилSiemarglДля таблицы хэшей памяти хватит.
а если сам файл из подобных хэшей состоит?
Я если честно не понял причин раздражения Зямы. Он считает что создал алгоритм?
Хм... его работоспособность надо доказать. Возможно речь идёт о двух-фазной работе
где вторая фаза осуществляет некую зачистку ключей.

Но здесь я миллионный раз бью себя по рукам. Я допускаю свою собственную ошибку
пытаясь влезть в моск к другому разработчику и ДОДУМАТЬ то что было сказано.
Я так больше не делаю. Я умолкаю и даю возможность ему описать то что имелось
в виду на уровне формальных steps алгоритма.

Еще раз редактирую описание. Ввожу примечание. (Внизу)

Dima TТут интересен примерный размер результата, влезет он в память или нет, из этого надо исходить, в том топике я задавал этот вопрос, но ТС пропал и вопрос остался без ответа.
В наихудшем сценарии в файле будет (к примеру 2 строки дубля) все остальные - уникальны.
Мы не укладываемся в память если будем брать unsortable_map. Нужно думать как работать
с пачками или порциями.

Bred eFeMВажно знать или указать не соотношение файл/память, а возможно ли разместить хеши+смещения всех строк или только "1/128" часть в оперативной памяти?
Я не очень понимаю о каком соотношении вы говорите.

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

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

И я не могу ответить на ваш вопрос о "хешах и смещениях". Возможно вы сами ответите на него в процессе.

Изопропил, вы готовы доказывать в топике что сортировка будет эффективно
решать мою задачу?

ИзопропилmaytonИзопропил, вы готовы доказывать в топике что сортировка будет эффективно
решать мою задачу?
она будет гарантированно её решать. метрики - у Кнута в третьем томе.
Прекрасно. Я рад что есть оппозиция. Только я в скобках замечу что сортировка - это minor.
Это не главная задача в топике.

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