Тяпничная унификация / C++

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация

227 сообщений из 227, показаны все 10 страниц

все

Тяпничная унификация

#39514321

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

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

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

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

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

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

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

Пример usecase:

Код: sql

$ sql-ru-uniq inputfile.txt outfile.txt

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

Go! Go!

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

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

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

...

Рейтинг:

0 / 0

01.09.2017, 21:48

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514323

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

mayton,

тестовые данные - приготовил?

...

Рейтинг:

0 / 0

01.09.2017, 21:51

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514324

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

01.09.2017, 21:52

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514337

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

mayton,

а мой ответ из первой темы был слишком сложен и недопонят ?

...

Рейтинг:

0 / 0

01.09.2017, 22:36

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514343

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

01.09.2017, 23:04

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514350

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

maytonSiemargl, это грубо. К чему так?Где тут грубость?

Берем хеш таблицу по строкам и всё.

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

...

Рейтинг:

0 / 0

01.09.2017, 23:13

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514351

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

01.09.2017, 23:15

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514352

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

mayton,

В чем у тебя сомнения ?

Если хэш совпал, достаточно перепроверить содержимое. Для таблицы хэшей памяти хватит.

...

Рейтинг:

0 / 0

01.09.2017, 23:18

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514353

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Siemargl, worst case?

...

Рейтинг:

0 / 0

01.09.2017, 23:20

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514354

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

maytonSiemargl, worst case?Сама задача. Слишком просто.

http://nedoblog.ru/физики-против-математиков/

...

Рейтинг:

0 / 0

01.09.2017, 23:22

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514376

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

02.09.2017, 09:12

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514397

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

UP! Чо-как?

...

Рейтинг:

0 / 0

02.09.2017, 11:23

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514439

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

02.09.2017, 13:32

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514441

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

SiemarglДля таблицы хэшей памяти хватит.
а если сам файл из подобных хэшей состоит?

...

Рейтинг:

0 / 0

02.09.2017, 13:38

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514444

wst

Участник

Сообщения: 177

Рейтинг: 0 / 0

Если при проходе хеши перестают влезать в память - придется поделить хеши на "маска 3-6 бит + остальной хеш" и устроить несколько проходов для разных масок. Если за первый проход посчитать распределение по маскам - самые "непопулярные" маски можно объединять и обрабатывать за 1 проход.

...

Рейтинг:

0 / 0

02.09.2017, 13:57

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514446

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

02.09.2017, 14:08

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514447

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

02.09.2017, 14:10

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514468

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

02.09.2017, 16:32

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514504

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

mayton,
Дано: текстовый файл большого размера.
Найти: список Создать файл-результат состоящий только из уникальных строк из этого файла.Для простоты в 2-4 раза превышающий объем оперативной памяти. Важно знать или указать не соотношение файл/память, а возможно ли разместить хеши+смещения всех строк или только "1/128" часть в оперативной памяти?

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

...

Рейтинг:

0 / 0

02.09.2017, 21:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514517

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

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

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

...

Рейтинг:

0 / 0

02.09.2017, 22:12

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514520

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

mayton,

нужно взять в руки кувалду - отсортировать файл любым алгоритмом внешней сортировки

...

Рейтинг:

0 / 0

02.09.2017, 22:15

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514523

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

02.09.2017, 22:21

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514527

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

02.09.2017, 22:27

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514528

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

02.09.2017, 22:30

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514531

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

maytonЭто не главная задача в топике
это подзадача.
хотя дубли можно ликвидировать непосредственно в процессе сортировки.

...

Рейтинг:

0 / 0

02.09.2017, 22:32

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514533

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

ИзопропилmaytonЭто не главная задача в топике
это подзадача.
хотя дубли можно ликвидировать непосредственно в процессе сортировки.
А чуть раньше?

...

Рейтинг:

0 / 0

02.09.2017, 22:35

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514553

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

mayton,

не хочется иметь зависимость от количесва дублей и размеров строк.
а ожидаемое количество дублей и их распределение может серьёзно влиять на
скорость обработки. вплоть до невозможности в некоторых случаях выполнить залачу

потому я и сторонник кувалды.

...

Рейтинг:

0 / 0

02.09.2017, 22:57

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514564

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

А при чем здесь размер строк? Я ввел искусственное ограничение в 64К строки просто
чтобы вынести за рамки топика дискуссии на тему 4G строк и т.п. безсмыслицы.

Кстати предлагаю подумать. Постановка СОРТИРОВКИ требует интерфейса СРАВНЕНИЯ.
Это реализация (и использование в коде) предикатов БОЛЬШЕ (">"), МЕНЬШЕ("<"), РАВНО("=").

В то время как задача унификации в чистом виде лишь спрашивает нас о том
равны строки или нет ("=") в декартовом произведении файла с самим собой.

Как вам такой реверанс?

...

Рейтинг:

0 / 0

02.09.2017, 23:26

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514583

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

maytonА при чем здесь размер строк?
чем больше длина - тем легче жить
maytonПостановка СОРТИРОВКИ требует интерфейса СРАВНЕНИЯ.
имею возможность на множестве строк задать полный порядок.
веселее было бы если бы мы работали на множестве, где нельзя задать полный порядок

...

Рейтинг:

0 / 0

02.09.2017, 23:59

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514605

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

maytonсортировка будет эффективно решать мою задачу?Сортировка чего, строк или их хешей?

1n. Читаем большой файл и пишем, например, в 256 временных [ хеш строки(8b) + её адрес в большом файле(6b) + длину(2b) ]
2a. Читаем все записи из временного в память, сортируем по хешу. (Если мало памяти, повторяем пункт 1n и для временного файла)
2b. Проверяем те, что с одинаковым хешем на коллизию-копию, дубликаты игнорим.
2c. Для каждой из обработанных записей, читаем в большом файле строку по адресу и переписываем в результат.

...

Рейтинг:

0 / 0

03.09.2017, 03:33

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514639

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Bred eFeM, хорошо. Go-go в имплементацию.

...

Рейтинг:

0 / 0

03.09.2017, 08:14

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514641

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

В продолжение темы хешей. Несколько мыслей. Ложить в хеш-таблицу хеши - масло
маслянное получается. Если мы берем от произвольной строки CRC32 то фактически
классифицируем строки на 4 млрд классов. Для MD5 - соотв на 2^128 классов.

Уж если мы пошли по порочному пути хеширования (сворачивания) строк
в более ограниченное множество - то нам и хеш-табличка-то не нужна.

Для CRC32 мы можем аллоцировать массив из 2^32 бит = 512 Mb и фиксировать
факт попадания строки в нужный класс. Для MD5 соотв у нас есть больше
поле для растягивания разрядной сетки (и все разряды одинаково хорошо шумят)
и мы можем жонглировать размером биткарты получая все более точные и точные
классификации наших строк.

Еще открытый вопрос. Сколько памяти считать доступной? Тут мне интересно
как в Windows/Linux проверить сколько мы можем аллоцировать без опасения
создать Page Faults?

Знатоки Windows/Linux страничной памяти. Поделитесь опытом.

...

Рейтинг:

0 / 0

03.09.2017, 08:33

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514642

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Изопропилmayton,

тестовые данные - приготовил?
По поводу данных. Я вопрос не забыл. Я помню.

В качестве исходных я сейчас ищу базы Ripe.Db (DNS), email/IP blacklists а также различные словари
и справочники которые у меня были на внешних HDD.

Но поскольку их сложно шарить (толстые файлы) то я буду их также искать на публичном доступе.
По крайней мере Ripe.Db я качал свободно.

...

Рейтинг:

0 / 0

03.09.2017, 08:45

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514666

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Посадил репку
https://sourceforge.net/p/sql-ru-uniq/code/HEAD/tree/

...

Рейтинг:

0 / 0

03.09.2017, 11:59

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514754

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonГлавное - сделать уникальность.
В том топике ты отличный алгоритм предложил: первый проход разложить по корзинам/файлам по маске хэша, второй проход каждую корзину привести к уникальности, третий - склеить обратно.
ИМХО лучше не придумаешь. Осталось только подобрать алгоритм деления на корзины чтобы на втором шаге памяти хватало.

...

Рейтинг:

0 / 0

03.09.2017, 20:15

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514768

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, я не отказываюсь от него. Просто хочу оценить какие еще есть возможности. И послушать что скажут мемберы.

Алгоритм сердитого Зямы тоже имеет право на жизнь только его надо описать в части фазы №2
и решить вопрос с коллизиями.

...

Рейтинг:

0 / 0

03.09.2017, 20:50

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514787

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Тестовые данные:
https://ftp.ripe.net/ripe/dbase/ripe.db.gz

...

Рейтинг:

0 / 0

03.09.2017, 22:09

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514804

д0кХ

Гость

mayton
Еще открытый вопрос. Сколько памяти считать доступной? Тут мне интересно
как в Windows/Linux проверить сколько мы можем аллоцировать без опасения
создать Page Faults?

Знатоки Windows/Linux страничной памяти. Поделитесь опытом.
Swappiness

Но линуксоиды не будут терять время ради экономии на спичках,
они используют имеющуюся утилиту sort

...

Рейтинг:

0 / 0

03.09.2017, 23:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514812

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

д0кХmayton Еще открытый вопрос. Сколько памяти считать доступной? Тут мне интересно
как в Windows/Linux проверить сколько мы можем аллоцировать без опасения
создать Page Faults?

Знатоки Windows/Linux страничной памяти. Поделитесь опытом.
Swappiness

Но линуксоиды не будут терять время ради экономии на спичках,
они используют имеющуюся утилиту sort
Спасибо Док за ссылки.

По поводу sort. Мы не ищем легких путей.

...

Рейтинг:

0 / 0

03.09.2017, 23:42

| Ответить | Цитировать | Написать

Тяпничная унификация

#39514814

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Попробуй отсортировать 5 гигабайтный ripe.db

...

Рейтинг:

0 / 0

04.09.2017, 00:06

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515107

д0kХ

Гость

maytonПопробуй отсортировать 5 гигабайтный ripe.db

Это мне вопрос ?

Не вопрос, 5 Gb ни о чем :)
Если нужно будет по работе я найду
способ дорисовать на лету( без рестарта ОС ) в сервер 8..16..32..64 Gb RAM.

...

Рейтинг:

0 / 0

04.09.2017, 14:30

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515118

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Ты бы качнул и глянул в содержимое файла. :)

Он -- как пенопласт внутри. Состоит из пустот и повторов.

А ты бы ради пенопласта поднимал амазонское облако... Хехе

...

Рейтинг:

0 / 0

04.09.2017, 14:37

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515133

д0kХ

Гость

maytonТы бы качнул и глянул в содержимое файла. :)

Он -- как пенопласт внутри. Состоит из пустот и повторов.

А ты бы ради пенопласта поднимал амазонское облако... Хехе

офтопик
У нас есть свое :)
Поменьше амазоновского , но с аналогичным функционалом.

...

Рейтинг:

0 / 0

04.09.2017, 15:01

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515135

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Качнул, заглянул, там полфайла
авторremarks: ****************************
remarks: * THIS OBJECT IS MODIFIED
remarks: * Please note that all data that is generally regarded as personal
remarks: * data has been removed from this object.
remarks: * To view the original object, please query the RIPE Database at:
remarks: * http://www.ripe.net/whois
remarks: ****************************

И еще много чего повторяется.

sort виндовса отказался сортировать:

Код: plaintext

Длина введенной записи превышает допустимую.  Задайте большее максимальное значение.

Похоже не нравится перевод строки 0x0A, можно попробовать заменить на 0x0D

...

Рейтинг:

0 / 0

04.09.2017, 15:02

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515201

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

затестил с хэш-таблицей

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

void test(const char* filename) {
	std::unordered_set<std::string> res;
	FILE* f = fopen(filename, "r");
	if (f == NULL) {
		printf("File not open %s\n", filename);
		return;
	}
	char buf[1024];
	int cnt = 0;
	while (fgets(buf, 1024, f) != NULL) {
		std::string s = buf;
		res.insert(s);
		cnt++;
		if(cnt%1000000 == 0) printf("Time %d ms. Total %d rows. Unique %d\r", (int)clock(), cnt, (int)res.size());
	}
	size_t size = 0;
	for (auto& r : res) size += r.size();
	printf("Time %d ms. Total %d rows. Unique %d rows. Size %llu bytes\n", (int)clock(), cnt, (int)res.size(), size);
	system("pause");
	fclose(f);
}

Результат:

Код: plaintext

