NSSet - 检查 NSValue 是否相等的成员

Question

我有一个 NSSet ，其中包含数千个 NSValue 对象（包装 CGPoints）。我想快速查找 NSSet 中是否存在给定的 CGPoint 值。在我看来，NSSet 的 member: 方法可以完成这里的工作，只不过它使用 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)]]);

但效果很好。

edit

-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

回答否。 2：

我不知道 NSSet 内部是如何实现的，但是考虑到您知道您正在存储点（带有 X 和 Y），我认为您通过实现自己的分区算法会更好。就我个人而言，如果你说你有数千个点，我会选择我自己的实现而不是 NSSet。

为每个像素存储巨大的二维数组可能是最快的方法，但它会在内存消耗方面杀死你。您需要快速但又轻便的东西。

那里有很多算法，您可以通过在维基百科或谷歌上搜索“空间分区算法”来找到它们。它还取决于您的编程技能，以及您愿意为此投入多少时间。

例如，一个非常简单的方法是实现四叉树，首先将屏幕（或区域）分成 4 个相等的部分。然后，如果需要的话，您也可以将该特定单元格分为 4 部分。这样做直到每个单元格包含足够少的点，以便您可以对所有这些点进行强力测试。
您可以在 wiki 上找到非常好的描述：http://en.wikipedia.org/wiki/Quadtree

希望这有帮助，

Answer 3

[mySet member:valueToCheck] 不应崩溃。当我在这里尝试时，NSValue 的 isEqual: 工作正常，事实上，当给定另一个 NSValue 进行比较时，可能会调用 isEqualToValue: 。 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: 方法，任何相等的东西都必须具有相同的哈希值。 customEqualFunction 和 customHashFunction 的 C 风格原型在 此处 和此处。

Answer 4

一种解决方案是子类化 NSSet 并重写 member: 来进行自己的比较。然后，您可以简单地调用 isEqualToValue: 进行自己的比较。查看 NSSet 文档。

另一种方法是向实现 isEqual: 的 NSValue 添加一个类别。在这种情况下，我更喜欢子类化，因为它是一个更受限制的解决方案。

Answer 5

这不仅仅是 -isEqual: 的问题，您也可能有 -hash 方法。如果您想使用 NSSet，您可能应该创建一个包装 CGPoint 的自定义类。 -isEqual: 就很简单了，-hash 可以通过某种方法来实现，将两个坐标的位组合起来，然后将它们视为 NSUInteger。

您还需要实现 NSCopying 协议，如果您的点是不可变的（只需在 -copyWithZone: 中保留并返回 self ），该协议也很简单。