Как стать автором
Обновить
26
0

Android

Отправить сообщение

Алгоритмы на графах — Часть 0: Базовые понятия

Время на прочтение5 мин
Количество просмотров260K

Вступление


Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.
Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.

Читать дальше →
Всего голосов 130: ↑118 и ↓12+106
Комментарии70

Как настроить расширяемую систему для регрессионного тестирования на телефонах: опыт мобильной Почты Mail.Ru

Время на прочтение10 мин
Количество просмотров19K


Привет, Хабр! Сегодня я хочу рассказать, как мы построили с нуля гибкую и расширяемую систему для выполнения автотестов на Android-смартфонах. Сейчас у нас используется около 60 устройств для регрессионного тестирования мобильного приложения Почты Mail.Ru. В среднем они тестируют около 20 сборок приложения ежедневно. Для каждой сборки выполняется около 600 UI-тестов и более 3500 unit-тестов.

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

Мы рассмотрим, как всё делать с самого начала тем, кто занимается написанием автотестов, а не инфраструктурой: начиная от покупки телефона, его перепрошивки и заканчивая созданием docker-контейнеров, внутри которых будет доступен телефон для автотестов.
Читать дальше →
Всего голосов 53: ↑52 и ↓1+51
Комментарии26

Введение в анализ сложности алгоритмов (часть 4)

Время на прочтение5 мин
Количество просмотров98K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1
Часть 2
Часть 3

Оптимальная сортировка


Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n2 ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

Этот финальный раздел — опциональный. Он несколько сложнее, так что можете не стесняясь пропустить его, если хотите.От вас потребуется сфокусироваться и потратить некоторое время на решение упражнений. Однако, так же здесь будет продемонстрирован очень полезный и мощный способ анализа сложности алгоритмов, что, безусловно, стоит внимания.
Читать дальше →
Всего голосов 58: ↑54 и ↓4+50
Комментарии6

Введение в анализ сложности алгоритмов (часть 2)

Время на прочтение11 мин
Количество просмотров169K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1

Сложность


Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.
Читать дальше →
Всего голосов 55: ↑53 и ↓2+51
Комментарии16

Введение в анализ сложности алгоритмов (часть 1)

Время на прочтение10 мин
Количество просмотров379K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Введение


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

Тем не менее, знание теории тоже имеет свои преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Как человек, который работал как в области академической науки, так и над созданием коммерческого ПО, я считаю эти инструменты по-настоящему полезными на практике. Надеюсь, что после прочтения этой статьи вы сможете применить их к собственному коду, чтобы сделать его ещё лучше. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.
Читать дальше →
Всего голосов 106: ↑98 и ↓8+90
Комментарии27

Введение в анализ сложности алгоритмов (часть 3)

Время на прочтение6 мин
Количество просмотров125K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1
Часть 2

Логарифмы


image
Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.
Читать дальше →
Всего голосов 74: ↑60 и ↓14+46
Комментарии4

Garbage Collection наглядно

Время на прочтение10 мин
Количество просмотров284K
В последнее время я работаю с клиентами над вопросами настроек JVM. Смахивает ситуация на то, что далеко не все из разработчиков и администраторов знают о том, как работает garbage collection и о том, как JVM использует память. Поэтому я решил дать вводную в эту тему с наглядным примером. Пост не претендует на то, чтобы покрыть весь объем знаний о garbage collection или настройке JVM (он огромен), ну и, в конце концов, об этом много чего хорошего написано уже в Сети.
Читать дальше →
Всего голосов 70: ↑68 и ↓2+66
Комментарии49

Эффективная работа с SQLite на примере ICQ

Время на прочтение9 мин
Количество просмотров29K
Как и во многих других приложениях, нам в мобильном ICQ приходится хранить достаточно много информации: сообщения, контакты и тому подобное. Когда количество запросов к этим данным достигает какого-то критического значения, приложение начинает тормозить. Долгий запуск, медленное открытие чата, медленная отправка сообщений, постоянные спиннеры — все это жутко напрягает. Чаще всего причиной тормозов является неудачная работа с данными. В статье я хочу поделиться нашим опытом рефакторинга структуры данных, оптимизации запросов и некоторыми удобными приемами для миграции.

Несколько слов об исходной задаче. Основная сущность у нас — профиль ICQ, у которого есть список контактов, а у тех есть сообщения. Наше приложение существует уже много лет, разрабатывалось разными людьми с разными подходами, номер версии основной БД уверенно приближался к 30. Кроме того, количество фич в продукте невозможно предсказать заранее, это тоже повлияло на архитектуру. В общем, модель данных изначально была примерно такой:

Читать дальше →
Всего голосов 50: ↑46 и ↓4+42
Комментарии8

Полиномиальные хеши и их применение

Время на прочтение9 мин
Количество просмотров85K
Здравствуй, хабр. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.

Введение


Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство.
Читать дальше →
Всего голосов 74: ↑69 и ↓5+64
Комментарии41

Размер Java объектов

