Сериализируйте структуру с указателями на NSData
Я должен добавить некоторую функциональность архивации к 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, и я должен буду загрузить его в фоновом режиме каждый раз, когда приложение запускается.
Каков был бы лучший способ достигнуть этого?
Спасибо!
4 ответа
Предполагая, что вам нужно придерживаться прямого C, потому что именно так все уже настроено, то, что вам нужно сделать, на самом деле довольно просто.
Просто напишите функцию C для записи вашего дерева на диск с некоторыми предположениями о порядке (например, вы сначала пишете нашу глубину слева направо). Для любых объектов Objective-C закодируйте их в NSData и запишите их размер и байты как часть вашего потока.
Когда вы считываете данные обратно, просто восстановите дерево на основе ваших предположений о порядке и установите указатели на дочерние элементы. Разархивируйте любой из встроенных объектов Objective-C, если это необходимо.
Вы, вероятно, можете как-то сделать это с помощью NSCoder, но, возможно, будет проще выполнить реконструкцию дерева вне этого, поскольку вы можете рекурсивно перемещаться по дереву, передавая любые аргументы, которые вам нравятся, что на самом деле не очень просто с NSCoding.
У меня есть некоторый (Desktop OS X) код, который делает что-то очень похожее на это, без встроенных объектов, но это довольно неудобно, и я не могу его опубликовать.
Одной из оптимизаций этого кода является чтение данных во внутренний буфер блоками МБ (а не по небольшому количеству байтов за раз для каждой структуры), а затем чтение данных из этого буфера, хотя я Я не уверен, что это когда-либо проводилось, и в любом случае это может иметь или не иметь существенного значения для iPhone. Похоже, есть аналогичная оптимизация для записи, которая, как я понимаю, с большей вероятностью будет выигрышной (запись на iPhone стоит дорого, или я так слышал).
Переопределите структуру узла дерева как объектный класс 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 и т. Д.
Я думаю, вам следует реализовать протокол NSCoding: в вашем initWithCoder: создать NSArray со всеми детьми и перераспределить такой массив struct в encodeWithCoder:.
Таким образом, вы сможете использовать исходный массив struct в остальной части проекта.
Вы всегда должны сначала попробовать простой способ:
// serializing:
[myTrie writeToFile:myPath atomically:NO];
// deserializing
NDTrie* myTrie = [NDTrie trieWithContentsOfFile:myPath];
Если это действительно недостаточно быстро, вы можете вручную сериализовать базовые структуры.
Редактировать:
Вы дали понять, что объем данных требует оптимизированной реализации.
Я предлагаю переписать структуру trieNode и методы доступа, чтобы использовать индексы вместо указателей для полей родительского и дочернего . Индексы будут указывать на один большой массив C структур trieNode, из которого распределены все узлы.
Этот массив C может храниться в объекте NSData в объекте-оболочке NDTrie . Тогда сериализация и десериализация будут означать просто сохранить / загрузить объект NSData (не считая проблем с порядком байтов).