• Алгоритм сортировки Timsort

      Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



      Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

      Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
      Читать дальше →
    • Arrays, Collections: Алгоритмический минимум

      Arrays, Collections: Алгоритмический минимум


      Массивы и списки


      Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники JDK 7.80.

      В самом обобщенном виде результат изучения представлен на рисунке. Подробности — в основном тексте.



      Рисунок 1. Методы Arrays, Collections и реализуемые ими алгоритмы
      Читать дальше →
    • Как построить классификатор изображений на основе предобученной нейронной сети

      main image

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

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

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

      Предсказание класса растения по фото


      В качестве примера мы рассмотрим задачу классификации изображений из конкурса LifeCLEF2014 Plant Identification Task. Задача заключается в том, чтобы предсказать таксономический класс растения, основываясь на нескольких его фотографиях.
      Читать дальше →
    • Топливо для ИИ: подборка открытых датасетов для машинного обучения


        Связанные проекты сообщества Open Data (проект Linked Open Data Cloud). Многие датасеты на этой диаграмме могут включать в себя данные, защищенные авторским правом, и они не упоминаются в данной статье


        Если вы прямо сейчас не делаете свой ИИ, то другие будут делать его вместо вас для себя. Ничто более не мешает вам создать систему на основе машинного обучения. Есть открытая библиотека глубинного обучения TensorFlow, большое количество алгоритмов для обучения в библиотеке Torch, фреймворк для реализации распределенной обработки неструктурированных и слабоструктурированных данных Spark и множество других инструментов, облегчающих работу.


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


        Мы разобрались в этом вопросе и собрали данные по датасетам, удовлетворяющим критериям открытости, востребованности, скорости работы и близости к реальным задачам.

        Читать дальше →
      • JavaScript без циклов

        • Translation
        Однажды я писал о том, что отступы можно считать показателем сложности кода (хотя и довольно грубым). Сами по себе отступы нейтральны, так как они – лишь средство форматирования текста, но всё дело в том, что они используются для выделения особых блоков программ, например – управляющих конструкций. Читая код и натыкаясь на отступ, программист вынужден принимать во внимание то, на что указывает отступ, держать в памяти контекст, в котором существует выделенный блок. Это, естественно, повторяется, если в выделенном отступами участке кода появляется ещё один особый фрагмент.

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


        Чем больше отступов – тем сложнее обычно и код
        Читать дальше →
      • Серия видеоуроков по Git для новичков

        • Tutorial
        Скорее всего, если вас привлекло название статьи, то вы начинаете свой путь знакомства с системой контроля версий Git. В данной статье я приведу 10+ видео о пошаговом вхождении в контроль версии используя Git. Данного курса будет вполне чем достаточно для работы с такими популярными сервисами как GitHub и Bitbucket.

        Однажды мой знакомый, который только начинал свой путь в ИТ кинул мне данный мемчик что слева, с вопросом "А чем плохо то?", поэтому чтобы понимать данную шутку и уметь работать с самым популярным на сегодня VCS (Version Control System) рекомендую к ознакомлению серии видеоуроков, которую я привел ниже.
        Читать дальше →
      • RSS – то, что нас ограничивает

          Я долго не мог заставить себя начать пользоваться RSS. Все вокруг писали о том, как это удобнокласноздорово, а я все чего-то ждал… Это же надо было потратить время и усилия на то, чтоб установить какой-то ридер, или зарегистрироваться в каком-то сервисе, предоставляющем эти услуги… А так лень… А подспудно где-то еще глодала мысль «а вдруг там не все так уж просто… и где эти фиды брать…» — ну и прочая лабудень. Но как-то в начале осени…
          Читать дальше →
        • Гонки на клавиатуре

            typeracer.ruПредставляю обществественности свой проектик — онлайн-игру Гонки на клавиатуре. Это игра на яваскрипте, клавиатурный тренажер, скрещенный с автогонками. Цель проста — набирать текст быстрее соперников. Можно играть в одиночку, можно с другими посетителями сайта, можно создать отдельную игру для себя и своих друзей.

            По сути, это русскоязычный клон аналогичной игры typeracer.com, но с рядом своих фишек.
          • Пять наиболее распространенных заблуждений в отношении Linux

            • Translation
            Пользуясь исключительно Linux на протяжении почти четырёх лет, я могу уверенно судить о том, что Linux может, а чего — не может. Ни в коем случае не претендуя на решение всех проблем, несколько самых распространённых заблуждений я все-таки постараюсь рассеять.
            Читать дальше →
          • О рейтингах и вообще, буквально несколько слов

              За последние дни люди предложили 5 (два на сайте и 3 в хабрапочте) вариантов нового рейтинга пользователей. Во всех случаях инициативу проявили пользователи, зарегистрировавшиеся осенью, т.е. за два последних месяца.
              Читать дальше →