Time 72756 ms. Total 143`404`062 rows. Unique 26`511`499 rows. Size 1`087`175`584 bytes

В x86 память закончилась примерно на 83 млн. записей, в x64 потребовалось 3.9 Гб.
Как-то не очень эффективно: почти 4 Гб на 1 Гб полезной инфы.

...

Рейтинг:

0 / 0

04.09.2017, 16:30

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515226

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Код: plaintext

1.
2.
3.
4.

std::map<string_hash, string_offset, string_counter>

if ( (it = mymap.find(hash(test_string)) !=mymap.end() 
    && !compare_strings(readfile(it.second(), test_string)) ) it.third()++;

...

Рейтинг:

0 / 0

04.09.2017, 17:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515227

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Спасибо дима. Чуть позже я подкину ещё пару файлов. По cddb и по анти-спам спискам.

...

Рейтинг:

0 / 0

04.09.2017, 17:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515240

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я щас с планшета пишу. Кто-нить может позаменять переводы строк на нормальные и поднять windows sort утилиту?

...

Рейтинг:

0 / 0

04.09.2017, 17:15

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515258

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

У меня есть мысль про биткарту и я ее думаю

А если сделать биткарту по CRC32? Это всего 0.5 Гб, скидывать первое найденное уникальное CRC в результат.
В итоге получим в один проход набор уникальных строк, но не все, т.к. будут такие у которых CRC совпало с ранее найденными, как-то их отловить вторым проходом надо.

PS Siemargl, 20770457 ничего не понял, можно подробнее.

...

Рейтинг:

0 / 0

04.09.2017, 17:34

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515318

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T,

Это хорошая тема.

...

Рейтинг:

0 / 0

04.09.2017, 19:30

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515348

д0kХ

Гость

maytonПопробуй отсортировать 5 гигабайтный ripe.db

Эту https://ftp.ripe.net/ripe/dbase/ ?

...

Рейтинг:

0 / 0

04.09.2017, 20:49

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515364

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Да

...

Рейтинг:

0 / 0

04.09.2017, 21:53

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515374

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

maytonподнять windows sort утилиту?

Код: plaintext

ps:
gc ripe_da.txt | sort | unique > out.txt

~64GB RAM, 2 часа, - решил больше не ждать, прибил.

...

Рейтинг:

0 / 0

04.09.2017, 22:33

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515380

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Bred eFeM, перед тем как прибивать надо было заскриншотить счетчики в таск-менеджере.

Особо меня интересовали-бы "Bytes read", "Bytes write". Они - ключевые в оценке эффективности
работы утилиты sort.

...

Рейтинг:

0 / 0

04.09.2017, 22:42

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515383

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Обновил репку.

Исходник Зямы надо как-то дополить... Хм. Уж слишком кратко.

...

Рейтинг:

0 / 0

04.09.2017, 22:51

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515385

д0kХ

Гость

$date ; sort -u ripe.db > ripe.db_uniq ; date
Mon Sep 4 22:43:12 EEST 2017
Mon Sep 4 22:51:35 EEST 2017

$ wc -l ripe.db_uniq
26511401 ripe.db_uniq

Не тюнил, запускал на рабочей станции
sort потребял 4 ГБ оперативной памяти и кушал 100% CPU ( всех ядер)
model name : Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz

последняя строка в файле

Код: plaintext

ZzzOSdqFpKgV/KRAen/gVZPxvCvws4lyj8U7ZWjOzIlCN7WRX35ZxgM6SGablMUO

...

Рейтинг:

0 / 0

04.09.2017, 22:58

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515388

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Спасибо Док.

Пока имеем следующее (на разных конфигурациях но впрочем это пристрелочное).

РеализацияВремяИсходник Димы на базе unordered_map70 secsort -u8 min

Вот такие пироги.

...

Рейтинг:

0 / 0

04.09.2017, 23:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515452

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Ввожу новые тестовые данные. Опенсорцная база MusicBrainz.
Она должна хранить сведенья хронометраже CD-треков и тегам к ним
Artist, Theme e.t.c.

ftp://ftp.eu.metabrainz.org/pub/musicbrainz/data/fullexport/20170902-001537/mbdump.tar.bz2

Качается долго. Не с первого раза. В формате bz2 - 4Г. После распаковки в tar - порядка 40Г.
Внутри tar - текстовые файлы. Я еще не все посмотрел. Там есть мелкие и есть очень большие.

...

Рейтинг:

0 / 0

05.09.2017, 08:35

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515462

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Первый проход с биткартой для CRC

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.

void test_bitmap(const char* filename) {
	std::vector<bool> res(0x100000000L, 0);
	FILE* f = fopen(filename, "r");
	if (f == NULL) {
		printf("File not open %s\n", filename);
		return;
	}
	char buf[1024];
	size_t cnt = 0, uniq_cnt = 0, uniq_total = 0;
	char* r;
	size_t size = 0;
	while (fgets(buf, 1024, f) != NULL) {
		size_t len = strlen(buf);
		cnt++;
		crc32_t crc = crc32(buf, len);
		if(!res[crc]) {
			res[crc] = true;
			uniq_total += len;
			uniq_cnt++;
		}

		if (cnt % 1000000 == 0) printf("Time %d ms. Total %d rows. Unique %d rows. Size %d bytes\r", (int)clock(), cnt, (int)uniq_cnt, (int)uniq_total);
	}
	printf("Time %d ms. Total %d rows. Unique %d rows. Size %d bytes\n", (int)clock(), cnt, (int)uniq_cnt, (int)uniq_total);
	system("pause");
	fclose(f);
}

Код: plaintext

Time 44024 ms. Total 143`404`062 rows. Unique 26`427`696 rows. Size 1`083`808`289 bytes

Потерялось ~83 тыс. строк (или 0.3%), CRC32 совпало с другими. Как-то теперь их надо получить.

Вариант загнать все в хэш-таблицу не рассматриваем, т.к. целиком загнать можно сразу и без CRC.

Как вариант: из уникальных найденных по CRC читаем кусок нужного размера и загоняем в std::map<crc32_t, string>, затем полный прогон исходного файла: если CRC есть в map - сравнение string, если разные, добавление в std::set<string>.
И так несколько раз пока найденное по CRC не закончится. В конце содержимое std::set добавить в найденное по CRC.

...

Рейтинг:

0 / 0

05.09.2017, 08:53

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515465

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я тоже думал об этом. Все эти хеши-хешей, биткарты и прочие Блумы не снимают
с нас обязанности - перепроверить на втором проходе потенциальные дубликаты
(ProbableDuplicates).

Можно попробовать завести счетчики (int32), и считать коллизии по CRC32.
Если коллизий больше 2 - то на втором проходе заводим в обычную мапу.

...

Рейтинг:

0 / 0

05.09.2017, 08:57

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515467

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хотя... зачем я говорю int32. Нам ведь интересен 0,1,2. Тогда вроде как и 2-х битиков хватит.

...

Рейтинг:

0 / 0

05.09.2017, 09:00

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515470

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonМожно попробовать завести счетчики (int32), и считать коллизии по CRC32.
Если коллизий больше 2 - то на втором проходе заводим в обычную мапу.
Лишнее это, достаточно размер найденного сравнить с размером исходного, если найдено меньше - были или повторы или коллизии, а точно что было без полной перепроверки никак не узнать.

...

Рейтинг:

0 / 0

05.09.2017, 09:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515484

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я поясню почему именно три значения.

Код: plaintext

1.
2.
3.
4.
5.

enum CRC_State {
  NO_KEYS_DETECTED(0), // Не было ни одного ключика в этом классе
  ONE_KEY(1), // Хотя-бы одна строка попала
  MORE_THAN_ONE(2) // Было несколько строк. Требуестя перепроверка.
}

...

Рейтинг:

0 / 0

05.09.2017, 09:14

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515505

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Интересная мысль, чтобы с битами не заморачиваться можно две биткарты использовать

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

		if(!res[crc]) { // CRC встретилось впервые
			res[crc] = true;
			uniq_total += len;
			uniq_cnt++;
		} else if(!dbl[crc]) { // Повтор CRC, сохраняем для перепроверки
			dbl[crc] = true;
			dbl_cnt++;
		}

тогда на втором проходе из найденных по CRC брать на перепроверку только те, что есть в dbl[].

Посчитал, получилось что надо перепроверить 3.4 млн. CRC из 26.4 млн., почти в 8 раз меньше проверять.
ripe.db в два прохода обработается.

...

Рейтинг:

0 / 0

05.09.2017, 09:52

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515513

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Два прохода это вообще идеально. Будет 140 сек.

Док сортировал ещё дольше. И не потому что дисковая подсистема слабая. Там все в поряде. Просто такова она
Есть внешняя сортировка.

Я думаю что все наши алгоритмы будут двухпроходные. Разница в нюансах структур данных. И в вероятности
Поймать out of memory.

...

Рейтинг:

0 / 0

05.09.2017, 10:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515530

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonДва прохода это вообще идеально. Будет 140 сек.
Проход с биткартой 44 сек 20771520 , но я там только читал, а тут еще надо будет писать найденные строки с уникальными CRC, затем прочитать их перед вторым проходом.
maytonЯ думаю что все наши алгоритмы будут двухпроходные. Разница в нюансах структур данных. И в вероятности
Поймать out of memory.
Да. По исходным данным двух проходов достаточно.
В крайнем случае если все проверить на втором проходе памяти не хватит - писать что надо проверить во временный файл, а затем допроверить его.

...

Рейтинг:

0 / 0

05.09.2017, 10:25

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515561

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonВвожу новые тестовые данные. Опенсорцная база MusicBrainz.
Она должна хранить сведенья хронометраже CD-треков и тегам к ним
Artist, Theme e.t.c.

ftp://ftp.eu.metabrainz.org/pub/musicbrainz/data/fullexport/20170902-001537/mbdump.tar.bz2

Качается долго. Не с первого раза. В формате bz2 - 4Г. После распаковки в tar - порядка 40Г.
Внутри tar - текстовые файлы. Я еще не все посмотрел. Там есть мелкие и есть очень большие.
Качнул. Архив 2.4 Гб. После распаковки 8 Гб. Самые большие 5 файлов 6 Гб.
Похоже на выгрузку таблиц из какой-то БД, подозреваю что там все нормализовано и повторов не будет.

...

Рейтинг:

0 / 0

05.09.2017, 11:33

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515657

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Странно. У меня 40 гиг. Проверь плиз не оборвался ли bzip с хвоста?

...

Рейтинг:

0 / 0

05.09.2017, 13:37

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515666

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Две биткарты это ок. Плюсую. Заодно L1/L2 кеши продуем. Дадим краш тест.

...

Рейтинг:

0 / 0

05.09.2017, 13:44

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515674

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Подозреваю ты ссылку не на тот файл дал, там есть mbdump-edit.tar.bz2 этот 4.2 Гб, качаю этот.

...

Рейтинг:

0 / 0

05.09.2017, 13:53

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515682

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Возможно так. Я вечером контрольные суммы приложу.

...

Рейтинг:

0 / 0

05.09.2017, 14:00

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515698

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

mayton, Прикрути меня к сорсфорж-проекту

с перепроверкой хэша
Reading file ripe.db
completed 5205 Mb
---------
number of unique strings: 26509777
--stats--
total strings: 143393110
re-readings: 116883333
hash collisions: 0

Process returned 0 (0x0) execution time : 1175.789 s
Press any key to continue.

для 64-битного хэша коллизий 0, убираем перепроверку
Process returned 0 (0x0) execution time : 221.396 s

...

Рейтинг:

0 / 0

05.09.2017, 14:17

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515791

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Dima TПодозреваю ты ссылку не на тот файл дал, там есть mbdump-edit.tar.bz2 этот 4.2 Гб, качаю этот.

Скачал, распаковал. Список файлов с размерами

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

  4 862 499 089 edit
     13 686 109 edit_area
    928 963 216 edit_artist
 28 998 579 350 edit_data
      3 422 839 edit_event
     16 323 279 edit_instrument
     34 436 585 edit_label
  4 244 196 429 edit_note
     33 788 599 edit_note_recipient
     11 592 277 edit_place
    950 615 025 edit_recording
    383 683 200 edit_release
    269 146 948 edit_release_group
      1 634 957 edit_series
     86 015 723 edit_url
    114 429 566 edit_work
    821 822 488 vote
17 файлов 41 774 835 679 байт

Прогнал edit_data через биткарту с CRC

Код: plaintext

Time 286619 ms. Total 55`149`625 rows. Unique 54`062`614 rows.

1 млн. повторов CRC, всего 2%, а там кроме повторов еще коллизии, т.е. чистых повторов еще меньше.

...

Рейтинг:

0 / 0

05.09.2017, 15:25

| Ответить | Цитировать | Написать

Тяпничная унификация

#39515918

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Добавил второй проход и сохранение результата

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.

