суббота, 18 февраля 2017 г.

Алгоритмы. Быстрая сортировка

Алгоритм быстрой сортировки является алгоритмом "разделяй и властвуй". Средняя сложность его выполнения O(n*log(n)), а вот в худших случаях O(n^2) и это "неочень".

Зачем же он нужен, если сортировка слиянием всегда имеет отличное O(n*log(n))?
Ответ простой: для его выполнения требуется значительно меньше дополнительной памяти - почти не требуется.

Пример, отсортируем массив [35,33,42,10,14,19,27,44,26,31].
Шаги выполнения:

Пример выполнения 2-го и 3-го шага
  1. Проверим базовый случай (base case) - начало любого рекурсивного алгоритма. Для быстрой сортировки: если элементов в массиве 0 или 1, то его сортировать не нужно. Если элементов больше, то переходим к шагу 2.
  2. Выберем опорный элемент (pivot-элемент) в массиве. Это может быть любой элемент – первый, последний или случайный. Пусть в нашем случае опорным будет последний элемент - 31. 
  3. Преобразуем массив. Относительно опорного q-элемента. Массив преобразуется следующим образом: [элементы <q, q, элементы >q]. Т.е. [26,27,19,10,14,31,33,44,35,42]
  4. Рекурсивно выполним алгоритм на двух подмассивах - [l, q-1], [q+1, r]. Где l - это первый элемент, r - последний, q - опорный. 
В отличие от сортировки слиянием, основная логика этого алгоритма - выбор опорного элемента и преобразование массива, выполняется до дополнительных рекурсивных вызовов.

Сортируйте быстро, не сортируйте медленно.



пятница, 17 февраля 2017 г.

Алгоритмы. Инверсии в массиве

Количество инверсий в массиве показывает, насколько это массив "хорошо" отсортирован. 

Что такое инверсия? Пара элементов A[i] и A[j] являются инверсией, если A[i] > A[j] и i < j. Массив [2, 4, 1, 3, 5] содержит три инверсии (2, 1), (4, 1), (4, 3). Максимальное количество инверсий в массиве из n элементов – (n*(n-1))/2.  Если в массиве инверсий нет, то массив полностью отсортирован. 

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

воскресенье, 12 февраля 2017 г.

Как придумать название для приложения?

Практический пример. Придумаем, как назвать видеоредактор для айфона.

Начнём с того, что найдём и выпишем названия конкурентов. Это видеоредакторы: Quik, Splice и т.д.

Далее выберем 5 слов, которые лучше всего описывают наше приложение. Подойдут: video, editor, sounds, music, merge.

Для каждого слова в словарях, в разделах reverse dictionary, ищем 10-15 связанных слов и выписываем их. Например, jazz, disc, jam будут связанными с music.

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

Результат

Словари:

Генератор слов:
http://www.bustaname.com/

Проверка на доступность доменов и страниц:
https://namechk.com/
http://whois.domaintools.com/



пятница, 10 февраля 2017 г.

Алгоритмы. Поиск подмассива максимальной суммы

Зачем искать подобный подмассив? Чтобы быть богатым и красивым. 

Пример. Известный астролог Павел Глоба по секрету рассказал вам об изменениях стоимости акций Apple. Следующие 16 дней их стоимость в долларах будет меняться так: [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]. Это означает, например, что в первый день акции стали стоить на 13$ дороже, Наш искомый подмассив с максимальной суммой будет [18,20,-7,12], и она будет равна: 18+20+(-7)+12 = 43. Т.е. если вы купите акции в конце 7-ого дня (перед ростом в +18$), а затем продадите их в конце 11-го (перед паданием в -5$) вы заработаете 43$. Неплохие деньги.

Описание
Алгоритмы. Построение и анализ CLRS, Раздел 4.1 

среда, 8 февраля 2017 г.

Где жить во время путешествия?

Самые популярные ресурсы для поиска жилья это AirBnb и Booking. Booking - это про отели, AirBnb - про квартиры. На букинге отличный поиск по различным критериям, например, стоимость за ночь, возможность бесплатной отмены бронирования, тип жилья (отель или хостел), звёздность отеля и т.д. Плюс к этому есть карта с отелями. Возможности поиска на AirBnb ничуть не хуже. Тут можно заранее почитать отзывы о хозяине квартире. Выбирайте то, что вам больше нравится. Если нужна кухня, выбирайте AirBnb. Если дёшево и сердито, то Booking. 

