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

Question

经过长时间(20多年)的编程后,我正试图重新开始.我的第一个真正的尝试是Scrabble/Words With Friends求解/骗子(选择你的定义).我已经建立了一个非常好的引擎,但它通过蛮力而不是效率或优雅来解决问题.经过大量研究后,很明显这个问题的最佳答案是DAWG或CDWAG.我已经在那里找到了一些C实现并且能够利用它们(对于相同的数据集,搜索时间从1.5s变为.005s).

但是,我试图弄清楚如何在纯Objective-C中做到这一点.在那,我也试图使其符合ARC标准.并且足够有效的iPhone.我看了很多,发现了几个数据结构库(即CHDataStructures),但它们主要是C/Objective-C混合,或者它们不符合ARC.他们非常依赖结构并将结构嵌入结构中.ARC并不真正关心它.

所以 - 我的问题是(对不起,我明白,如果这是tl;博士,如果它似乎完全是一个新问题 - 只是无法理解这个对象的东西)你如何编程经典数据结构(树等)在Objective-C中从头开始？我不想依赖NS [Mutable] {Array,Set等}.有没有人有一个简单/基本的树实现或类似的东西,我可以创建我的DAWG？

Answer 1

为什么在你开始走路之前就搬起石头砸自己的脚呢？

你说你是

试图弄清楚如何在纯 Objective-C 中做到这一点

然而你

不想依赖 NS[Mutable]{Array,Set,etc}

另外，你想使用ARC，还是不想使用ARC？如果您坚持使用 Objective-C，那么就使用 ARC，如果您不想使用 Foundation 集合，那么不使用 ARC 可能会更好。

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

至于其他不兼容 ARC 的库：如果您遵循ARC 设置的一些规则，您可以很容易地使它们兼容。这是否值得在很大程度上取决于第三方代码库的大小。

特别是，从 void* 到 id 的转换（反之亦然）需要桥接转换，因此您可以编写：

void* pointer = (__bridge void*)myObjCObject;

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