Оптимизация скорости [поиска] приложений на примере FAppSter для Android

Приветствую Вас, читатели хабра,

начну с небольшой предыстории — с описания проблемы, а далее продолжу тем, как я проблему решал.

Я, как гордый обладатель андроид-телефона, очень рад открытости системы и возможности ставить туда множество приложений как из разных маркетов, так и скачанных откуда-то. В среднем на моём старом добром Galaxy Note около 150 приложений, большинством из которых я периодически пользуюсь.

С чувством, что чем больше коров приложений, тем больше молока пользы от моего телефона, я заметил, что кучу времени я провожу в листаниях от экрана к экрану в поисках иконки нужного приложения. Когда коров программ мало, тогда их легче найти. Их можно поставить на домашний экран или разнести по папочкам. Всё это хорошо и удобно, если используются 20-30 приложений.
Но раз уж я отношусь к категории хэви-юзеров, то начал искать быстрый метод поиска приложений.

Требования к решению проблемы довольно просты:
поиск должен быть быстрым и ресурсосберегающим (процессор, батарея), а также всё должно происходить автоматически — я не хочу ничего сам устанавливать, сортировать или распихивать по папкам.

Для решения поставленной задачи начал искать приложение для быстрого поиска и нашёл в маркете несколько аппликаций для поиска и запуска приложений, но у всех у них были различные недостатки, особенно в поиске, поэтому пришлось довольствоваться стандартным андроидным поиском от Google. Он был конечно медленноват, но искал неплохо и находил, что нужно.

В какой-то момент после апдейта на андроид 4.1 на смену поиску пришёл Google Now, который вдруг перестал работать без соединения с интернетом (возможно только у меня?), жутко начал грызть батарею и предлагать мне поездки, куда я вовсе ехать и не хочу. Только вот искать программы совсем перестал.

С мыслью: «Ээх, гугл, что ж с тобой стало — менеджеры по сбору личных данных заменили разработчиков» стал искать другие программы, но окромя сплошных лаунчеров, которые надо самому настраивать, ничего не нашёл (возможно не по тем словам искал).

Ну раз ничего нет, что же делать, я и сам копать траншею по клавишам в IDE бить умею, думаю, там делов-то на день, сделаю сам себе удобную прогу — как говорится: «Лучше день потерять, а потом за час долететь».

Главное условие: нахождение результата должно происходить быстро.

Вот об этом и поговорю в этой статье (чтоб не скучно было, текст будет периодически сопровождаться кодом)
Всё, что написано не ново, а скорее является подборкой того, на что нужно обращать внимание для улучшения быстродействия программ.
В качестве наглядного примера приведена конкретная программа, написанная в Java для ОС Андроид, но приведённые аспекты распространяются и на другие среды.

Основное действие в желаемой программе — это поиск других программ по введённому ключевому слову, т.е. поиск в метаданных других приложений.
Запрос этих данных от операционки не представляет больших проблем:

Intent i=new Intent(Intent.ACTION_MAIN, null); i.addCategory(Intent.CATEGORY_LAUNCHER);  final List<ResolveInfo> apps = context.getPackageManager().queryIntentActivities(i, 0); 

0. Самое простое решение — линейный поиск

На самом деле- пробегаем по списочку и всё, что нашлось, показываем пользователю.
И вот оно — дерево торможение. При 150 программах такой поиск занимает несколько секунд.
Ну это и логично при сложности О(n), что означает в худшем случае 150 операций сравнения до нахождения, а это не есть хорошо, хотелось бы всё-таки О(log(n)). Как мы все знаем, при поиске такую сложность нам дают деревья (не буду вдаваться какие деревья дают при поиске какую сложность, но хорошая табличка здесь).
Вывод: не используйте линейный поиск, если у вас много элементов.

1. Быстрое решение — поиск с помощью деревьев

а) Большинство деревьев работает при поиске информации со сложностью O(log(n)), т.е. для 150 элементов в среднем нужны чуть больше двух операций. Такое улучшение почти в 50-70 раз меня устроило (а если учесть, что поиск происходит в нескольких полях, то улучшение в тысячи раз).
Вывод: если хотите искать что-то в неструктурированной информации — запаситесь временем или всё же структурируйте информацию.

б) Где же взять это самое дерево? Сначала нужно произвести постройку дерева из имеющейся информации — этот процесс называют индексированием. Здесь и скрывается большое НО: это самое индексирование может занимать от O(n log(n)) до, о боже, O(n^2).
Вывод: не забывайте о том, что при «Лучше день потерять, а потом за час долететь» вначале день вы всё же теряете, поэтому занимайтесь индексированием, только если данных много, искать собираетесь часто и данные меняются редко (это же действует и для данных в хэш-таблицах и сортированных списках).

в) Из чисто мазохистских побуждений я конечно пару дней поэкспериментировал с имплементированием своего собственного индексирования, получив желаемое дерево с ускорением процесса поиска. Правда после тестирования собственного дерева, решил сравнить его по скорости с индексами из Sqlite — результаты были далеко не в пользу моей имплементации (думаю здесь видна медленность Java по сравнению с имплементацией Sqlite в С). Решил всё-таки использовать Sqlite.
Вывод: не надо изобретать колесо — используйте для индексов готовые быстрые решения, написанные в нативных языках.

