Структуры данных Objective-C (Создание собственной DAWG) - PullRequest
Новая
       16

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

11 голосов
/ 24 октября 2011

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

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

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

1 Ответ

3 голосов
/ 25 октября 2011

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

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

пытаетесь понять, как это сделать в чистом 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, и вам нужно только исправить некоторые заголовочные файлы.

...