Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.
Артур @zilopop
Пользователь
Эта бесконечная гирлянда
2 мин
27KУдивительно, что такая книга, как эта, до сих пор не была замечена на Хабре. Не могу не попытаться исправить этот недочет.
Итак, хочу представить вам книгу американского информатика Дугласа Роберта Хофштадтера «Гедель, Эшер, Бах: эта бесконечная гирлянда».
Ахилл: Вот если бы книга называлась «Гориллы, серебро, золото» или «Эму, золото…» — тогда бы я еще мог понять…
Черепаха: Может быть, вы предпочли бы «Медь, серебро, бабуины»?
Будучи написано более тридцати лет назад, это невероятное произведение ничуть не утратило своей интересности.
+38
Учим Python качественно
4 мин
1.4MЗдравствуйте всем!
Решил поделиться методом обучения сего мощного, но в одно и тоже время лёгкого языка программирования. Он действительно лёгкий. Вам не надо будет запоминать и вводить лишних символов, которые Вы можете встретить в Си-подобных языках.
Удобочитаемый синтаксис, прост в обучении, высокоуровневый язык, Объектно-Ориентированый язык программирования (ООП), мощный, интерактивный режим, масса библиотек. Множество иных плюсов… И это всё в одном языке.
Для начала окунёмся в возможности и узнаем, что же умеет Python?
Решил поделиться методом обучения сего мощного, но в одно и тоже время лёгкого языка программирования. Он действительно лёгкий. Вам не надо будет запоминать и вводить лишних символов, которые Вы можете встретить в Си-подобных языках.
Удобочитаемый синтаксис, прост в обучении, высокоуровневый язык, Объектно-Ориентированый язык программирования (ООП), мощный, интерактивный режим, масса библиотек. Множество иных плюсов… И это всё в одном языке.
Для начала окунёмся в возможности и узнаем, что же умеет Python?
+32
Введение в CQRS + Event Sourcing: Часть 2
8 мин
48KВ прошлой статье я начал с основ CQRS + Event Sourcing. В этот раз я предлагаю продолжить и более подробно посмотреть на ES.
В примере который я выкладывал с моей прошлой статьей магия Event Sourcing’а была скрыта за абстракцией IRepository и двумя методами IRepository.Save() и IRepository.GetById<>().
Для того чтобы поподробнее разобраться что происходит я решил рассказать о процессе сохранения и загрузки агрегата из Event Store на примере проекта Lokad IDDD Sample от Рината Абдулина. У него в аппликейшен сервисах идет прямое обращение к Event Store, без дополнительных абстракций, поэтому все выглядит очень наглядно. Application Service — это аналог CommandHandler, но который обрабатывает все комманды одного агрегата. Такой подход очень удобный и мы тоже на него в одном проекте перешли.
В примере который я выкладывал с моей прошлой статьей магия Event Sourcing’а была скрыта за абстракцией IRepository и двумя методами IRepository.Save() и IRepository.GetById<>().
Для того чтобы поподробнее разобраться что происходит я решил рассказать о процессе сохранения и загрузки агрегата из Event Store на примере проекта Lokad IDDD Sample от Рината Абдулина. У него в аппликейшен сервисах идет прямое обращение к Event Store, без дополнительных абстракций, поэтому все выглядит очень наглядно. Application Service — это аналог CommandHandler, но который обрабатывает все комманды одного агрегата. Такой подход очень удобный и мы тоже на него в одном проекте перешли.
+12
Предсказание ухода лояльных игроков в ММО
6 мин
17KВ прошлой статье я описал, как мы в Иннове используем data mining для предсказания ухода новичков, только начинающих свой путь в ММОРПГ Aion, на основе логов их действий за пару часов или дней, проведенных в игре. Но у нас также есть и ветераны, посвятившие игре месяцы и годы, и они тоже иногда уходят. Мы уже научились с высокой точностью предсказывать угасание их интереса теми же методами data mining.
+67
Начинающие стартаперы: хватит страдать фигней
7 мин
13KRecovery Mode
Перевод
Это перевод статьи с TechCrunch, написанной Полом Стоматьо, соучредителем сервиса печати фотографий Picplum поддержанного Y Combinator. В этом внушительно мотивирующем посте, Пол рассказывает о том, как по его мнению нужно правильно делать стартапы.
Небольшой экскурс в историю. Вы помните, как первый раз подключились к Интернету? Еще до того, как ваш компьютер был всегда на связи и когда выход в онлайн нужно было планировать. Радость видеть новые браузеры, например, появление Phoenix. Ваше волнение, когда вы впервые попробовали работать в Интернете при помощи вашего нового скоростного соединения. Это было время, когда сайты редко использовали JavaScript, а DHTML был модным словечком года. Сейчас сложно поверить, что Chrome-у всего лишь несколько лет.
Небольшой экскурс в историю. Вы помните, как первый раз подключились к Интернету? Еще до того, как ваш компьютер был всегда на связи и когда выход в онлайн нужно было планировать. Радость видеть новые браузеры, например, появление Phoenix. Ваше волнение, когда вы впервые попробовали работать в Интернете при помощи вашего нового скоростного соединения. Это было время, когда сайты редко использовали JavaScript, а DHTML был модным словечком года. Сейчас сложно поверить, что Chrome-у всего лишь несколько лет.
+60
PostgreSQL vs Oracle
3 мин
62KСравнение с точки зрения разработчика
Сразу оговорюсь — я не имею ничего против размещения части бизнес логики в хранимых функциях, если это предусмотрено в архитектуре системы и оправдано по ряду практических соображений, которые выходят за рамки этой статьи.
+66
Я, наверное, знаю ООП. Опыт объектно-ориентированного программирования и дизайна. Ответ «не знающим ООП.»
8 мин
35KПосле появления статей типа "Я не знаю ООП" — возникает желание внести ясность, «сорвать покровы» и «докопаться до истины».
Обычно выделяют (читай: на собеседовании требуют назвать) четыре «принципа объектно-ориентированного программирования»: абстракцию, инкапсуляцию, наследование и полиморфизм.
На мой взгляд (не говоря о том, что абстракция и полиморфизм могут быть запросто отнесены к подразделам наследования), принцип тут один, в общем, тот же самый, что при проектировании баз данных: представление всего в виде объекта — некоторой штуковины со свойствами. Набор обычно бывает фиксированным, и тогда говорят о классе объектов, а даже если понятия класса и нет, то наличие свойств с определёнными названиями подразумевается логикой программы, т.е. нечто типа класса в виде некоего минимального набора свойств всё равно присутствует. В общем, воззрения восходят к давнему С-шному/паскалевскому типу данных struct/record. Потом к этому добавили немного «функциональности» (в смысле функционального программирования): значением свойства может быть функция, причём такая, которая имеет доступ к самой структуре/записи, значением одного из свойств которой она является. Сей феномен, в лучших традициях немецкого латиноязычного нейминга (когда опция называется «вариантом», а степень числа — «потенцией»), назвали «методом». Желание повторно использовать код, в сочетании с представлением каждого предмета как некоего подобия паскалевской «записи», привело к появлению концепции «наследования».
Принципы объектно-ориентированности
Обычно выделяют (читай: на собеседовании требуют назвать) четыре «принципа объектно-ориентированного программирования»: абстракцию, инкапсуляцию, наследование и полиморфизм.
На мой взгляд (не говоря о том, что абстракция и полиморфизм могут быть запросто отнесены к подразделам наследования), принцип тут один, в общем, тот же самый, что при проектировании баз данных: представление всего в виде объекта — некоторой штуковины со свойствами. Набор обычно бывает фиксированным, и тогда говорят о классе объектов, а даже если понятия класса и нет, то наличие свойств с определёнными названиями подразумевается логикой программы, т.е. нечто типа класса в виде некоего минимального набора свойств всё равно присутствует. В общем, воззрения восходят к давнему С-шному/паскалевскому типу данных struct/record. Потом к этому добавили немного «функциональности» (в смысле функционального программирования): значением свойства может быть функция, причём такая, которая имеет доступ к самой структуре/записи, значением одного из свойств которой она является. Сей феномен, в лучших традициях немецкого латиноязычного нейминга (когда опция называется «вариантом», а степень числа — «потенцией»), назвали «методом». Желание повторно использовать код, в сочетании с представлением каждого предмета как некоего подобия паскалевской «записи», привело к появлению концепции «наследования».
+11
Памятка пользователям ssh
13 мин
1.5Mabstract: В статье описаны продвинутые функций OpenSSH, которые позволяют сильно упростить жизнь системным администраторам и программистам, которые не боятся шелла. В отличие от большинства руководств, которые кроме ключей и -L/D/R опций ничего не описывают, я попытался собрать все интересные фичи и удобства, которые с собой несёт ssh.
Предупреждение: пост очень объёмный, но для удобства использования я решил не резать его на части.
Оглавление:
Предупреждение: пост очень объёмный, но для удобства использования я решил не резать его на части.
Оглавление:
- управление ключами
- копирование файлов через ssh
- Проброс потоков ввода/вывода
- Монтирование удалённой FS через ssh
- Удалённое исполнение кода
- Алиасы и опции для подключений в .ssh/config
- Опции по-умолчанию
- Проброс X-сервера
- ssh в качестве socks-proxy
- Проброс портов — прямой и обратный
- Реверс-сокс-прокси
- туннелирование L2/L3 трафика
- Проброс агента авторизации
- Туннелирование ssh через ssh сквозь недоверенный сервер (с большой вероятностью вы этого не знаете)
+344
Отладка Hadoop приложений
6 мин
5KСколько бы ни говорили, что логи способны полностью заменить отладку, увы и ах — это не совсем так, а иногда — совсем не так. Действительно, иногда и в голову не придет, что надо было писать в лог именно эту переменную — в то же время, в режиме отладки можно часто просмотреть сразу несколько структур данных; можно, в конце концов, наткнутся на проблемный участок абсолютно случайно. Поэтому иногда отладка неизбежна, и часто она способна сэкономить очень немало времени.
Отлаживать однопоточное Java приложение просто. Отлаживать многопоточное Java приложение — чуть сложнее, но все равно просто. Отлаживать мультипроцессное Java приложение? С процессами, запущенными на разных машинах? Это определенно сложнее. Именно поэтому все руководства по Hadoop рекомендуют обращаться к отладке только и исключительно тогда, когда другие опции (читай: логгинг) исчерпаны и не помогли. Ситуация зачастую усложняется тем, что на больших кластерах у вас может и не быть доступа к конкретным map/reduce узлам (именно с этим вариантом я и столкнулся). Но давайте решать проблему по частям. Итак…
Самый простой вариант из всех возможных. Локальная инсталляция Hadoop — все выполняется на одной машине, и более того — в одном процессе, но в разных потоках. Отладка эквивалентна отладке обычного мультипоточного Java приложения — что может быть тривиальнее?
Как же этого добиться? Мы идем в директорию, где у нас развернут наш локальных Hadoop (я полагаю, что вы умеете это делать или умеете прочитать соответствующую инструкцию и уже теперь с этим справитесь).
Наша задача — добавить еще одну опцию JVM, где-то в районе 282-283 строки (в зависимости от версии, номер может и измениться), сразу после того, как скрипт закончил формировать
Отлаживать однопоточное Java приложение просто. Отлаживать многопоточное Java приложение — чуть сложнее, но все равно просто. Отлаживать мультипроцессное Java приложение? С процессами, запущенными на разных машинах? Это определенно сложнее. Именно поэтому все руководства по Hadoop рекомендуют обращаться к отладке только и исключительно тогда, когда другие опции (читай: логгинг) исчерпаны и не помогли. Ситуация зачастую усложняется тем, что на больших кластерах у вас может и не быть доступа к конкретным map/reduce узлам (именно с этим вариантом я и столкнулся). Но давайте решать проблему по частям. Итак…
Сценарий первый: локальный Hadoop
Самый простой вариант из всех возможных. Локальная инсталляция Hadoop — все выполняется на одной машине, и более того — в одном процессе, но в разных потоках. Отладка эквивалентна отладке обычного мультипоточного Java приложения — что может быть тривиальнее?
Как же этого добиться? Мы идем в директорию, где у нас развернут наш локальных Hadoop (я полагаю, что вы умеете это делать или умеете прочитать соответствующую инструкцию и уже теперь с этим справитесь).
$ cd ~/dev/hadoop $ cp bin/hadoop bin/hdebug $ vim bin/hdebug
Наша задача — добавить еще одну опцию JVM, где-то в районе 282-283 строки (в зависимости от версии, номер может и измениться), сразу после того, как скрипт закончил формировать
$HADOOP_OPTS
:+21
Зарплата напоказ
6 мин
3.2KЯ когда-то работал в компании, где нельзя было говорить о своей зарплате под страхом… я даже не знаю чего. Как дети испытывают ужас от того, что “взрослые заругают”, так и мы боялись ей делиться. О том, какая кара нас ожидает, приходилось только догадываться.
Ад в представлении Босха.
И все равно все все знали. Почему? Потому что чтобы закон работал, за ним должна стоять идея, которую разделяет большинство. Какая идея стояла за этим законом? Идея скрыть несправедливую оплату труда. Ведь если она справедливая, то зачем скрывать?
+127
Эмулятор Bluestacks + Eclipse: ускоряем отладку и тестирование Android-приложений
3 мин
98KТуториал
Об эмуляторе Android под названием Bluestacks на Хабре уже писали. Но писали или в общем, или мало, или сухо. Тем временем проект подрос и ныне вполне пригоден для использования при тестировании и отладке приложений под Android. Зачем это делать? А затем, что Bluestacks работает намного, нет, даже намного-намного быстрее стандартного эмулятора из Android SDK. Под катом я расскажу о нюансах использования Bluestacks, настройке отладки из-под Eclipse, приведу пару замеров скорости работы и расскажу о нескольких ложках дёгтя в бочке мёда.
+43
Самоорганизующиеся команды
5 мин
9.3KЯ работаю в одной молодой консалтинговой компании, которая специализируется на вопросах личной эффективности. В отличие от многих других компаний, которые берут и пытаются применять чьи-то готовые техники, мы разработали свою методологию и свой собственный концепт, который называется Энерджи Менеджмент. Сам концепт Энерджи Менеджмента станет предметом следующей статьи, а сегодня мы затронем вопросы эффективности с точки зрения организации команд, дав в качестве примера две известные компании, которые уже упоминались на хабре, и которые так же как и мы не стали брать готовые шаблоны развития, а сделали что-то свое и с нуля. В следующих статьях я планирую рассказать непосредственно о нашем концепте Энерджи Менеджмент, и его принципиальных отличиях от Тайм-Менеджмента.
+28
Использование разделяемой памяти в Java и off-heap кеширование
6 мин
59KНа прошлой неделе состоялся успешный эксперимент по запуску нового решения для download-сервиса. Один достаточно скромный сервер (2 x Intel Xeon E5620, 64 GB RAM) под управлением Java-приложения собственной разработки принял на себя нагрузку восьми Tomcat'ов, обслуживая более 70 тысяч HTTP-запросов в секунду общей пропускной способностью 3000 Mb/s. Таким образом, весь трафик Одноклассников, связанный с пользовательскими смайликами, обрабатывался одним сервером.
Вполне естественно, что высокие нагрузки требовали нестандартных решений. В цикле статей о разработке высоконагруженного сервера на Java я расскажу о проблемах, с которыми нам пришлось столкнуться, и о том, как мы их преодолели. Сегодня речь пойдет о кешировании изображений вне Java Heap и об использовании Shared Memory в Java.
Вполне естественно, что высокие нагрузки требовали нестандартных решений. В цикле статей о разработке высоконагруженного сервера на Java я расскажу о проблемах, с которыми нам пришлось столкнуться, и о том, как мы их преодолели. Сегодня речь пойдет о кешировании изображений вне Java Heap и об использовании Shared Memory в Java.
+63
Занимательное функциональное программирование в Ruby
13 мин
10KПеревод
Эта статья посвящена бесцельному путешествию по вырожденной форме Ruby в попытках узнать больше о функциональном программировании, простоте и дизайне программных интерфейсов.
Предположим, что единственный способ представления кода — лямбда-выражение, а единственная доступная структура данных — массив:
square = ->(x) { x * x }
square.(4) # => 16
person = ["Dave",:male]
print_person = ->((name,gender)) {
puts "#{name} is a #{gender}"
}
print_person.(person)
Это самые основы функционального программирования: функции — единственное, что у нас есть. Давайте попробуем написать что-то более похожее на реальный код в таком же стиле. Посмотрим, как далеко мы сможем зайти без особых мучений.
+61
XNA Draw: улучшаем графику игры
6 мин
23KТуториал
Всем привет.
Все мои восемь статьей на хабре — статьи о геймдеве, большая часть из них связана с таким замечательным фреймворком, как XNA. Первым знакомством с XNA была статья о создании музыкальной игрушки, потом сложность статей нарастала, я начал писать об системах частиц, а затем о шейдерах и еще шейдерах.
В целом — на шейдерах я и хотел закончить, однако, стоить немного дополнить их, я расскажу о нескольких алгоритмах для улучшения графики в игре. Примеры улучшений:
Если интересно — под хабракат.
+75
Бесплатные способы продвижения Android-приложений
5 мин
66KВсем привет! В этом топике мне хотелось бы обсудить одну из самых интересных и в тоже время загадочных тем для большинства, как мне кажется, инди-разработчиков – это продвижение своих собственных приложений. Скажу пару слов о себе: я примерно 2 года занимаюсь Android-разработкой (исключительно в качестве хобби, правда). У меня есть десяток приложений в Play Store, с совокупным количеством загрузок более 5 млн. Ни то что бы очень много, да и большая часть загрузок приходится на одно приложение, но какие-то выводы касательно маркетинга я для себя сделал. Здесь я хочу поделиться своим опытом, наблюдениями, а так же призываю Вас рассказывать о своих результатах в комментариях. Обмен опытом в этом вопросе был бы полезен всем, я думаю.
+50
Информация
- В рейтинге
- Не участвует
- Откуда
- Киев, Киевская обл., Украина
- Дата рождения
- Зарегистрирован
- Активность