2. Вывод данных из базы

Следующая серьёзная потеря времени происходит при выводе данных из базы.
Дело в том, что деревья/индексы лишь содержат указатели на нужные данные, которые теперь нужно прочитать и транспортировать туда, откуда они были запрошены. На этом месте оптимировать получится только засчёт уменьшения количества данных на выходе, что конкретно означает, что

SELECT * FROM data

— это зло, которое расходует системные ресурсы (память и процессорные такты для аллокации и сборщика мусора).
Вывод: указывайте конкретно столбцы, которые Вам нужны, иначе ненужные Вам данные блокируют ресурсы.

3. Память или быстродействие

Решите, что Вам важнее в программе: небольшой расход тактов процессора или маленький расход памяти. Последнее имеет приоритет в редких случаях, когда памяти просто мало. Если программа постоянно работает на заднем фоне, то важны оба фактора. В большинстве случаев первый фактор важнее: чем меньше операций Ваша программа выполняет, тем быстрее она работает, а значит остаётся больше тактов для других приложений. Если уже запрошенная/посчитанная/найденная информация не изменяется и понадобится снова, её лучше кэшировать, чтобы не использовать процессор вторично для подсчёта того, что уже было подсчитано.

Теперь рассмотрим как конкретно в нашем случае такое кэширование способствует улучшению быстродействия:

а) при ожидаемом повторном применении данных, полученных в определённых участках кода (циклы, функции), выгоднее сохранять полученный результат. Например:

static int[] a=new int[1000]; for(int i=0;i<a.length;i++){ ... } // 1.  for(int i=0,len=a.length;i<len;i++){ ... }  // 2.  for(int i:a){ ... } // 3. 

Если сравнить вариант 1 и 2, то вариант 2 — быстрее, потому что экономит пару операций по экстракции значения length из объекта a, хотя в данном случае это некритично из-за прямого доступа к переменной. Если это была бы функция length(), тогда всё было бы намного печальнее в варианте 1 (в интерпретированных языках точно печально, в компилированных — зависит от компайлера: он может эту печальку увидеть и оптимировать, а может и нет). Я бы назвал первый вариант табу.

В документации к андроиду гугл настойчиво просит употреблять вариант 3, что наталкивает меня на мысль, что int[] имплементирован как List, а не как Array, поэтому применение итератора даёт преимущества в скорости.
Вывод: в зависимости от языка программирования следует посмотреть в документацию и узнать какой способ рекомендуется. Для Array обычно вариант 2, для List обычно вариант 3.

Дальнейшие оптимизации зависят от языка программирования, но стоит помнить, что каждое применение функций означает работу со стэком (конечно исключая си-шные inline функции). Другие микрооптимизации в этом месте приводить не буду (может быть тема для другой статьи).
Такое микрооптимирование кажется чем-то ненужным, но если подумать, что при больших количествах повторных выполнений этот участок замедляется порой в 1000 раз из-за неправильного кода, то улучшение заметно.

б) в нашем случае помимо текстовой информации о приложениях выводится также и иконка приложения.
Обычно она запрашивается через функцию loadIcon(), но этот запрос ищет иконку в пакетах приложений, что длится дольше, чем запросить её из базы данных. Поэтому во время индексирования, добавим также и иконки в Sqlite базу. Опять же налицо выбор между быстродействием и расходом памяти: более быстрое выполнение требует кэширования и характеризуется дополнительным расходом памяти.
Вывод: кэширование даёт плюсы не только при микрооптимировании, но также и при макрооптимировании

4. Графическая оболочка

Одна сторона медали — это поиск информации, другая — что происходит в это время в графической оболочке.
Взаимодействие с пользователем не влияет напрямую на скорость выполнения задачи, но даёт ему ощущение того, «тормозит» ли программа или «летает». Прежде всего это ощущение обусловлено реакцией программы на действия пользователя. То есть действие программы должно проходить по образцу:

клик -> изменение оболочки -> запуск длительной операции -> получение результатов -> изменение оболочки

вместо

клик -> запуск длительной операции -> получение результатов -> изменение оболочки

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

a) Отделение длительной операции поиска от треда, в котором работает графическая оболочка.
Современные процессоры содержат несколько ядер и обработка параллельных задач для них не составляет труда.
Выделение в отдельный тред в зависимости от системы может происходить различными способами, самый простой — использование асинхронных функций (которые часто имеют в названии окончание Async). Если же функция своя, то её можно параллелизировать различными способами, в андроиде например через AsyncTask, Handler или даже Timer.

Применение AsyncTask выглядит примерно так:

