Android - оптимизируйте запуск приложения - PullRequest
Новая
       21

Android - оптимизируйте запуск приложения

0 голосов
/ 21 июня 2011

РЕДАКТИРОВАТЬ:

Я следовал вашим хорошим советам и использовал структуру данных trie для хранения своего словаря. Структура, которую я выбрал, это эта для заинтересованных людей.

Но сейчас у меня есть еще одна проблема: построение моей структуры данных три при каждом запуске моего приложения очень долго! Может быть, мой словарь слишком велик, или, может быть, выбранная мною реализация не подходит для простого словаря.

Так есть ли способ сохранить эту структуру даже после закрытия приложения, например, зарегистрированной базы данных, или, если вы думаете, что проблема вызвана реализацией, вы можете порекомендовать мне другую?

У меня серьезная проблема с проектом моего андроида.

Цель здесь - вычислить все слова, которые можно составить из серии из 6 букв

Для этого в моем BDD есть две таблицы:

  • 'words' с двумя столбцами: '_id'and' mots '
  • и временная таблица 'temp' с такими же столбцами.

'words' содержит все слова из словаря (он огромен), а 'temp' содержит все возможные комбинации букв, которые можно составить из 6 букв (по крайней мере, из 3 букв).

Я пытаюсь выбрать в таблице «temp» слово, которое является реальным, то есть слово, которое находится в таблице «words». Вот мой код для этого:

Я делаю первый выбор слов, которые содержат хорошие буквы (используются как минимум 3 буквы) 

db.execSQL("CREATE TABLE temp2 (_id integer primary key autoincrement, mots text not null);");
db.execSQL("INSERT INTO temp2 (_id, mots) SELECT * FROM words WHERE mots like '%"+lettres.tab_char.get(0)+"%' OR mots like '%"+lettres.tab_char.get(1)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(2)+"%' OR mots like '%"+lettres.tab_char.get(3)+"%' OR mots like '%"+lettres.tab_char.get(4)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(5)+"%';");

(lettre.tab_char - это ArrayList (Character), который содержит буквы, используемые для создания комбинаций в temp)

Я делаю соединение между таблицами 'temp2' и 'temp': 

String MY_QUERY = "SELECT temp2._id, temp2.mots FROM temp2 INNER JOIN temp ON temp2.mots = temp.mots;";
Cursor test =  db.rawQuery(MY_QUERY, null);

После этого я помещаю свои значения в список.

Это работает, но действительно очень медленно: не могли бы вы помочь мне, пожалуйста?

Ответы [ 2 ]

1 голос
/ 21 июня 2011

Алгоритм, который вы ищете, на самом деле называется " trie " (сокращение от re trie val).Они чрезвычайно хорошо подходят для такого рода расчетов (Android фактически использует их в приложениях SMS и почты для выполнения таких операций, как замена смайликов).Если все сделано правильно, вы будете удивлены производительностью, которую вы можете получить от него.Я согласен с Полом: вы определенно не должны делать запрос, как в данный момент.Фактически, многие реализации даже загружают весь файл словаря в файл в памяти и используют этот файл для поиска и проверки слов в течение всего времени жизни приложения.Список слов скрэббл (ссылка также содержится в следующем вопросе: twl06.zip ) занимает всего 1,9 МБ и содержит 178 тыс. Слов.Время в памяти должно быть намного меньше, чем 1,9 МБ, поскольку несколько слов будут иметь общие префиксы (например, «лестница» и «взгляд» будут иметь общий префикс STA, который затем разветвляется на два листа [«I» и«R»], и так далее ...)

Вот хорошее место для начала: Алгоритм генерации анаграмм

1 голос
/ 21 июня 2011

В целом используемый вами алгоритм действительно неэффективен.Сначала вы просматриваете каждую запись 6 раз, используя подстановочный знак, а затем снова соединяете этот гигантский результат со всем вашим набором данных.

SQL, вероятно, не является подходящим местом для этого.SQL хорош в запросах, это скорее расчет.Выполните сопоставление в коде.

Существует множество способов выполнить это, но поиск правильного решения зависит от ваших требований.Могут ли буквы повторяться?Насколько большой словарный запас "огромный"?Это все еще вписывается в несколько МБ?Должен ли этот поиск происходить почти мгновенно?

Обновление:

Учитывая ваши требования, я должен согласиться с Джо.Это действительно больше структура данных, чем алгоритм, но путь - это путь.При загрузке приложения вы сможете создать трижды, и тогда каждое "совпадение" будет довольно простым поиском, идущим вниз по трию.

...