powered by simpleCommunicator - 2.0.38     © 2025 Programmizd 02
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Поиск уникальных png иконок
57 сообщений из 57, показаны все 3 страниц
Поиск уникальных png иконок
    #40111067
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть набор 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.
TIconList = class
strict private
  type
    TIconSize = record
      Width: Word;
      Height: Word;
    end;
    THash = type Integer;
    TIconBucket = TDictionary<THash, Integer>;
  class var
    FCurIdx: Integer;
strict private
  FIcons: TObjectDictionary<TIconSize, TIconBucket>;
strict private
  class function CalcHash(AData: Pointer; ADataSize: Integer): THash; static;
public
  constructor Create;
  destructor Destroy; override;
  function TryAddIcon(AData: Pointer; ADataSize, AWidth, AHeight: Integer): Integer;
end;

{ TIconList }

constructor TIconList.Create;
begin
  inherited Create;
  FIcons := TObjectDictionary<TIconSize, TIconBucket>.Create([doOwnsValues]);
end;

destructor TIconList.Destroy;
begin
  FIcons.Free;
  inherited Destroy;
end;

class function TIconList.CalcHash(AData: Pointer; ADataSize: Integer): THash;
begin
  // Result := 0;
end;

function TIconList.TryAddIcon(AData: Pointer; ADataSize, AWidth,
  AHeight: Integer): Integer;
var
  LSize: TIconSize;
  LBucket: TIconBucket;
  LHash: THash;
begin
  LSize.Width := AWidth;
  LSize.Height := AHeight;
  if not FIcons.TryGetValue(LSize, LBucket) then begin
    LBucket := TIconBucket.Create;
    FIcons.Add(LSize, LBucket);
  end;
  LHash := CalcHash(AData, ADataSize);
  if not LBucket.TryGetValue(LHash, Result) then begin
    Result := FCurIdx;
    Inc(FCurIdx);
    LBucket.Add(LHash, Result);
  end;
end;

и использование
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
var
  LMemStrm: TMemoryStream;
  LIStrm: IStream;
begin
  LMemStrm := TMemoryStream.Create;
  try
    LIStrm := TStreamAdapter.Create(LMemStrm, soReference);
    GPCheck(GdipSaveImageToStream(Handle, LIStrm, @TGDIPlusManager.PngEncoder, nil));
    Idx := IconList.TryAddIcon(LMemStrm.Memory, LMemStrm.Size, FIconWidth, FIconHight);
  finally
    LMemStrm.Free;
  end;
end;


Т.е. под каждый размер заводим словарь хешей, потом для картинки вычисляем хеш и смотрим его наличие в соответствующем словаре. Коллизию хешей, в виду малого количества иконок считаем невозможной.

Вопросы: на сколько адекватный алгоритм? Какой хеш использовать (скорость в приоритете)? Есть ли в Delphi Rio готовые реализации хеш-функций?

С уважением, Vasilisk
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111069
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Первая ссылка в гугле:
https://docwiki.embarcadero.com/Libraries/Sydney/en/System.Hash

PS: Алгоритм неадекватный вообще. В том числе из-за "коллизию хэшей считаем невозможной".
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111076
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
В том числе
А еще?
Dimitry Sibiryakov
коллизию хэшей считаем невозможной
Ну не хочется на каждый чих еще и CompareMem дергать. Он тогда будет вызываться в 99%. Тогда и хеши со словарями не нужны.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111078
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
Он тогда будет вызываться в 99%.
99% хешей совпадает? :)
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111079
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_А еще?

1. Не озвучен критерий уникальности.
2. Не озвучена допустимость ложноположительных срабатываний.
3. Не озвучена допустимость ложноотрицательных срабатываний.

Из этих трёх условий может вытекать всё, что угодно, вплоть до тривиального
CRC32 непосредственно файлов.

_Vasilisk_
не хочется на каждый чих еще и CompareMem дергать

Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111081
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Для них CompareMem как раз оптимален.

Не когда этих иконок десятки тысяч.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111083
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreatНе когда этих иконок десятки тысяч.

В условии написано, что уникальный - десятки. CompareMem для остальных
остановится уже на первых байтах.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111084
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Коллизия хеша среди валидных PNG файлов? На хотя бы 4-байтовом хеше вероятность, кмк, минимальна. Но никто не мешает при коллизии сравнивать непосредственно файлы.
Хотя да, для 10 образцов легче не городить премудростей.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111086
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В любом случае бутылочным горлышком будет диск.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111087
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

