Objective-C 数据结构（构建我自己的 DAWG）
在很长一段时间（20 多年）没有编程之后，我试图重新开始编程。我的第一次真正的尝试是拼字游戏/Words With Friends 解算器/作弊器（选择你的定义）。我已经构建了一个相当好的引擎，但它通过蛮力而不是效率或优雅来解决问题。经过大量研究，很明显，这个问题的最佳答案是 DAWG 或 CDWAG。我在那里找到了一些 C 实现，并且能够利用它们（对于相同的数据集，搜索时间已从 1.5 秒缩短到 0.005 秒）。
然而，我试图弄清楚如何在纯 Objective-C 中做到这一点。与此同时，我还试图使其符合ARC标准。对于 iPhone 来说足够高效。我看了很多，发现了几个数据结构库（即 CHDataStructures ），但是它们大多是 C/Objective-C 混合体，或者不符合 ARC 标准。它们非常依赖结构并将对象嵌入到结构中。 ARC 并不真正关心这个。
所以 - 我的问题是（抱歉，我明白这是否太长；博士，如果这看起来完全是一个新问题 - 只是我还不能理解这个对象的东西）你如何对经典数据结构（树等）进行编程从头开始使用 Objective-C？我不想依赖 NS[Mutable]{Array,Set,etc}。有没有人有一个简单/基本的树或类似的实现，我可以在创建 DAWG 时从中抄袭？
After not programming for a long, long time (20+ years) I'm trying to get back into it. My first real attempt is a Scrabble/Words With Friends solver/cheater (pick your definition). I've built a pretty good engine, but it's solves the problems through brute force instead of efficiency or elegance. After much research, it's pretty clear that the best answer to this problem is a DAWG or CDWAG. I've found a few C implementations our there and have been able to leverage them (search times have gone from 1.5s to .005s for the same data sets).
However, I'm trying to figure out how to do this in pure Objective-C. At that, I'm also trying to make it ARC compliant. And efficient enough for an iPhone. I've looked quite a bit and found several data structure libraries (i.e. CHDataStructures ) out there, but they are mostly C/Objective-C hybrids or they are not ARC compliant. They rely very heavily on structs and embed objects inside of the structs. ARC doesn't really care for that.
So - my question is (sorry and I understand if this was tl;dr and if it seems totally a newb question - just can't get my head around this object stuff yet) how do you program classical data structures (trees, etc) from scratch in Objective-C? I don't want to rely on a NS[Mutable]{Array,Set,etc}. Does anyone have a simple/basic implementation of a tree or anything like that that I can crib from while I go create my DAWG?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
为什么在你开始走路之前就搬起石头砸自己的脚呢？
你说你是
但你
另外，您想使用 ARC，还是不想使用 ARC？如果您坚持使用 Objective-C，那么就使用 ARC，如果您不想使用 Foundation 集合，那么不使用 ARC 可能会更好。
我的建议：使用 NS[Mutable]{Array,Set,etc} 并让你的基本算法与 ARC 一起使用。这应该是你的首要也是唯一的目标，其他一切都是过早的优化。特别是如果您的目标是“重新开始编程”而不是编写最快的拼字游戏分析器和拼字游戏。求解器。如果您后来发现需要优化，您有一些可以分析瓶颈的工作代码，如果需要，您仍然可以替换 Foundation 集合。
至于其他不兼容 ARC 的库：如果您遵循一些 ARC 设置的规则。这是否值得在很大程度上取决于第三方代码库的大小。
特别是，从 void* 到 id 的转换需要桥接转换，因此您可以编写：
类似地，如果您将 C 结构中的所有指针标记为 __unsafe_unretained ，您应该能够使用 C 代码照原样。更好的是：如果 C 代码可以构建为静态库，则可以在关闭 ARC 的情况下构建它，并且只需要修复一些头文件。
Why shoot yourself in the foot before you even started walking?
You say you're
yet you
Also, do you want to use ARC, or do you not want to use ARC? If you stick with Objective-C then go with ARC, if you don't want to use the Foundation collections, then you're probably better off without ARC.
My suggestion: do use NS[Mutable]{Array,Set,etc} and get your basic algorithm working with ARC. That should be your first and only goal, everything else is premature optimization. Especially if your goal is to "get back into programming" rather than writing the fastest possible Scrabble analyzer & solver. If you later find out you need to optimize, you have some working code that you can analyze for bottlenecks, and if need be, you can then still replace the Foundation collections.
As for the other libraries not being ARC compatible: you can pretty easily make them compatible if you follow some rules set by ARC. Whether that's worthwhile depends a lot on the size of the 3rd party codebase.
In particular, casting from void* to id and vice versa requires a bridged cast, so you would write:
Similarly, if you flag all pointers in C structs as
__unsafe_unretainedyou should be able to use the C code as is. Even better yet: if the C code can be built as a static library, you can build it with ARC turned off and only need to fix some header files.