#iphone #objective-c #automatic-ref-counting #chdatastructures
#iPhone #objective-c #автоматический подсчет ссылок #chdatastructures
Вопрос:
После долгого, долгого времени (более 20 лет) без программирования Я пытаюсь вернуться к этому. Моя первая настоящая попытка — это решатель / читер в стиле Scrabble / Words With Friends (выберите свое определение). Я создал довольно хороший движок, но он решает проблемы с помощью грубой силы, а не эффективности или элегантности. После долгих исследований совершенно ясно, что лучшим решением этой проблемы является DAWG или CDWAG. Я нашел там несколько реализаций C и смог их использовать (время поиска увеличилось с 1,5 с до 0,005 с для одних и тех же наборов данных).
Тем не менее, я пытаюсь выяснить, как это сделать в чистом Objective-C. При этом я также пытаюсь сделать его совместимым с ARC. И достаточно эффективен для iPhone. Я немного поискал и нашел несколько библиотек структур данных (например, CHDataStructures ), но в основном это гибриды C / Objective-C или они не совместимы с ARC. Они очень сильно зависят от структур и встраивают объекты внутри структур. ARC на самом деле это не волнует.
Итак, мой вопрос (извините, и я понимаю, было ли это tl; dr, и если это кажется совершенно новым вопросом — просто пока не могу разобраться с этим объектом) как вы программируете классические структуры данных (деревья и т. Д.) С нуля в Objective-C? Я не хочу полагаться на NS[Изменяемый] {Массив, набор и т. Д.} . Есть ли у кого-нибудь простая / базовая реализация дерева или что-нибудь в этом роде, из чего я могу списать, пока я создаю свой DAWG?
Комментарии:
1. Все, что вы можете написать на C, является Objective-C, поскольку Objective-C полностью является надмножеством C. В основном это основано на парадигме ООП, подобной Smalltalk, которая, похоже, неприменима к этой проблеме.
2. Понятно и извините, если я не сделал это очевидным в моем первоначальном вопросе. Я понимаю, что я мог бы реализовать DAWG как «вещь» C, а затем обернуть материал Objective-C вокруг этого, чтобы вставить / перечислить / сериализовать / и т.д. Однако в качестве упражнения я хочу создать чисто объектно-ориентированную реализацию. Поверьте мне, я понимаю, что это не оптимально, скорее всего, не обеспечит самую быструю реализацию или даже самую экономичную. Тем не менее, это научит меня и других, как заставить работать объектную структуру данных. Чисто дидактический.
3. @outis: ARC = автоматический подсчет ссылок.
4. Рассматривали ли вы возможность использования GADDAG вместо DAWG? Обычно это в два раза быстрее, чем традиционные алгоритмы DAWG, но занимает примерно в 5 раз больше места для стандартных словарей Scrabble.
5. Я сделал, но из того, что я видел об алгоритме — его в два раза сложнее реализовать, и я не уверен, что 5x памяти для приложения iphone подходит. Тем более, что скорость в 2 раза выше, и я не делаю так много поисковых запросов.
Ответ №1:
Зачем стрелять себе в ногу, прежде чем вы даже начали ходить?
Вы говорите, что вы
пытаюсь выяснить, как это сделать в чистом Objective-C
тем не менее, вы
не хочу полагаться на NS [Изменяемый] {Массив, набор и т. Д.}
Кроме того, вы хотите использовать ARC или не хотите использовать ARC? Если вы придерживаетесь Objective-C, тогда используйте ARC, если вы не хотите использовать коллекции Foundation, тогда вам, вероятно, лучше обойтись без ARC.
Мое предложение: используйте NS [Mutable] {Array, Set и т. Д.} И Заставьте ваш базовый алгоритм работать с ARC. Это должно быть вашей первой и единственной целью, все остальное — преждевременная оптимизация. Особенно, если ваша цель — «вернуться к программированию», а не писать максимально быстрый анализатор и решатель Scrabble. Если позже вы обнаружите, что вам нужно оптимизировать, у вас есть рабочий код, который вы можете проанализировать на наличие узких мест, и, если потребуется, вы все равно сможете заменить базовые коллекции.
Что касается других библиотек, не совместимых с ARC: вы можете довольно легко сделать их совместимыми, если будете следовать некоторым правилам, установленным ARC. Стоит ли это того, во многом зависит от размера сторонней кодовой базы.
В частности, для преобразования void * в id и наоборот требуется мостовое приведение, поэтому вы бы написали:
void* pointer = (__bridge void*)myObjCObject;
Аналогично, если вы помечаете все указатели в структурах C как __unsafe_unretained
вы должны иметь возможность использовать код C как есть. Еще лучше: если код C может быть собран как статическая библиотека, вы можете создать его с выключенным ARC и нужно только исправить некоторые заголовочные файлы.
Комментарии:
1. Действительно ценю ответ. Дело в том, что я заставил его работать со встроенным встроенным NS [типом данных] — двумя разными способами. Один из них был с грубым перечислением, поэтому я мог использовать «.» в качестве подстановочного знака. Другой был с хэшем в NSDictionary с элементами NSMutableArray. Первый медленный, второй очень быстрый, но не дает мне простой реализации подстановочных знаков. Следовательно, пытаюсь создать DAWG. Итак, я пытаюсь построить дерево только из объектов Objective-C (т. Е. Создать класс «letter», а затем создать DAWG связанных объектов «letter»). Я лаю не на то дерево?
2. Вы уже смотрели на OFC? У них есть 3 разные версии коллекции деревьев. code.google.com/p/ofc
3. Это не тот, который появлялся раньше. Спасибо за указатель. Я сообщу о результатах. Похоже, что это довольно большая база кода для просеивания.
4. Я просмотрел код OFC. Это действительно классная библиотека материалов, но в своем коде она использует структуры с объектами внутри. ARC это не нравится. Так что действительно возникает вопрос — это из-за производительности или потому, что создание связанного списка чистых объектов просто не работает?
5. Любая структура может быть представлена как класс Objective-C. Некоторые могут использовать структуры по привычке, некоторые из соображений производительности, трудно сказать. До недавнего времени никто толком не знал, какие ошибки есть, а какие нет. Я ожидаю, что в будущем все больше и больше библиотек будут совместимы с ARC, хотя бы путем добавления правильных ключевых слов компилятора (__unsafe_unretained id object;).