Ну так не забывай что расход памяти так в 10000 раз больше.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111091
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
rgreat
Dimitry Sibiryakov,

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

Откуда? Хранятся-то только уникальные. А дубли, которые пойдут после 11-ти, сразу же удалять
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111093
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Fr0sT-Brutal,

А, ну да. Забыл что тут частный случай и уникальных мало.

Странная задача.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111095
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
rgreat, чего только не приходится делать нашему брату)) может, аватарки какие-то фильтровать надо
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111102
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не понимаю, какой смысл считать хэш, чтобы потом его сравнить с существующими, если можно хранить все существующие в памяти, раз их будет несколько десятков всего. Это максимум - 30 килобайт.
Ну и потом.
1. Сравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый список, иначе 2.
2. CompareMem по хранимым иконкам таких размеров. Если не нашли - уникальная, добавляем в хранимый список, иначе - пропуск.
CompareMem на килобайт будет работать так быстро, что тысячи иконок проскочат за такт. Диск будет тормозить, это да.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111106
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YuRockСравниваем размер. Если такого еще не было - уникальная, добавляем в хранимый
список, иначе 2.

Внезапно здесь размер выступает в роли хэша. Единственное отличие - способ
вычисления и вероятность коллизий.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111110
L_argo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Делайте по файлу MD5. И забыть по коллизии.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111114
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L_argo,

MD5 не гарантия уникальности.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111116
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ни один хэш не гарантия уникальности. По определению.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111124
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat
99% хешей совпадает? :)
Да. Я же написал, что из 10000 иконок уникальных от силы 30.
Dimitry Sibiryakov
1. Не озвучен критерий уникальности.
Две иконки равны, если они имеют идентичные размеры и они "визуально неотличимы". Вместо "визуально неотличимы" можно использовать "у них совпадает каждый пиксел"
Dimitry Sibiryakov
2. Не озвучена допустимость ложноположительных срабатываний.
3. Не озвучена допустимость ложноотрицательных срабатываний.
Допустимо помещение в список нескольких одинаковых иконок. Недопустимо выбрасывание иконки из-за того, что алгоритм посчитал ее похожей на другую
Dimitry Sibiryakov
Иконки 32х32 - маленькие . Для них CompareMem как раз оптимален.
Но их очень много. И т.к. 99% идентичные, то для них CompareMem будет сравнивать все байты
Dimitry Sibiryakov
В условии написано, что уникальный - десятки. CompareMem для остальных
остановится уже на первых байтах.
Для каждой иконки с большой вероятностью найдется пара. А значит для каждой иконки CompareMem пробежит все байты
Fr0sT-Brutal
Но никто не мешает при коллизии сравнивать непосредственно файлы.
Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше
Dimitry Sibiryakov
В любом случае бутылочным горлышком будет диск.
Они все в памяти. В объектах GDI+
rgreat
Странная задача.
Задача попытка перейти от иконок на ImageList без переписывания API.

Грубо говоря есть такой код
Код: pascal
1.
2.
for i := 0 to 10000 do
  Manager.DrawObject(LBmp.Handle, Point[i]);  // LBmp: TBitmap;

Manager понятия не имеет какие битмапы ему подсовывают. Он их преобразовывает в png, сохраняет на диск, а потом у внешней библиотеки вызывает
Код: pascal
1.
LoadIcon(FileName);

В идеале было бы переписать все так
Код: pascal
1.
2.
3.
Idx := Manager.AddIcon(LBmp.Handle);
for i := 0 to 10000 do
  Manager.DrawObjectIdx(Idx, Point[i]);

но это реально очень много переписывать.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111126
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_,

> Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше

Коллизия будет 1 раз из нескольких десятков проверок.
У тебя же несколько десятков уникальных иконок.

Иначе придется каждую с каждой проверять, ну или раньше одинаковые найдешь, если повезет.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111128
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше

Да, именно так, смысла в хэше нет. Каждую иконку тебе надо развернуть до битмапа
чтобы игнорировать разницу метаданных и сжатия, а потом уже голые пиксели можно
тупо сравнивать CompareMem. Хэш, конечно, мог бы дать ускорение, но усложнит
код, который всё равно скорее всего упрётся в диск, а не непосредственно сравнение.

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

