NSSet-член для проверки равенства NSValue

Question

У меня есть NSSet, содержащий много тысяч NSValue объектов (упаковка CGPoints).Я хотел бы очень быстро найти, существует ли данное значение CGPoint в NSSet.Мне кажется, что member: метод NSSet мог бы выполнить работу здесь, за исключением того, что он проверяет равенство, используя isEqual:.NSValue объекты используют isEqualToValue:, и поэтому, когда я выполняю код:

[mySet member:valueToCheck];

, это фактически приводит к сбою Xcode.

1) Есть ли способ использовать пользовательское равенствопроверить, чтобы это работало для NSValue объектов?

2) Является ли это даже лучшим подходом (т.е. достаточно ли member: достаточно быстр)?Сценарий таков, что у меня есть NSSet, содержащий большое количество точек, представляющих пиксели на экране (iPad).Позже мне нужно бомбардировать этот набор со многими тысячами точек в секунду, чтобы увидеть, существуют ли они в наборе.Мой подход кажется грубым для достижения этого.Я думал о создании чего-то вроде огромного двумерного битового массива, где каждый индекс представлял бы пиксель на экране.Как только я узнаю точку, которую проверяю, я могу просто перейти прямо к этой точке массива и проверить 1 или 0 ... это звучит лучше или хуже?

Спасибо

Answer 1

Можете ли вы получить это в простой воспроизводимый случай? Например, я только что попробовал:

NSValue *v = [NSValue valueWithCGPoint:CGPointMake(1, 1)];
NSSet *s = [NSSet setWithObject:v];
NSLog(@"%@", [s member:[NSValue valueWithCGPoint:CGPointMake(1, 1)]]);

Но это работает просто отлично.

редактировать

-isEqual: не проблема:

NSValue *v1 = [NSValue valueWithPoint:NSMakePoint(1, 1)];
NSValue *v2 = [NSValue valueWithPoint:NSMakePoint(1, 1)];
NSLog(@"%d", [v1 isEqual:v2]); //logs "1"

-hash не проблема:

NSLog(@"%d", ([v1 hash] == [v2 hash])); //logs "1"

Это разные объекты:

NSLog(@"%d", (v1 != v2)); //logs "1"

Проблема в вашем коде. Попробуйте очистить и восстановить.

Answer 2

[mySet member:valueToCheck] не должен быть сбой.isEqual: NSValue работает нормально, когда я пытаюсь сделать это здесь, и на самом деле, вероятно, вызывает isEqualToValue:, когда ему дано другое значение NSValue для сравнения.Является ли valueToCheck действительно NSValue, или это CGPoint?

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

CFSetCallBacks callbacks = kCFTypeSetCallBacks;
callbacks.equal = customEqualFunction;
callbacks.hash = customHashFunction;
NSMutableSet *set = (NSMutableSet *)CFSetCreateMutable(NULL, 0, &callbacks);

Ограничения для этих функцийпредположительно такие же, как в методах NSObject hash и isEqual:, все равное должно иметь одинаковый хеш.Прототипы в стиле C для customEqualFunction и customHashFunction описаны здесь и здесь .

Answer 3

Ответить нет.2:

Я не знаю, как NSSet реализован внутри, но, учитывая, что вы знаете, что храните точки (с X и Y), я думаю, что вам было бы лучше, если бы вы реализовали свой собственный алгоритм разбиения.Лично я бы выбрал свою собственную реализацию вместо NSSet, если вы скажете, что у вас тысячи точек.

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

Существует множество алгоритмов, и вы можете найти их, выполнив поиск "алгоритмов пространственного разделения" в Википедии или Google.Это также зависит от ваших навыков программирования и от того, сколько времени вы готовы вложить в это.

Например, довольно простым было бы реализовать четырехугольное дерево, с которого вы начинаете погружаться с экрана (или площадь) в 4 равных частях.Затем, если и где это необходимо, вы делите эту конкретную ячейку также на 4 части.И вы будете делать это до тех пор, пока в каждой ячейке не будет достаточно маленькое количество точек, чтобы вы могли проверить их все методом грубой силы.Вы можете найти очень хорошее описание на вики: http://en.wikipedia.org/wiki/Quadtree

Надеюсь, это поможет,

Answer 4

Это проблема не только с -isEqual:, у вас также может быть проблема с методом -hash .Если вы хотите использовать NSSet, вам, вероятно, следует создать собственный класс, который оборачивает CGPoint.-isEqual: тогда тривиален, а -hash может быть реализован с помощью некоторого метода объединения битов обеих координат и последующей обработки их как NSUInteger.

Вы также захотите реализовать протокол NSCopying, который также тривиален, если ваши очки неизменны (просто сохраните и верните себя в -copyWithZone:).

Answer 5

Одним из решений будет подкласс NSSet и переопределение member: для собственного сравнения. Ваше собственное сравнение может тогда просто позвонить isEqualToValue:. Ознакомьтесь с примечаниями по подклассам в NSSet документации .

Другой подход заключается в добавлении категории к NSValue, которая реализует isEqual:. В этом случае я бы предпочел создание подклассов, потому что это более ограниченное решение.