#objective-c #ios #ipad #equality #nsset
#objective-c #iOS #iPad #равенство #nsset
Вопрос:
У меня есть, NSSet содержащий много тысяч NSValue объектов (обертывание CGPoints ). Я хотел бы очень быстро определить, существует ли данное CGPoint значение в NSSet . Мне кажется, что member: метод an NSSet мог бы выполнить эту работу здесь, за исключением того, что он проверяет равенство с помощью isEqual: . NSValue объекты используют isEqualToValue: , и поэтому, когда я выполняю код:
[mySet member:valueToCheck];
на самом деле это приводит к сбою Xcode.
1) Есть ли какой-нибудь способ использовать пользовательскую проверку на равенство, чтобы заставить это работать для NSValue объектов?
2) Является ли это вообще лучшим подходом (т.Е. member: Достаточно быстрым в первую очередь)? Сценарий заключается в том, что у меня есть NSSet , содержащий большое количество точек, представляющих пиксели на экране (iPad). Позже мне нужно бомбардировать этот набор многими тысячами точек в секунду, чтобы увидеть, существуют ли они в наборе. Мой подход кажется грубым для достижения этого. Я думал о создании чего-то вроде огромного двумерного массива битов, где каждый индекс представляет пиксель на экране. Как только я узнаю точку, для которой я тестирую, я могу просто перейти прямо к этой точке в массиве и проверить наличие 1 или 0… это звучит лучше или хуже?
Спасибо
Ответ №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"
Проблема в вашем коде. Попробуйте очистить и перестроить.
Комментарии:
1. Хммм, теперь вы упомянули об этом — похоже, у меня это действительно работает. Я полагаю, что это, должно быть, была проблема с самим Xcode (это приводило к тому, что сам Xcode подходил, а не приложение). Мне просто нужно проверить, достаточно ли высока скорость сейчас, вернемся через минуту …!
2.Да, я думаю, что я только что столкнулся с ошибкой Xcode 4. К счастью, это больше не сбой. Я только что протестировал скорость этого подхода, и кажется, что он может быть достаточно быстрым. Потенциально
NSSetможет достичь пропускной способности более 750 000 объектов, и для обеспечения достаточной скорости потребуется проверять примерно 10 000 точек в секунду. Кажется, что это просто справляется с этим — для меня этого может быть недостаточно. Я удивлен скоростью этого, хотя … быстрее, чем я думал сначала. Мне нужно провести более тщательные тесты, прежде чем я буду уверен, достаточно ли это хорошо.3.
- (void)testNSValuePointHash { NSValue *v1 = [NSValue valueWithPoint:NSMakePoint(1,1)]; NSValue *v2 = [NSValue valueWithPoint:NSMakePoint(2,2)]; STAssertTrue([v1 hash] != [v2 hash], nil); }Этот тест завершается неудачей, и это может быть связано. Я думаю, что это ошибка в NSValue, не так ли? Все NSValues с точками, где две оси имеют одинаковое значение, похоже, дают хэш 0.
Ответ №2:
Для ответа № 2:
Я не знаю, как NSSet реализован внутренне, но, учитывая, что вы знаете, что вы сохраняете точки (с X и Y), я думаю, вам было бы лучше реализовать свой собственный алгоритм разделения. Лично я бы выбрал свою собственную реализацию вместо NSSet, если вы говорите, что у вас тысячи точек.
Сохранение огромных двумерных массивов для каждого пикселя, вероятно, было бы самым быстрым способом, но это убьет вас с точки зрения потребления памяти. Вам нужно что-то быстрое, но в то же время легкое.
Существует множество алгоритмов, и вы можете найти их, выполнив поиск «алгоритмы пространственного разбиения» в википедии или Google. Это также зависит от ваших навыков программирования и того, сколько времени вы готовы вложить в это.
Например, довольно простым решением было бы реализовать четырехъядерное дерево, где вы начинаете с разделения экрана (или области) на 4 равные части. Затем, если и где это необходимо, вы также разделяете эту конкретную ячейку на 4 части. И вы делаете это до тех пор, пока в каждой ячейке не будет содержаться достаточно небольшое количество точек, чтобы вы могли проверить их все методом перебора. Вы можете найти очень хорошее описание в wiki:http://en.wikipedia.org/wiki/Quadtree
Надеюсь, это поможет,
Комментарии:
1. Очень полезный ответ, спасибо. Если бы я использовал логический массив (если это возможно, я никогда раньше его не создавал!), тогда потребовалось бы 100 КБ — я не уверен, что это привело бы к сбоям в моем приложении, но я полагаю, что это может быть излишним, если алгоритм пространственного разбиения может достичь тех же результатов достаточно быстро. В противном случае я бы предпочел самое простое решение.
2. Имея целочисленные координаты и только на экране ipad, это заняло бы около 800 КБ (хранение одного байта на пиксель) накладные расходы. Это не так уж и много. Тем не менее, я думаю, что я бы все равно выбрал более умный алгоритм :). Я понятия не имею, о чем ваше приложение, и все сводится к вашим конкретным потребностям.
3. Это хорошая идея, но только если вы доказали, что использование
NSSetявляется узким местом .NSSetему более 20 лет, и у разработчиков Foundation было все это время, чтобы настроить его, чтобы он был безумно эффективным. (то же самое для всех других коллекций) Если вы можете доказать, что быстрее не использоватьNSSet, то обязательно используйте что-нибудь другое. Но сначала следуйте простым маршрутом, а затем профилируйте и измеряйте, где находятся ваши замедления.4. На данный момент очень сложно сказать, будет ли NSSet узким местом — похоже, что он находится прямо на границе производительности, в которой я нуждаюсь. Этот ответ был очень полезен, и я, возможно, в конечном итоге использую один из упомянутых здесь подходов, однако мой основной вопрос касался использования
NSSet, поэтому я пометил ответ от @Dave как ответ. Спасибо5. Для сравнения, кажется, что подход с массивным логическим массивом работает настолько быстро, насколько это возможно. С массивом:
BOOL boolArray[748][1004]и 25 000 тестовых точек это занимает всего 0,017 секунды. Более того, загрузка массива со значениями происходит мгновенно по сравнению с загрузкойNSSet. Мне все еще нужно посмотреть, возможен ли в моем приложении массив размером 800 КБ. Производительность в этом случае очень важна для обеспечения достойного пользовательского интерфейса, и такой подход, безусловно, хорош.
Ответ №3:
[mySet member:valueToCheck] сбой не должен быть. NSValue isEqual: отлично работает, когда я пробую это здесь, и на самом деле, вероятно, вызывает isEqualToValue: , когда задано другое значение NSValue для сравнения. valueToCheck Действительно ли это NSValue, или это CGPoint?
Нет способа переопределить методы хэша и сравнения по умолчанию для NSSet. Но NSSet является бесплатным соединением с CFSetRef , и вы можете легко указать там пользовательские методы хеширования и сравнения:
CFSetCallBacks callbacks = kCFTypeSetCallBacks;
callbacks.equal = customEqualFunction;
callbacks.hash = customHashFunction;
NSMutableSet *set = (NSMutableSet *)CFSetCreateMutable(NULL, 0, amp;callbacks);
Ограничения на эти функции предположительно такие же, как на методы NSObject hash и isEqual: , все, что равно, должно иметь одинаковый хэш. Прототипы в стиле C для customEqualFunction и customHashFunction описаны здесь и здесь.
Ответ №4:
Одним из решений было бы создать подкласс NSSet и переопределить member: для выполнения собственного сравнения. Затем ваше собственное сравнение могло бы быть простым вызовом isEqualToValue: . Взгляните на примечания к подклассам в NSSet документации.
Другим подходом было бы добавить категорию к, NSValue которая реализует isEqual: . В этом случае я бы предпочел создание подклассов, потому что это более ограниченное решение.
Комментарии:
1. Нет. Не создавать подклассы
NSSet. Это кластер классов, и его выделение в подклассы является нетривиальной задачей.2. @Дэйв ДеЛонг: Создание подклассов
NSSetв порядке. Я согласен, что обычно в этом нет необходимости, но это можно сделать. В документации не указано, что это кластер классов. Вот выдержка изNSSetдокументации: «Примечания к подклассам В подклассах не должно быть особой необходимости. Если вам нужно настроить поведение, часто лучше рассмотреть композицию вместо создания подклассов. Для переопределения методов В подклассе необходимо переопределить все его примитивные методы: элемент count: objectEnumerator»3. Это является кластером классов. В документации говорится, что это бесплатный мост, соединенный с
CFSet, а бесплатный мост работает только из-за кластеров классов.4. @Dave Достаточно справедливо. Ваш ответ более взвешенный. (В настоящее время у меня есть только веб-доступ, поэтому я не смог протестировать предложенное мной решение.) Немного странно, что в документах нет упоминания о том, что это кластер классов. В документах NSArray это очень ясно.
5. кроме того, у меня есть исходный код здесь, передо мной 😉 Вы можете убедиться в этом сами, создав экземпляр
NSSetи выяснив, каковоclassимя экземпляра. ЭтоNSCFSet(NSCF*— показатель того, что класс является TFB’d).
Ответ №5:
Проблема не только с -isEqual: , у вас также может возникнуть проблема с методом -hash. Если вы хотите использовать NSSet, вам, вероятно, следует создать пользовательский класс, который оборачивает CGPoint. -isEqual: тогда это тривиально и -hash может быть реализовано некоторым методом объединения битов обеих координат и последующей обработки их как NSUInteger.
Вы также захотите реализовать NSCopying протокол, который также тривиален, если ваши точки неизменяемы (просто сохраните и верните self в -copyWithZone: ).
Комментарии:
1. -1
-hashне проблема. Вы можете создать два уникальныхNSValueобъекта, которые содержат одно и то жеCGPointзначение, и они будут иметь одинаковое-hashзначение и будут возвращатьYESиз-isEqual:2. @DaveDeLong: это немного жесткое голосование против, учитывая, что основная часть моего ответа является альтернативой использованию NSValue.