Но вообще сначала хорошо бы провести эксперимент и посмотреть на результат
md5sum по этим файлам, например. Возможно, даже с разворачиванием в битмап можно
не заморачиваться, а тупо сравнивать файлы побайтово.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111132
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat
Коллизия будет 1 раз из нескольких десятков проверок.
У тебя же несколько десятков уникальных иконок.
Смотри. Пусть у нас есть три группы иконок. Теперь, что получается:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
procedure TryAddIcon(AIcon);
begin
  LHash := CalcHash(AIcon);
  if IconList.TryGetValue(LHash, LIcon) then begin
    // Иконка, кроме первых трех вызовов, уже есть в списке, поэтому получили равенство хешей
    // Но мы не уверены, что это не коллизия, поэтому должны еще и сравнить побайтово.
    // Т.е. сравнение будет вызываться почти всегда
    if not CompareMem(AIcon, LIcon) then
      AddIcon(AIcon);
  end;
end;

Теперь без хешей
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
procedure TryAddIcon(AIcon);
begin
  for LIcon in IconList then begin
    // CompareMem будет вызываться для каждой иконки из списка,
    // но на других иконках функция вернет False при обнаружении первого же расхождения
    // зато выигрываем на невычислении хеша
    if not CompareMem(AIcon, LIcon) then begin
      AddIcon(AIcon);
      Exit;
    end;
  end;
end;
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111133
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
Смотри. Пусть у нас есть три группы иконок.
А почему 3 группы а не десятки уникальных иконок?

Ну и ИМХО можно не проверять на полную идентичность, особенно если забацать одновременно 2 принципиально разных хэша.

В то что могут одновременно совпасть 2 разных хеша я не верю.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111135
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
_Vasilisk_
Еще раз - коллизии будут постоянно. Тогда вообще нет смысла в хеше

Ты путаешь коллизию и совпадение. Коллизия - это когда два разных набора данных имеют один хеш. Я был неправ насчет CompareMem при совпадении - да, это неприменимо. Но коллизии хеша на валидных PNG... что-то мне мало в это верится. Возьми хеш побольше тогда.

На тупом CompareMem у тебя будет максимум NFiles*NUniques сравнений, в среднем - пополам. Причем эти сравнения наверняка по большей части будут выходить гораздо раньше окончания файлов.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111136
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat
А почему 3 группы а не десятки уникальных иконок?
Потому что при общем количестве 10000 иконок разницы между 3 и 10 нет
rgreat
если забацать одновременно 2 принципиально разных хэша.
О! Вот это уже ближе к делу.
Fr0sT-Brutal
Ты путаешь коллизию и совпадение.
Не путаю. Но они неотличимы без сравнения данных
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111139
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
Потому что при общем количестве 10000 иконок разницы между 3 и 10 нет
Ну при 3х уникальных, я бы и сам посоветовал comparemem. :)
Другое дело если уникальных десятки.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111145
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_Вот это уже ближе к делу.

Бери сразу пять. Чтобы время их вычисления окончательно сравнялось со временем
сравнения, а суммарный размер - с размером самой иконки. И будет тебе счастье,
ага...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111150
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Чтобы время их вычисления окончательно сравнялось со временем сравнения,
Ша! Сейчас тестировать будем.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111154
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
А значит для каждой иконки CompareMem пробежит все байты
А ты уверен, что "пробежать все байты" - медленнее, чем пробежать по этим байтам и посчитать какой-то хэш?
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111155
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
Dimitry Sibiryakov
Чтобы время их вычисления окончательно сравнялось со временем сравнения,
Ша! Сейчас тестировать будем.
Даю прогноз: если иконки уже в памяти, то метод с CompareMem займёт 0 - 16 миллисекунд.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111158
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Гм... Я тоже подумываю над подобной задачей, правда пока не приступал. Думаю использование хэшей обязательно (по крайней мере для моей задачи)
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111188
ъъъъъ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Каждый файл ico может содержать до 65 535 изображений.
Т.обр. если картинка 32х32, то общее максимальное количество пикселей может достигать 65535*32*32. Пусть каждый пиксель будет 4 байта... файлик получится размером 268 435 456 байт.
10-20 тыс иконок... э...
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111189
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ъъъъъ
Каждый файл ico
Казалось бы при чем здесь файлы, а тем более ico, если в стартовом посте написано
_Vasilisk_
Есть набор png иконок
?
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111190
ъъъъъ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
_Vasilisk_,

вот я лошара...
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111207
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задача очень похожа на дедубликацию файлов на диске.

