SiemarglУ меня такого файла нет. Выкладывай ссылки на входные данные.
Хм.. Оказывается этот файл обновляется каждый день. Ищи который 114 Мб в архиве.

Модератор: Ссылка удалена

Dima Tmaytonпод Windows10-x64/MinGW-6.4.0.
Ты компилятор обновил? С++11 понимает?

Помня что у тебя акторы не скомпилировались, не стал unordered_map и unordered_set использовать. Они немного побыстрее чем map и set.
Не завязывайся на мой компиллятор. Делай лучшее решение.
А я уж скомпиляю где-нибудь. Хоть на виртуалке.

Стабильные это какие?

Они одинаковые. Все алгоритмы я буду тестировать на всех наборах данных.

По сути будет матрица.

Ставте буфер строки в 64 к

Наверное malloc + memset медленнее отработал.

Спасибо Дима. Приду домой посмотрю.

ИзопропилSiemarglохуллиард трехбуквенных паролей, которые хэшировать себе дороже.
я предупреждал об этом ))
Все в порядке Не поддавайтесь панике. Эти все рабочие моменты. Просто
надо иметь в виду что данные могут быть любые.

Bred eFeMсейчас смотрю-думаю считать crc вместе с поиском конца строки.
Ну, и асинхронное чтение и многопоток как прикрутить.

Бро. Про асинхронность и многопоток ты подумал верно. Только моя интуиция
подсказывает что мы (в данном топике) боремся с алгоритмом. Основной
поинт сложности в том что формула асимптоматики здесь не работает.
Верне сказать она ЕЩЕ не работает потому что у нас нет бесконечности
данных. И на границе перехода от памяти к диску эта формула резко
ломается. Всплывают коэффициенты которые опять-же для асимптоматики
не играют роли но нашем кейсе ИГРАЮТ и очень даже. Еще поинт добавляет
характер и род носителя. Например мы можем легко делать seek по оперативке
а тот-же seek по диску стоит во много раз дороже. Это надо учитывать.

А деревья поиска можно вначале по длине строк разбить (заодно экономия в записи), и далее или по 8-битной сумме или по одному из байтов crc.
Деревья поиска - это хоршая тема. У тебя кст. есть учотка в sourceforge?

И нужно доопределится с условиями задачи, RAM достаточно для crc+offset уникального набора или нет?
(4G ~ 16 байт для каждой из не более чем 200М уникальных строк в наборе или необходимо реализовать промежуточную выгрузку на диск )
Дружище. Это 100% на откуп тебе. Я вообще никак не модерирую ваш код.
Я просто создал нечто вроде тестовой площадки для обкатки идей и решений.
Но если твой код будет делать "бо-бо" обычному пользователю (вешать ОС, или
работать бесконечно нужно без всякой надежды на завершение)
то скорее всего обычный пользователь зайдет в таск менеджер и прибъет
твой процесс. И будет прав. И это будет самая лучшая и честная критика.

Поэтому - go-go кодить!

Друзья! О чем я сейчас думаю. Близится тестирование.

1) Я думаю о тестовой среде как запускать все ваши сорцы. Для этого мне (как минимум) нужна
возможность передавать вам аргументы командной строки. Хотя-бы имя файла. Если STDIN
то нужно это как-то передать тоже аргументом. Типа признак того что данные ожидаются именно оттуда.

From file:



From stdin:




2) Каждый алгоритм (опционально) может иметь некий настроечный параметр. Объем доступной для него
памяти. By default я буду брать примерно 80% от доступной оперативы (то что показывает task manager
в разделе free memory).

Например:




Данный пример говорит что алгоритму рекомендовано аллоцировать (прямо или косвенно) 2 гига памяти.
Если он превысит его то ошибки конечно не будет но и ничего хорошего тоже не ожидается. То есть
это рекомендация. Можно юзать. Можно нет. Но если она будет то это хорошо. В любом алгоритме
всегда есть какой-то манёвр или workaround в части памяти. Хеш-мапа может брать взвешенную
сумму длинн ключей и их количества. Может брать LRU и свопировать редкие ключи.
Биткарты соотв можно делить на 2,4,8. Технически это выглядит как отсечение старшего
бита или нескольких битов от INT32.

Если в алгоритме есть еще вектор параметров - то его тоже надо дать аргументами консоли. Буфера.
Тайминги. Гэпы. Ограничители. Типы хеш-функций и какие-то вещественные настройки типа там
коэфициенты заполнения buckets в хешмапах.

Я как и обещал буду кодить свой алгоритм ближе к выходным (сегодня еле дополз до дивана и слабеющей
рукой средним пальцем набиваю текст положив ноут себе на пузо) и буду думать над средой тестинга.

3) Я также думаю о сборе статистики с наших трех тестовых файлов (Test-File-Stats (TFS)). Думаю собирать
- rows
- cardinality
- соотношение двух вышесказанных (типа какова плотность повторов)
- средняя длина строки и максимальная (в окрестности выборки)
- медиана
- 75-й и 97 перцентиль
- размер файла

Еще экспериментально

- наличие ярко выраженного префикса (справочник)
- разреженные строки (много пробелов или повторов)

Статистика будет собираться экономно. Не по всему файлу. Будем брать семплы (фрагменты) с начала где-то 5%
с середины 5% и с хвоста тоже. Я думаю что это репрезентативно.

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

Грубо говоря мы попробуем дать ПРОГНОЗ на правильный алгоритм для нового файла используя новый TFS.

Дима. Я вот думаю о кешах.




Может их слить в один?. И еще вдруг возникла мысль что мы записываем не Бит-Карту а Трит-Карту .

Может перевести в троичную систему (виртуально) ? Ну примерно... как мы мапим 4 символа латиницы в 3 байта Base64.

Dima T, да. Стоит попробовать.