• Структуры данных: бинарные деревья. Часть 2: обзор сбалансированных деревьев

      Первая статья цикла

      Интро


      Во второй статье я приведу обзор характеристик различных сбалансированных деревьев. Под характеристикой я подразумеваю основной принцип работы (без описания реализации операций), скорость работы и дополнительный расход памяти по сравнению с несбаланчированным деревом, различные интересные факты, а так же ссылки на дополнительные материалы.
      Читать дальше →
    • С чего начать внедрение Hadoop в компании



        Алексей Еремихин ( alexxz )


        Я хочу навести порядок в головах, чтобы люди поняли, что такое Hadoop, и что такое продукты вокруг Hadoop, а также для чего не только Hadoop, но и продукты вокруг него можно использовать на примерах. Именно поэтому тема — «С чего начать внедрение Hadoop в компании?»

        Структура доклада следующая. Я расскажу:

        • какие задачи я предлагаю решать с помощью Hadoop на начальных этапах,
        • что такое Hadoop,
        • как он устроен внутри,
        • что есть вокруг него,
        • как Hadoop применяется в Badoo в рамках решения задач с первого пункта.

        Читать дальше →
      • Shazam: алгоритмы распознавания музыки, сигнатуры, обработка данных

        • Translation
        В ресторане заиграла почти забытая песня. Вы слушали её в далёком прошлом. Сколько трогательных воспоминаний способны вызвать аккорды и слова… Вы отчаянно хотите послушать эту песню снова, но вот её название напрочь вылетело из головы! Как быть? К счастью, в нашем фантастическом высокотехнологичном мире есть ответ на этот вопрос.

        У вас в кармане лежит смартфон, на котором установлена программа для распознавания музыкальных произведений. Эта программа – ваш спаситель. Для того чтобы узнать название песни, не придётся ходить из угла в угол в попытках выудить из собственной памяти заветную строчку. И ведь не факт, что это получится. Программа, если дать ей «послушать» музыку, тут же сообщит название композиции. После этого можно будет слушать милые сердцу звуки снова и снова. До тех пор, пока они не станут с вами единым целым, или – до тех пор, пока вам всё это не надоест.


        Мобильные технологии и невероятный прогресс в области обработки звука дают разработчикам алгоритмов возможность создавать приложения для распознавания музыкальных произведений. Одно из самых популярных решений такого рода называется Shazam. Если дать ему 20 секунд звучания, неважно, будет ли это кусок вступления, припева или часть основного мотива, Shazam создаст сигнатурный код, сверится с базой данных и воспользуется собственным алгоритмом распознавания музыки для того, чтобы выдать название произведения.

        Как же всё это работает?
        Читать дальше →
      • Просто о Хиндли-Милнере

        • Translation

        Введение


        Robert MilnerЕсли вы когда-нибудь интересовались не слишком популярными языками, то должно быть слышали о «Хиндли-Милнере». Этот алгоритм вывода типов используются в F# и Haskell и OCaml, как и в их предшественнике ML. Некоторые исследователи даже пытаются использовать ХМ для оптимизации динамических языков вроде Ruby, JavaScript и Clojure.

        И не смотря на его распространенность, до сих пор не было простого и понятного объяснения, что же это такое. Как же эта магия работает? Всегда ли выводимые типы будут верными? Или чем Хиндли-Милнер лучше, скажем, Java? И пока те, кто действительно знает что такое ХМ будут восстанавливаться от очередного умственного перенапряжения, мы попробуем разобраться в этом сами.
        Читать дальше →
      • Ликбез по типизации в языках программирования

        image

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

        В полной версии находится подробное описание всех видов типизации, приправленное примерами кода, ссылками на популярные языки программирования и показательными картинками.
        Читать дальше →
      • Перевод: Этика Code Review

        • Translation
        Недавно мне на глаза попалась небольшая, но очень емкая статья одного разработчика, в которой он рассматривает code reiew с довольно неожиданной стороны. Большинство материалов, посвященных code review, рассказывают о технических вопросах: какими утилитами пользоваться, как интегрировать code review в процесс continuous integration и прочие технические моменты. Автор же рассматривает code review как социальное взаимодействие. И, на мой взгляд, об этом стоит почитать. Под катом — перевод.
        Читать дальше →
      • Pull request'ы на GitHub или Как мне внести изменения в чужой проект

        • Tutorial
        По просьбе tulskiy делаю вольный перевод частей официальной документации GitHub'а Fork A Repo и Send pull requests.

        Итак, что же такое «запрос на включение (сделанных вами изменений)» (именно так я перевёл pull request)? В официальной документации гитхаба говорится следующее:
        Pull request'ы позволяют вам рассказать другим о тех изменениях, которые вы разместили в своём GitHub-репозитории. Как только pull request отправлен, заинтересованные стороны рассматривают ваши изменения, обсуждают возможные правки или даже добавляют дополняющие коммиты, если нужно.

        Говоря своим языком: Посылая pull request, вы говорите автору изначального репозитория (и всем заинтересованным лицам): «Смотрите, что я сделал, не хотите ли принять мои изменения и влить их в проект?»
        Читать дальше, но теперь уже обо всём по порядку
      • Вы неправильно пишете животных

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


          Уязвимость рекурсивных алгоритмов навигации муравья: спираль смерти

          Не знаю, кто писал большую часть птиц, но я хочу обратить внимание на особенность, позволяющую провести инъекцию произвольного яйца в гнездо. Дело в том, что птица проверяет только расположение и количество яиц, но не их хэши. В 20% случаев кукушка, эксплуатирующая этот баг, может внести яйцо с сохранением контрольной суммы, чего вполне достаточно для повышения прав в гнезде.

          Но пойдём далее. Я не знаю, кто разрабатывал архитектуру ящериц, но они бегают в одном процессе, а дышат в другом. При этом платформа не поддерживает многозадачность, поэтому костыль с максимальной длиной бега в 4-6 секунд просто эпичен.
          Читать дальше →
        • На волосок от смерти: Почти случившиеся космические катастрофы



            Читать про произошедшие космические катастрофы, прямо скажем, печально. Очень жалко людей, а понимание, что старания конструкторов с резервированием важных систем, работа ЦУПа по контролю и управлению ситуацией, подготовка и героизм самих космонавтов — всё это не смогло предотвратить катастрофу, портит настроение. В этом смысле гораздо позитивнее катастрофы, которые могли произойти, но были предотвращены талантом конструкторов, трудом ЦУПа, решительными и умелыми действиями экипажей или простой удачей.
            Читать дальше →
          • О патриотизме и реализме

              О сегодняшней российской космонавтике в русскоязычном интернете имеется два мнения: “мы в космосе первые” и “мы в космосе последние”.

              Souyz

              С “последними” всё достаточно ясно: если не интересоваться космонавтикой, а поверхностный взгляд формировать из просмотра популярных СМИ, то перед глазами встают картины взрывающихся ракет и коррупционные скандалы. К примеру, прошлогоднее падение “Протона” затмило, в информационном поле, остальные три десятка успешных запусков. То же самое касается и раздувания новостей о коррупции в Роскосмосе. Она, конечно, есть, но, несмотря на нее, отрасль работает и развивается, хоть и не так быстро как хотелось бы.

              Сегодня я хотел поговорить о “мы впереди планеты всей”. Вполне объективные показатели: лидирующие положение на мировом рынке космических запусков, стабильно надежное обеспечение пилотируемой программы МКС, экспорт ракетных двигателей, ракет и разгонных блоков, позволяют России находиться в списке ведущих мировых космических держав. Но те, кому известны эти факты, ударяются в обратную крайность — полагают, что Роскосмос занимает верхнюю ступеньку космического пьедестала.
              Читать дальше →
            • Беззеркальные камеры и закон компьютерных мощностей

                Бум компактных системных камер, разразившийся три года назад, застал врасплох как орды кропозеркальщиков, продолжавших на все лады расхваливать преимущества любимых систем, так и любителей топовых компактных камер, готовых вкладывать огромные деньги в функциональность фотоаппаратов, едва ли сравнимую с зеркалками самого младшего уровня. Не секрет, что беззеркальные камеры вызвали своим появлением не только закономерный интерес, но и шквал ненависти; прежде чем за «беззеркалками» в англоязычном мире утвердилась аббревиатура CSC (Compact System Cameras), большинство называло их не иначе как EVIL (Electronic Viewfinder, Interchangeable Lens). Всерьёз поговаривали о заговоре корпораций, о поглощении сегментов рынка и даже о мировой войне, объявленной владельцам огромных полноформатных коробок со стороны толп нищебродов, желающих блеснуть профессионализмом, но не готовых расплачиваться за удовольствие от фотоснимков необходимостью таскать огромные кофры с аппаратурой.
                Читать дальше →
              • Уроки космических катастроф


                  Конец января — траурное время для NASA. Их катастрофы очень «кучно» пришлись на конец января-начало февраля. За всю историю освоения космоса произошло пять космических катастроф, в них погиб двадцать один человек. И самое печальное в этих катастрофах то, что их всех могло бы и не быть. Ни одна из них не произошла из-за действия непреодолимой внешней силы, случайности или вины экипажа.
                  Читать дальше →
                • Как мы искали Марс-3

                    Честное слово, это почти случайно получилось, что такая новость пришла к началу апреля и Дню космонавтики. Сегодня я расскажу о том, как история, которая началась и оборвалась более 40 лет назад, внезапно получила продолжение в наши дни. О том, как простой юзернейм вконтакта, в своем интересе к Марсу дошел до NASA. О том, что международная солидарность ученых — не пустой звук. И о том, что космос ближе, чем кажется.

                    Мы искали Марс-3.

                    И мы нашли его! Прямо на Марсе, на дне гигантского кратера Птолемея, среди безжизненных пустошей и валунов.

                    О том, как мы это сделали, сегодняшний рассказ.


                    Читать дальше →
                  • Рассказы о копирайте и интеллектуальной собственности



                      Вот уже некоторое время мы с коллегами составляем список художественных произведений на тему копирайт-пиратство. И вот недавно я неожиданно узнал, что пользователь под ником Рыжий Тигра (связаться с ним пока не удалось) тоже давно составляет подобный список, и он нашел таких произведений гораздо больше. Желающие могут ознакомиться с его списком и дополнениями в комментариях по поисковой фразе «хрестоматия копирайта».

                      Я объединил наши списки, и постарался отбросить наименее интересные работы, которые часто представляют собой просто художественно оформленные споры о копирайте. В итоге получилось около 20 рассказов. Ссылки приведены только для тех работ, которые авторы опубликовали сами, или распространяются по свободным лицензиям (были случаи, когда авторы протестовали против размещения ссылок на произведения). Некоторые вещи написаны профессионалами, некоторые — любителями, в том числе программистами. Не советую читать сразу все подряд, так как тема, в общем-то, одна, и может наскучить, хотя сюжеты и драматические эффекты встречаются весьма разнообразные.
                      Читать дальше →
                    • Расширение возможностей экрана блокировки в Android 4.2.x

                        Многие владельцы планшетов линейки Nexus или других моделей под управлением Android 4.2.x, заметили что разработчики Google довольно мало внимания уделили экрану блокировки. В данном посте хочу рассказать про один очень полезный инструмент, который позволит использовать экран блокировки более эффективно. Речь пойдет о DashClock Widget (GooglePlay).


                        Кому интересно — прошу под кат.
                        Читать дальше →
                      • Мультиварка — умная кастрюля или «не доведенный до ума» гаджет


                          Этот пост будет полезен всем, кто хотя бы иногда что-то готовит сам, а также помогает или мешает это делать другим.
                          Из него можно узнать, что это за гаджет — мультиварка, какие у нее технические возможности и невозможности, внутренность, наружность, достоинства (много) и недостатки (тоже много). Расскажу кое-что и о маленьких мультиварочных хитростях, а также позволю себе общее лирическое отступление о программировании на кухне.
                          Цель поста — рассказать про мультиварки, как класс объектов, не выделяя особо его представителей, но, чтобы не вести разговор о сферической мультиварке в вакууме, сделаю основным примером разбора мою модель — Panasonic SR-TMJ181.
                          Те, у кого нет мультиварки узнают, нужна ли она им, но и те, у кого она есть, надеюсь, без новых знаний не останутся.
                          Читать дальше →
                        • Как стать еще мобильнее, или что делать, если рядом нет розетки с 220V?

                          image Думаю, многим из нас знакома такая ситуация, когда вдруг обнаруживаешь, что твой телефон или интернет-планшет вот-вот разрядится, причем, происходит это, как назло, в самый неподходящий для этого момент.
                          Что же делать, если необходимо подзарядить батарею, например, сидя на семинаре вдали от розетки, на пикнике вдали от бортовой сети автомобиля, там, где нет возможности воткуть привычную зарядку в 220V?

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

                          Читать далее
                        • Они пишут правильную вещь

                            Пойду по одному из путей описанных в недавней статье про блоггеров и буду тут изредка давать ссылки на интересные статьи. Если вам не понравится — пишите и я прикрою эти записи только для личного использования :)

                            Правильная вещь появляется за 31 секунду, до времени Х.В то время, когда 120-ти тонный шаттл стоит, окруженный почти 4-мя миллионами фунтов ракетного топлива, источая ядовитые пары, с явным желанием бросить вызов земной гравитации; его бортовые компьютеры получают команду. Четыре идентичных компьютера, работающие под управлением идентичного ПО, собирают информацию из тысяч датчиков, принимая сотни миллисекундных решений, утверждая каждое решение, сверяясь друг с другом 250 раз в секунду. Пятый компьютер, с другим ПО, готов взять управление на себя в случае сбоя остальных четырех.В момент времени -6.6 секунды, если давления, насосы и температуры в норме, компьютеры дают приказ зажечь главные двигатели шаттла – каждый из трех двигателей вспыхивает ровно через 160 миллисекунд, тонны сверхохлажденного жидкого топлива попадают в камеры сгорания, корабль дрожит на своей пусковой площадке, удерживаемый на земле только креплениями. Когда главные двигатели достигают силы тяги в миллион фунтов, их выхлопы превращаются в голубые бриллианты пламени.

                            Прочитать статью целиком...

                            P.S. Очень бы хотелось, что бы и Хабрахабр был надёжен как программа шатла.
                          • Непрофильные вопросы на интервью

                              *внимание, это очень спорный и субъективный текст*

                              Иногда собеседования могут превратиться в скучную рутину и это может плохо сказаться на впечатлении от кандидата, и впечатлении кандидата о вас. Для меня собеседования всегда были возможностью узнать для себя что-то новое параллельно процессу оценивания знаний кандидата на ту или иную позицию. Но ведь кроме сугубо профильных вопросов хочется еще и кандидата узнать немного больше. Как правило, этим занимается HR-служба, но помимо общей характеристики бывает важно увидеть, как человек думает и ведет себя в вопросах «не о погоде».

                              Вот некоторые из вопросов, которые я задаю на интервью, чтобы его разнообразить.

                              Объясните ребенку, что такое обфускация кода, простыми словами, так, чтобы тот понял.

                              В качестве ребёнка выступаю я сам. Вместо «обфускация кода» может быть любое понятие, в зависимости от позиции. Этот вопрос помогает увидеть, может ли человек сделать сложное простым.
                              Читать дальше →