На сегодня это уже решенная задача. Там - нечего изобретать. Берите утилиты dedup (тысячи их).
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111229
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Задача очень похожа на дедубликацию файлов на диске.
На сегодня это уже решенная задача.
Это замечательно. За исключением одного маленького факта
_Vasilisk_
Они все в памяти. В объектах GDI+
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111252
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
_Vasilisk_
Не путаю. Но они неотличимы без сравнения данных

Отличимы тем, что вероятность одного стремится к нулю.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111295
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Но достигнет нуля только в случае когда размер хэша сравняется с размером
хэшируемых данных. А по условиям задачи ложноотрицательные ответы недопустимы.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111319
Fr0sT-Brutal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ну этак надо от всех хешей вообще избавиться, ведь есть 0.00000001% шанс совпадения на реальных данных
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111322
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сделал на CompareMem, посмотрел на результаты. На 10 000 иконок 16х16 время обнаружения дубликатов стабильно 100 миллисекунд вне зависимости от количества уникальных иконок. Проверял для 1, 5, 10, 20 уникальных иконок.

На вариант с поиском по хешу (без проверки коллизий) уходит 168 миллисекунд также вне зависимости от количества уникальных иконок
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111330
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот итоговый класс
Код: 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.
type
  TIconList = class
  strict private
    type
      TIconSize = record
        Width: Integer;
        Height: Integer;
      end;
      TIconData = TArray<Byte>;
      TIconItem = record
        Data: TIconData;
        Index: Integer;
      end;
      TIconItems = TList<TIconItem>;
    class var
      FCurIdx: Integer;
  strict private
    FIcons: TObjectDictionary<TIconSize, TIconItems>;
  public
    constructor Create;
    destructor Destroy; override;
    function TryAddIcon(const AIcon: TIconData; AWidth, AHeight: Integer;
      out AIndex: Integer): Boolean;
  end;

{ TIconList }

constructor TIconList.Create;
begin
  inherited Create;
  FIcons := TObjectDictionary<TIconSize, TIconItems>.Create([doOwnsValues]);
end;

destructor TIconList.Destroy;
begin
  FIcons.Free;
  inherited Destroy;
end;

function TIconList.TryAddIcon(const AIcon: TIconData; AWidth,
  AHeight: Integer; out AIndex: Integer): Boolean;
var
  LSize: TIconSize;
  LItems: TIconItems;
  LItem: TIconItem;
begin
  LSize.Width := AWidth;
  LSize.Height := AHeight;
  if not FIcons.TryGetValue(LSize, LItems) then begin
    LItems := TIconItems.Create;
    FIcons.Add(LSize, LItems);
  end;
  for LItem in LItems do begin
    if
      (Length(LItem.Data) = Length(AIcon)) and
      CompareMem(LItem.Data, AIcon, Length(AIcon))
    then begin
      AIndex := LItem.Index;
      Result := False;
      Exit;
    end;
  end;
  AIndex := FCurIdx;
  Inc(FCurIdx);
  LItem.Data := AIcon;
  LItem.Index := AIndex;
  LItems.Add(LItem);
  Result := True;
end;

...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111344
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_,

Прикольно, а с хешами какой код?
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111351
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
TIconItems = TDictionary<Integer, Integer>;

function TIconList.TryAddIcon(const AIcon: TIconData; AWidth,
  AHeight: Integer; out AIndex: Integer): Boolean;
var
  LSize: TIconSize;
  LItems: TIconItems;
  LHash: Integer;
begin
  LSize.Width := AWidth;
  LSize.Height := AHeight;
  if not FIcons.TryGetValue(LSize, LItems) then begin
    LItems := TIconItems.Create;
    FIcons.Add(LSize, LItems);
  end;
  LHash := THashBobJenkins.GetHashValue(AIcon[0], Length(AIcon));
  if LItems.TryGetValue(LHash, AIndex) then begin
    Result := False;
    Exit;
  end;
  AIndex := FCurIdx;
  Inc(FCurIdx);
  LItems.Add(LHash, AIndex);
  Result := True;
end;

...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111386
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_,

Можно подоптимизировать, наверно. Например, Length(AIcon) 2 раза вызывается, а можно сделать один.

Ну и, раз кол-во одинаковых не влияет, значит время тратится вообще не на сравнение.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111389
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
mayton
Задача очень похожа на дедубликацию файлов на диске.
На сегодня это уже решенная задача.
Это замечательно. За исключением одного маленького факта
_Vasilisk_
Они все в памяти. В объектах GDI+

