Fuzzy NSDictionary - 使用最近的键
我有一个大约 4000 个数字的列表，例如： {10, 20, 30, 40, 50,...}
每个数字都是 NSDictionary 中的一个键，所以我可以获取与数字关联的对象，例如
[NSDictionary objectForKey:[NSNumber numberWithInt:20];
但是如果键不在字典中，我想找到最近的键（假设值之间存在有意义的关系，在我的示例中，10>20>30等） 。
那么例如
[NSDictionary objectForKey:[NSNumberWithInt:19]] would return the value for key:20.
或者是否有另一种数据结构更适合执行此操作？我想过使用排序的 NSArray，其中键是数组索引，然后如果对象为 null，则继续递增数组指针，直到找到对象，但这将导致一个包含 999,999 个元素的稀疏数组:)
谢谢
I have a list of around 4000 numbers e.g: {10, 20, 30, 40, 50,...}
Each number is a key in an NSDictionary, so I can fetch the object associated with a number, e.g.
[NSDictionary objectForKey:[NSNumber numberWithInt:20];
However if the key is not in the dictionary, I'd like to find the nearest key (assuming there is a meaningful relationship between values, in my example, 10>20>30 etc).
So e.g.
[NSDictionary objectForKey:[NSNumberWithInt:19]] would return the value for key:20.
Or is there another data structure that would be more appropriate for doing this? I'd thought of using a sorted NSArray, where the key would be the array index, then if object was null keep incrementing the array pointer until the object is found, however this would result in a sparsly populated array with 999,999 elements :)
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
本质上，您需要保留键的排序列表（NSMutableArray）。要查找键，请使用 NSArray 的
indexOfObject:inSortedRange:options:usingComparator:方法，传入NSBinarySearchingInsertionIndex作为选项，该选项将执行二分搜索，为您提供索引，即使它没有找到确切的元素。您必须自己获取两个密钥并进行比较。Essentially you need to keep a sorted list (NSMutableArray) of keys. To find a key use the
indexOfObject:inSortedRange:options:usingComparator:method of NSArray passing inNSBinarySearchingInsertionIndexas the options which will perform a binary search giving you an index even if it doesnt find the exact element. You'll have to fetch both keys yourself and compare them.假设您的数字列表按升序排列，您可以在数组中进行二分搜索。
因此，在查找键 x 时，您将从索引 array.length/2 开始，将该位置的键与 x 进行比较，如果大于 x 则继续查找左侧部分，如果小于 x 则继续查找右侧部分。继续，直到找到最接近 x 的键。
这非常快（在您的情况下大约是 log(4000) ~ 12 个数组查找）并且不需要额外的存储。
Assuming your list of numbers is in ascending order you could do a binary search in the array.
So when looking for the key x, you would start at index array.length/2, compare the key at that position with x and continue with the left part if it was greater than x or with the right part if it was less than x. Continue until you've found the closest key to x.
Thats very fast (in your case about log(4000) ~ 12 array lookups) and does not need additional storage.