вторник, 7 февраля 2017 г.

A/B тестирование

AB-тесты – это прагматичный подход к тестированию нового функционала – когда функционал доступен только определенной группе людей, а не всем сразу. Вы делаете это для того, чтобы проверить готов ли ваш функционал и действительно ли он хорош, чтобы быть доступным всем. Пример, Instagram проверял реакцию людей на рекламу в ленте. Не все видели рекламу, но у тех, кто видел её, реакция оказалась очень негативной и Instagram отказался от это идеи (на тот момент). Facebook, Google, Instagram и другие компании постоянно используют AB-тесты, для проверки своих идей и гипотез. 

понедельник, 6 февраля 2017 г.

Инструменты для изучения английского языка

Если хотите увеличить словарный запас, то есть приложения Duolingo и LinguaLeo. Они содержат различные подходы к тренировке слов - аудирование, написание, перевод с русского на английский и наоборот и т.д. Чтобы лучше на слух воспринимать английскую речь, слушайте подкасты 6 Minutes от BBC Learning English, технические подкасты, например, Accidental Tech Podcast (ATP), или для вдохновления Entrepreneurial Thought Leaders. Также приятный способ изучения английского – это просмотр любимых сериалов, с субтитрами или без, например на ororo.tv. Есть много разных инструментов, но главное, чтобы вы понимали, зачем вам это нужно.

воскресенье, 5 февраля 2017 г.

Аналитика мобильных приложений. Amplitude

Что пользователи делают в моём приложении? Сервис Amplitude поможет ответить на этот вопрос. Как он работает? На определенные действия в приложении вы отправляет на сервера Amplitude соотвествующие события. Например, на открытие экрана регистрации вы отправите "registration screen opened", а на успешную регистрацию "registration success". У вас есть цель, чтобы максимальный процент пользователей, которые попали на экран регистрации, успешно его прошли. Пример: в предыдущей версии приложения 60% пользователей прошли экран регистрации, затем вы сделали новый дизайн экрана и их количество упало до 45%. Вывод: нужно вернуть старый дизайн. Amplitude в свою очередь поможет найти такие критичные места в приложении.

amplitude.com

пятница, 3 февраля 2017 г.

Политическая сатира в сериалах

Политическая сатира – это когда весело и про политиков. Например, сериал The Thick Of It, родом из туманного альбиона, про трудности политтехнологий и глупости людей, к которым эти технологии хотят применить. По нему и фильм сняли In The Loop с Джеймсом "Сопрано" Гандольфини. Затем появился Veep с Джулией Дрейфус – нелепые комичные истории про вице-президента. И на последок ужастик Braindead – о том, как все политики сошли с ума, стали принимать безумные законы, а всё потому что им в голову залезли инопланетные жуки. В главных ролях этой хоррор-комедии Мэри Элизабет Уинстед – девушка из Кловерфилд, 10. 

четверг, 2 февраля 2017 г.

Инструменты разработки под iOS

Xcode – основная среда разработки под iOS. В ней есть и текстовый редактор для кода и визуальный редактор Interface Builder для интерфейсов. В процессе разработки программисты сталкиваются с однимим и теми же проблемами и множество готовых решений можно найти либо на stackoverflow, либо на github. Популярные библиотеки для разработки: AFNetworking, SDWebImage, Crashlytics и т.д.

https://medium.com/ios-os-x-development/libraries-used-in-the-top-100-ios-apps-5b845ad927b7#.bbpipvobj

среда, 1 февраля 2017 г.

Алгоритмы. Асимптотическая сложность умножения в столбик

В школе нас учили, как умножать числа в столбик. Асимптотическая сложность для такого "алгоритма" – O(n^2). Это значит, что на умножение двух чисел, состоящих из 5 цифр, нам надо выполнить 5^2 = 25 операций. Есть другой способ – метод быстрого умножения Карацубы. Он имеет сложность O(n^1.58). Например, вы решили перемножить два числа состоящих из 1000 цифр. Если вы умножаете в столбик, вы совершите 1млн операций. Используя метод К., вы сделаете около 50 тысяч операций – т. е. умножите в 20 раз быстрее.