public class Run extends AsyncTask<Context, Integer, Boolean> {     @Override     protected Boolean doInBackground(Context... arg0) { ... }      @Override     protected void onPostExecute(Boolean result) {         super.onPostExecute(result);         // do something or catch by listener     } }  Run r=new Run();r.execute(this); 

Применение Handler попроще, но и возможностей поменьше:

private final Handler hRefresh = new Handler(); private final Runnable runRefreshData = new Runnable() {         @Override         public void run() { ... }     };  hRefresh.post(runRefreshData);  // or hRefresh.postDelayed(runRefreshData,100); 

Timer и стандартный Java Thread рассматривать здесь не буду.

б) опционально можно при помощи анимации графической оболочки скрывать задержки, вызванные поиском информации в процессе заднего плана (если такой процесс длится не дольше 1 секунды). Например, чтобы спрятать процесс записи сделанной фотографии в память, на экране показывается секундная анимация.

в) более длительные процессы потребуют анимацию ожидания или указатель прогресса (например во время индексирования). Самое важное в данном случае опять же, чтоб действие в графической оболочке не прекращалось.

Вывод: графическая оболочка даёт пользователю чувство, что всё работает быстро, даже если обработка занимает определённое время

5. Логика приложения

Очень важно чётко представлять логику программы — в каком именно месте важна быстрота:

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

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

@Override     public void onCreate(Bundle savedInstanceState) {         super.onCreate(savedInstanceState);         Debug.startMethodTracing("OnCreate");         setContentView(R.layout.a_main);         ...         Debug.stopMethodTracing();     }

@Override     public void onResume() {         super.onResume();         Debug.startMethodTracing("OnResume");         ...         Debug.stopMethodTracing();     }

В результате анализа FAppSter получились такие результаты

OnCreate:

OnResume:

Т.е. в нашем случае и в OnCreate, и в OnResume больше 80% времени заняты загрузкой, подсчётом и рисованием графических элементов. Чем их больше и чем сложнее их структура и расположение, тем больше требуется пересчётов в координаты на экране. Особенно использование адаптивного дизайна с шириной/высотой указанной в android:weight="" требует повышенных затрат во время построения графики. Эту проблему можно решить, используя различные файлы разметки для разных размеров экранов, вместо одного, приспособляющегося. Это конечно увеличит размер конечного .apk-файла, но одновременно увеличит скорость запуска приложения.
Каюсь: этот момент ещё не полностью удовлетворён, но он прочно закреплён в плане действий

Другой аспект представляют из себя скрытые элементы оболочки, которые будут показаны пользователю только при определённых условиях. Для экономии времени при загрузке таких элементов в андроиде используется ViewStub. Taк, например, в FAppSter’е есть возможность переключения между разными клавиатурами, а также между сеткой и списком. Всё, что в данный момент может не понадобиться, пакуем в файле разметки в ViewStub:

<ViewStub             android:id="@+id/stub_lv_sugg"             android:inflatedId="@+id/lv_sugg"             android:layout="@layout/a_main_lv_sugg"             android:layout_width="wrap_content"             android:layout_height="wrap_content"/>

а в программном коде используем вместо lvSugg=(ListView)findViewById(R.id.lv_sugg);

if (lvSugg == null) {             lvSugg = (ListView) ((ViewStub) findViewById(R.id.stub_lv_sugg)).inflate(); }

Вывод: при сложных графических оболочках, много времени при старте андроид-приложения тратится на загрузку графических элементов, которую стоит оптимировать

б) Логика использования программы
В разных приложениях эта логика разная, но конкретно на примере FAppSter основная цель — уменьшить время нахождения желаемой программы. Значительное уменьшение этого времени по сравнению с той же стандартной поисковой строкой, добился засчёт следующих умозаключений:

• Если вводить полное название и потом искать результат, то сам процесс ввода занимает много времени и склонен к ошибкам
• Если использовать выпадающий автоматический список autocomplete по мере ввода, то количество ошибок при вводе уменьшается и скорость нахождения возрастает
• Если показывать результаты уже по мере ввода, сортируя их по приоритету, то вероятность более быстрого нахождения цели возрастает
• Если заменить стандартную клавиатуру, и уменьшить количество кнопок до латиницы, то вероятность попадания по неправильной кнопке уменьшается
• Если использовать принцип навигационной системы и деактивировать кнопки по мере ввода, то вероятность ошибок уменьшается
• Если объединить кнопки в клавиатуре, тем самым уменьшив её, то вероятность попадания по неправильной клавише уменьшается (по типу T9)
• Если искать информацию о программе не только в названии, но и в других метаданных, то вероятность нахождения программы не зная названия возрастает
• Если русские названия преобразовывать с помощью транслита, то возможен также поиск названий на русском языке
• Если разрешить пользователям вручную добавлять ключевые слова к программам, то возможна персонализация поиска

Это то, что уже заимплементировано.
Программа сделана для себя, поэтому бесплатная и без рекламы — качайте, кому нужно. Можете также распространять APK.
Если у кого-то есть идеи по улучшению — пишите на английском на официальную страницу.
Или на русском пишите в группу ВКонтакте.

На самом деле у меня и у самого ещё много идей, как улучшить поиск, но к сожалению свободного времени пока не хватает, нужно ведь ещё работать за деньги на дядю. Так что мгновенного имплементирования пожеланий не ждите, но по возможности пожелания добавляю и на вопросы отвечаю ;)

Заключение

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

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