iphone - Objective-C 数据结构(构建我自己的 DAWG)

Question

在很长很长一段时间(20 多年)没有编程之后，我正试图重新投入其中。我的第一个真正尝试是拼字游戏/Words With Friends 求解器/作弊器(选择您的定义)。我已经构建了一个非常好的引擎，但它是通过蛮力而不是效率或优雅来解决问题的。经过大量研究，很明显这个问题的最佳答案是 DAWG 或 CDWAG。我在那里找到了一些 C 实现并且能够利用它们(对于相同的数据集，搜索时间从 1.5 秒减少到 .005 秒)。

但是，我正在尝试弄清楚如何在纯 Objective-C 中执行此操作。那时，我也在努力做到这一点 ARC合规。并且对于 iPhone 来说足够高效。我看了很多，发现了几个数据结构库(即 CHDataStructures )，但它们大多是 C/Objective-C 混合体，或者它们不符合 ARC。他们非常依赖结构并将对象嵌入到结构中。 ARC 并不关心这个。

所以 - 我的问题是(抱歉，我明白这是否是 tl;dr，如果它看起来完全是一个新问题 - 只是我还不能理解这个对象的东西)你如何编写经典数据结构(树等)在 Objective-C 中从头开始？我不想依赖 NS[Mutable]{Array,Set,etc}。有没有人有一个简单/基本的树或类似的东西的实现，我可以在创建我的 DAWG 时引用？

Answer 1

为什么还没开始走路就搬起石头砸自己的脚？

你说你是

trying to figure out how do this in pure Objective-C

还是你

don't want to rely on a NS[Mutable]{Array,Set,etc}

还有，你是想用ARC，还是不想用ARC？如果您坚持使用 Objective-C 然后使用 ARC，如果您不想使用 Foundation 集合，那么最好不要使用 ARC。

我的建议:使用 NS[Mutable]{Array,Set,etc} 并让你的基本算法与 ARC 一起工作。那应该是您的第一个也是唯一的目标，其他一切都是过早的优化。特别是如果您的目标是“重新开始编程”而不是编写最快的拼字游戏分析器和求解器。如果您后来发现需要优化，您有一些可以分析瓶颈的工作代码，如果需要，您仍然可以替换 Foundation 集合。

至于其他不兼容 ARC 的库:如果您遵循一些 rules set by ARC，您可以很容易地使它们兼容。 .这是否值得在很大程度上取决于第 3 方代码库的大小。

特别是，从 void* 到 id 的转换，反之亦然需要桥接转换，因此您可以这样写:

void* pointer = (__bridge void*)myObjCObject;

同样，如果您将 C 结构中的所有指针标记为 __unsafe_unretained，您应该能够按原样使用 C 代码。更好的是:如果 C 代码可以构建为静态库，您可以在关闭 ARC 的情况下构建它，只需要修复一些头文件。