|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Есть набор png иконок. Размером до 32х32. Нужно из этого набора найти только уникальные иконки. По прогнозам всего будет 2-3 различных размера, в каждом размере до 10 уникальных иконок. Всего иконок порядка 10000-20000. Идея решения Код: pascal 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.
Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
Т.е. под каждый размер заводим словарь хешей, потом для картинки вычисляем хеш и смотрим его наличие в соответствующем словаре. Коллизию хешей, в виду малого количества иконок считаем невозможной. Вопросы: на сколько адекватный алгоритм? Какой хеш использовать (скорость в приоритете)? Есть ли в Delphi Rio готовые реализации хеш-функций? С уважением, Vasilisk ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 16:30 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Первая ссылка в гугле: https://docwiki.embarcadero.com/Libraries/Sydney/en/System.Hash PS: Алгоритм неадекватный вообще. В том числе из-за "коллизию хэшей считаем невозможной". ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 16:35 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov В том числе Dimitry Sibiryakov коллизию хэшей считаем невозможной ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 16:53 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Он тогда будет вызываться в 99%. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:02 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_А еще? 1. Не озвучен критерий уникальности. 2. Не озвучена допустимость ложноположительных срабатываний. 3. Не озвучена допустимость ложноотрицательных срабатываний. Из этих трёх условий может вытекать всё, что угодно, вплоть до тривиального CRC32 непосредственно файлов. _Vasilisk_ не хочется на каждый чих еще и CompareMem дергать Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:02 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Для них CompareMem как раз оптимален. Не когда этих иконок десятки тысяч. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:05 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreatНе когда этих иконок десятки тысяч. В условии написано, что уникальный - десятки. CompareMem для остальных остановится уже на первых байтах. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:08 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Коллизия хеша среди валидных PNG файлов? На хотя бы 4-байтовом хеше вероятность, кмк, минимальна. Но никто не мешает при коллизии сравнивать непосредственно файлы. Хотя да, для 10 образцов легче не городить премудростей. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:10 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
В любом случае бутылочным горлышком будет диск. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:12 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, Ну так не забывай что расход памяти так в 10000 раз больше. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:14 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat Dimitry Sibiryakov, Ну так не забывай что расход памяти так в 10000 раз больше. Откуда? Хранятся-то только уникальные. А дубли, которые пойдут после 11-ти, сразу же удалять ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:17 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Fr0sT-Brutal, А, ну да. Забыл что тут частный случай и уникальных мало. Странная задача. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:18 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat, чего только не приходится делать нашему брату)) может, аватарки какие-то фильтровать надо ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:19 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Не понимаю, какой смысл считать хэш, чтобы потом его сравнить с существующими, если можно хранить все существующие в памяти, раз их будет несколько десятков всего. Это максимум - 30 килобайт. Ну и потом. 1. Сравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый список, иначе 2. 2. CompareMem по хранимым иконкам таких размеров. Если не нашли - уникальная, добавляем в хранимый список, иначе - пропуск. CompareMem на килобайт будет работать так быстро, что тысячи иконок проскочат за такт. Диск будет тормозить, это да. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:30 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
YuRockСравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый список, иначе 2. Внезапно здесь размер выступает в роли хэша. Единственное отличие - способ вычисления и вероятность коллизий. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:39 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Делайте по файлу MD5. И забыть по коллизии. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 17:53 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
L_argo, MD5 не гарантия уникальности. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:00 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Ни один хэш не гарантия уникальности. По определению. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:05 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat 99% хешей совпадает? :) Dimitry Sibiryakov 1. Не озвучен критерий уникальности. Dimitry Sibiryakov 2. Не озвучена допустимость ложноположительных срабатываний. 3. Не озвучена допустимость ложноотрицательных срабатываний. Dimitry Sibiryakov Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален. Dimitry Sibiryakov В условии написано, что уникальный - десятки. CompareMem для остальных остановится уже на первых байтах. Fr0sT-Brutal Но никто не мешает при коллизии сравнивать непосредственно файлы. Dimitry Sibiryakov В любом случае бутылочным горлышком будет диск. rgreat Странная задача. Грубо говоря есть такой код Код: pascal 1. 2.
Manager понятия не имеет какие битмапы ему подсовывают. Он их преобразовывает в png, сохраняет на диск, а потом у внешней библиотеки вызывает Код: pascal 1.
В идеале было бы переписать все так Код: pascal 1. 2. 3.
но это реально очень много переписывать. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:36 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_, > Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше Коллизия будет 1 раз из нескольких десятков проверок. У тебя же несколько десятков уникальных иконок. Иначе придется каждую с каждой проверять, ну или раньше одинаковые найдешь, если повезет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:48 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше Да, именно так, смысла в хэше нет. Каждую иконку тебе надо развернуть до битмапа чтобы игнорировать разницу метаданных и сжатия, а потом уже голые пиксели можно тупо сравнивать CompareMem. Хэш, конечно, мог бы дать ускорение, но усложнит код, который всё равно скорее всего упрётся в диск, а не непосредственно сравнение. Можно даже не заморачиваться со случаями когда один пиксель отличается младшим битом в одном цвете. Но вообще сначала хорошо бы провести эксперимент и посмотреть на результат md5sum по этим файлам, например. Возможно, даже с разворачиванием в битмап можно не заморачиваться, а тупо сравнивать файлы побайтово. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 18:55 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat Коллизия будет 1 раз из нескольких десятков проверок. У тебя же несколько десятков уникальных иконок. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
Теперь без хешей Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:07 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Смотри. Пусть у нас есть три группы иконок. Ну и ИМХО можно не проверять на полную идентичность, особенно если забацать одновременно 2 принципиально разных хэша. В то что могут одновременно совпасть 2 разных хеша я не верю. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:10 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше Ты путаешь коллизию и совпадение. Коллизия - это когда два разных набора данных имеют один хеш. Я был неправ насчет CompareMem при совпадении - да, это неприменимо. Но коллизии хеша на валидных PNG... что-то мне мало в это верится. Возьми хеш побольше тогда. На тупом CompareMem у тебя будет максимум NFiles*NUniques сравнений, в среднем - пополам. Причем эти сравнения наверняка по большей части будут выходить гораздо раньше окончания файлов. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:10 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat А почему 3 группы а не десятки уникальных иконок? rgreat если забацать одновременно 2 принципиально разных хэша. Fr0sT-Brutal Ты путаешь коллизию и совпадение. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:20 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Потому что при общем количестве 10000 иконок разницы между 3 и 10 нет Другое дело если уникальных десятки. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:23 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_Вот это уже ближе к делу. Бери сразу пять. Чтобы время их вычисления окончательно сравнялось со временем сравнения, а суммарный размер - с размером самой иконки. И будет тебе счастье, ага... Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 19:55 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Чтобы время их вычисления окончательно сравнялось со временем сравнения, ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 20:23 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ А значит для каждой иконки CompareMem пробежит все байты ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 21:52 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Dimitry Sibiryakov Чтобы время их вычисления окончательно сравнялось со временем сравнения, ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 21:57 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Гм... Я тоже подумываю над подобной задачей, правда пока не приступал. Думаю использование хэшей обязательно (по крайней мере для моей задачи) ... |
|||
:
Нравится:
Не нравится:
|
|||
11.11.2021, 22:08 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Каждый файл ico может содержать до 65 535 изображений. Т.обр. если картинка 32х32, то общее максимальное количество пикселей может достигать 65535*32*32. Пусть каждый пиксель будет 4 байта... файлик получится размером 268 435 456 байт. 10-20 тыс иконок... э... ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 00:23 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
ъъъъъ Каждый файл ico _Vasilisk_ Есть набор png иконок ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 00:38 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_, вот я лошара... ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 01:15 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Задача очень похожа на дедубликацию файлов на диске. На сегодня это уже решенная задача. Там - нечего изобретать. Берите утилиты dedup (тысячи их). ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 09:15 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
mayton Задача очень похожа на дедубликацию файлов на диске. На сегодня это уже решенная задача. _Vasilisk_ Они все в памяти. В объектах GDI+ ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 10:42 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ Не путаю. Но они неотличимы без сравнения данных Отличимы тем, что вероятность одного стремится к нулю. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 11:50 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Но достигнет нуля только в случае когда размер хэша сравняется с размером хэшируемых данных. А по условиям задачи ложноотрицательные ответы недопустимы. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 13:28 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Ну этак надо от всех хешей вообще избавиться, ведь есть 0.00000001% шанс совпадения на реальных данных ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 14:05 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Сделал на CompareMem, посмотрел на результаты. На 10 000 иконок 16х16 время обнаружения дубликатов стабильно 100 миллисекунд вне зависимости от количества уникальных иконок. Проверял для 1, 5, 10, 20 уникальных иконок. На вариант с поиском по хешу (без проверки коллизий) уходит 168 миллисекунд также вне зависимости от количества уникальных иконок ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 14:07 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
Вот итоговый класс Код: pascal 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 14:12 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_, Прикольно, а с хешами какой код? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 14:29 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
rgreat а с хешами какой код? Код: pascal 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 14:40 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_, Можно подоптимизировать, наверно. Например, Length(AIcon) 2 раза вызывается, а можно сделать один. Ну и, раз кол-во одинаковых не влияет, значит время тратится вообще не на сравнение. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 15:34 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ mayton Задача очень похожа на дедубликацию файлов на диске. На сегодня это уже решенная задача. _Vasilisk_ Они все в памяти. В объектах GDI+ По постановке задачи - это все выглядит как одноразовая задача. Почистить ресурсы от дублей и забыть эту задачу как страшный сон. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 15:37 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
YuRock Length(AIcon) 2 раза вызывается, а можно сделать один. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 15:42 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
mayton По постановке задачи - это все выглядит как одноразовая задача. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 15:43 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ YuRock Length(AIcon) 2 раза вызывается, а можно сделать один. Может, конечно, я отстал от жизни. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 15:52 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
YuRock Length - всё же функция Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9.
Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 16:58 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_, я особо в детали во всех сообщениях не вникал, но правильно ли понимаю, что алгоритм без хэшей - просто по очереди перебираются иконки, сравниваются через CompareMem с уже отобранными, и если не совпадает ни с одной, то иконка добавляется. А с хэшем - считается хэш каждой иконки и сравниваются хеши. Т.е. как бы выигрыш по скорости, что хэш считается 1 раз для иконки, а если 10 уникальных, то потом 10 сравнений хэшей, а не 10 сравнений CompareMem. И 1-ый вариант, без хэшей, на реальных данных сейчас получается быстрее? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 17:29 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
s62 правильно ли понимаю, ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 17:45 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
_Vasilisk_ mayton Задача очень похожа на дедубликацию файлов на диске. На сегодня это уже решенная задача. _Vasilisk_ Они все в памяти. В объектах GDI+ Правильно ли я понимаю что надо каждый раз искать уникальные не из файловой системы а из памяти в объектах GDI ? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 18:49 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
mayton Правильно ли я понимаю что надо каждый раз искать уникальные не из файловой системы а из памяти в объектах GDI ? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 19:49 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
И каждый GDI+ объект-иконку можно преобразовать в байтовый массив для сравнения? Если массивы одинаковы - то и GDI+ содержимое тоже одинаково. Верно? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 20:34 |
|
Поиск уникальных png иконок
|
|||
---|---|---|---|
#18+
mayton И каждый GDI+ объект-иконку можно преобразовать в байтовый массив для сравнения? mayton Если массивы одинаковы - то и GDI+ содержимое тоже одинаково. Верно? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.11.2021, 22:45 |
|
|
start [/forum/topic.php?all=1&fid=58&tid=2036882]: |
0ms |
get settings: |
10ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
31ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
132ms |
get tp. blocked users: |
2ms |
others: | 317ms |
total: | 528ms |
0 / 0 |