Есть ли самый быстрый способ подсчета повторений объектов в массиве, чем HashTable? - PullRequest
Новая
       26

Есть ли самый быстрый способ подсчета повторений объектов в массиве, чем HashTable?

0 голосов
/ 10 февраля 2011

Я постараюсь быть максимально ясным. Я уже реализовал свое решение, и оно работает, мне просто нужно знать, будет ли лучше использовать другую структуру данных вместо хэш-таблицы

Это вопрос колледжа, но я уже подчинился учителю, и он работает, я просто хотел посмотреть, поступит ли кто-нибудь по-другому.

Итак, вот в чем проблема:

С учетом изображения (PPM 3, все данные хранятся в формате ASCII в RGB). например 

P3
# The P3 means colors are in ASCII, then 3 columns and 2 rows,
# then 255 for max color, then RGB triplets
3 2
255
255   0   0     0 255   0     0   0 255
255 255   0   255 255 255     0   0   0

Мне нужно разделить каждый пиксель на постоянную, которая будет степенью двойки (2,4,8 ………… 64,128) 

c= 32;
Pixel2(255/c,255/c,255/c) = Pixel2(7,7,7)

Затем мне нужно преобразовать все пиксели в патчи заданной ширины, и патч будет накапливать значения RGB пикселей, которые он содержит

например. 

w=3;   imageW = 10; imageH=10;
Patch[0].r = Pixel[0].r + Pixel[1].r + Pixel[2].r +
             Pixel[10].r + Pixel[11].r + Pixel[12].r +
             Pixel[20].r + Pixel[21].r + Pixel[22].r;
Patch[0].g = Same for g component;
Patch[0].b = Same for b component;

Patch[1].r = Pixel[1].r + Pixel[2].r + Pixel[3].r +
             Pixel[11].r + Pixel[12].r + Pixel[13].r +
             Pixel[21].r + Pixel[22].r + Pixel[23].r;
etc…

Затем мне нужно посчитать количество повторений каждого патча на изображении. Итак, у меня есть класс Image, который читает изображение из файла (ifstream), и класс Pixel, в котором есть компоненты r, g, b и nAparations. Я читаю пиксели, делю их на заданную константу и получаю патчи, суммирующие значения содержащихся в них пикселей.

После этого у нас есть вектор данных в моем классе Image, который представляет собой массив объектов Patches. например, * 1 020 * 

data = [Patch0{r comp,g comp, b comp, 1 parition}, Patch1{r comp,g comp, b comp, 1 parition} …..];

Теперь, что я сделал, это использовал хеш-таблицу, вставьте каждый патч, если он уже вставлен, просто обновите его компонент nAppearances, если нет, вставьте его. После того, как все вставлены, верните вектор со всеми элементами в хеш-таблице. Этот вектор будет иметь только одно вхождение каждого патча, а его компонент nAppearances будет содержать количество раз, когда каждый патч появляется на изображении.

Есть ли другой способ? Или лучше использовать хеш-таблицу?

Кроме того, какую хеш-функцию вы бы использовали? В настоящее время я использую 

hash = patch.r * 1 + patch.g *2 + patch.b*3;
tableSize = maximun number of patches (assuming no one repeats)
insert into table[hash%tableSize];

Хэш-таблица допускает коллизии, каждая позиция в таблице имеет список элементов.

Извините, если оно слишком большое, просто хотелось прояснить. Также извините, если мой английский недостаточно хорош! спасибо.

Ответы [ 2 ]

0 голосов
/ 11 февраля 2011

с помощью хэш-функции @CashCow я набрал немного скорости.

unsigned int colornum (unsigned int red, unsigned int green, unsigned int blue) {return (red << 16 | green <<8 | синий);} </p>

тогда хеш - просто colornum (r, g, b)% hashTableSize;

Дело в том, что мне нужно сделать подсчет количества повторений патчей для большого количества изображений, (По одному за раз), и они могут сильно различаться (у одного может быть только 81 патч, изображение 10x10, другое может быть 1024x1024 с до + 1 миллиона патчей, если все они разные ..)

Поэтому у меня возникают проблемы с адаптацией hashTableSize для этой операции (colornum (r, g, b)% hashTableSize) в каждом изображении, потому что большое число для очень маленького изображения не будет оптимальным, а наоборот вызовет многоо столкновениях ... Я также изучил другие известные быстрые хеш-функции, такие как murmurhash2, но я не знаю, как правильно их реализовать.(Мне все еще нужно сделать% hashtableSize для неподписанного int, который они возвращают? Потому что, если это да, тогда я не думаю, что они должны быть быстрее, чем @CashCow sugestion, поскольку я делаю ОЧЕНЬ МНОГО операций)

Если это имеет какое-либо значение, сразу после этого мне нужно будет извлечь массив исправлений и отсортировать его (потому что мне нужно будет сравнить их и найти различия, и, насколько я знаю, самый быстрый способсравнивать два массива объектов. Сначала они отсортированы правильно ??) поэтому, если вы знаете какой-либо метод, который бы быстро вычислял число повторений, а также позвольте мне позже получить уже отсортированный, скажем.

I 'Я думаю, что сбалансированное дерево может сработать. Это асимптотически хуже как поиск, так и вставка, но я бы избавился от проблемы радикально разных размеров изображений, а также смог бы получить их, отсортированные по trasversal Inorder (donне знаю, что это имя на английском языке ..).Любые мысли по этому поводу был бы признателен.Еще раз спасибо!

0 голосов
/ 10 февраля 2011

2 вещи

первый: если вы собираетесь использовать хэш-цвета:

Если R, G и B - цвета от 00 до FF, проще всего просто создать 24-битную хеш-функцию, т.е. RRGGBB, а затем изменить ее на некоторое простое число, равное размеру вашей хеш-таблицы. Какого размера ваш хэш-стол? Это простое число?

Например, 65536 будет очень плохим выбором размера хеш-таблицы. 65539 было бы хорошо.

unsigned int colornum (unsigned int red, unsigned int green, unsigned int blue) { возврат (красный << 16 | зеленый << 8 | синий); } </p>

тогда хеш просто colornum(r,g,b) % hashTableSize;

альтернативы хешу: Используйте std :: set с 24-битным числом RGB или с номерами rgb, но для сравнения используйте 24-битное число. Таким образом, вы можете посчитать количество дубликатов. Это не так быстро, как хэш.

Кстати, если вы можете себе это позволить, 2 ^ 24 - это всего 16 МБ, и если вы используете набор битов, который будет использовать 2 МБ. Вы могли бы пройтись по всем своим цветам, установив «флаг» для каждого возникающего цвета, а затем подсчитать дубликаты таким образом.

...