Проверьте, что NSString содержит общее имя на iPhone.

. Мне интересно, какой лучший подход должен был бы проверить, содержится ли общее имя в NSString в приложении iPhone. У меня есть отсортированный плоский текстовый файл ~ 5500 обычных американских имен, ограниченных новыми строками. NSString, которую я ищу для имени, не очень длинный, скорее всего, размер обычного предложения.Проверьте, что NSString содержит общее имя на iPhone.

Мой первоначальный план состоял в том, чтобы загрузить отсортированный список в память, а затем перебрать каждое слово в NSString, выполняющее двоичный поиск списка, чтобы определить, было ли это слово общим именем.

Мне лучше попытаться поместить этот список имен в CoreData или таблицу SQLite и выполнить запрос с этим? Я понимаю, что мне не пришлось бы загружать весь список в память, если бы я пошел по этому маршруту.

Я предполагаю, что эта ситуация является распространенной проблемой со словарными словарями для словесных игр, поэтому мне просто интересно, что лучше всего подходит для быстрого поиска. Благодаря!

источник

2011-01-10 Dan Auclair

Можете ли вы уточнить, что вы подразумеваете под «проверкой, содержится ли общее имя в NSString». Означает ли это, что «пользователь по имени Джон вступил», или это означает «Джон»? Другими словами, строка, которую вы проверяете, состоит только из имени, или имя должно быть найдено в строке, содержащей «другое вещество» помимо имени? Это может повлиять на выбранный подход. Кроме того, «как быстро» вам нужно это сделать? – johne

Это имя должно быть найдено в строке, которая содержит «другое вещество» помимо имени. Строка не длинная, стандартное предложение может составлять 50 - 100 символов. Хотелось бы как можно быстрее, но я понимаю, что есть компромисс с памятью. –

Ну, если скорость была проблемой, я бы, вероятно, построил DFA из ~ 5500 имен на лету. Вы можете сериализовать DFA в энергонезависимой памяти, если вам нужно. DFA должен быть знаком с Unicode, вероятно, с UTF8 для удобства.Тогда я бы, вероятно, использовал 'CFStringGetCStringPtr' /' CFStringGetBytes', чтобы захватить копию строки UTF8 и запустить DFA. Производительность будет ~ 'O (n)', где 'n' - размер строки для поиска. – johne

SQLite идеально подходит для этого с точки зрения скорости поиска и минимизации использования памяти. Это также сделало бы возможным, возможно, обновить первый список имен через Интернет, если это необходимо.

Использование базовых данных (на самом деле это оболочка exabourate вокруг SQLite) в этом случае будет излишним, особенно если вы не нуждаетесь в возможностях ORM.

источник

2011-01-10 22:24:00

NSSet также может быть полезен. Dave DeLong's answer для другого вопроса демонстрирует, что NSSets имеют постоянное время поиска, то есть O (1).

Загрузите свои имена в NSMutableSet по одному. Это будет самая медленная часть, но ее нужно будет сделать только один раз. Если ваш файл представляет собой простой файл с именами строк, может быть проще использовать стандартную библиотеку C для чтения файла, так как линейный ввод не поддерживается Cocoa.

После этого просто используйте [nameSet containsObject:name], чтобы проверить, есть ли он в списке.

Пару недостатков такого подхода:

Имя, которое вы хотите проверить, должен быть в том же случае, как имя в наборе, то есть “ Пол ” и “ Paul ” разные строки. Вы можете обойти это путем преобразования всех имен в нижний регистр, прежде чем вставлять их в набор, а затем также преобразовать имя, которое вы хотите проверить, в нижний регистр, прежде чем проверять его на соответствие.
Возможно, было бы проще просто пойти с уже принятым ответом.

источник

2011-01-11 02:55:25 dreamlax

Этот подход кажется мне более понятным, но я думаю, что я иду с SQLite, так что мне не нужно загружать все в память заранее - хотя это может быть не проблема с только 5500 записей. –

@ Joe: Да, почему на земле используется структура данных, предоставленная инфраструктурой, предназначенная для быстрого поиска, когда вы можете наслаждаться накладными расходами SQL-анализатора ничем иным, как чем-то выглядеть в таблице с 1 столбец. – dreamlax

Проверьте, что NSString содержит общее имя на iPhone.

ответ

Смежные вопросы