По постановке задачи - это все выглядит как одноразовая задача. Почистить ресурсы от дублей и забыть эту задачу как страшный сон.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111390
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YuRock
Length(AIcon) 2 раза вызывается, а можно сделать один.
Нет смысла. Т.к. длина хранится по отрицательному смещению, и это смещение вычисляется сразу, то что Length, что переменная дадут идентичный ассемблерный код. Только с разным смещением
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111391
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
По постановке задачи - это все выглядит как одноразовая задача.
Как раз наоборот - это будет постоянно работающий код. Иначе вопрос оптимизации вообще бы не стоял
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111394
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
YuRock
Length(AIcon) 2 раза вызывается, а можно сделать один.
Нет смысла. Т.к. длина хранится по отрицательному смещению, и это смещение вычисляется сразу, то что Length, что переменная дадут идентичный ассемблерный код. Только с разным смещением
Length - всё же функция, требует вызова, возврата. Накладные расходы таки есть.
Может, конечно, я отстал от жизни.
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111425
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
YuRock
Length - всё же функция
Это не функция, но таки с переменной поэкономнее
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
procedure TForm1.Button1Click(Sender: TObject);
var
  LBytes: TBytes;
  LSavedLen: Integer;
  LLen: Integer;
begin
  LSavedLen := Length(LBytes);
  LLen := LSavedLen;
end;

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
Unit1.pas.466: LSavedLen := Length(LBytes);
008F83F7 8B45F8           mov eax,[ebp-$08]
008F83FA 8945EC           mov [ebp-$14],eax
008F83FD 837DEC00         cmp dword ptr [ebp-$14],$00
008F8401 740B             jz $008f840e
008F8403 8B45EC           mov eax,[ebp-$14]
008F8406 83E804           sub eax,$04
008F8409 8B00             mov eax,[eax]
008F840B 8945EC           mov [ebp-$14],eax
008F840E 8B45EC           mov eax,[ebp-$14]
008F8411 8945F4           mov [ebp-$0c],eax
Unit1.pas.467: LLen := LSavedLen;
008F8414 8B45F4           mov eax,[ebp-$0c]
008F8417 8945F0           mov [ebp-$10],eax
Unit1.pas.468: end;
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111441
s62
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_,
я особо в детали во всех сообщениях не вникал, но правильно ли понимаю, что алгоритм без хэшей - просто по очереди перебираются иконки, сравниваются через CompareMem с уже отобранными, и если не совпадает ни с одной, то иконка добавляется. А с хэшем - считается хэш каждой иконки и сравниваются хеши. Т.е. как бы выигрыш по скорости, что хэш считается 1 раз для иконки, а если 10 уникальных, то потом 10 сравнений хэшей, а не 10 сравнений CompareMem.
И 1-ый вариант, без хэшей, на реальных данных сейчас получается быстрее?
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111457
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
s62
правильно ли понимаю,
Все правильно
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111489
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_
mayton
Задача очень похожа на дедубликацию файлов на диске.
На сегодня это уже решенная задача.
Это замечательно. За исключением одного маленького факта
_Vasilisk_
Они все в памяти. В объектах GDI+

Правильно ли я понимаю что надо каждый раз искать уникальные не из файловой системы а из
памяти в объектах GDI ?
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111516
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Правильно ли я понимаю что надо каждый раз искать уникальные не из файловой системы а из памяти в объектах GDI ?
Да. Только GDI+
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111530
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И каждый GDI+ объект-иконку можно преобразовать в байтовый массив для сравнения?
Если массивы одинаковы - то и GDI+ содержимое тоже одинаково. Верно?
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111543
s62
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
22395080
Код: pascal
1.
  TIconData = TArray<Byte>;
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111586
Фотография _Vasilisk_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
И каждый GDI+ объект-иконку можно преобразовать в байтовый массив для сравнения?
Да. У объекта есть метод SaveToStream
mayton
Если массивы одинаковы - то и GDI+ содержимое тоже одинаково. Верно?
Все так
...
Рейтинг: 0 / 0
Поиск уникальных png иконок
    #40111607
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
_Vasilisk_, бери хеш-табличку с любой хеш-функцией. Тебе даже CRC32 подойдет потому что для 20000 картинок
4 млрд классов более чем достаточно.
...
Рейтинг: 0 / 0
57 сообщений из 57, показаны все 3 страниц
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Поиск уникальных png иконок
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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