• Умные алгоритмы обработки строк в ClickHouse

      В ClickHouse постоянно возникают задачи, связанные с обработкой строк. Например, поиск, вычисление свойств UTF-8 строк или что-то более экзотическое, будь то поиск типа учёта регистра или поиск по сжатым данным.


      Всё началось с того, что руководитель разработки ClickHouse Лёша Миловидов o6CuFl2Q пришёл к нам на факультет компьютерных наук в НИУ ВШЭ и предложил огромное количество тем для курсовых и дипломов. Когда я увидел «Умные алгоритмы обработки строк в ClickHouse» (я, человек, который увлекается разными алгоритмами, в том числе экспериментальными), сразу же настроил планов, как сделаю самый крутой диплом. Мою радость и выражение лица можно описать следующей картинкой:



      Читать дальше →
      • +57
      • 11.7k
      • 7
    • Размещаем сайт в анонимной сети I2P (+ параноидальный режим)



        Предположим, что ты уже зашел несколько раз в I2P, початился там с ребятами в irc, проникся идеей ламповой невидимой и задумался о собственном (в)кладе в I2P. В раздумьях об этом ты посидел пару дней перед раскрытым блокнотом — узнав попутно из новостей, что не только флибуста, но и рутрекер был запрещен, — и наконец вспомнил про то что ты Сноуден и основатель викиликс (весьма неожиданный поворот, признаюсь, я сам не ожидал от тебя такого), и уже давно ищешь плацдарм для размещения общественно значимой информации. Например, ты решил выкладывать куда-нибудь картинки с котиками, которых ты налайкал в твиттере (Сноуден лайкает котиков в твиттере, ты знал?). И выбор твой пал на I2P.
        Читать дальше →
      • Королева офисных мышей: обзор Logitech Marathon M705

          Периферии для компьютеров повезло больше чем самим компьютерам. Она устаревает гораздо дольше, чем само компьютерное железо. Это значит, что мышь, бывшая отличной три-четыре года назад, может по-прежнему оставаться лучшей в своем сегменте. Поэтому, когда у меня сломалась предыдущая мышь-долгожитель, я переехал на Logitech M705 — классику в прямом смысле проверенную временем.

          Читать дальше →
        • Прототип. От идеи до опытной партии. Литье в силикон

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


            Читать дальше →
          • Поиск текстов, не соответствующих тематике и нахождение похожих статей

              У меня есть сайт со статьями схожей тематики. На сайте было две проблемы: спамерские сообщения и дубликаты статей, причём дубликаты часто являлись не точными копиями.

              Данный пост повествует о том, как я решил эти проблемы.

              Дано:
              • общее количество статей 140 000;
              • количество спама: примерно 16%;
              • количество не чётких дубликатов: примерно 63%;

              Задача: избавиться от спама и дубликатов, а так же не допустить их дальнейшего появления.



              Читать дальше →
            • Опыт заказа в китайских интернет-магазинах

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

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

                  Итак, начнем. Заранее прошу прощения за большое количество текста и излишнее словоблудие.
                  Читать дальше →
                • Как прикрепить к новому таскбару Windows 7 любой файл

                  • Tutorial
                  logo Новый таскбар Windows 7 отличается не только от дока макос, но также умом и сообразительностью. В частности, он очень обижается, когда к нему хотят прикрепить (pin) что-либо, отличное от .exe файла: скрипт, программу на питоне. Логику разработчиков легко понять: новый таскбар автоматически помещает прикрепляемые документы в контекстное меню программ. Например, если перетащить на таскбар текстовый документ, то к таскбару будет прикреплен notepad, а сам документ будет доступен по правому клику из списка 'pinned items'. К сожалению, у данного подхода есть две проблемы. Во-первых, нужно делать правый клик на иконке — лишнее движение, очень неудобное на тачпадах ноутбуков. Во-вторых, данный способ не работает для многих типов файлов, например — .bat файлов или скриптов на питоне. Гугление, как ни странно, быстрого ответа не дает. Поэтому, уважаемые коллеги, я вкратце законспектировал последовательность шагов, которая позволяет прикрепить к таскбару любой файл и сменить его иконку.

                  Ознакомиться с заклинанием
                • Что будет, если вы задумаете собрать 3D принтер своими руками

                  С чего всё начиналось


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

                  Немного погодя, оказалось, что все компоненты стоят вместе как готовый принтер и настрой сильно упал (Ох уж эти московские перекупщики), но на помощь пришел Китай со своими сверхдешевыми электроникой и электромеханическими компонентами. В порыве радости был заказан комплект электроники RAMPS 1.4 (Как самый простой в использовании по отзывам), 5 шаговых двигателей типа nema 17 (момент удержания должен быть не меньше 1.5кг/см, но я взял аж 4кг/см), 2 метра приводного ремня размера t2.5 с двумя алюминиевыми шкивами по 20 зубьев, а так же нагревательную платформу (mk2a самая распространенная), так же нужно не забыть взять 12 линейных подшипников lm8uu. На всё я потратил чуть больше 13 тысяч рублей, что, согласитесь, несколько меньше, чем, даже, комплекты для самостоятельной сборки в магазинах.

                  Спустя 2 месяца ожидания


                  За эти месяцы я успел познакомиться на форуме с несколькими интересными людьми, один из которых любезно распечатал на своем Replicator2 детали для моего принтера (Я выбрал конструкцию Prusa Mendel i2 из-за её дешевизны и простоты сборки). Кстати говоря, точность изготовления деталей мало на что влияет и, в принципе, можно их делать хоть из ложек, я лично сделал часть деталей для рамы из толстой фанеры. Большой проблемой было найти направляющие валы, которые стоят от 600 рублей за метр (Каленые и прочные, т.е. избыточная прочность), но решение было найдено на рынке: обычные прутки из нержавейки диаметром 8мм отлично подошли (Нужно всего 3 метра, как и что резать, написано на Вики), так же 6 метров шпилек м8 и 6 подшипников 608 (Как в роликах и скейтбордах). В качестве блока питания можно использовать что угодно от 400Вт 12-19В. Забрав с почты последнюю посылку (Не буду говорить про нашу почту, все и так всё знают. Битые и мятые коробки, ожидание, потерянные извещения), я понял, что предстоит много работы.

                  image
                  Читать дальше →
                • Латентно-семантический анализ

                  Как находить тексты похожие по смыслу? Какие есть алгоритмы для поиска текстов одной тематики? – Вопросы регулярно возникающие на различных программистских форумах. Сегодня я расскажу об одном из подходов, которым активно пользуются поисковые гиганты и который звучит чем-то вроде мантры для SEO aka поисковых оптимизаторов. Этот подход называет латентно-семантический анализ (LSA), он же латентно-семантическое индексирование (LSI)

                  Латентно-семантический анализ

                  Читать дальше →
                • Machine Learning. Курс от Яндекса для тех, кто хочет провести новогодние каникулы с пользой

                  • Tutorial
                  Новогодние каникулы – хорошее время не только для отдыха, но и для самообразования. Можно отвлечься от повседневных задач и посвятить несколько дней тому, чтобы научиться чему-нибудь новому, что будет помогать вам весь год (а может и не один). Поэтому мы решили в эти выходные опубликовать серию постов с лекциями курсов первого семестра Школы анализа данных.

                  Сегодня — о самом важном. Современный анализ данных без него представить невозможно. В рамках курса рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.



                  Читает курс лекций Константин Вячеславович Воронцов, старший научный сотрудник Вычислительного центра РАН. Заместитель директора по науке ЗАО «Форексис». Заместитель заведующего кафедрой «Интеллектуальные системы» ФУПМ МФТИ. Доцент кафедры «Математические методы прогнозирования» ВМиК МГУ. Эксперт компании «Яндекс». Доктор физико-математических наук.
                  Содержание и видео всех лекций курса
                • Знакомство с Apache Mahout

                  • Translation
                  Привет.

                  Моя первая статья на Хабре показала, что не многие знают о библиотеке Mahout. (Может быть, конечно, я в этом ошибаюсь.) Да и ознакомительного материала по этой теме здесь нет. Поэтому я решил написать пост, рассказывающий о возможностях библиотеки. Пара проб пера показали, что лучшим введением в тему будут небольшие выдержки из книги “Mahout in Action” Owen, Anil, Dunning, Friedman. Поэтому я сделал вольный перевод некоторых мест, которые, как мне кажется, хорошо рассказывают об области применения Mahout.



                  Читать перевод
                  • +10
                  • 23.1k
                  • 4
                • Как я писал фикс широкоэкранных разрешений для FlatOut


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

                  Читать дальше
                • Алгоритмы и структуры данных JDK

                  [ english version ]
                  Периодически проверяя нет ли реализации того или иного стандартного алгоритма в jdk, пришла мысль составить подобный обзор. Также интересны были причины наличия/отсутствия многих известных структур данных.
                  Формат обзора — только ключевые свойства и особенности структур и алгоритмов в составе jdk, подробности и детали — расписаны в javadoc или легко найти в исходниках.
                  Надеюсь на конструктивную критику и коллективный разум если что упустил.
                  Хватит вступлений, итак, давайте рассмотрим что включает в себя текущий jdk 7 и почему.
                  Читать дальше →
                • Делаем радиоуправление для самолета


                    Прочитав этот пост загорелся и я идеей склепать свой самолетик. Взял готовые чертежи, заказал у китайцев моторчики, аккумуляторы и пропеллеры. А вот радиоуправление решил сделать самостоятельно, во-первых — так интереснее, во-вторых — надо себя чем-то занять пока посылка с остальными запчастями будет ехать, ну и в третьих — появилась возможность соригинальничать и добавить всяких плюшек.
                    Осторожно, картинки!
                    Читать дальше →
                  • Обзор java.util.concurrent.*

                    • Tutorial
                    В повседневной работе не так уж часто приходится сталкиваться с пакетом для многопоточности java.util.concurrent. Иногда существуют проектные ограничения по использованию java 1.4.2, где нет данного пакета, но чаще всего хватает обычной синхронизации и не требуется ничего сверхъестественного. К счастью, периодически возникают задачи, заставляющие немного пораскинуть мозгами и либо написать велосипед, либо порыться в javadoc'ах и найти что-то более подходящее. С велосипедом проблем нет — просто берешь и пишешь, благо ничего суперсложного в многопоточности нет. С другой стороны, меньше кода — меньше багов. Тем более, что на многопоточность никто в здравом уме юнит тестов не пишет, т.к. это уже полноценные интеграционные тесты получаются со всеми вытекающими последствиями.

                    Что выбрать для конкретного случая? В условиях запарки и deadline'ов довольно сложно охватить весь java.util.concurrent. Выбирается что то похожее и вперед! Так, постепенно, в коде появляются ArrayBlockingQueue, ConcurrentHashMap, AtomicInteger, Collections.synchronizedList(new LinkedList()) и другие интересности. Иногда правильно, иногда нет. В какой то момент времени начинаешь осознавать, что более 95% стандартных классов в java вообще не используются при разработке продукта. Коллекции, примитивы, перекладывание байтиков с одного места на другое, hibernate, spring или EJB, еще какая то библиотека и, вуаля, приложение готово.

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

                      Владельцы дисков WD серии Green сталкиваются с слишком частой парковкой головок. В этой статье было описано как решить проблему с помощью DOS-утилиты wdidle3 от поддержки WD. Со времен этой статьи прошло много времени, но проблема осталась. Да и сам метод решения с помощью DOS-утилиты не является гуманным.
                      В процессе решения этой проблемы наткнулся на программу idle3-tools, с помощью которой можно указать время парковки головок из Linux.
                      Читать дальше →
                    • Фильтр Калмана

                      • Tutorial


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

                        С каждым днем слово java все больше и больше воспринимается уже не как язык, а как платформа благодаря небезызвестному invokeDynamic. Именно поэтому сегодня я бы хотел поговорить про виртуальную java машину, а именно — об так называемых Performance опциях в Oracle HotSpot JVM версии 1.6 и выше (server). Потому что сегодня почти не встретить людей, которые знают что-то больше чем -Xmx, -Xms и -Xss. В свое время, когда я начал углубляться в тему, то обнаружил огромное количество интересной информации, которой и хочу поделится. Отправной точкой, понятное дело, послужила официальная документация от Oracle. А дальше — гугл, эксперименты и общение:

                        -XX:+DoEscapeAnalysis


                        Начну, пожалуй, с самой интересной опции — DoEscapeAnalysis. Как многие из Вас знают, примитивы и ссылки на объекты создаются не в куче, а выделяются на стеке потока (256КБ по умолчанию для Hotspot). Вполне очевидно, что язык java не позволяет создавать объекты на стеке на прямую. Но это вполне себе может проделывать Ваша JVM 1.6 начиная с 14 апдейта.

                        Про то, как работает сам алгоритм можно прочитать тут (PDF). Если коротко, то:

                        • Если область видимости объекта не выходит за область метода, в котором он создается, то такой объект может быть создан на фрейме стека вместо кучи (на самом деле не сам объект, а его поля, на совокупность которых заменяется объект);
                        • Если объект не покидает область видимости потока, то к такому объекту другие потоки не имеют доступа и следовательно все операции синхронизации над объектом могут быть удалены.


                        Для реализации данного алгоритма строится и используется так называемый — граф связей (connection graph), по которому на этапе анализа (алгоритмов анализа — несколько) осуществляется проход для нахождения пересечений с другими потоками и методами.
                        Таким образом после прохода графа связей для любого объекта возможно одно из следующих следующих состояний:

                        • GlobalEscape — объект доступен из других потоков и из других методов, например статическое поле.
                        • ArgEscape — объект был передан как аргумент или на него есть ссылка из объекта аргумента, но сам он не выходит из области видимости потока в котором был создан.
                        • NoEscape — объект не покидает область видимости метода и его создание может быть вынесено на стек.


                        После этапа анализа, уже сама JVM проводит возможную оптимизацию: в случае если объект NoEscape, то он может быть создан на стеке; если объект NoEscape или ArgEscape, то операции синхронизации над ним могут быть удалены.

                        Следует уточнить, что на стеке создается не сам объект а его поля. Так как JVM заменяет цельный объект на совокупность его полей (спасибо Walrus за уточнение).

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

                            for (int i = 0; i < 1000*1000*1000; i++) {
                                Foo foo = new Foo();
                            }
                        

                        скорость выполнения может увеличится в 8-15 раз. Хотя, на казалось бы, очевидных случаях из практики о которых недавно писалось (тут и тут) EscapeAnalys не работает. Подозреваю, что это связано с размером стека.

                        Кстати, EscapeAnalysis как раз частично ответственен за известный спор про StringBuilder и StringBuffer. То есть, если Вы вдруг в методе использовали StringBuffer вместо StringBuilder, то EscapeAnalysis (в случае срабатывания) устранит блокировки для StringBuffer'а, после чего StringBuffer вполне превращается в StringBuilder.
                        Читать дальше →