void test_bitmap(const char* filename, const char* filename_out) {
	FILE* f = fopen(filename, "r");
	if (f == NULL) {
		printf("Not open %s\n", filename);
		return;
	}
	FILE* f_out = fopen(filename_out, "w");
	if(f_out == NULL) {
		printf("Not open %s\n", filename_out);
		fclose(f);
		return;
	}
	printf("Find unique row in %s\n", filename);
	char buf[1024];
	size_t cnt = 0, uniq_cnt = 0, uniq_total = 0, dbl_cnt = 0;
	char* r;
	size_t size = 0;
	std::map<crc32_t, std::string> map_dbl;
	{
		std::vector<bool> dbl(0x100000000L, 0);
		{
			std::vector<bool> res(0x100000000L, 0);
#ifdef TEST
			while (fgets(buf, sizeof(buf), f) != NULL && cnt < TEST) {
#else
			while (fgets(buf, sizeof(buf), f) != NULL) {
#endif
				size_t len = strlen(buf);
				//uniq_total += len;
				crc32_t crc = crc32(buf, len);
				if(!res[crc]) { // CRC встретилось впервые
					res[crc] = true;
					uniq_total += len;
					fputs(buf, f_out);
					uniq_cnt++;
				} else if(!dbl[crc]) { // Повтор CRC, сохраняем для перепроверки
					dbl[crc] = true;
					dbl_cnt++;
				}

				cnt++;
				if ((cnt & 0xFFFFF) == 0) printf("Time %d ms. Total %d rows. Unique %d rows. Size %d kbytes\r", (int)clock(), cnt, (int)uniq_cnt, (int)(uniq_total / 1024));
			}
			printf("Time %d ms. Total %d rows. Unique %d rows. Size %d kbytes\n", (int)clock(), cnt, (int)uniq_cnt, (int)(uniq_total / 1024));
		}
		//res.clear();
		//res.resize(0);

		// Загрузка найденных строк с повторами в map_dbl
		printf("Doubles CRC %d rows. \n", (int)dbl_cnt);
		fclose(f_out);
		f_out = fopen(filename_out, "r");
		if (f_out == NULL) {
			printf("Not open %s\n", filename_out);
			fclose(f);
			return;
		}
		cnt = 0;
		while (fgets(buf, sizeof(buf), f_out) != NULL) {
			size_t len = strlen(buf);
			crc32_t crc = crc32(buf, len);
			if(dbl[crc]) {
				map_dbl[crc] = buf;
			}
			cnt++;
			if ((cnt & 0xFFFFF) == 0) printf("Time %d ms. Total %d rows.\r", (int)clock(), cnt);
		}
		printf("Time %d ms. Total %d rows.\n", (int)clock(), cnt);
		fclose(f_out);
	}
	//dbl.clear();
	//dbl.resize(0);

	// Поиск коллизий (совпало CRC)
	std::set<std::string> dop;
	fseek(f, SEEK_SET, 0);
	cnt = 0;
#ifdef TEST
	while (fgets(buf, sizeof(buf), f) != NULL && cnt < TEST) {
#else
	while (fgets(buf, sizeof(buf), f) != NULL) {
#endif
		size_t len = strlen(buf);
		crc32_t crc = crc32(buf, len);
		std::map<crc32_t, std::string>::iterator it = map_dbl.find(crc);
		if(it != map_dbl.end() && it->second != buf) {
			dop.insert(buf);
		}

		cnt++;
		if ((cnt & 0xFFFFF) == 0) printf("Time %d ms. Total %d rows. Unique %d rows.\r", (int)clock(), cnt, (int)dop.size());
	}
	printf("Time %d ms. Total %d rows. Unique %d rows.\n", (int)clock(), cnt, (int)dop.size());

	// Дозапись найденного
	if(dop.size() != 0) {
		f_out = fopen(filename_out, "a");
		if (f_out == NULL) {
			printf("Not open %s\n", filename_out);
			fclose(f);
			return;
		}
		for(std::set<std::string>::iterator it = dop.begin(); it != dop.end(); it++) {
			fputs(it->c_str(), f_out);
		}
		fclose(f_out);
	}
	fclose(f);
	printf("Time %d ms. Total unique %d rows.\n", (int)clock(), (int)dop.size() + uniq_cnt);
}

Код: plaintext

1.
2.
3.
4.

Time 49004 ms. Total 143404062 rows. Unique 26427696 rows. Size 1058406 kbytes
Doubles CRC 3402140 rows.
Time 63732 ms. Total 26427696 rows.
Time 157496 ms. Total 143404062 rows. Unique 83803 rows.
Time 157539 ms. Total unique 26511499 rows.

Вроде правильно, количество строк совпало с 20770314

Памяти тратит 1 Гб максимум, в начале на биткарты.

PS std::vector<bool> почему-то отказался память возвращать, clear() и resize(0) не помогли. Пришлось скобок наставить.

...

Рейтинг:

0 / 0

05.09.2017, 17:25

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516020

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Коллеги я забыл ваши учетки в sourceforge. Сообщите plz.

...

Рейтинг:

0 / 0

05.09.2017, 21:26

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516025

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Сведенья по тестовым данным.

md5Filesize8e32018f35dde63bcb347e8ad4456305ripe.db5 462 799 419a7d47a1ebed601c4c9c2df7cc85f74aehashkiller-dict.txt1 237 341 935

Чуть позже я сделаю enrichment этих данных чтоб добавить кардинальность и количество строк.

...

Рейтинг:

0 / 0

05.09.2017, 21:46

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516027

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, спрасибо. Статистика хорошая.

По поводу сорца.

Код: plaintext

1.
2.
3.
4.
5.

while (fgets(buf, sizeof(buf), f) != NULL) {
#endif
				size_t len = strlen(buf);
				//uniq_total += len;
				crc32_t crc = crc32(buf, len);

Я не знаю как устрена твоя функция crc32 но КМК мы сжигаем полезные мегафлопы
на расчете strlen. Можно было объединить это всесте с crc32. А результаты вернуть по ссылкам.

...

Рейтинг:

0 / 0

05.09.2017, 21:49

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516036

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Старые проекты такие как primegen-experiments, Card-raytracer-benchmark никуда не пропали
просто я тихонько мигрирую на гитхаб. Так что все сорцы сохранились.

Я пытаюсь исследовать возможности github и bitbucket и выбрать что удобнее.
GitHub не позволяет скрыть исходники (по крайней мере бесплатно). И это
минус который заставляет меня искать другие планы хостинга.

...

Рейтинг:

0 / 0

05.09.2017, 22:15

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516132

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonКоллеги я забыл ваши учетки в sourceforge. Сообщите plz.
Еле нашел кем там числюсь: dmitriyt

Посмотри в этом проекте, в настройках может остались кто учавствовал: https://sourceforge.net/projects/card-raytracer-bench/

...

Рейтинг:

0 / 0

06.09.2017, 08:45

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516134

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

maytonКоллеги я забыл ваши учетки в sourceforge. Сообщите plz.Учетка аналогичная, письмо через сорсфордж отправлял.
добавь к проекту обсуждения или тикеты, можно было бы там отписываться.

битбукетом пользуюсь для личных коммерческих проектов

...

Рейтинг:

0 / 0

06.09.2017, 08:48

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516140

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Добавил обоих.

...

Рейтинг:

0 / 0

06.09.2017, 08:59

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516145

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonЯ не знаю как устрена твоя функция crc32 но КМК мы сжигаем полезные мегафлопы
на расчете strlen. Можно было объединить это всесте с crc32. А результаты вернуть по ссылкам.

crc32() где-то в инете нашел

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.

#pragma once
#include <stdint.h>
#include <stdlib.h> 
#define CRCPOLY 0xEDB88320

typedef uint32_t crc32_t;

// Инициализация таблицы
static crc32_t* crc32_init() noexcept {
	crc32_t* crc_tab = (crc32_t*)malloc(256 * sizeof(crc32_t));
	if (crc_tab != NULL) {
		// Заполнение таблицы
		for (crc32_t i = 0; i < 256; i++) {
			crc32_t c = i;
			for (crc32_t j = 0; j < 8; j++) {
				if ((c & 1) != 0) {
					c = CRCPOLY ^ (c >> 1);
				}
				else {
					c = c >> 1;
				}
			}
			crc_tab[i] = c;
		}
	}
	return crc_tab;
}

// Расчет CRC32 блока памяти. prev_crc32 результат предыдущего блока
crc32_t crc32(const void* data, size_t size, crc32_t prev_crc32 = 0) noexcept {
	static crc32_t* crc_tab = NULL;
	if (crc_tab == NULL) {
		crc_tab = crc32_init();
	}
	else if (size == 0 && crc_tab != NULL) {
		free(crc_tab);
		crc_tab = NULL;
	}
	// Расчет
	prev_crc32 ^= 0xffffffff;
	if (crc_tab != NULL) {
		const uint8_t* buf = (uint8_t*)data;
		for (size_t i = 0; i < size; i++) {
			prev_crc32 = (prev_crc32 >> 8) ^ crc_tab[(prev_crc32 & 0xFF) ^ *buf];
			buf++;
		}
	}
	return prev_crc32 ^= 0xffffffff;
}

Если тут что-то менять, то fgets() на fread() или вообще WinAPI задействовать, т.е. читать страницами кратно секторам.
Я замеры делал: fgets() 60% времени съедает. Просто прочитать файл (5.2 Гб) с подсчетом кол-во строк: 26 сек. с добавлением strlen() и crc32() 44 сек. Т.е. чисто чтение 200 Мб/сек, хотя файл лежал на SSD с чтением 700 МБ/сек, а может вообще в кэше виндовса.

В общем надо чтение ускорять, потом можно акторы добавить и расчет crc32 распараллелить :)

Попозже соберу исходники в отдельный проект. На скорую руку писал в проекте для тестов, там помойка из всякой всячины.

...

Рейтинг:

0 / 0

06.09.2017, 09:08

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516148

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я-бы предложил пока без акторов. Но отказаться от строковых операций
и сделать работу на базе fopen/fread. Тоесть работать с потоком байт(символов).

...

Рейтинг:

0 / 0

06.09.2017, 09:13

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516154

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TmaytonКоллеги я забыл ваши учетки в sourceforge. Сообщите plz.
Еле нашел кем там числюсь: dmitriyt

Посмотри в этом проекте, в настройках может остались кто учавствовал: https://sourceforge.net/projects/card-raytracer-bench/
Я тогда посчитал что коммитов больше не будет и
поудалял участников и списка девелоперов.

Поскольку я больше сабжем не занимался то и
просматривать changes мне уже не хотелось.

Лишняя обязанность была ни к чему. Но я могу
возобновить активности по Card-Raytrace если
будут предложения от мемберов.

...

Рейтинг:

0 / 0

06.09.2017, 09:23

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516215

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

maytonДобавил обоих.закоммитил

...

Рейтинг:

0 / 0

06.09.2017, 10:25

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516275

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Siemargl,

Oh! Thnx.

...

Рейтинг:

0 / 0

06.09.2017, 11:26

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516803

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

По поводу своего сорца. Я до него доберусь не раньше выходных (я так думаю).

Дима. Не видел пока еще твоего коммита. Размышлял по поводу worst-case. Я думаю если объединить
файл сам с собой через cat, то мы как раз получим этот самый случай.

Siemargl. Интересный алгоритм. Насколько я понял предлагается использовать сам файл как хранилище
искомых строк. У меня возникает вопрос дисковой нагрузки. Надо сделать бенчмарк чтобы посмотреть
насколько это дорогая операция.

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

В настоящий момент я уже выделяю их столько:

1) Naive Hash-table.(NHT) Это самая первая наивная идея о которой думал каждый разработчик. И которая возможно
нелетает вследствие некоторого соотношения cardinality/rows. Но она тоже участвует в гонке.
2) CRC32-2-Phase . Вариант Димы.
3) Big-File-Unique-Lines-Counting (BFULC) . Вариант Зямы.
4) Split-Bucket-Processing-2-Phase (SBP2P) . Мой вариант который я еще не осилил.
5) Linux-Sort-Unique (LSU) . Куда-ж без него (машу Дохтару рукой).

Если есть еще варианты - пишите. Прошу также коммитить работающий код.

Илья? Сова? Вас тоже приглашаю.

...

Рейтинг:

0 / 0

06.09.2017, 21:56

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516808

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

mayton,

если хэш адекватный размеру исходников (64бит для 5Гб хватает), то перепроверка не требуется, иначе удесятеряет/вниз скорость

я могу ускорить перепроверку, введя кэш LFU, но честно говоря, возник вопрос - а какая точность решения задачи допустима?

...

Рейтинг:

0 / 0

06.09.2017, 22:18

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516809

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Нужно точное решение. Боюсь что приближенное просто никому не будет нужно.

...

Рейтинг:

0 / 0

06.09.2017, 22:26

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516811

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Обновлённые сведенья по тестовым выборкам.

md5FileSizeRowsCardinalityCard/RowsAvgRowLenc4095f84f8f0e20fc15e85108face730edit_data27G43 891 6806608e32018f35dde63bcb347e8ad4456305ripe.db5 462 799 419143 410 60438a7d47a1ebed601c4c9c2df7cc85f74aehashkiller-dict.txt1 237 341 93588 405 43013
Некоторые колонки я еще не посчитал. Сорян. Нечем

...

Рейтинг:

0 / 0

06.09.2017, 22:35

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516825

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

mayton,

ждем твое решение на яве

...

Рейтинг:

0 / 0

06.09.2017, 23:06

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516830

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Данную тулзу я напишу на сях.

...

Рейтинг:

0 / 0

06.09.2017, 23:18

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516833

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Дима. Я посмотрел на этот кусок функции и возникла мысль что не стоит так часто
очищать полезную таблицу магических констант для CRC32. Пускай она живет все
время пока работает приложение. ИМХО.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.