Время на прочтение5 мин
Количество просмотров188K
Знаете сколько в памяти занимает строка? Каких только я не слышал ответов на этот вопрос, начиная от «не знаю» до «2 байта * количество символов в строке». А сколько тогда занимает пустая строка? А знаете сколько занимает объект класса Integer? А сколько будет занимать Ваш собственный объект класса с тремя Integer полями? Забавно, но ни один мой знакомый Java программист не смог ответить на эти вопросы… Да, большинству из нас это вообще не нужно и никто в реальных java проектах не будет об этом думать. Но это, ведь, как не знать объем двигателя машины на которой Вы ездите. Вы можете быть прекрасным водителем и даже не подозревать о том, что значат цифры 2.4 или 1.6 на вашей машине. Но я уверен, что найдется мало людей, которые не знакомы со значением этих цифр. Так почему же java программисты так мало знают об этой части своего инструмента?

Integer vs int

Все мы знаем, что в java — everything is an object. Кроме, пожалуй, примитивов и ссылок на сами объекты. Давайте рассмотрим две типичных ситуации:
//первый случай
int a = 300;
//второй случай
Integer b = 301;

В этих простых строках разница просто огромна, как для JVM так и для ООП. В первом случае, все что у нас есть — это 4-х байтная переменная, которая содержит значение из стека. Во втором случае у нас есть ссылочная переменная и сам объект, на который эта переменная ссылается. Следовательно, если в первом случае мы определено знаем, что занимаемый размер равен:
sizeOf(int)

то во втором:
sizeOf(reference) + sizeOf(Integer)

Забегая вперед скажу — во втором случае количество потребляемой памяти приблизительно в 5 раз больше и зависит от JVM. А теперь давайте разберемся, почему разница настолько огромна.

Из чего же состоит объект?

Прежде чем определять объем потребляемой памяти, следует разобраться, что же JVM хранит для каждого объекта:
  • Заголовок объекта;
  • Память для примитивных типов;
  • Память для ссылочных типов;
  • Смещение/выравнивание — по сути, это несколько неиспользуемых байт, что размещаются после данных самого объекта. Это сделано для того, чтобы адрес в памяти всегда был кратным машинному слову, для ускорения чтения из памяти + уменьшения количества бит для указателя на объект + предположительно для уменьшения фрагментации памяти. Стоит также отметить, что в java размер любого объекта кратен 8 байтам!

Читать дальше →
Всего голосов 118: ↑107 и ↓11+96
Комментарии39

JSR 133 (Java Memory Model) FAQ (перевод)

Время на прочтение25 мин
Количество просмотров146K
Добрый день.
В рамках набора на курс «Multicore programming in Java» я делаю серию переводов классических статей по многопоточности в Java. Всякое изучение многопоточности должно начинаться с введения в модель памяти Java (New JMM), основным источником от авторов модели является «The Java Memory Model» home page, где для старта предлагается ознакомится с JSR 133 (Java Memory Model) FAQ. Вот с перевода этой статьи я и решил начать серию.
Я позволил себе несколько вставок «от себя», которые, по моему мнению, проясняют ситуацию.
Я являюсь специалистом по Java и многопоточности, а не филологом или переводчиком, посему допускаю определенные вольности или переформулировки при переводе. В случае, если Вы предложите лучший вариант — с удовольствием сделаю правку.
Этот статья также подходит в качестве учебного материала к лекции «Лекция #5.2: JMM (volatile, final, synchronized)».

Также я веду курс «Scala for Java Developers» на платформе для онлайн-образования udemy.com (аналог Coursera/EdX).

Ну и да, приходите учиться ко мне!


JSR 133 (Java Memory Model) FAQ


Jeremy Manson и Brian Goetz, февраль 2004

Содержание:
Что такое модель памяти, в конце концов?
Другие языки, такие как C++, имеют модель памяти?
Что такое JSR 133?
Что подразумевается под «переупорядочением» (reordering)?
Что было не так со старой моделью памяти?
Что вы подразумеваете под «некорректно синхронизированы»?
Что делает синхронизация?
Как может случиться, что финальная поля меняют значения?
How do final fields work under the new JMM?
Что делает volatile?
Решила ли новая модель памяти «double-checked locking» проблему?
Что если я пишу виртуальную машину?
Почему я должен беспокоиться?
Читать дальше →
Всего голосов 56: ↑51 и ↓5+46
Комментарии32

Google Cloud Messaging: «Сова, открывай! Пуш пришел!»

Время на прочтение6 мин
Количество просмотров63K
Всем известный сервис Google Cloud Messaging (GCM) нужен для того, чтобы ваше приложение всегда показывало актуальные данные пользователю. Схема работы сервиса включает в себя три компоненты.



Непосредственно сервер GCM, ваш пуш-сервер и устройство с установленным приложением. Алгоритм работы простой: устройство регистрируется в GCM, получает registrationId – некий токен, который используется в дальнейшем, – сохраняет его у себя локально и передает серверу. Далее пуш-сервер использует этот registrationId для отправки сообщений вашему приложению на устройстве.

