android - iOS 和 Android 测试单词正确性的效率

Question

我有一个依赖于单词的应用程序想法...我仍处于游戏设计阶段，并且担心测试单词的正确性。根据我的研究，一个英语单词数据库大约有 50K+。

考虑到 iPhone、iPad 或 Android 的强大功能，我是否需要为这些数据创建某种树形哈希，或者一个数组就足够了？我以前从未真正接触过这么大的东西......

我知道ios有一个搜索数组的方法...

BOOL isTheObjectThere = [myArray containsObject: @"my string"];

这会让我的生活变得轻松，但我不确定这在现实世界中是否有效。

接下来几个月我都没有 Android 或 iOS 的开发环境，我的主要平台将是 iOS，然后是 Android，因此使用 Objective-C 代码引用。

第一次回答后编辑:

我找到了 objective-c 的二进制搜索方法，一旦我对我的开发环境进行排序，肯定会试一试。

NSArray *sortedArray = ... // must be sorted
id searchObject = ...
NSRange searchRange = NSMakeRange(0, [sortedArray count]);
NSUInteger findIndex = [sortedArray indexOfObject:searchObject 
                                    inSortedRange:searchRange
                                    options:NSBinarySearchingFirstEqual
                                        usingComparator:^(id obj1, id obj2)
                                        {
                                            return [obj1 compare:obj2];
                                        }];

Answer 1

平台对您的问题并不重要。

如果您将字典存储在按字母顺序排序的数组中，那么您可以在 O(log n) 中测试一个单词，这对于 n=50k 大约需要 15 个步骤。