Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
maytonподнять windows sort утилиту? Код: plaintext 1. ~64GB RAM, 2 часа, - решил больше не ждать, прибил. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.09.2017, 22:33 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Bred eFeM, перед тем как прибивать надо было заскриншотить счетчики в таск-менеджере. Особо меня интересовали-бы "Bytes read", "Bytes write". Они - ключевые в оценке эффективности работы утилиты sort. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.09.2017, 22:42 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Обновил репку. Исходник Зямы надо как-то дополить... Хм. Уж слишком кратко. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.09.2017, 22:51 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
$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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.09.2017, 22:58 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Спасибо Док. Пока имеем следующее (на разных конфигурациях но впрочем это пристрелочное). РеализацияВремяИсходник Димы на базе unordered_map70 secsort -u8 min Вот такие пироги. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.09.2017, 23:03 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Ввожу новые тестовые данные. Опенсорцная база 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 - текстовые файлы. Я еще не все посмотрел. Там есть мелкие и есть очень большие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 08:35 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Первый проход с биткартой для 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. Код: plaintext Потерялось ~83 тыс. строк (или 0.3%), CRC32 совпало с другими. Как-то теперь их надо получить. Вариант загнать все в хэш-таблицу не рассматриваем, т.к. целиком загнать можно сразу и без CRC. Как вариант: из уникальных найденных по CRC читаем кусок нужного размера и загоняем в std::map<crc32_t, string>, затем полный прогон исходного файла: если CRC есть в map - сравнение string, если разные, добавление в std::set<string>. И так несколько раз пока найденное по CRC не закончится. В конце содержимое std::set добавить в найденное по CRC. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 08:53 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Я тоже думал об этом. Все эти хеши-хешей, биткарты и прочие Блумы не снимают с нас обязанности - перепроверить на втором проходе потенциальные дубликаты (ProbableDuplicates). Можно попробовать завести счетчики (int32), и считать коллизии по CRC32. Если коллизий больше 2 - то на втором проходе заводим в обычную мапу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 08:57 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Хотя... зачем я говорю int32. Нам ведь интересен 0,1,2. Тогда вроде как и 2-х битиков хватит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 09:00 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
maytonМожно попробовать завести счетчики (int32), и считать коллизии по CRC32. Если коллизий больше 2 - то на втором проходе заводим в обычную мапу. Лишнее это, достаточно размер найденного сравнить с размером исходного, если найдено меньше - были или повторы или коллизии, а точно что было без полной перепроверки никак не узнать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 09:03 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Я поясню почему именно три значения. Код: plaintext 1. 2. 3. 4. 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 09:14 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Интересная мысль, чтобы с битами не заморачиваться можно две биткарты использовать Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. тогда на втором проходе из найденных по CRC брать на перепроверку только те, что есть в dbl[]. Посчитал, получилось что надо перепроверить 3.4 млн. CRC из 26.4 млн., почти в 8 раз меньше проверять. ripe.db в два прохода обработается. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 09:52 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Два прохода это вообще идеально. Будет 140 сек. Док сортировал ещё дольше. И не потому что дисковая подсистема слабая. Там все в поряде. Просто такова она Есть внешняя сортировка. Я думаю что все наши алгоритмы будут двухпроходные. Разница в нюансах структур данных. И в вероятности Поймать out of memory. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 10:03 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
maytonДва прохода это вообще идеально. Будет 140 сек. Проход с биткартой 44 сек 20771520 , но я там только читал, а тут еще надо будет писать найденные строки с уникальными CRC, затем прочитать их перед вторым проходом. maytonЯ думаю что все наши алгоритмы будут двухпроходные. Разница в нюансах структур данных. И в вероятности Поймать out of memory. Да. По исходным данным двух проходов достаточно. В крайнем случае если все проверить на втором проходе памяти не хватит - писать что надо проверить во временный файл, а затем допроверить его. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 10:25 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
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 Гб. Похоже на выгрузку таблиц из какой-то БД, подозреваю что там все нормализовано и повторов не будет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 11:33 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Странно. У меня 40 гиг. Проверь плиз не оборвался ли bzip с хвоста? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 13:37 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Две биткарты это ок. Плюсую. Заодно L1/L2 кеши продуем. Дадим краш тест. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 13:44 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Подозреваю ты ссылку не на тот файл дал, там есть mbdump-edit.tar.bz2 этот 4.2 Гб, качаю этот. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 13:53 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Возможно так. Я вечером контрольные суммы приложу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 14:00 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 14:17 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
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. Прогнал edit_data через биткарту с CRC Код: plaintext 1 млн. повторов CRC, всего 2%, а там кроме повторов еще коллизии, т.е. чистых повторов еще меньше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 15:25 |
|
||
|
Тяпничная унификация
|
|||
|---|---|---|---|
|
#18+
Добавил второй проход и сохранение результата Код: 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. Код: plaintext 1. 2. 3. 4. Вроде правильно, количество строк совпало с 20770314 Памяти тратит 1 Гб максимум, в начале на биткарты. PS std::vector<bool> почему-то отказался память возвращать, clear() и resize(0) не помогли. Пришлось скобок наставить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.09.2017, 17:25 |
|
||
|
|

start [/forum/topic.php?fid=57&msg=39515383&tid=2018073]: |
0ms |
get settings: |
11ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
169ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
60ms |
get tp. blocked users: |
1ms |
| others: | 279ms |
| total: | 554ms |

| 0 / 0 |
