ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
25 сообщений из 227, страница 2 из 10
  2  все
Тяпничная унификация
    #39514533
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ИзопропилmaytonЭто не главная задача в топике
это подзадача.
хотя дубли можно ликвидировать непосредственно в процессе сортировки.
А чуть раньше?
...
Рейтинг: 0 / 0
02.09.2017, 22:35
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514553
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
mayton,

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

потому я и сторонник кувалды.
...
Рейтинг: 0 / 0
02.09.2017, 22:57
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514564
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А при чем здесь размер строк? Я ввел искусственное ограничение в 64К строки просто
чтобы вынести за рамки топика дискуссии на тему 4G строк и т.п. безсмыслицы.

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

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

Как вам такой реверанс?
...
Рейтинг: 0 / 0
02.09.2017, 23:26
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514583
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
maytonА при чем здесь размер строк?
чем больше длина - тем легче жить
maytonПостановка СОРТИРОВКИ требует интерфейса СРАВНЕНИЯ.
имею возможность на множестве строк задать полный порядок.
веселее было бы если бы мы работали на множестве, где нельзя задать полный порядок
...
Рейтинг: 0 / 0
02.09.2017, 23:59
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514605
Bred eFeM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bred eFeM
Участник
maytonсортировка будет эффективно решать мою задачу?Сортировка чего, строк или их хешей?

1n. Читаем большой файл и пишем, например, в 256 временных [ хеш строки(8b) + её адрес в большом файле(6b) + длину(2b) ]
2a. Читаем все записи из временного в память, сортируем по хешу. (Если мало памяти, повторяем пункт 1n и для временного файла)
2b. Проверяем те, что с одинаковым хешем на коллизию-копию, дубликаты игнорим.
2c. Для каждой из обработанных записей, читаем в большом файле строку по адресу и переписываем в результат.
...
Рейтинг: 0 / 0
03.09.2017, 03:33
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514639
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Bred eFeM, хорошо. Go-go в имплементацию.
...
Рейтинг: 0 / 0
03.09.2017, 08:14
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514641
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В продолжение темы хешей. Несколько мыслей. Ложить в хеш-таблицу хеши - масло
маслянное получается. Если мы берем от произвольной строки 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
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Изопропилmayton,

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

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

Но поскольку их сложно шарить (толстые файлы) то я буду их также искать на публичном доступе.
По крайней мере Ripe.Db я качал свободно.
...
Рейтинг: 0 / 0
03.09.2017, 08:45
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514666
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Посадил репку
https://sourceforge.net/p/sql-ru-uniq/code/HEAD/tree/
...
Рейтинг: 0 / 0
03.09.2017, 11:59
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514754
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonГлавное - сделать уникальность.
В том топике ты отличный алгоритм предложил: первый проход разложить по корзинам/файлам по маске хэша, второй проход каждую корзину привести к уникальности, третий - склеить обратно.
ИМХО лучше не придумаешь. Осталось только подобрать алгоритм деления на корзины чтобы на втором шаге памяти хватало.
...
Рейтинг: 0 / 0
03.09.2017, 20:15
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514768
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, я не отказываюсь от него. Просто хочу оценить какие еще есть возможности. И послушать что скажут мемберы.

Алгоритм сердитого Зямы тоже имеет право на жизнь только его надо описать в части фазы №2
и решить вопрос с коллизиями.
...
Рейтинг: 0 / 0
03.09.2017, 20:50
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514787
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Тестовые данные:
https://ftp.ripe.net/ripe/dbase/ripe.db.gz
...
Рейтинг: 0 / 0
03.09.2017, 22:09
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514804
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
mayton
Еще открытый вопрос. Сколько памяти считать доступной? Тут мне интересно
как в Windows/Linux проверить сколько мы можем аллоцировать без опасения
создать Page Faults?

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

Но линуксоиды не будут терять время ради экономии на спичках,
они используют имеющуюся утилиту sort
...
Рейтинг: 0 / 0
03.09.2017, 23:03
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514812
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0кХmayton Еще открытый вопрос. Сколько памяти считать доступной? Тут мне интересно
как в Windows/Linux проверить сколько мы можем аллоцировать без опасения
создать Page Faults?

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

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

По поводу sort. Мы не ищем легких путей.
...
Рейтинг: 0 / 0
03.09.2017, 23:42
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39514814
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Попробуй отсортировать 5 гигабайтный ripe.db
...
Рейтинг: 0 / 0
04.09.2017, 00:06
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515107
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonПопробуй отсортировать 5 гигабайтный ripe.db

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

Не вопрос, 5 Gb ни о чем :)
Если нужно будет по работе я найду
способ дорисовать на лету( без рестарта ОС ) в сервер 8..16..32..64 Gb RAM.
...
Рейтинг: 0 / 0
04.09.2017, 14:30
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515118
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты бы качнул и глянул в содержимое файла. :)

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

А ты бы ради пенопласта поднимал амазонское облако... Хехе
...
Рейтинг: 0 / 0
04.09.2017, 14:37
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515133
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonТы бы качнул и глянул в содержимое файла. :)

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

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

 
офтопик
У нас есть свое :)
Поменьше амазоновского , но с аналогичным функционалом.
...
Рейтинг: 0 / 0
04.09.2017, 15:01
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515135
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Качнул, заглянул, там полфайла
автор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
1.
Длина введенной записи превышает допустимую.  Задайте большее максимальное значение.
Похоже не нравится перевод строки 0x0A, можно попробовать заменить на 0x0D
...
Рейтинг: 0 / 0
04.09.2017, 15:02
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515201
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
затестил с хэш-таблицей
Код: 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
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Код: 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
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Спасибо дима. Чуть позже я подкину ещё пару файлов. По cddb и по анти-спам спискам.
...
Рейтинг: 0 / 0
04.09.2017, 17:03
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515240
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я щас с планшета пишу. Кто-нить может позаменять переводы строк на нормальные и поднять windows sort утилиту?
...
Рейтинг: 0 / 0
04.09.2017, 17:15
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515258
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
У меня есть мысль про биткарту и я ее думаю

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

PS Siemargl, 20770457 ничего не понял, можно подробнее.
...
Рейтинг: 0 / 0
04.09.2017, 17:34
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39515318
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T,

Это хорошая тема.
...
Рейтинг: 0 / 0
04.09.2017, 19:30
| Ответить | Цитировать | Написать  
25 сообщений из 227, страница 2 из 10
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]