В этом материале будут рассмотрены проблемы на двух участках, который обозначены на схеме: пуш-сервер – GCM и GCM – устройство.
Читать дальше →
Всего голосов 45: ↑44 и ↓1+43
Комментарии30

Приглашаем на первый Moscow AndroidDevs Meetup 23 апреля

Время на прочтение2 мин
Количество просмотров5.3K


23 апреля в московском офисе Mail.Ru Group состоится первый Moscow AndroidDevs Meetup. Это открытая неформальная встреча для всех Android-разработчиков Москвы. В программе мероприятия — доклады наших программистов по Android-разработке, а после — их обсуждение и общение единомышленников в свободной обстановке.

Михаил Чабанов в докладе «Android WebView: актуальные проблемы и их решение» расскажет о сложностях при работе с интерфейсами, инжектируемыми в JavaSctipt и трудностях с определением статуса загрузки страницы в WebView и их решении. Речь пойдет и о способах взаимодействия со встроенными в web-страницу медиаплеером, извещениях WebView о системных вызовах: onBackPressed, onStop, onStart. Михаил рассмотрит также вопросы безопасности при работе с WebView.
Читать дальше →
Всего голосов 25: ↑21 и ↓4+17
Комментарии4

Обзор бортовой системы в Tesla

Время на прочтение4 мин
Количество просмотров84K


Недавно мы писали о знаменитом электромобиле Tesla Model S. Этот пост вызвал живейший интерес на Хабре, мы получили очень много вопросов об устройстве и поведении автомобиля на дороге. И идя на встречу вашим пожеланиям, решили поподробнее рассказать о системе управления и бортовом оборудовании Теслы.
Много фотографий под катом
Всего голосов 133: ↑118 и ↓15+103
Комментарии60

SlideStackView или Extending ViewGroup в Android (часть 2)

Время на прочтение31 мин
Количество просмотров10K


Недавно я рассказывал о своём опыте разработки SlideStackView в мобильной почте Mail.Ru под Android. Тогда я пообещал, что в ближайшее время подготовлю вторую часть, в которой расскажу о том, как реализовать наиболее интересную, с точки зрения программирования визуальных компонентов, часть. Естественно, речь пойдёт о том, что добавляет интерактивность в приложение — об анимации. Все уже давно привыкли к тому, что мобильное приложение должно быть отзывчивым к действиям пользователя. Очевидно, что основным способом взаимодействия с вашим приложением является использование Touch screen.
Читать дальше →
Всего голосов 39: ↑38 и ↓1+37
Комментарии6

Несколько полезных шаблонов для Android-разработки под eclipse

Время на прочтение3 мин
Количество просмотров29K

Вступление


Привет, коллеги.

Сегодня я хочу поделиться с вами несколькими полезными шаблончиками (templates) для IDE Eclipse, которые помогут вам ускорить некоторые рутинные операции при разработке под Android. Я пока что использую Eclipse для разработки, но, я уверен, что Idea позволит создавать совершенно аналогичные шаблоны.

Что такое шаблоны? Это заранее заготовленные кусочки кода, которые IDE может быстро подставлять для вас при нажатии на Ctrl+Space. Например, введите «syso» в eclipse, нажмите Ctrl+Space. Бац, у вас появился System.out.println(), или «fore» — у вас появится готовый шаблон для цикла for each. Более того, данные кусочки параметризированы, и IDE предложит вам ввести имена для нужных переменных.

Если вам это интересно, приступим.
Читать дальше →
Всего голосов 42: ↑38 и ↓4+34
Комментарии22

Работа с сетью в Android: трафик, безопасность и батарейка

Время на прочтение8 мин
Количество просмотров83K
На сегодняшний день в Google Play насчитывается более 800 тысяч приложений. Многие из них реализованы на основе клиент-серверного общения. При разработке таких приложений нужно учесть три основных момента, о которых пойдет речь в этой статье.

Читать дальше →
Всего голосов 69: ↑63 и ↓6+57
Комментарии19

SlideStackView или extending ViewGroup в Android

Время на прочтение19 мин
Количество просмотров18K
Занимаясь разработкой почтового приложения под Android, мы в Mail.Ru очень часто анализируем, насколько удобно для конечного пользователя построена навигация внутри нашей программы. Думаю, что не стоит объяснять насколько это важно, потому что все, кто пользуются мобильными приложениями, и без этого знают, что продукт, который не предоставляет интуитивно понятную и быструю навигацию, будет проигрывать тем продуктам, которые об этом позаботились. Удобство и тщательно продуманная навигация – это то, за что пользователь будет либо любить ваше приложение, либо каждый раз проявлять невероятные усилия, чтобы не разбить свой телефон об пол.

Читать дальше →
Всего голосов 37: ↑36 и ↓1+35
Комментарии7

Информация

В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Работает в
Зарегистрирован
Активность