Objective-C Структуры данных (создание собственного DAWG)

Не программируя в течение долгого, долгого времени (20+ лет), я пытаюсь вернуться к нему. Моя первая реальная попытка - это Scrabble/Words With Friends solver/cheater (выберите свое определение). Я построил неплохой движок, но он решает проблемы с помощью грубой силы вместо эффективности или элегантности. После долгих исследований было довольно ясно, что лучшим ответом на эту проблему является DAWG или CDWAG. Я нашел несколько реализаций C там и смог использовать их (время поиска увеличилось с 1,5 до 0,00 для тех же наборов данных).

Однако, я пытаюсь понять, как это сделать в чистом Objective-C. При этом я также пытаюсь сделать его ARC совместимым. И достаточно для iPhone. Я посмотрел совсем немного и нашел несколько библиотек структуры данных (т.е. CHDataStructures), но они в основном C/Objective-C гибридов или они не совместимы с ARC. Они очень сильно полагаются на структуры и внедряют объекты внутри структур. ARC на самом деле не заботится об этом.

Итак - мой вопрос (извините, и я понимаю, было ли это tl; dr, и если он кажется полностью новым вопросом - просто еще не может окунуться в этот объект), как вы программируете классические структуры данных (деревья, и т.д.) с нуля в Objective-C? Я не хочу полагаться на NS [Mutable] {Array, Set и т.д.}. Кто-нибудь имеет простую/базовую реализацию дерева или что-то в этом роде, из которого я могу свернуть, пока я иду, создаю свой DAWG?

Ответ 1

Зачем стрелять себе в ногу, прежде чем вы даже начнете ходить?

Вы говорите, что вы

пытается выяснить, как это сделать в чистом Objective-C

но вы

не хотят полагаться на NS [Mutable] {Array, Set и т.д.}

Кроме того, вы хотите использовать ARC, или вы не хотите использовать ARC? Если вы придерживаетесь Objective-C, тогда перейдите к ARC, если вы не хотите использовать коллекции Foundation, тогда вам, вероятно, будет лучше без ARC.

Мое предложение: используйте NS [Mutable] {Array, Set и т.д.} и получите базовый алгоритм работы с ARC. Это должно быть вашей первой и единственной целью, все остальное - преждевременная оптимизация. Особенно, если ваша цель - "вернуться к программированию", а не написать быстрый анализатор и решатель Scrabble. Если вы позже узнаете, что вам нужно оптимизировать, у вас есть рабочий код, который вы можете проанализировать для узких мест, и, если нужно, вы можете по-прежнему заменить коллекции Foundation.

Что касается других библиотек, не совместимых с ARC: вы можете легко сделать их совместимыми, если вы выполните некоторые правила установленные ARC. Независимо от того, что это стоит, многое зависит от размера сторонней кодовой базы.

В частности, отбрасывание с void * на id и наоборот требует мостового броска, поэтому вы должны написать:

void* pointer = (__bridge void*)myObjCObject;

Аналогично, если вы указали все указатели в C-структурах как __unsafe_unretained, вы должны использовать код C как есть. Еще лучше: если код C можно создать как статическую библиотеку, вы можете построить его с отключенным ARC и только исправить некоторые файлы заголовков.