• Видео лучших докладов Java-конференции JPoint 2015 — Часть 2



      Как многие из вас знают, в конце апреля в Москве JUG.ru проведет четвертую по счету конференцию JPoint. Любителей окунуться в океан Java-технологий ждут два увлекательных дня с морем общения и кучей докладов. Месяц назад я начал рассказывать о лучших докладах прошлогодней JPoint. Сегодня пришло время второй части.

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

      Top 5 докладов JPoint 2015
    • Задачи тысячелетия. Просто о сложном

      image
      Привет, хабралюди!

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

      После доказательства гипотезы (теперь уже теоремы) Пуанкаре Григорием Перельманом, основным вопросом, который заинтересовал многих, был: «А что же он собственно доказал, объясните на пальцах?» Пользуясь возможностью, попробую объяснить на пальцах и остальные задачи тысячелетия, или по крайней мере подойти в ним с другой более близкой к реальности стороны.
      Читать дальше →
    • Разбираемся с hashCode() и equals()


      Я недавно начал заниматься программированием, и в этой области для меня много нового. Данная статья рассчитана на начинающих java-программистов, и, надеюсь, поможет в освоении излюбленной темы для собеседований “hashCode и equals”.
      Хочу сразу предостеречь, что я не являюсь экспертом в данной теме и могу что-то не так понимать, поэтому, если вы нашли ошибку или неточность — свяжитесь со мной.
      Читать дальше →
    • Покупаем на taobao.com

        Я оставил в России много настольных игр, везти их с собой во Вьетнам смысла не видел. Надеялся, что можно будет что-то купить на месте. Облом-с, тут про настольные игры мало чего слышали, никаких магазинчиков специализированных нет. Выход был найден — рядом Китай, с огромным ассортиментом и относительно небольшими ценами. Сейчас я вам расскажу, на примере закупки настольных игр, как можно покупать что-то в Китае.

        taobao.com — это китайский ebay, или что-то на него похожее. Большое количество разных магазинов, предоставляющих разного вида товары. Если я все правильно понял — сам taobao это как аггрегатор таких магазинов. Можно найти огромное количество разных товаров: игрушки, техника, одежда, и т.д. и т.п. Разброс цен большой, как всегда для Китая, от очень и очень низких, до обычных европейских. Качество соответственное.

        Читать дальше
      • Я хочу работать в Google! Телефонное интервью (часть 1)

          Привет Хабр! Давно не писал. Да это и понятно. Защита диссертации, получение PhD, а сейчас ещё и активный поиск работы — всё это занимает очень много драгоценного времени. Но разговор сегодня пойдёт не о том. Хотелось бы поделиться с Вами, уважаемые хабралюди, ресурсами и описанием процесса подготовки к телефонному техническому интервью с Гуглом, первый технический этап которого я уже прошёл, и теперь готовлюсь ко второму, который будет в пятницу.
          Читать дальше →
        • Python на Хабре

            Некоторое время назад, в силу определенных причин, мне пришла в голову мысль о том, чтобы начать изучать какой-нибудь новый язык программирования. В качестве альтернатив для этого начинания я определил два языка: Java и Python. После продолжительного метания между ними и сопутствующих нытья и долбежки головой о стену (у меня с новыми языками всегда так — сомнения, раздумья, проблема выбора и т.д.), я все-таки остановился на Python. Окей, выбор сделан. Что дальше? А дальше я стал искать материал для изучения…
            Читать дальше →
          • Визуализация алгоритмов для сборки мусора

            • Tutorial
            Большинство разработчиков воспринимают сборку мусора (garbage collection) как нечто само собой разумеющееся. Это стандартный процесс, который периодически освобождает память, удаляя ненужные объекты. А вот американский программист Кен Фокс (Ken Fox) захотел досконально разобраться и заглянуть «под капот» современных сборщиков мусора.

            Кен «поигрался» с пятью разными алгоритмами сборки мусора и опубликовал маленькие анимации, которые наглядно демонстрируют их работу.

            Анимации большего размера выложены на github.com/kenfox/gc-viz.
            Читать дальше →
            • +37
            • 31,5k
            • 8
          • Разбор финальных задач Яндекс.Алгоритма 2014

              1 августа в офисе Яндекса, открывшемся недавно в Берлине, состоялся финал нашего чемпионата по программированию. И его победителем снова стал известный всем, кто интересуется спортивным программированием, Геннадий Короткевич.

              Задания для Алгоритма готовила международная команда. В нее вошли программисты из России, Беларуси, Польши и США. Это специалисты МГУ имени М.В. Ломоносова, Университета Карнеги-Меллон, сотрудники Яндекса и Google. В Яндексе задачи составляли разработчики минского и киевского офиса, а потом проверяли их на своих коллегах. Один из составителей в прошлом году сам был финалистом Алгоритма. Специально для Хабрахабра мы разобрали с авторами все задачи. Кстати, несмотря на то, что соревнование завершено, вы можете попробовать себя в вирутальном контесте.



              На победу претендовали многие финалисты. Среди них были победители и призеры АСМ ICPC и TopCoder Open, разработчики Google и Facebook. В финальном раунде сражались призёры Алгоритма-2013 Евгений Капун и Ши Бисюнь, чемпион АСМ ICPC Михаил Кевер, а также один из самых титулованных спортивных программистов мира Пётр Митричев. В этом году побороться за приз решил также Макото Соэдзимо — составитель заданий для Алгоритма-2013 и администратор TopCoder Open.

              Борьба за первое место разгорелась между Геннадием Короткевичем и Хосакой Кадзухиро из Токийского университета. Лучший результат — четыре задачи при 66 минутах штрафного времени — показал Короткевич, подтвердив титул чемпиона. Кадзухиро решил столько же задач, но набрал больше штрафного времени (90 минут) и занял второе место. Третье место завоевал Ван Циньши из университета Цинхуа: он решил четыре задачи при 125 минутах штрафа.
              Читать дальше →
            • Поиск подстроки. Алгоритм Кнута–Морриса-Пратта

              В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

              index = -1
              for i in xrange(len(haystack)-len(needle)+1):
                  success = True
                  for j in xrange(len(needle)):
                      if needle[j]<>haystack[i+j]:
                          success = False
                          break
                  if success:
                      index = i
                      break
              print index
              


              Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

              Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае.
              Читать дальше →
            • Динамические деревья

                Перед прочтением статьи рекомендую посмотреть посты про splay-деревья (1) и деревья по неявному ключу (2, 3, 4)

                Динамические деревья (link/cut trees) мало освещены в русскоязычном интернете. Я нашел только краткое описание на алголисте. Тем не менее эта структура данных очень интересна. Она находится на стыке двух областей: потоки и динамические графы.

                В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. Улучшенные алгоритмы Диница и проталкивания предпотока работают за и соответственно. Если вы не знаете, что такое поток, и на лекциях у вас такого не было, спешите пополнить свои знания в Кормене.

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

                Перед тем, как нырнуть под кат, попробуйте решить следующую задачу. Дан взвешенный граф в виде последовательности ребер. По последовательности можно пройти только один раз. Требуется посчитать минимальное покрывающее дерево, используя памяти и времени. По прочтении статьи вы поймете, как легко и просто можно решить эту задачу, используя динамические деревья.
                Читать дальше →
                • +50
                • 31,9k
                • 5
              • Какие бывают типы OutOfMemoryError или из каких частей состоит память java процесса

                  Если вы словили OutOfMemoryError, то это вовсе не значит, что ваше приложение создает много объектов, которые не могут почиститься сборщиком мусора и заполняют всю память, выделенную вами с помощью параметра -Xmx. Я, как минимум, могу придумать два других случая, когда вы можете увидеть эту ошибку. Дело в том, что память java процесса не ограничивается областью -Xmx, где ваше приложение программно создает объекты.

                  image

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

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


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

                  Логарифмы


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

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


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

                  Сложность


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

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


                  Введение


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

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

                    По долгу службы мне периодически приходится пользоваться профайлером, так как требования к производительности серверов задокументированы и не могут опускаться ниже определенного уровня. Помимо некоторых очевидных архитектурных изменений и решений частенько находятся повторяющиеся места от модуля к модулю, от одного проекта к другому, которые создают дополнительную нагрузку на виртуальную машину, которыми и хочу поделиться.
                    Так уж случилось, что на глаза чаще всего попадался код работы с Date потому с него и начнем:

                    Date

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

                        public boolean isValid(Date start, Date end) {
                            Date now = new Date();
                            return start.before(now) && end.after(now); 
                        }
                    

                    Казалось бы — вполне очевидное и правильное решение. В принципе, да, за исключением двух моментов:
                    • Использовать Date сегодня в java — уже, пожалуй, моветон, учитывая тот факт, что почти все методы в нем уже Deprecated.
                    • Нету смысла создавать новый объект даты, если вполне можно обойтись примитивом long:

                        public boolean isValid(Date start, Date end) {
                            long now = System.currentTimeMillis();
                            return start.getTime() < now && now < end.getTIme(); 
                        }
                    


                    SimpleDateFormat

                    Очень часто в веб проектах возникает задача перевести строку в дату или наоборот дату в строку. Задача довольно типичная и чаще всего выглядит так:

                        return new SimpleDateFormat("EEE, d MMM yyyy HH:mm:ss Z").parse(dateString);
                    

                    Это правильное и быстрое решение, но если серверу приходится парсить строку на каждый пользовательский реквест в каждом из сотен потоков — это может ощутимо бить по производительности сервера в виду довольно тяжеловесного конструктора SimpleDateFormat, да и помимо самого форматера создается множество других объектов в том числе и не легкий Calendar (размер которого > 400 байт).

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

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

                    Но решения есть и их как минимум 2:
                    • Старый, добрый ThreadLocal — cоздаем SimpleDateFormat для каждого потока 1 раз и переиспользуем для каждого последующего запроса. Данный подход поможет ускорить парсинг даты в 2-4 раза за счет избежания создания объектов SimpleDateFormat на каждый запрос.
                    • Joda и ее потокобезопасный аналог SimpleDateFormat — DateTimeFormat. Хоть йода в целом и медленнее дефолтного Java Date API в парсинге дат они идут наравне. Несколько тестов можно глянуть тут.

                    Читать дальше →
                  • Знай сложности алгоритмов

                    • Перевод
                    Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!
                    Читать дальше →
                  • JDK concurrent package

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

                    Пакет java.util.concurrent, входящий в состав HotSpot JDK, предоставляет следующие инструменты для написания многопоточного кода:
                    • Atomic
                    • Locks
                    • Collections
                    • Synchronization points
                    • Executors
                    • Accumulators _jdk 1.8_

                    Читать дальше →
                    • +8
                    • 29,2k
                    • 5
                  • Работа с цветом: полезные инструменты, книги, статьи для веб-дизайнеров

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

                      Инструменты




                      Colour Lovers — старый и функциональный инструмент для подбора цветовых схем. Аналоги — Colourcode, Color Scheme Designer и конечно Kuler. Подобных сайтов великое множество, но эти, на мой взгляд, самые удобные.
                      Читать дальше →
                      • +65
                      • 85k
                      • 8
                    • Про Linux — для любознательных Windows-пользователей



                        Так уж получилось, что даже на Хабре многие имеют очень смутное представление о семействе OS Linux.

                        Цель данной статьи – максимально популярным языком рассказать про особенности и отличия Linux от Windows для тех, кто вообще не имел с ним дела.

                        Я уже не один год свободно пользуюсь Archlinux, загружая винду лишь «на поиграться». Данная статья рассказывает о вещах, которые я выяснил эмпирическим путем, тыкаясь словно слепой котенок. Если бы в свое время мне попалась бы именно такая информация именно в такой форме — это сэкономило бы мне как минимум 2 года, в течение которых я переходил с Windows на Linux.

                        Станиславский заинтригован!