将带指向NSData的指针的结构体序列化

Question

我需要在 Objective-C Trie 实现（NDTrie on github）中添加某种归档功能，但是我对 C 语言及其数据结构的经验非常有限。

struct trieNode
{
    NSUInteger key;
    NSUInteger count,
    size;
    id object;
    __strong struct trieNode ** children;
    __strong struct trieNode * parent;
};

@interface NDTrie (Private)
- (struct trieNode*)root;
@end

我需要创建一个包含树形结构的NSData - 或者以其他方式序列化/反序列化整个树形结构(符合NSCoding？)，但我不知道如何使用包含指针的C结构和NSData一起工作。

由于这是一个iPhone项目，每次应用程序启动时都需要在后台加载，因此反序列化结果对象的性能非常关键。

最好的方法是什么？

谢谢！

- leolobato

Answer 1

重新实现trie节点结构作为Objective C类。例如：

@interface TrieNode
{
    NSUinteger key;
    NSUInteger count;
    //NSUInteger size; // not needed if you use an NSArray for the children.
    id object;
    NSArray* children;
    TrieNode* parent;
}
// methods
@end

然后，您可以使用标准的Objective-C机制对这些对象进行存档和取消存档。如果在实施上述操作并对代码进行分析后，发现性能存在问题，您可以开始进行优化。例如，通过使用C结构指针访问ivars等方式。

aTrieNode->parent;

或者通过将NSArray替换为C数组等方式。

- JeremyP

---

问题在于我必须重写整个现有的实现，以使用类而不是结构体 - 这就是为什么我正在寻找一种序列化现有结构体的方法，这应该会更快地实现。 - leolobato

对我来说，它似乎并不复杂。只有一个源文件，如果你使用一个类，你可能会发现事情变得更简单。我可能会自己试一下... - JeremyP

Answer 2

假设你需要坚持使用纯C，因为已经设置好了，你需要做的实际上非常简单。

只需编写一个C函数将您的树写入磁盘，并对排序进行一些假设（例如，您按深度优先、从左到右进行编写）。对于任何Objective-C对象，请将它们编码为NSData，并将其大小和字节作为流的一部分写出。

当您读取数据时，只需根据您的排序假设重建树，并设置指向子项的指针。根据需要取消归档嵌入的Objective-C对象。

您可能可以通过NSCoder以某种方式完成此操作，但是在外部进行树重建可能更容易，因为您可以递归下传递任何您喜欢的参数，这在NSCoding中并不是很容易。

我有一些（桌面OS X）代码与此非常相似，没有嵌入式对象，但它非常棘手，我无法发布它。

该代码的一个优化是将数据读入内部缓冲区，以MB块为单位（而不是每个结构体一次读取少量字节），然后从该缓冲区读取数据，尽管我不确定是否进行了基准测试，并且在iPhone上可能或可能不会有显着差异。看起来写入也有类似的优化，这更有可能是一个胜利，据我所知（iPhone的写入很昂贵，或者我听说过）。

- Snydely Whiplash

Answer 3

你应该总是先尝试简单的方法：

// serializing:
[myTrie writeToFile:myPath atomically:NO];

// deserializing
NDTrie* myTrie = [NDTrie trieWithContentsOfFile:myPath];

如果速度还不够快，您可以考虑手动序列化底层结构。

编辑：

您明确表示需要优化实现的数据量。

我建议重写trieNode结构和访问方法，使用索引而不是指针来处理parent和children字段。这些索引将指向一个大的C数组，其中所有节点都是从中分配的trieNode结构。

这个C数组可以保存在包装的NDTrie对象中的NSData对象中。序列化和反序列化只需要保存/加载NSData对象（除了字节顺序问题）。

- Nikolai Ruhe

---

问题在于我的数据集非常大，现在我无法将其适应设备内存中的临时NSArray和实际trie数据结构 - 而且创建这两个结构的速度太慢了。这就是为什么我正在寻找一种跳过此数组重新创建并序列化实际trie模型的方法。 - leolobato

Answer 4

我认为你应该实现NSCoding协议：在你的initWithCoder:中创建一个包含所有children的NSArray，并在encodeWithCoder:中重新分配这样的结构数组。

这样，你就能在项目的其余部分使用原始的结构数组了。

- unixo