// Расчет CRC32 блока памяти. prev_crc32 результат предыдущего блока
crc32_t crc32(const void* data, size_t size, crc32_t prev_crc32 = 0) noexcept {
	static crc32_t* crc_tab = NULL;
	if (crc_tab == NULL) {
		crc_tab = crc32_init();
	}
	else if (size == 0 && crc_tab != NULL) {
		free(crc_tab);
		crc_tab = NULL;
	}
	// Расчет

[/SRC]

...

Рейтинг:

0 / 0

06.09.2017, 23:29

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516852

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Siemargl, запустил твоё приложение под Windows10-x64/MinGW-6.4.0.
Анализировал hashkiller-dict.txt.
Где-то после 8 минут работы - прервал. Скушал доступную память
(где-то с 4Г занятых у меня до 7.9). При этом в консоли было
Completed 940 Mb.

Вобщем надо что-то подоптимизировать. Это был самый мелкий файл
из моей тестовой выборки.

...

Рейтинг:

0 / 0

07.09.2017, 00:19

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516891

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonДима. Я посмотрел на этот кусок функции и возникла мысль что не стоит так часто
очищать полезную таблицу магических констант для CRC32. Пускай она живет все
время пока работает приложение. ИМХО.
Это было задумано для освобождения памяти, т.к. незачем считать CRC от блока в 0 байт, но в нашем случае встречаются пустые строки, где size == 0.
Закаментил, затестил, на 5 сек быстрее стало чем 20773604 :

Код: plaintext

Time 152806 ms. Total unique 26511499 rows.

...

Рейтинг:

0 / 0

07.09.2017, 07:35

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516898

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonДима. Не видел пока еще твоего коммита.
Вчера вечером пытался заменить fgets() на fread(), запутался в поисках конца последней полной строки: указатели, смещения ... (((
Сегодня оформлю в отдельный проект вариант с fgets(), залью.
maytonРазмышлял по поводу worst-case. Я думаю если объединить
файл сам с собой через cat, то мы как раз получим этот самый случай.
Да, так и есть. На перепроверку во втором проходе пойдут все уникальные найденные по CRC.

...

Рейтинг:

0 / 0

07.09.2017, 07:48

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516899

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, может стрельнуть последовательность чередующихся пустых строк.

...

Рейтинг:

0 / 0

07.09.2017, 07:51

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516903

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

Помня что у тебя акторы не скомпилировались, не стал unordered_map и unordered_set использовать. Они немного побыстрее чем map и set.

...

Рейтинг:

0 / 0

07.09.2017, 07:59

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516904

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

maytonSiemargl, запустил твоё приложение под Windows10-x64/MinGW-6.4.0.
Анализировал hashkiller-dict.txt.
Где-то после 8 минут работы - прервал. Скушал доступную память
(где-то с 4Г занятых у меня до 7.9). При этом в консоли было
Completed 940 Mb.

Вобщем надо что-то подоптимизировать. Это был самый мелкий файл
из моей тестовой выборки.У меня такого файла нет. Выкладывай ссылки на входные данные.

...

Рейтинг:

0 / 0

07.09.2017, 08:00

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516905

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TВчера вечером пытался заменить fgets() на fread(), запутался в поисках конца последней полной строки: указатели, смещения ... (((
Сегодня оформлю в отдельный проект вариант с fgets(), залью.
ОК. Закоммить стабильную версию с fgets(). Я буду смотреть.
Мне уже хочется что-то с чем-то сравнивать.

...

Рейтинг:

0 / 0

07.09.2017, 08:00

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516906

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

07.09.2017, 08:04

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516914

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

07.09.2017, 08:18

| Ответить | Цитировать | Написать

Тяпничная унификация

#39516973

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

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

Он сейчас 666Мб в архиве. Нужны стабильные данные.
Кроме того, обещали строки до 64кб, а не охуллиард трехбуквенных паролей, которые хэшировать себе дороже.
Модератор: Ссылка удалена

...

Рейтинг:

0 / 0

07.09.2017, 09:33

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517002

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

07.09.2017, 09:52

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517011

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

maytonСтабильные это какие?Одинаковые для всех тестеров/участников

...

Рейтинг:

0 / 0

07.09.2017, 09:57

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517016

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

07.09.2017, 10:01

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517018

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SiemarglКроме того, обещали строки до 64кб, а не охуллиард трехбуквенных паролей
Жестокий тест

Если его ухудшить 20777122 то мой код тоже затупит и память жрать начнет. Поставил на закачку.

Про макс.размер строки: у меня буфер 1024 байта для fgets(). Сколько поставить?

...

Рейтинг:

0 / 0

07.09.2017, 10:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517042

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

Прогнал hashkiller-dict.txt.

Код: plaintext

1.
2.
3.
4.

Time 27394 ms. Total 88608579 rows. Unique 58915144 rows. Size 760280 kbytes
Doubles CRC 7481488 rows.
Time 48109 ms. Total 58915144 rows.
Time 161480 ms. Total 88608579 rows. Unique 406432 rows.
Time 161585 ms. Total unique 59321576 rows.

Собственно записей 88 млн., меньше чем в ripe.db, но уникальных 59 млн., т.е. две трети.
Модератор: Ссылка удалена

...

Рейтинг:

0 / 0

07.09.2017, 10:16

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517054

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

07.09.2017, 10:22

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517065

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

ард трехбуквенных паролейдля 1-3(4) буквенных - битмап.

заменить fgets() на fread(), сейчас смотрю-думаю считать crc вместе с поиском конца строки.
Ну, и асинхронное чтение и многопоток как прикрутить.

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

И нужно доопределится с условиями задачи, RAM достаточно для crc+offset уникального набора или нет?
(4G ~ 16 байт для каждой из не более чем 200М уникальных строк в наборе или необходимо реализовать промежуточную выгрузку на диск )

...

Рейтинг:

0 / 0

07.09.2017, 10:27

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517446

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Зафиксировал. Можно запускать.

Потестил на линуксе: есть небольшая проблема с биткартой, std::vector<bool> долго инициализируется. 4-5 сек.
В MSVC быстро, правда при компиляции в DEBUG тоже тупит. Для начала запусти на маленьком файле, если будет тупить - значит биткарта.

Что-то много претензий к vector<bool> уже накопилось, писал где-то самодельный, надо поискать.

...

Рейтинг:

0 / 0

07.09.2017, 15:11

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517700

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

07.09.2017, 19:17

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517734

д0kХ

Гость

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

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

Я прверял под линуксом.

malloc - не запрашивает память у ОС
реальное выделение памяти процессу просходит при memset.

...

Рейтинг:

0 / 0

07.09.2017, 20:15

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517741

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

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

Я прверял под линуксом.

malloc - не запрашивает память у ОС
реальное выделение памяти процессу просходит при memset.
ИМХО Это ни при чем. Для

Код: plaintext

std::vector<bool> dbl(0x100000000L, 0);

какая-то побитовая инициализация.

...

Рейтинг:

0 / 0

07.09.2017, 20:44

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517748

Изопропил

Участник

Сообщения: 33 046

Рейтинг: 0 / 0

Siemarglохуллиард трехбуквенных паролей, которые хэшировать себе дороже.
я предупреждал об этом ))

...

Рейтинг:

0 / 0

07.09.2017, 20:56

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517766

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

ИзопропилSiemarglохуллиард трехбуквенных паролей, которые хэшировать себе дороже.
я предупреждал об этом ))
он перегнул про три буквы, подлиннее там пароли. Да и 62^3 = 238328, всего, а это все варианты [a-z][A-Z][0-9] во всех сочетаниях по три.
Минимум 8 букав обычное требование.

...

Рейтинг:

0 / 0

07.09.2017, 21:34

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517777

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

07.09.2017, 21:51

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517789

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

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

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

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

...

Рейтинг:

0 / 0

07.09.2017, 22:07

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517811

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

From file:

Код: plaintext

$ sql-ru-uniq-mayton-utility ripe.db

From stdin:

Код: plaintext

$ sql-ru-uniq-mayton-utility -

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

Например:

Код: plaintext

$ sql-ru-uniq-mayton-utility ripe.db 2048M

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

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

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

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

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

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

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

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

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

...

Рейтинг:

0 / 0

07.09.2017, 22:45

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517902

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

Выходной файл удобнее задавать явно, чтобы не заморачиваться с генерацией имен.

Код: plaintext

my-util ripe.db ripe.uniq

PS Просьба удалить мой пост 20780400 , случайно отправил ничего не написав.

...

Рейтинг:

0 / 0

08.09.2017, 07:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517930

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Добавил функцию для проверки результата , кому надо - можете пользоваться.
Возвращает XOR(CRC32) всех непустых строк, т.е. от порядка строк не изменится. Выводит общую статистику:

Код: plaintext

check file ripe-uni.db
CRC: A4E3E012  Rows: 26511419  Bytes: 1087175584  Min row: 1  Max row: 8663

...

Рейтинг:

0 / 0

08.09.2017, 08:06

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517951

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Код: plaintext

1.
2.
3.

		std::vector<bool> dbl(0x100000000L, 0);
		{
			std::vector<bool> res(0x100000000L, 0);

...

Рейтинг:

0 / 0

08.09.2017, 09:04

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517968

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

Код: plaintext

1.
2.
3.

		std::vector<bool> dbl(0x100000000L, 0);
		{
			std::vector<bool> res(0x100000000L, 0);

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

Может перевести в троичную систему (виртуально) ? Ну примерно... как мы мапим 4 символа латиницы в 3 байта Base64.
Я думаю может вообще выкинуть dbl и писать повторы сразу в map<crc, string>, т.к. следующий шаг это заполнение map по dbl.

...

Рейтинг:

0 / 0

08.09.2017, 09:26

| Ответить | Цитировать | Написать

Тяпничная унификация

#39517970

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

...

Рейтинг:

0 / 0

08.09.2017, 09:27

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518010

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

У меня другой алгоритм родился:
Шаг 1. Берем две биткарты и для каждой строки считаем CRC разными способами. Пишем два результата. Формат записи: смещение до начала строки в исходном файле.
Шаг 2. Сливаем результаты в один и пишем ответ. Смещение возрастает, поэтому в один проход два результата можно сравнить.

Главный минус: нет 100% гарантии исключения коллизий. Например для 2-х разных строк один из способов гарантированно даст разные CRC, но есть маленькая вероятность что попадется комбинация из 3-х строк, из которых 1-3 будут иметь коллизию в первой биткарте, 2-3 во второй. В итоге 3-я будет пропущена.

Зато по памяти все прогнозируемо: ровно 1 Гб под биткарты. Если есть еще память, то там кэшировать результат в vector<size_t>.

...

Рейтинг:

0 / 0

08.09.2017, 10:18

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518366

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Сделал блочное чтение. Быстрее стало в 2 с лишним раза. Кто хочет - можете пользоваться. Класс block_read.h

Зафиксировал. Там два проекта:
uniq-mem - просто добавляет в unordered_set<string> и в конце скидывает его в файл.
uniq-crc - с биткартами и CRC32

По скорости одинаково работают.

...

Рейтинг:

0 / 0

08.09.2017, 17:32

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518432

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хопа. Я вернулся.

...

Рейтинг:

0 / 0

08.09.2017, 21:19

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518455

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Дима. Посмотрел твой код. Мне понравился этот метод. Хитро придумал.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

	bool getset(size_t pos) {
		size_t idx = pos >> 5;
		assert(idx <= len);
		uint32_t mask = 1 << (pos & 31);
		bool ret = (bitmap[idx] & mask) != 0;
		bitmap[idx] |= mask;
		return ret;
	}

...

Рейтинг:

0 / 0

08.09.2017, 21:57

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518459

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Далее. Похоже Дима сделал аж 2 реализации. Одну из них я выше называл Naive Hash-table(NHT).
Ну что-ж. Отлично. Больше вариантов.

Пора как-то навести порядок с названиями. Идентифицировать хотяб.

Заведу табличку.

AuthorAlgorithmSourceNameCommentsDima-TNaive Hash-table(NHT)uniq-memDima-TCRC32-2-Phase(CRC32-2P)uniq-crcMaytonSplit-Bucket-Processing-2-Phase(SPB2P)spb2pВ разработке..SiemarglBig File Unique Lines Counting(BFULC)siemargl_bighashДокLinux Sorting Utility(LSU)sortЛинуксовая утилита

Откоментируйте если чо не так.

P.S. Хотя Док не является автором Линуксовой сортировки но он ее усиленно продвигал по сабжу.
Поэтому я ставлю докторскую колбасу унификацию под видом Linux sort -u

...

Рейтинг:

0 / 0

08.09.2017, 22:33

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518538

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonПохоже Дима сделал аж 2 реализации. Одну из них я выше называл Naive Hash-table(NHT).
Давно ее сделал 20770314 , просто оформил в проект, чтобы было с чем результаты сравнивать.

После замены fgets() на блочное чтение уникальных строк в ripe.db стало чуть меньше, как понял fgets() 0xA на конце оставляет и еще что-то есть.

...

Рейтинг:

0 / 0

09.09.2017, 09:11

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518560

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Dima T,

Не сходится с моим результатом 20772846

Или может файл поменялся. Надо исходников Md5 сверять

...

Рейтинг:

0 / 0

09.09.2017, 11:49

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518562

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Если есть какие-то changes по исходным данным - редактируйте табличку и публикуйте. Я тоже учту.

...

Рейтинг:

0 / 0

09.09.2017, 11:55

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518570

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SiemarglDima T,

Не сходится с моим результатом 20772846

Или может файл поменялся. Надо исходников Md5 сверять
Я давно заметил что не сходится, потом присмотрелся:
у тебя 143393110 строк в файле, у меня 143404062

Файлы разные.

...

Рейтинг:

0 / 0

09.09.2017, 12:18

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518572

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

ИМХО надо по одним и тем же файлам все прогонять. Я для того и сделал второй вариант чтобы было с чем сравнить.
И у меня еще нюанс: пустые строки игнорируются, т.е. любая комбинация 0xA и 0xD считается одним переводом строки.

...

Рейтинг:

0 / 0

09.09.2017, 12:22

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518580

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SiemarglDima T,

Не сходится с моим результатом 20772846

Или может файл поменялся. Надо исходников Md5 сверять
Прогнал твой код со своим файлом, сходится
Мой результат: Time 50668 ms. Total unique 26511418 rows.
Твой: number of unique strings: 26511419 Время 176 сек.
Разница в 1, т.к. я пустые строки пропускаю.

PS Ты бы добавил передачу имени файла в параметрах и сохранение результата

Можешь мой main() взять за основу

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

int main(int argc, char** argv) {
	if(argc <= 2) {
		printf("\n\n Select unique rows from text file. \n\n Command line:\n uniq1 source_file result_file\n");
		return 0;
	}
	printf("Compile %s %s\n", __DATE__, __TIME__);
	read_file(argv[1], argv[2]);
	crc32_t crc = file_checksum(argv[2]);
	return 0;
}

...

Рейтинг:

0 / 0

09.09.2017, 12:56

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518582

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Siemargl, заменил в твоем коде map на unordered_map время упало с 176 сек. до 122 сек.

...

Рейтинг:

0 / 0

09.09.2017, 13:04

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518592

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TSiemargl, заменил в твоем коде map на unordered_map время упало с 176 сек. до 122 сек.
+1

...

Рейтинг:

0 / 0

09.09.2017, 13:41

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518595

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Последний тестовый файл я добавляю к исследованию. 13Гб в открытом виде.
1.2 миллиарда строк. По некоторым соображениям я не буду давать на него
ссылки в форуме (сами понимаете, есть действующие правила). Но дам в личку
если кому надо.

...

Рейтинг:

0 / 0

09.09.2017, 13:47

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518598

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Dima TSiemargl, заменил в твоем коде map на unordered_map время упало с 176 сек. до 122 сек.
Это был предусмотренный резерв - хидер уже подключен =)

Просто жду, когда будет нормальный набор тестов и Майтон что то напишет. Потом будем красить красоту.

...

Рейтинг:

0 / 0

09.09.2017, 13:49

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518617

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Еще немного затюнинговал: Заменил crc32() на хэш попроще.
ripe.db проходит за 40 сек вместо 50 :)

mayton, затестил триткарту 20780617 , скорость чуть-чуть выше, хоть у проца меньше промахов кэша, но доп.расчеты съели сэкономленное время.
Не буду ее добавлять, т.к. по результату первого шага удаляется первая биткарта (512 Мб), а на втором шаге используется только вторая.
От второй биткарты тоже не буду избавляться, т.к. при ее использовании 2-3 шаги можно делать частями если за раз не проходит.

...

Рейтинг:

0 / 0

09.09.2017, 15:09

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518632

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Siemargl, я начал запускать твой алгоритм. Вобщем нужны аргументы command-line. Я добавил.

Посмотри коммит https://sourceforge.net/p/sql-ru-uniq/code/16/

Есть еще закомментареные секции печати unique слов и отдельно отчет по статистике.
Я не знаю что с этим делать поэтому пока оставил как есть. Вобщем сделай как ты считаешь
нужным но чтоб я мог приступить к тестингу с выводом резалта.

...

Рейтинг:

0 / 0

09.09.2017, 16:38

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518633

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

mayton, мой обнови. Добавил однопроходный вариант с более агрессивным расходом памяти. ripe.db за 26 сек.
Если будет вылетать, то двухпроходный запускается с доп.ключом /L.

...

Рейтинг:

0 / 0

09.09.2017, 16:41

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518638

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, ого. С вылетанием - это плохо. С точки зрения конечного пользователя. Может задать
какую-то логику. Если превышаем 80% от доступной памяти - то откат агрессивного алгоритма
и старт экономного.

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

По поводу твоего блочного чтения. Я не совсем понял зачем там копирование памяти.

Код: plaintext

1.
2.
3.

		if (p == buf_end) { // конец буфера, строка не полная. Перенос в начало и дочитывание.
			size_t s = buf_end - cur;
			if (cur != buf_end) memcpy(buf, cur, s);

Мне казалось блочное чтение строк можно реализовать без него. Или я ошибаюсь? ХЗ.

...

Рейтинг:

0 / 0

09.09.2017, 16:58

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518648

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima T, ого. С вылетанием - это плохо. С точки зрения конечного пользователя. Может задать
какую-то логику. Если превышаем 80% от доступной памяти - то откат агрессивного алгоритма
и старт экономного.

Падающие алгоритмы мне будет сложно тетсировать. Что обрабатывать? Аварийное завершение.
Синий экран. Вобщем у меня не получится автоматизация тестирования.
Поразмышлял про ключик. Он не спасет, в обоих случаях в памяти будет биткарта + map из повторившихся строк. В первом еще set из строк на хэше которых коллизия была, но их не много.
В общем чтобы ключик спасал надо вариант с ключиком допрописывать на еще 2+ проходов.
Добавлю обработку исключений при нехватке памяти.
maytonПо поводу твоего блочного чтения. Я не совсем понял зачем там копирование памяти.

Код: plaintext

1.
2.
3.

		if (p == buf_end) { // конец буфера, строка не полная. Перенос в начало и дочитывание.
			size_t s = buf_end - cur;
			if (cur != buf_end) memcpy(buf, cur, s);

Мне казалось блочное чтение строк можно реализовать без него. Или я ошибаюсь? ХЗ.
Логика такая: есть буфер 1 Мб например, прочитали туда 1Мб и парсим последовательно: наткнулись на конец строки - отдали на обработку и т.д., а когда наткнулись на конец буфера и в нем только начало строки, то начало строки копируется в начало буфера, затем буфер дочитывается из файла.
Это только на концах буфера происходит, можно просто размер буфера увеличить чтобы это реже происходило.

...

Рейтинг:

0 / 0

09.09.2017, 17:44

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518661

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TЛогика такая: есть буфер 1 Мб например, прочитали туда 1Мб и парсим последовательно: наткнулись на конец строки - отдали на обработку и т.д., а когда наткнулись на конец буфера и в нем только начало строки, то начало строки копируется в начало буфера, затем буфер дочитывается из файла.
Это только на концах буфера происходит, можно просто размер буфера увеличить чтобы это реже происходило.
Для твоего алгоритма (update CRC32) не обязательно подавать на вход целую строку. Можно в 2 шага.
Update head, update tail.

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

...

Рейтинг:

0 / 0

09.09.2017, 19:42

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518663

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima TЛогика такая: есть буфер 1 Мб например, прочитали туда 1Мб и парсим последовательно: наткнулись на конец строки - отдали на обработку и т.д., а когда наткнулись на конец буфера и в нем только начало строки, то начало строки копируется в начало буфера, затем буфер дочитывается из файла.
Это только на концах буфера происходит, можно просто размер буфера увеличить чтобы это реже происходило.
Для твоего алгоритма (update CRC32) не обязательно подавать на вход целую строку. Можно в 2 шага.
Update head, update tail.

Тебе целая строка может только понадобиться на только в той фазе когда ты ее кладешь в хеш-таблицу.
Согласен, но я руководствуюсь принципом изолированности уровней: нижний не знает что делает верхний. Нижний читает, верхний считает.
Задача нижнего выдать строку целиком. Так проще, иначе в коде каша получается: нижний должен сообщить что это кусок, а не целое, верхний должен это как-то обрабатывать. И выигрыша в производительности тут доли процента, а то и наоборот потери будут из-за лишних проверок целая/нецелая.

PS Добавил обработку исключений нехватки памяти. Пока просто останов и удаление неполного результата.

...

Рейтинг:

0 / 0

09.09.2017, 20:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518665

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonПоследний тестовый файл я добавляю к исследованию. 13Гб в открытом виде.
1.2 миллиарда строк. По некоторым соображениям я не буду давать на него
ссылки в форуме (сами понимаете, есть действующие правила). Но дам в личку
если кому надо.
Думаю мой код его за один проход переварит даже на твоем ноуте, но если ты сделаешь

Код: plaintext

copy big.txt+big.txt superbig.txt

то на superbig.txt вылетит.

Завалялся файлик с утерянными паспортами 1.2 Гб, для эмуляции недостатка памяти скомпилировал в x86, он обработался, там 100% уникальных строк, пришлось его удвоить чтобы вылетать начало. В общем чем больше уникальных строк, тем меньше надо памяти.

Пока думаю что делать если память кончилась, надо как-то задействовать наработанное и перейти к плану Б.

PS Интересное наблюдение: Win7 в диспетчере задач показывает *32 на x86 процессах, а Win10 - нет. Похоже MS передумал уходить от x86.

...

Рейтинг:

0 / 0

09.09.2017, 20:17

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518667

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TPS Добавил обработку исключений нехватки памяти. Пока просто останов и удаление неполного результата.
Тут вот какое дело. Я думаю что исключение нехватки памяти это очень ПОЗДНЕЕ событие.
Мой поинт в том чтобы не ловить эти грабли а заведомо до запуска утилиты оценивать свободное
место. Дело в том что механизмы swap и paging-file в Win/Linux подкинут нам медвежью услугу. Они отодвинут
это событие далеко в будущее но при этом алгоритм просядет в производительности. Поэтому
я полагаю что не стоит ждать этого события а просто подстроиться под "актуальные" условия.

Под моим линуксом (Ubuntu на виртуалке VBox) это может выглядеть так. Я вызываю внешний процесс free -m и просто ловлю output
и беру значение Mem/Free. Я думаю что это вполне-себе natural-way для Linux программинга.

В данном вопросе я не профи. Я не очень силен в архитектуре памяти OS-Linux поэтому если я где-то не прав
то пускай опытный линуксоид аргументирует где я не прав и почему.

...

Рейтинг:

0 / 0

09.09.2017, 20:31

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518670

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Поясняющая картинка

...

Рейтинг:

0 / 0

09.09.2017, 20:52

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518671

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima TPS Добавил обработку исключений нехватки памяти. Пока просто останов и удаление неполного результата.
Тут вот какое дело. Я думаю что исключение нехватки памяти это очень ПОЗДНЕЕ событие.
Я про это тоже думал. Как вариант кидать исключение при выводе статистики:

Код: plaintext

if ((cnt & 0xFFFFF) == 0) printf(...

в этот момент оценивать скорость обработки, и если она упала в несколько раз, значит начался своп, можно кидать исключение. Или просто ограничится x86 процессом где 2 Гб наше все.

maytonМой поинт в том чтобы не ловить эти грабли а заведомо до запуска утилиты оценивать свободное
место.
Тут проблема оценивать расход памяти в ходе расчета: std::string забирает доп. память для служебной инфы, контейнеры забирают под массивы хэшей/деревья и т.д. и т.п. Например мой код с unordered_set<string> на ripe.db (проект uniq-mem) съедает 4 Гб оперативки, хотя результат всего 1 Гб.
Расход памяти никак не оценить изнутри, т.е. средствами языка. Можно конечно средства ОС вызывать, но это как-то не спортивно.

...

Рейтинг:

0 / 0

09.09.2017, 20:57

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518672

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonПод моим линуксом (Ubuntu на виртуалке VBox)
В виртуалке такие вещи не надо тестить, там проблемы с дисковым IO. Я пишу в виртуалке, там все тормозит, тестю на хосте I7-6700К 4 ГГц, память 32 Гб DDR4, диск SSD.

...

Рейтинг:

0 / 0

09.09.2017, 21:07

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518680

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TЯ про это тоже думал. Как вариант кидать исключение при выводе статистики:

Код: plaintext

if ((cnt & 0xFFFFF) == 0) printf(...

в этот момент оценивать скорость обработки, и если она упала в несколько раз, значит начался своп, можно кидать исключение. Или просто ограничится x86 процессом где 2 Гб наше все.

Мы никогда точно не сможем подобрать эту скорость. Она слишком кастомизирована. И зависит
от активности пользователя. Может от чёто копирует там. Или стартовал какое-то тяжелое приложение.
Антивирус проснулася.. Да мало ли.

...

Рейтинг:

0 / 0

09.09.2017, 21:58

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518681

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TТут проблема оценивать расход памяти в ходе расчета: std::string забирает доп. память для служебной инфы, контейнеры забирают под массивы хэшей/деревья и т.д. и т.п. Например мой код с unordered_set<string> на ripe.db (проект uniq-mem) съедает 4 Гб оперативки, хотя результат всего 1 Гб.
Расход памяти никак не оценить изнутри, т.е. средствами языка. Можно конечно средства ОС вызывать, но это как-то не спортивно.
Да. Я собственно ратую за кастомизацию приложения. Его надо будет "разлохматить" хотя-бы в два направления.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

int64_t getFreeMemory(){
     #ifdef __WIN32
       ....
     #elseif
         // Linux (RHEL/Ubuntu e.t.c)
          ....
     #endif
}

Без этой ветки мы далеко не уедем.

Еще есть такой поинт. Если мы часто и много юзаем структуры с указателями. То исходник собранный под x86
красив и компактен и тоже самое с рантаймом. А если собираем под x64 то указатель пухнет до безобразия
и теряем перформанс как следствие толстых структур данных которые не лезут в кеш и за счет естественной
просадки производительности вызванной длинной арифметикой. Тоесть есть разумный поинт не пересекать
границу 2G вообще.

А если уж пересекать то так чтобы ... Эххх. Сразу в 8G или в 16G рвануть.

...

Рейтинг:

0 / 0

09.09.2017, 22:05

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518740

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TВ виртуалке такие вещи не надо тестить, там проблемы с дисковым IO. Я пишу в виртуалке, там все тормозит, тестю на хосте I7-6700К 4 ГГц, память 32 Гб DDR4, диск SSD.
100% ты прав. Я там тестить не буду. На виртуал-боксе я смотрю какие есть фичи и возможности
под современные линуксы. Своя рабочая станция под Linux для себе уже в обсуждении. Я пока
жадничаю с конфигурацией и решаю что прикупить а что нет. Так-что... Coming soon

...

Рейтинг:

0 / 0

10.09.2017, 11:20

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518751

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonДа. Я собственно ратую за кастомизацию приложения. Его надо будет "разлохматить" хотя-бы в два направления.
Поизучал варианты. Этот самый простой в реализации.
Добавил mem_used.h

С биткартой интересно получается: calloc() изначально реальную память не занимает, а только по мере использования. Т.е. на маленьком файле 100-200 строк биткарта забирает несколько Мб.

maytonЕще есть такой поинт. Если мы часто и много юзаем структуры с указателями. То исходник собранный под x86
красив и компактен и тоже самое с рантаймом. А если собираем под x64 то указатель пухнет до безобразия
и теряем перформанс как следствие толстых структур данных которые не лезут в кеш и за счет естественной
просадки производительности вызванной длинной арифметикой. Тоесть есть разумный поинт не пересекать
границу 2G вообще.

А если уж пересекать то так чтобы ... Эххх. Сразу в 8G или в 16G рвануть.
Есть такое: на ripe.db в x64 пик 857 Мб, а для x86 - 747 Мб. Если вычесть биткарту 512 Мб, то имеем 345/235 или в 1.47 раза больше памяти под x64.

Но по времени: x64 - 26.9 сек, x86 - 32.9 сек.
Не знаю почему так, то ли компилятор лучше заточен под x64, то ли проц.

И такой момент обнаружился: на виртуалке (Win7) 3 Гб, 2 Гб свободно. На x86 исключение о нехватке памяти ожидаемо на 1.9 Гб, а на x64 исключение на 1.7 Гб.

...

Рейтинг:

0 / 0

10.09.2017, 12:40

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518752

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TПоизучал варианты. Этот самый простой в реализации.
Добавил mem_used.h

О. Спасибо. Как раз это я искал.

...

Рейтинг:

0 / 0

10.09.2017, 12:44

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518760

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Навел порядок в тестовых данных. Файлы попереименовывал в lst для удобства. Ввел счетчик
поврежденных строк. Это те которые больше 64к. Как я и обещал мы их просто отбросим из
эксперимента. Некоторые стат-показатели глюканули (где -1). Буду разбираться. Скорее всего
я не учел что SHA1 имеют резкую гистограмму длин строк. Ну и кардинальность надо посчитать
и вписать.

NameFile LengthRowsDamaged RowsCardinalityAvg RLMedian RL75-perc RL97-perc RLMax RLc:\db\1.2billion\1.2billion.lst13 GB120677026301010121863c:\db\anti-spam\dom-bl-base.lst3 MB22800601616202867c:\db\anti-spam\dom-bl.lst13 KB77201616192733c:\db\anti-spam\from-bl.lst4 MB16811602828314071c:\db\CDDB\edit.lst4 GB438916800109112117118119c:\db\CDDB\edit_area.lst13 MB92867701314141415c:\db\CDDB\edit_artist.lst885 MB5370593701617171718c:\db\CDDB\edit_data.lst27 GB438906351045656428586298765502c:\db\CDDB\edit_event.lst3 MB23562201313131314c:\db\CDDB\edit_instrument.lst15 MB130516001111111112c:\db\CDDB\edit_label.lst32 MB210772801515161617c:\db\CDDB\edit_note.lst3 GB26856966215411417449051183c:\db\CDDB\edit_note_recipient.lst32 MB232297401314141516c:\db\CDDB\edit_place.lst11 MB81403301313131314c:\db\CDDB\edit_recording.lst906 MB5590619101615161617c:\db\CDDB\edit_release.lst365 MB2361387101515151516c:\db\CDDB\edit_release_group.lst256 MB1634517501515151516c:\db\CDDB\edit_series.lst1 MB11991801212121213c:\db\CDDB\edit_url.lst82 MB517968501515151516c:\db\CDDB\edit_work.lst109 MB648825601616161617c:\db\CDDB\md5.lst1 KB2304645495657c:\db\HashKiller\hashkiller-dict.lst1 GB8840540921129124155224c:\db\Linked-In\SHA1.lst240 MB6143150040-1-1-140c:\db\Psyc\AllMain_aA4_eE3_gG6_lL1_oO0__sS5_tT7.lst5 GB549682416099101431c:\db\Psyc\CommonPassword_aA4_eE3_bB8_gG6_lL1_oO0_zZ2_sS5_tT7.lst3 GB39085521308881115c:\db\Psyc\ComputerJargonLower+4PrefixWPA.lst1 GB8954436901212141935c:\db\Psyc\FamilyNamesLower+4PrefixWPA.lst1 GB13070572801011121521c:\db\Psyc\FemaleNamesLower+4PrefixWPA.lst1011 MB9527654801010111319c:\db\Psyc\JunkLower+4PrefixWPAFull.lst1 GB8693605301111131727c:\db\Psyc\MaleNamesLower+4PrefixWPA.lst662 MB633379650910111319c:\db\Psyc\md5.lst51 bytes1049-1-1-149c:\db\Psyc\MovieNamesLower+4PrefixWPAFull.lst161 MB1319800701112131620c:\db\ripe\ripe.lst5 GB1434106040373644828662

...

Рейтинг:

0 / 0

10.09.2017, 13:28

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518776

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Придумал как использовать разрешенное кол-во памяти. Сейчас переделаю, будет столько проходов, сколько память позволит.

...

Рейтинг:

0 / 0

10.09.2017, 15:02

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518826

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Вот может пригодится.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

int64_t getFreeMemory() {
     #ifdef WIN32
          MEMORYSTATUSEX statex;
          statex.dwLength = sizeof (statex);
          GlobalMemoryStatusEx(&statex);
          return statex.ullAvailPhys;
     #else
     ....

...

Рейтинг:

0 / 0

10.09.2017, 17:56

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518827

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TЕсть такое: на ripe.db в x64 пик 857 Мб, а для x86 - 747 Мб. Если вычесть биткарту 512 Мб, то имеем 345/235 или в 1.47 раза больше памяти под x64.
Еще волнует такой момент. А сколько битиков в обоих биткартах включено?

...

Рейтинг:

0 / 0

10.09.2017, 18:00

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518842

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Закоммитил. Третий параметр сколько можно использовать памяти в Мб, по умолчанию поставил 1.5 Гб. Минимум 1 Гб.

...

Рейтинг:

0 / 0

10.09.2017, 18:45

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518848

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima TЕсть такое: на ripe.db в x64 пик 857 Мб, а для x86 - 747 Мб. Если вычесть биткарту 512 Мб, то имеем 345/235 или в 1.47 раза больше памяти под x64.
Еще волнует такой момент. А сколько битиков в обоих биткартах включено?
26`424`906 битика. То что ты процитировал, там одна биткарта была. Для повторов map. В последней версии вернул вторую обратно.
На ripe.db в итоге биткарта целиком вся в памяти оказывается.

...

Рейтинг:

0 / 0

10.09.2017, 18:51

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518860

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

26 424 906 битиков на 4 млрд? Это получается.. 0,006. Физический вакуум. Это что мы так слабенько
используем пространство? Мдя...

...

Рейтинг:

0 / 0

10.09.2017, 19:50

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518866

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

mayton26 424 906 битиков на 4 млрд? Это получается.. 0,006. Физический вакуум. Это что мы так слабенько
используем пространство? Мдя...
Смотря как считать: в виде std::set<std::string> результат занимает 4 Гб, т.е. в 8 раз больше чем биткарта.

С другой стороны там всего 26`511`418 уникальных записей, т.е. почти все (99.67%) отловлены биткартой в первый проход. Потенциал биткарты не раскрыт этим маленьким файлом. Файлик с паспортами утерянными устанавливает 104`699`918 бит из 105`629`005 уникальных строк и проверяется в один проход. Тут заполняемость похуже 98.8%. Прогони свой файл на 1.2 млрд. записей, там коллизий много должно быть если все строки уникальные.

...

Рейтинг:

0 / 0

10.09.2017, 20:10

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518867

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TЗакоммитил. Третий параметр сколько можно использовать памяти в Мб, по умолчанию поставил 1.5 Гб. Минимум 1 Гб.
Хм... после того как ты добавил win-функции я перестал успешно собирать твой исходник.

Код: plaintext

1.
2.

c:\tmp\ccwjaIPM.o:uniq-crc.cpp:(.text+0x347): undefined reference to `GetProcessMemoryInfo'
collect2.exe: error: ld returned 1 exit status

gcc version 6.3.0 (x86_64-win32-seh-rev1, Built by MinGW-W64 project)

...

Рейтинг:

0 / 0

10.09.2017, 20:10

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518870

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TС другой стороны там всего 26`511`418 уникальных записей, т.е. почти все (99.67%) отловлены биткартой в первый проход. Потенциал биткарты не раскрыт этим маленьким файлом. Файлик с паспортами утерянными устанавливает 104`699`918 бит из 105`629`005 уникальных строк и проверяется в один проход. Тут заполняемость похуже 98.8%. Прогони свой файл на 1.2 млрд. записей, там коллизий много должно быть если все строки уникальные.
Надо попробовать BloomFilter. Он более эффективно заполнит эту пустоту. И на размере сэкономить можно.

...

Рейтинг:

0 / 0

10.09.2017, 20:15

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518873

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima TЗакоммитил. Третий параметр сколько можно использовать памяти в Мб, по умолчанию поставил 1.5 Гб. Минимум 1 Гб.
Хм... после того как ты добавил win-функции я перестал успешно собирать твой исходник.

Код: plaintext

1.
2.

c:\tmp\ccwjaIPM.o:uniq-crc.cpp:(.text+0x347): undefined reference to `GetProcessMemoryInfo'
collect2.exe: error: ld returned 1 exit status

gcc version 6.3.0 (x86_64-win32-seh-rev1, Built by MinGW-W64 project)
Я не знаю как с твоим MinGW-W64 бороться. У меня собирается в MSVC и в debian. Там так написано

Код: plaintext

1.
2.
3.

#if defined(_WIN32) || defined(_WIN64)
...
if(GetProcessMemoryInfo(...

Залил скомпилированный uniq-crc.exe в zip-архиве. Пароль 12345

...

Рейтинг:

0 / 0

10.09.2017, 20:21

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518878

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonНадо попробовать BloomFilter. Он более эффективно заполнит эту пустоту. И на размере сэкономить можно.
Это он и есть. Биткарта + хэш дают два ответа:
1. Точно уникально.
2. Возможно уникально или повтор.

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

...

Рейтинг:

0 / 0

10.09.2017, 20:30

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518880

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TmaytonНадо попробовать BloomFilter. Он более эффективно заполнит эту пустоту. И на размере сэкономить можно.
Это он и есть. Биткарта + хэш дают два ответа:
1. Точно уникально.
2. Возможно уникально или повтор.

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

...

Рейтинг:

0 / 0

10.09.2017, 20:32

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518884

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Затестил ripe.db с биткартой 128 Мб, т.е. хэш 31 бит: отфильтровалось уникальных 26`340`849 или 99.3%. Вывод: CRC32 как хэш не надо использовать.
Но биткарту уменьшать смысла тоже нет, думаю наоборот надо увеличить, т.к. для огромных файлов, типа твоего 1.2 млрд. записей, чем больше тем лучше, т.к. коллизий будет меньше и перепроверять в итоге меньше.
1.2 млрд. уникальных записей это 25% моей биткарты, очень много.

...

Рейтинг:

0 / 0

10.09.2017, 20:43

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518885

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Dima TЗалил скомпилированный uniq-crc.exe в zip-архиве. Пароль 12345
Он у тебя запустился?

...

Рейтинг:

0 / 0

10.09.2017, 20:52

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518887

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonНет. У него метод похитрее. Для ключа активируются несколько бит. Хотя в общих чертах это да... биткарта.
Почитал вики, действительно хитрее: он пустоты предлагает более эффективно использовать генеря несколько хэшей и если хоть один из них новый, то элемент уникальный. Завтра допилю :)

...

Рейтинг:

0 / 0

10.09.2017, 21:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518888

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TDima TЗалил скомпилированный uniq-crc.exe в zip-архиве. Пароль 12345
Он у тебя запустился?
Да. Бинарник работает отлично.

...

Рейтинг:

0 / 0

10.09.2017, 21:03

| Ответить | Цитировать | Написать

Тяпничная унификация

#39518964

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonХм... после того как ты добавил win-функции я перестал успешно собирать твой исходник.

Код: plaintext

1.
2.

c:\tmp\ccwjaIPM.o:uniq-crc.cpp:(.text+0x347): undefined reference to `GetProcessMemoryInfo'
collect2.exe: error: ld returned 1 exit status

...

Рейтинг:

0 / 0

11.09.2017, 07:14

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519416

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonНадо попробовать BloomFilter. Он более эффективно заполнит эту пустоту. И на размере сэкономить можно.
С полноценным фильтром Блума ерунда получается.
ВикиОбычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом
В нашем случае непонятно как это использовать.

Например
Строкаhash1()hash2()Результатqqq12Уникальноwww34Уникальноeee23Возможно повтор
Как дальше определить что "eee" уникальная строка? Только сравнив со всеми уникальными ранее найденными, т.е. их все в память загрузить, а они туда не влазят.

...

Рейтинг:

0 / 0

11.09.2017, 18:11

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519423

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Dima T,

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

...

Рейтинг:

0 / 0

11.09.2017, 18:23

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519457

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SiemarglDima T,

Нет смысла брать два разных хэша, если можно сразу взять один суммарной длины. Я так понимаю, что математически - хуже во много мульенов раз (что то типа разницы между суммой величин и произведением).
Фильтр Блума основан на N хэшей, он пустоты заполняет в маленькой биткарте: если хоть один хэш не подошел, то можно ответить что искомого значения точно нет в множестве, не проверяя множество.

Там экономия на размере биткарты: или два хэша по 32 бита в одной биткарте на 32 бита, или вместе в одной на 64 бита.

...

Рейтинг:

0 / 0

11.09.2017, 19:13

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519501

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TmaytonХм... после того как ты добавил win-функции я перестал успешно собирать твой исходник.

Код: plaintext

1.
2.

c:\tmp\ccwjaIPM.o:uniq-crc.cpp:(.text+0x347): undefined reference to `GetProcessMemoryInfo'
collect2.exe: error: ld returned 1 exit status

gcc version 6.3.0 (x86_64-win32-seh-rev1, Built by MinGW-W64 project)
Посмотри psapi.h есть там объявление GetProcessMemoryInfo() ?
Может он в какие-нибудь #if обернут, тогда может какой-то #define надо объявить.
Привет. Только дополз до ноутбука. Завал по проекту. ОК. Посмотрю.
Надо студию поставить. Последний раз я качал 2005 году Express Ed.
Что щас там чо и как у большого брата?

...

Рейтинг:

0 / 0

11.09.2017, 21:48

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519511

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TmaytonНадо попробовать BloomFilter. Он более эффективно заполнит эту пустоту. И на размере сэкономить можно.
С полноценным фильтром Блума ерунда получается.
ВикиОбычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом
В нашем случае непонятно как это использовать.

Я кажется понял твое негодование. Ты хочешь решить задачу в 1 проход? Мне кажется
какие-бы алгоритмы и структуры мы не применяли но встает такая аксиома.

Если не сохранять ключи на 1-м проходе то второй проход будет как минимум
необходим для отчота

По поводу Блума (BF) чорт бы его подрал. Эта структура - вспомогательная. Ее обычно
ставят в каскад к основной структуре. Например к диску. Быстро отбивать "дурные"
негативные реквесты на isExist(string key). Я бы - вставил ее в цепочку с LRU (на 100 ключей хотяб)
и можно читать основной файл. Примерно как в алгоритме Зямы. (Насколько я его понял).

По поводу экономии места. Я щас навскидку не помню. Чуть позже я опубликую
блог своей борьбы со Слоном. Тоесть с Хадупом. Там я разбирал работу встроенного
BF в слона и был очень разочарован удобством API. Специально потом лазил в вики
чтоб понять какие там нужны аргументы к коснтруктору чтоб контролировать ситуацию
полностью. Вобщем слушай телегу.

BF может работать на любом объеме биткарт. Его можно впихнуть в 256Мб и в 128 и в 64.
Он очень толерантен к размеру. В этом его главное преимущество. За размер мы заплатим
свою цену. Это false-positive срабатывания которые мы всё равно решаем за счет второго
прохода. Формулу достоверности в % я предоставить не могу но у меня есть свой численный
метод который даёт табличку аспектов таких как
- размер биткарты
- количество ключей которые мы хотим положить
- % false-positive срабатываний (обычно берут 3-5%)
- количество хеш-функций.
Все 4 аспекта связаны формулой. Если двигаешь что-то одно - то меняется другое. Это уравнение
с 3 неизвестными долго вгоняло меня в ступор пока я не решил просто зафиксировать 2 из
трех неизвестных и уравнение решилось.

Что произойдет если BF заполнять количеством ключей гораздо больше чем было расчитано?
Ничего страшного. Он так-же будет работать. Тянется как резиновый. Вот только свойства
false-positive у него ухудшатся.

Экпериментально я установил что BF заполненный на 100% оценочным числом ключей
содежит в себе одинаковое количество включенных и выключенных бит. Тоесть он
шумит битами в соотношении 50%. Красиво шумит. Криптографически красиво.

Вот почему меня вдруг заинтересовало (по топику выше) насколько плотно мы используем
карту CRC-32. И я вспомнил свою борьбу со Слоном.

Какая польза от BF в наших разработках? Он сэкономит место для других полезных структур данных
в оперативке. Вот пожалуй всё.

...

Рейтинг:

0 / 0

11.09.2017, 22:14

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519512

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Siemargl, привет бро. Пофикси plz то что у тебя закомментарено.

...

Рейтинг:

0 / 0

11.09.2017, 22:16

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519562

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

maytonSiemargl, привет бро. Пофикси plz то что у тебя закомментарено.В связи с отсутствием валидных входных данных, моя гениальная программа не требует фиксов.

Собственно, я об этом уже писал. 20783791

Кстати см, что модеры похерили ваши хакерские БД

...

Рейтинг:

0 / 0

11.09.2017, 23:22

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519563

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Это я удалил. Не compliance по отношению к правилам
форума. Но в личку могу дать ссылки.

...

Рейтинг:

0 / 0

11.09.2017, 23:25

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519613

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonНадо студию поставить. Последний раз я качал 2005 году Express Ed.
Что щас там чо и как у большого брата?
У меня стоит бесплатная Visual Studio Community 2015 .
Есть 2017 , ее не пробовал ставить.

В целом подтянулись, стандарты С++11 и 14 поддерживает. Но в С отсебятина так и осталась.

...

Рейтинг:

0 / 0

12.09.2017, 07:04

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519628

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonЯ кажется понял твое негодование. Ты хочешь решить задачу в 1 проход? Мне кажется
какие-бы алгоритмы и структуры мы не применяли но встает такая аксиома.

Если не сохранять ключи на 1-м проходе то второй проход будет как минимум
необходим для отчота
В 1-й проход я получаю 100% ключей с уникальным хэшем и по каким из них были повторы или коллизии. Или 100% уникальных хэшей. Дальше мне остается проверять только те ключи, по которым были повторы хэша. И проверять только в подмножестве уже найденных, а не во всех найденных. Т.е. хэш это вспомогательный ID для поиска того что надо допроверять. После первого прохода биткарта в найденными уникальными удаляется из памяти. В общем на первой биткарте нельзя использовать Блума.

Пока писал, понял: на второй биткарте (где хранятся хэши повторов) можно использовать Блума, т.к. не смертельно если на втором проходе я перепроверю 3-5% ранее найденных уникальных. Зато можно значительно уменьшить биткарту с 512 Мб до 128/64 Мб, а освободившуюся память более эффективно использовать.

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

PS В камментах описал алгоритм, но забыл поправить описаловку после изменения. Поправлю.

...

Рейтинг:

0 / 0

12.09.2017, 08:01

| Ответить | Цитировать | Написать

Тяпничная унификация

#39519879

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonЭто я удалил. Не compliance по отношению к правилам
форума. Но в личку могу дать ссылки.
Я тот файлик глянул на предмет что за длинные строки там

Начало самой длинной (422894 байта)

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.

$HEX[706d6a5883807daadee0ddf3f3f6f4fef7f8f8fffcfdfdfffafafafff8f7f6fee6e4e2f383807daa706d6a580000000
906060602ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00fefefe01fbfbfb04f7f7f708f6f6f609ededed12bec0be58b5bab7cbffffffffced
dd3ffc3d5cbffd8e2ddffe8ebeafff0ededffecdcd7fff1e1dbffffffffffbdc2becec0c3c159f6f6f609ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff002b2b2b010101010643413f1a73706d5f7e7b778d827f7ca585827eb3827f7ca57e7b778d73706d5
f43413f1a010101062b2b2b01ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f70
0f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f
7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f70
0f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f
7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f70
0f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
02b2b2b010101010643413f1a73706d5f7e7b778d827f7ca585827eb3827f7ca57e7b778d73706d5f43413f1a010101062b2
b2b01ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
...

ИМХО Троян какой-то текстовый. Что бы это могло означать?

...

Рейтинг:

0 / 0

12.09.2017, 14:09

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520072

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Понятия не имею что там.

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

Был вариант сгенерить их. Но этот вариант был:
- не убедителен
- не имел хорошей энтропии

И я решил просто искать в открытых источниках справочники и выгрузки БД

...

Рейтинг:

0 / 0

12.09.2017, 19:27

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520078

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Список аннулированных паспортов Легально и много (105 млн. записей).

Если покопаться в открытых данных , то там много полезного для наших тестов найдется.

...

Рейтинг:

0 / 0

12.09.2017, 19:48

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520106

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TmaytonХм... после того как ты добавил win-функции я перестал успешно собирать твой исходник.

Код: plaintext

1.
2.

c:\tmp\ccwjaIPM.o:uniq-crc.cpp:(.text+0x347): undefined reference to `GetProcessMemoryInfo'
collect2.exe: error: ld returned 1 exit status

Код: plaintext

  WINBOOL WINAPI GetProcessMemoryInfo(HANDLE Process,PPROCESS_MEMORY_COUNTERS ppsmemCounters,DWORD cb);

...

Рейтинг:

0 / 0

12.09.2017, 20:56

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520114

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T Список аннулированных паспортов Легально и много (105 млн. записей).

Если покопаться в открытых данных , то там много полезного для наших тестов найдется.
Спасибо. Качнул паспорта. Добавлю в тестовые выборки.

...

Рейтинг:

0 / 0

12.09.2017, 21:36

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520119

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

NameFile LengthRowsDamaged RowsCardinalityAvg RLMedian RL75-perc RL97-perc RLMax RLc:\db\1.2billion\1.2billion.lst13 GB120677026301010121863c:\db\anti-spam\dom-bl-base.lst3 MB22800601616202867c:\db\anti-spam\dom-bl.lst13 KB77201616192733c:\db\anti-spam\from-bl.lst4 MB16811602828314071c:\db\CDDB\edit.lst4 GB438916800109112117118119c:\db\CDDB\edit_area.lst13 MB92867701314141415c:\db\CDDB\edit_artist.lst885 MB5370593701617171718c:\db\CDDB\edit_data.lst27 GB438906351045656428586298765502c:\db\CDDB\edit_event.lst3 MB23562201313131314c:\db\CDDB\edit_instrument.lst15 MB130516001111111112c:\db\CDDB\edit_label.lst32 MB210772801515161617c:\db\CDDB\edit_note.lst3 GB26856966215411417449051183c:\db\CDDB\edit_note_recipient.lst32 MB232297401314141516c:\db\CDDB\edit_place.lst11 MB81403301313131314c:\db\CDDB\edit_recording.lst906 MB5590619101615161617c:\db\CDDB\edit_release.lst365 MB2361387101515151516c:\db\CDDB\edit_release_group.lst256 MB1634517501515151516c:\db\CDDB\edit_series.lst1 MB11991801212121213c:\db\CDDB\edit_url.lst82 MB517968501515151516c:\db\CDDB\edit_work.lst109 MB648825601616161617c:\db\HashKiller\hashkiller-dict.lst1 GB8840540921129124155224c:\db\Linked-In\SHA1.lst240 MB6143150040-1-1-140c:\db\Psyc\AllMain_aA4_eE3_gG6_lL1_oO0__sS5_tT7.lst5 GB549682416099101431c:\db\Psyc\CommonPassword_aA4_eE3_bB8_gG6_lL1_oO0_zZ2_sS5_tT7.lst3 GB39085521308881115c:\db\Psyc\ComputerJargonLower+4PrefixWPA.lst1 GB8954436901212141935c:\db\Psyc\FamilyNamesLower+4PrefixWPA.lst1 GB13070572801011121521c:\db\Psyc\FemaleNamesLower+4PrefixWPA.lst1011 MB9527654801010111319c:\db\Psyc\JunkLower+4PrefixWPAFull.lst1 GB8693605301111131727c:\db\Psyc\MaleNamesLower+4PrefixWPA.lst662 MB633379650910111319c:\db\Psyc\MovieNamesLower+4PrefixWPAFull.lst161 MB1319800701112131620c:\db\ripe\ripe.lst5 GB1434106040373644828662c:\db\passports\list_of_expired_passports.csv1 GB10948187401011111125

...

Рейтинг:

0 / 0

12.09.2017, 21:57

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520198

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima Tпропущено...

Посмотри psapi.h есть там объявление GetProcessMemoryInfo() ?
Может он в какие-нибудь #if обернут, тогда может какой-то #define надо объявить.
Посмотрел. Норм. Есть. Не обернут ни во что.

Код: plaintext

  WINBOOL WINAPI GetProcessMemoryInfo(HANDLE Process,PPROCESS_MEMORY_COUNTERS ppsmemCounters,DWORD cb);

Тогда непонятно что ему не нравится.

На всякий случай залил свежий exe в zip, пароль 12345.

...

Рейтинг:

0 / 0

13.09.2017, 08:00

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520691

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

Дайте данных )

Собрал однопроходный (держим все строки в памяти) черновик.
Потоптал пенопласт - проверил, работает ли идея растасовки строк и быстрого отсева копий.
Вроде получилось, теперь есть идеи распараллелить...

P.S.
"Девять миллиардов имён Бога"

...

Рейтинг:

0 / 0

13.09.2017, 19:05

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520695

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Bred eFeMДайте данных )
Качай Список аннулированных паспортов .

Для ужесточения сделай

Код: plaintext

copy passport.csv + passport.csv crash-test.csv

...

Рейтинг:

0 / 0

13.09.2017, 19:21

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520710

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Bred eFeMВроде получилось, теперь есть идеи распараллелить...
Откомпилируй в x86 для начала. Если отработает - параллель.

...

Рейтинг:

0 / 0

13.09.2017, 19:47

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520725

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Во всех остальных случаях (рабочая станция + 1 физический диск) - не заморачивайтесь!
Не тратьте время на ерунду! У вас узким местом будет канал дисковой подсистемы
и ничего вы там не распараллелите.

Подумайте над алгоритмом.

...

Рейтинг:

0 / 0

13.09.2017, 20:30

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520731

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Bred eFeMДайте данных )

Собрал однопроходный (держим все строки в памяти) черновик.
Потоптал пенопласт - проверил, работает ли идея растасовки строк и быстрого отсева копий.
Вроде получилось, теперь есть идеи распараллелить...

P.S.
"Девять миллиардов имён Бога"
Ты брутфорсишь наш первый вариант который Naive Hash-table(NHT) ?
Посмотри исходник Димы под названием uniq-mem.

Еще. Если у тебя есть оригинальная идея. Мы имеем общий репозитарий. Регайся в sourceforge.

По поводу имен Бога. Это дежа-вю... Тяпничный pwdgen

...

Рейтинг:

0 / 0

13.09.2017, 20:39

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520791

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

Dima Tкачай список- ужо, это я из-за него и психанул - как оказалось там 7 раз одно и то же в кучу слито.
- ну и строки одинаковой длины - хороший тест.
Откомпилируй в x86 для началапопробую, но особо смысла не вижу - по использованию памяти должно работать: динамично до 512М для строк не более 4 символов + динамично до 64М под структуру + рабочих 128М + rtl/over ~ 64M
+ 8-12 байт на каждую строку = в теории до 100М строк можно побороть.

maytonТы брутфорсишь наш первый вариант который Naive Hash-table(NHT) ?- не, не знаю, начальную идею уже озвучивал - разбивка по длинам, дальше по 8-ми битам хеша - потом внутри этих групп по 24-битам отсеивание.
- теперь уже как бы есть для себя эталон - можно попробовать насколько не точным будет использовать второй хеш, а не полное сравнение, для перепроверки копия/коллизия.

Регайся в sourceforgeвроде была учётка, но я пока FPC/Delphi, если пройду по тестам засуржу в С ))

ничего вы там не распараллелите. Подумайте над алгоритмом.- когда ос читает диск/пишет данные в твой буфер, а ты в это время читаешь предыдущий буфер/наполняешь структуру - можно и сэкономить несколько секунд )
- да и финальная стадия очень просится в несколько потоков, только для каждого уже нужно будет +128М для 24 битного сита.

...

Рейтинг:

0 / 0

13.09.2017, 23:32

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520836

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Bred eFeMDima Tкачай список- ужо, это я из-за него и психанул - как оказалось там 7 раз одно и то же в кучу слито.
- ну и строки одинаковой длины - хороший тест.
В паспортах нет повторов.
Bred eFeMничего вы там не распараллелите. Подумайте над алгоритмом.- когда ос читает диск/пишет данные в твой буфер, а ты в это время читаешь предыдущий буфер/наполняешь структуру - можно и сэкономить несколько секунд )
- да и финальная стадия очень просится в несколько потоков, только для каждого уже нужно будет +128М для 24 битного сита.
Не совсем так: ОС занимается упреждающим чтением, т.е. пока ты парсишь очередной прочитанный кусок, в это время виндовс готовит тебе следующий.

...

Рейтинг:

0 / 0

14.09.2017, 07:02

| Ответить | Цитировать | Написать

Тяпничная унификация

#39520865

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Bred eFeMвроде была учётка, но я пока FPC/Delphi, если пройду по тестам засуржу в С ))
Ну Окей. Пускай на FPC. Главное чтоб работало быстро.. Ультра-быстро.

- когда ос читает диск/пишет данные в твой буфер, а ты в это время читаешь предыдущий буфер/наполняешь структуру - можно и сэкономить несколько секунд )
- да и финальная стадия очень просится в несколько потоков, только для каждого уже нужно будет +128М для 24 битного сита.
Да Async I/O мы попробуем. Но это техника применительна ко всем алгоритмам которые мы делаем.
По сути это просто технический trick. Мы его обязательно учтем. Но КМК самое главное - это понять
наши входные данные и выбрать подход.

...

Рейтинг:

0 / 0

14.09.2017, 08:42

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521075

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonДрузья. По поводу параллелизма. Не спешите. Данный алгоритм - последовательный
по своей природе. Если у вас дисковое хранилище на базе RAID-0 то пробуйте. Но
нам будет очень сложно обобщить ваши результаты на обычные конфигурации.

Во всех остальных случаях (рабочая станция + 1 физический диск) - не заморачивайтесь!
Не тратьте время на ерунду! У вас узким местом будет канал дисковой подсистемы
и ничего вы там не распараллелите.
Ты плохо думаешь о рабочих станциях: обычный бюджетный SSD на SATA3 выдает 400-500 Мб/сек. последовательного чтения. Наш случай.
Мой i7 в одно ядро парсит со скоростью 100-240 Мб/сек. Чем короче строки, тем ниже скорость.

Цифры говорят что есть чем занять простаивающие ядра.

Другой вопрос как сравнивать производительность многопоточного и однопоточного алгоритмов ?
ИМХО это разные весовые категории, поэтому однопоточные надо сравнивать с однопоточными.

...

Рейтинг:

0 / 0

14.09.2017, 13:18

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521083

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T,

Смотрите. Я готов добавить ещё одну графу мультипоточности в наши будущие бенчмарки..

Но будем ли мы все алгоритмы укомплектовывать этой опцией?

...

Рейтинг:

0 / 0

14.09.2017, 13:29

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521106

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima T,

Смотрите. Я готов добавить ещё одну графу мультипоточности в наши будущие бенчмарки..

Но будем ли мы все алгоритмы укомплектовывать этой опцией?
Сомневаюсь что все будут иметь многопоточный вариант.
Думаю для тестов основным надо считать однопоточный вариант. Его и мерить.

Если кто предложит дополнительно многопоточный - можно тоже померить. Доп.графы не надо, достаточно просто пометки MT в названии алгоритма.

...

Рейтинг:

0 / 0

14.09.2017, 13:55

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521391

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Возникли мысли по поводу расхода памяти. Насколько мы рационально используем
пространство?

Я вспомнил свои эксперименты в студенчестве.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

struct OptionalPointer {
    union
    {
        char *s;
        char c[32];
    };
};

struct Node {
    uint32_t mask;
    OptionalPointer *p1;
    OptionalPointer *p2;
    // .....
    OptionalPointer *p32;
};

Я обратил внимание на то что в древовидных структурах наибольший оверхед
занимают листовые вершины. Основное мясо листовых узлов - указатели.
И я пытался переиспользовать пространство указателя. Для коротких строк
(меньше 31 символов) я переиспользовал место указателя.

Я также заметил что у нас есть файлы типа passport. И у них весьма резкая
гистограмма длины. 11 символов на каждый элемент. Это можно использовать.
Я не просто так мерял 97-й перцентиль. Эта величина должна помочь в выяснении
закономерностей. Может кто-то и придумает регулярную структуру данных.
Не такую общую как unordered_map.

...

Рейтинг:

0 / 0

14.09.2017, 22:04

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521416

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

Итак, без оптимизаций тайминги на паспортах такие (~3GHz):
(да, там нет повторов - совсем забыл, что отключал инкремент позиции при чтении файла)

- загрузка и заполнение структуры (много реаллоков - буду тюнить) ~40c;
- отсеивание дублей по второму 32 битному хешу ~10c;
- память 2,5GB

много/мало - как у вас? )

Насколько мы рационально используем пространство?да, думаю над своим аллокатором под эту задачу.

...

Рейтинг:

0 / 0

14.09.2017, 23:37

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521419

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Бенчмарки буду гнать на всей коллекций файлов. Не только на паспортах

...

Рейтинг:

0 / 0

14.09.2017, 23:42

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521425

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

mayton, хорошо!, только у мну те что есть, отличаются от табличных )

Код: plaintext

1.
2.
3.
4.

ripe.db (5 462 799 419)
- load: ~55s
- calc: ~8s
- ram:  ~2.5GB
- result:  9701336 / 107196073 / 133709268 / 143410604   (zero / copy / valid / total)

...

Рейтинг:

0 / 0

15.09.2017, 00:16

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521493

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Bred eFeMИтак, без оптимизаций тайминги на паспортах такие (~3GHz):
(да, там нет повторов - совсем забыл, что отключал инкремент позиции при чтении файла)

- загрузка и заполнение структуры (много реаллоков - буду тюнить) ~40c;
- отсеивание дублей по второму 32 битному хешу ~10c;
- память 2,5GB

много/мало - как у вас? )
Для паспортов мне 600 Мб требуется.

Выше обсуждали что в процессе надо контролировать расход памяти, в итоге остановились на опросе ОС занимаемой процессом памяти mem_used.h
Т.к. теоретически может попасться такой файл что съест всю память. Тогда или прога свопиться начнет или ОС перестанет выделять память для твоего процесса, т.е. вылет с исключением std::bad_alloc.

PS У mayton`а есть супер-файлик 20783786

...

Рейтинг:

0 / 0

15.09.2017, 08:08

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521509

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Bred eFeM, ripe.db возможно обновляется. Поэтому данные и будут отличаться. Это норм.

...

Рейтинг:

0 / 0

15.09.2017, 08:43

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521520

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TPS У mayton`а есть супер-файлик 20783786
Кстати я-бы проверил в сколько максимальное количество buckets может работать стандартная
реализация std::*_map.

...

Рейтинг:

0 / 0

15.09.2017, 09:01

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521526

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima TPS У mayton`а есть супер-файлик 20783786
Кстати я-бы проверил в сколько максимальное количество buckets может работать стандартная
реализация std::*_map.
Нам хватит

Код: plaintext

1.
2.
3.

max_size = 576460752303423487
max_bucket_count = 1152921504606846975
max_load_factor = 1

http://www.cplusplus.com/reference/unordered_map/unordered_map/max_size/

...

Рейтинг:

0 / 0

15.09.2017, 09:12

| Ответить | Цитировать | Написать

Тяпничная унификация

#39521748

Bred eFeM

Участник

Сообщения: 580

Рейтинг: 0 / 0

есть супер-файлик 20783786 щёлоч в профиле, спасибо

...

Рейтинг:

0 / 0

15.09.2017, 12:34

| Ответить | Цитировать | Написать

Тяпничная унификация

#39522079

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T

Код: plaintext

max_bucket_count = 1152921504606846975

Отлично.

...

Рейтинг:

0 / 0

15.09.2017, 21:17

| Ответить | Цитировать | Написать

Тяпничная унификация

#39522092

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Несколько мыслей. По поводу хеш-таблиц. Есть у меня мнение что они не оптимальны
для нашей задачи. Например, взять паспорта. У них - ограниченная длина. 11 символов.
Мы для решения в Naive Hash-Table аллоцируем 1 объект std::string. И ясен пень - это не на стеке.
Это в динамической памяти процесса. Сколько там будет аллоцировано? ХЗ. Platform dependent.
Я очень верю в С++ и его способности хорошо "закатывать" шаблонизированный код в
эффективный бинарный. Но что можно сказать об аллокации памяти?

Может мы укрупним единицу аллокации? Пускай там лежит пара строк.

...

Рейтинг:

0 / 0

15.09.2017, 21:40

| Ответить | Цитировать | Написать

Тяпничная унификация

#39522095

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

По поводу тех справочников и выгрузок где есть ярко выраженный префиксный порядок.
Ох... я чувствую что иду по неверному пути Паниковского Базиста. Но я думаю
о том чтобы прогрузить их в RadixTree/RTrie, и прочик Ахо-Корасики.

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

Кстати идею с префиксом можно расширить и на хеш-таблицы.

...

Рейтинг:

0 / 0

15.09.2017, 21:44

| Ответить | Цитировать | Написать

Тяпничная унификация

#39522462

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonМожет мы укрупним единицу аллокации? Пускай там лежит пара строк.
ИМХО Так мы до самодельного архиватора дойдем :)

Нашел еще одно тормозное место: fwrite(). Заменил на блочную запись ( block_write.h ), стало чуть быстрее: паспорта были 18 сек. стали 14 сек.

Пытаюсь многопоточный вариант сделать на акторах. Обнаружилась проблема: при чтении быстрее обработки память занимает очередь из прочитанного, но необработанного. Тупо все в очереди ставить - не вариант.
Параллелить можно не только чтение, так тут не особо запараллелишь. Запараллелил расчет хэшей, т.к. без разницы в каком порядке прочитанные блоки на последующую обработку попадут.

...

Рейтинг:

0 / 0

17.09.2017, 19:13

| Ответить | Цитировать | Написать

Тяпничная унификация

#39523619

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Dima TmaytonМожет мы укрупним единицу аллокации? Пускай там лежит пара строк.
ИМХО Так мы до самодельного архиватора дойдем :)
Размышляю над архиватором, возможно оно может пригодится для получения хэша: строим словарь, общий для всего множества, и далее начало пожатой строки используем как хэш. Например паспорт скорее всего целиком в 32 бита поместится после сжатия: 105 млн. строк в 344 Мб, т.е. ~3.3 байта на строку. С ripe.db статистика похуже: 180 Мб (пожал только уникальные) для 30 млн. строк, т.е. 6 байт на строку.
Кроме того можно сжатыми строками оперировать, например во временные файлы их писать. Текст жмется в 4-6 раз.

Правда тут есть большой минус в том что первый проход надо будет делать для построения словаря.

...

Рейтинг:

0 / 0

20.09.2017, 10:02

| Ответить | Цитировать | Написать

Тяпничная унификация

#39523993

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TDima Tпропущено...

ИМХО Так мы до самодельного архиватора дойдем :)
Размышляю над архиватором, возможно оно может пригодится для получения хэша: строим словарь, общий для всего множества, и далее начало пожатой строки используем как хэш. Например паспорт скорее всего целиком в 32 бита поместится после сжатия: 105 млн. строк в 344 Мб, т.е. ~3.3 байта на строку. С ripe.db статистика похуже: 180 Мб (пожал только уникальные) для 30 млн. строк, т.е. 6 байт на строку.
Кроме того можно сжатыми строками оперировать, например во временные файлы их писать. Текст жмется в 4-6 раз.

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

Паспорта конечно можно перевести в целые числа. Но как такой метод потом включать в общий поток тестирования? Непонятно.

Или будет отдельно бранч узких алгоритмов.

...

Рейтинг:

0 / 0

20.09.2017, 19:16

| Ответить | Цитировать | Написать

Тяпничная унификация

#39525122

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Написал многопоточный вариант, правда не полноценный, а только однопроходную часть, алгоритм тот же, но с акторами :) Сделал чтение блоками 256 Kб, запараллелил разбор блока на строки и расчет хэшей строк, остальное как было.
Исходники завтра покажу, после причесывания.

Результаты такие (оба варианта работали в одинаковом режиме, т.е. в один проход чтения файла)

I7-6700K, DDR4, 4 ядра без HT, 4 потока:
ФайлОднопоточноМногопоточнопаспорта (1.2 Гб)12.9 сек.4.1 сек.ripe.db (5.2 Гб)24.4 сек.7.6 сек.
I7-3770K, DDR3, 4 ядра c HT, 8 потоков
ФайлОднопоточноМногопоточнопаспорта (1.2 Гб) 15.9 сек.5.6 сек.ripe.db (5.2 Гб) 27.9 сек.9.2 сек.

PS Т.к. памяти у меня много и все там закэшировано, то максимальное чтение удалось выжать 2+ Гб/сек. Это просто чтение, разбор на строки, подсчет количества строк и контрольной суммы XOR(хэш строк). Полноценная работа 500 Мб/сек максимум, т.е IO ни при чем, есть куда тюнинговать алгоритм.

PPS Амдал не дает больше чем в 3 раза ускориться :(

...

Рейтинг:

0 / 0

22.09.2017, 19:37

| Ответить | Цитировать | Написать

Тяпничная унификация

#39525163

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, ого круть.

Только я-бы протестировал "холодный" старт. Тоесть условия при которых
файл еще ни разу не читался.

...

Рейтинг:

0 / 0

22.09.2017, 21:44

| Ответить | Цитировать | Написать

Тяпничная унификация

#39525199

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Холодный старт. Перезагрузка перед каждым замером.

I7-3770K, DDR3, 4 ядра c HT, 8 потоков, SSD SATA3 (SanDisk SDSSDHII120G)
ФайлОднопоточноМногопоточноПодсчет строкпаспорта (1.2 Гб) 17.7 сек. 6.1 сек.3.4 сек.ripe.db (5.2 Гб) 29.5 сек. 18.3 сек.15.0 сек.
Третья колонка: просто чтение, разбор на строки, подсчет количества строк и контрольной суммы XOR(хэш строк).

...

Рейтинг:

0 / 0

23.09.2017, 07:28

| Ответить | Цитировать | Написать

Тяпничная унификация

#39525211

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Залил исходник к себе в акторы uniq.cpp , как еще один пример использования акторов.

Дублировать в местную репку? Он не полностью дублирует однопоточный вариант, не стал делать контроль за памятью и переключение на "план Б" с несколькими проходами когда памяти не хватает.

...

Рейтинг:

0 / 0

23.09.2017, 09:28

| Ответить | Цитировать | Написать

Тяпничная унификация

#39525223

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Давай зальем. Будет больше направлений развития.

...

Рейтинг:

0 / 0

23.09.2017, 10:08

| Ответить | Цитировать | Написать

Тяпничная унификация

#39525298

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Залил uniq-mt.cpp
Бинарники тоже.

...

Рейтинг:

0 / 0

23.09.2017, 16:41

| Ответить | Цитировать | Написать

Тяпничная унификация

#39525373

д0kХ

Гость

maytonВозникли мысли по поводу расхода памяти. Насколько мы рационально используем
пространство?

Я вспомнил свои эксперименты в студенчестве.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

struct OptionalPointer {
    union
    {
        char *s;
        char c[32];
    };
};

struct Node {
    uint32_t mask;
    OptionalPointer *p1;
    OptionalPointer *p2;
    // .....
    OptionalPointer *p32;
};

...

Рейтинг:

0 / 0

24.09.2017, 03:19

| Ответить | Цитировать | Написать

Тяпничная унификация

#39533017

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

UP. Приношу свои извенения за праздность и таймаут. Об этой задаче я не забыл.
Я о ней помню. И думаю.

Мои размышления о сравнении алгоритмов унесли меня в такую даль.... В нейронные
сети. И тому подобное. Вобщем я страдал прокрастинацией и думал о шаге №2 (анализ
результатов) и в уме построил отдельную задачу которая должна брать в анализ
таблицу результатов и методом нечеткой логики выбирать нужный алгоритм автоматически
исходя из признаков самого текстового файла. Где признаки - есть сэмпл. Выборка
первых 100-1000 строк.

И из-за этой прокрастинации а также из-за чортовых шахмат я провтыкал уже почти месяц.

Но я не забыл. Я помню. Ждите....

...

Рейтинг:

0 / 0

08.10.2017, 18:46

| Ответить | Цитировать | Написать

Тяпничная унификация

#39533023

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonВыборка первых 100-1000 строк.
ЕМНИП ты сам выше ругал архиваторы, которые по анализу начала файла делают предположение о содержимом всего файла.
maytonНо я не забыл. Я помню. Ждите....
Не горит :)

PS Тут еще интересная тема была 20817876 тянет на пятничную

...

Рейтинг:

0 / 0

08.10.2017, 18:55

| Ответить | Цитировать | Написать

Тяпничная унификация

#39533068

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Я не ругал архиваторы. Я говорил что их применяют не так.

...

Рейтинг:

0 / 0

08.10.2017, 20:58

| Ответить | Цитировать | Написать

227 сообщений из 227, показаны все 10 страниц

все

Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?all=1&fid=57&tid=2018073]:	0ms
get settings:	9ms
get forum list:	14ms
check forum access:	4ms
check topic access:	4ms
track hit:	162ms
get topic data:	13ms
get forum data:	3ms
get page messages:	180ms
get tp. blocked users:	1ms
others:	13ms

total:	403ms