powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
25 сообщений из 227, страница 3 из 10
Тяпничная унификация
    #39515348
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПопробуй отсортировать 5 гигабайтный ripe.db

Эту https://ftp.ripe.net/ripe/dbase/ ?
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515364
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515374
Bred eFeM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonподнять windows sort утилиту?
Код: plaintext
1.
ps:
gc ripe_da.txt | sort | unique > out.txt

~64GB RAM, 2 часа, - решил больше не ждать, прибил.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515380
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Bred eFeM, перед тем как прибивать надо было заскриншотить счетчики в таск-менеджере.

Особо меня интересовали-бы "Bytes read", "Bytes write". Они - ключевые в оценке эффективности
работы утилиты sort.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515383
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Обновил репку.

Исходник Зямы надо как-то дополить... Хм. Уж слишком кратко.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #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
1.
ZzzOSdqFpKgV/KRAen/gVZPxvCvws4lyj8U7ZWjOzIlCN7WRX35ZxgM6SGablMUO
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515388
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо Док.

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

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

Вот такие пироги.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515452
Фотография 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 - текстовые файлы. Я еще не все посмотрел. Там есть мелкие и есть очень большие.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515462
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Первый проход с биткартой для 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
Тяпничная унификация
    #39515465
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тоже думал об этом. Все эти хеши-хешей, биткарты и прочие Блумы не снимают
с нас обязанности - перепроверить на втором проходе потенциальные дубликаты
(ProbableDuplicates).

Можно попробовать завести счетчики (int32), и считать коллизии по CRC32.
Если коллизий больше 2 - то на втором проходе заводим в обычную мапу.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515467
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотя... зачем я говорю int32. Нам ведь интересен 0,1,2. Тогда вроде как и 2-х битиков хватит.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515470
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonМожно попробовать завести счетчики (int32), и считать коллизии по CRC32.
Если коллизий больше 2 - то на втором проходе заводим в обычную мапу.
Лишнее это, достаточно размер найденного сравнить с размером исходного, если найдено меньше - были или повторы или коллизии, а точно что было без полной перепроверки никак не узнать.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515484
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я поясню почему именно три значения.

Код: plaintext
1.
2.
3.
4.
5.
enum CRC_State {
  NO_KEYS_DETECTED(0), // Не было ни одного ключика в этом классе
  ONE_KEY(1), // Хотя-бы одна строка попала
  MORE_THAN_ONE(2) // Было несколько строк. Требуестя перепроверка.
}
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515505
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Интересная мысль, чтобы с битами не заморачиваться можно две биткарты использовать
Код: 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
Тяпничная унификация
    #39515513
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Два прохода это вообще идеально. Будет 140 сек.

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

Я думаю что все наши алгоритмы будут двухпроходные. Разница в нюансах структур данных. И в вероятности
Поймать out of memory.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515530
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДва прохода это вообще идеально. Будет 140 сек.
Проход с биткартой 44 сек 20771520 , но я там только читал, а тут еще надо будет писать найденные строки с уникальными CRC, затем прочитать их перед вторым проходом.
maytonЯ думаю что все наши алгоритмы будут двухпроходные. Разница в нюансах структур данных. И в вероятности
Поймать out of memory.
Да. По исходным данным двух проходов достаточно.
В крайнем случае если все проверить на втором проходе памяти не хватит - писать что надо проверить во временный файл, а затем допроверить его.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515561
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Тяпничная унификация
    #39515657
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Странно. У меня 40 гиг. Проверь плиз не оборвался ли bzip с хвоста?
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515666
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Две биткарты это ок. Плюсую. Заодно L1/L2 кеши продуем. Дадим краш тест.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515674
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Подозреваю ты ссылку не на тот файл дал, там есть mbdump-edit.tar.bz2 этот 4.2 Гб, качаю этот.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515682
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Возможно так. Я вечером контрольные суммы приложу.
...
Рейтинг: 0 / 0
Тяпничная унификация
    #39515698
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Тяпничная унификация
    #39515791
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Тяпничная унификация
    #39515918
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Добавил второй проход и сохранение результата
Код: 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
Тяпничная унификация
    #39516020
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Коллеги я забыл ваши учетки в sourceforge. Сообщите plz.
...
Рейтинг: 0 / 0
25 сообщений из 227, страница 3 из 10
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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