Сериализация структуры с указателями на NSData

Question

Мне нужно добавить некоторую функциональность архивирования в реализацию Objective-C Trie ( NDTrie на 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?), Но я понятия не имею, как работать с NSData и структура C, содержащая указатели.

Производительность при десериализации полученного объекта будет иметь решающее значение, поскольку это проект iPhone, и мне нужно будет загружать его в фоновом режиме при каждом запуске приложения.

Каков наилучший способ достичь этого?

Спасибо!

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 для архивирования и разархивирования этих объектов.

Если после реализации вышеуказанного и профилирования вашего кода вы обнаружите, что производительность является проблемой, вы можете начать оптимизацию. Например, при доступе к ivars с использованием указателя на структуру C, например,

aTrieNode->parent;

или путем замены NSArray на массив C и т. Д.

Answer 2

Предполагая, что вам нужно придерживаться прямой C, потому что это то, как все уже настроено, то, что вам нужно сделать, на самом деле довольно просто.

Просто напишите функцию C, чтобы записать ваше дерево на диск, с некоторым предположением о порядке упорядочения (например, вы пишете нашу глубину сначала слева направо). Для любых объектов Objective C закодируйте их в NSData и запишите их размер и байты как часть вашего потока.

Когда вы читаете данные обратно, просто воссоздайте дерево, основываясь на ваших предположениях о порядке упорядочения, и устанавливайте указатели на детей. Разархивируйте любой из вложенных объектов Objective-C соответствующим образом.

Вероятно, вы можете как-то сделать это с NSCoder, но может быть проще выполнить реконструкцию дерева вне этого, так как вы можете перебирать дерево, передавая любые аргументы, которые вам нравятся, что на самом деле не очень легко с NSCoding. *

У меня есть некоторый код (Desktop OS X), который делает что-то очень похожее на это без встроенных объектов, но это довольно неудобно, и я не могу опубликовать его.

Одна оптимизация в этом коде состоит в том, чтобы считывать данные во внутренний буфер, кусками МБ (а не небольшим количеством байтов за раз для каждой структуры), а затем читать данные из этого буфера, хотя я Я не уверен, что когда-либо тестировался, и это может или не может иметь существенное значение на iPhone в любом случае. Похоже, что есть аналогичная оптимизация для записи, которая, как я понимаю, скорее всего будет выигрышной (записи iPhone стоят дорого, или я так слышал).

Answer 3

Я думаю, что вы должны реализовать протокол NSCoding: в вашем initWithCoder: создайте NSArray со всеми children и перераспределите такой массив структуры в encodeWithCoder:.

Таким образом, вы сможетеиспользовать оригинальный массив struct в остальной части проекта.

Answer 4

Сначала вы всегда должны попробовать легкий путь:

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

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

Если это на самом деле недостаточно быстро, вы можете посмотреть сериализацию базовых структур вручную.

Edit:

Вы ясно дали понять, что объем данных требует оптимизированной реализации.

Я бы предложил переписать структуру trieNode и получить доступ к методам, чтобы использовать индексы вместо указателей для полей parent и children. Индексы будут указывать на один большой массив C структур trieNode, где все узлы распределены.

Этот массив C может храниться в объекте NSData в обертывающем объекте NDTrie. Сериализация и десериализация в этом случае означают только сохранение / загрузку объекта NSData (без учета порядка байтов).