Сравнение* древовидных графов

Автор: admin от 29-07-2017, 19:35, посмотрело: 256

Привет, Хабр!



* На самом деле не совсем так. При разработке информационной системы, частью которой является различная обработка конструкторско-технологической документации, у меня возникла проблема, которую вкратце можно описать следующим образом. Сегодня мы имеем один состав изделия, за день приходит несколько изменений по различным частям этого изделия и к вечеру уже неясно, что же изменилось? Изделия порой могут иметь более 10 000 элементов в составе, элементы не уникальны, а реальность такова, что изменения по составу могут активно приходить, хотя изделие уже почти готово. Непонимание объема изменений усложняет планирование.



Состав изделия можно представить в виде древовидного графа. Не найдя подходящего способа сравнения двух графов, я решил написать свой велосипед.
->

Категория: Программирование

 

Разбор задач финала Яндекс.Алгоритма 2017

Автор: admin от 27-07-2017, 14:55, посмотрело: 430

На днях завершился Яндекс.Алгоритм 2017 — наш чемпионат по спортивному программированию. В финальном раунде 25 финалистам нужно было за два с половиной часа решить шесть задач. Первое место вновь завоевал Геннадий Короткевич из питерского ИТМО — это уже четвёртая его победа после состязаний 2013, 2014 и 2015 года. Никола Йокич из Швейцарской высшей технической школы Цюриха и выпускник Университета Токио Макото Соэдзима стали вторым и третьим, повторив свои прошлогодние результаты. Вот как распределились денежные призы: победа — 300 тысяч рублей, второе место — 150 тысяч, третье — 90 тысяч.



Разбор задач финала Яндекс.Алгоритма 2017



Заявки на участие в Алгоритме 2017 подали 4840 человек. Более 60% из них — россияне. На втором месте по количеству заявок — Беларусь, далее следуют Украина, Индия и Китай. В общей сложности на чемпионат зарегистрировались жители нескольких десятков стран, включая Сингапур, Камерун, Венесуэлу и Перу.



Мы по традиции публикуем формулировки и разобранные решения задач финала.

->

Категория: Программирование, Яндекс

 

Конкурс по программированию: JSDash (промежуточные результаты 2)

Автор: admin от 26-07-2017, 17:45, посмотрело: 288

Объявление: срок приёма решений продлевается до 17 августа.



Спасибо всем, кто уже принял участие в нашем конкурсе по программированию! Мы получили 39 решений от 26 уникальных участников. Публикуем новые промежуточные результаты.
->

Категория: Программирование

 

Случайный лес vs нейросети: кто лучше справится с задачей распознавания пола из аудио (ч.1)

Автор: admin от 26-07-2017, 17:40, посмотрело: 334

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



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



Случайный лес vs нейросети: кто лучше справится с задачей распознавания пола из аудио (ч.1) ->

Категория: Программирование

 

Быстрое удаление пробелов из строк на процессорах ARM — альтернативный анализ

Автор: admin от 26-07-2017, 11:05, посмотрело: 319

Оригинал статьи: https://github.com/blu/ascii_pruner

Автор: Мартин Кръстев



Один мой друг обратил мое внимание на интересную статью на habrahabr.ru — русский перевод статьи Дэниела Лемира Быстрое удаление пробелов из строк на процессорах ARM. Эта статья заинтриговала меня по двум причинам: во-первых, кто-то на самом деле потратил время и усилия по поиску оптимального решения общей проблемы на не-x86 архитектуре (ура!), а во-вторых, результаты автор дал в конце статьи немного озадачили меня: порядка 6-ти кратное преимущество для Intel? Автор сделал однозначный вывод, что ARM-у ну очень далеко по соотношению «эффективность на такт» до «большого железа» от Интела в этой простой задаче.



Вызов принят!

->

Категория: Программирование

 

Точное вычисление средних и ковариаций методом Уэлфорда

Автор: admin от 24-07-2017, 13:45, посмотрело: 216

Метод Уэлфорда — простой и эффективный способ для вычисления средних, дисперсий, ковариаций и других статистик. Этот метод обладает целым рядом прекрасных свойств:




  • достигает отличных показателей по точности решений;

  • его чрезвычайно просто запомнить и реализовать;

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



Оригинальная статья Уэлфорда была опубликована в 1962 году. Тем не менее, нельзя сказать, что алгоритм сколь-нибудь широко известен в настоящее время. А уж найти математическое доказательство его корректности или экспериментальные сравнения с другими методами и вовсе нетривиально.



Настоящая статья пытается заполнить эти пробелы.



Точное вычисление средних и ковариаций методом Уэлфорда

->

Категория: Программирование

 

Быстрое восстановление данных. Схема бабочки для регенерирующих кодов

Автор: admin от 20-07-2017, 18:35, посмотрело: 274

Быстрое восстановление данных. Схема бабочки для регенерирующих кодов


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



Предположим, что система хранения состоит из [i]n[/i] узлов. Рассмотрим файл, состоящий из B символов поля [i]GF(q)[/i], который кодируется в n? символов над [i]GF(q)[/i] и распределяется по узлам, так, что каждый узел хранит ? символов. Код построен таким образом, что данные могут быть целиком восстановлены по информации с [i]k[/i] узлов. При этом для восстановления данных одного узла достаточно получить [i]?

Категория: Программирование, Системное администрирование

 

Сортировка пузырьком в коде Qualcomm

Автор: admin от 20-07-2017, 16:15, посмотрело: 301

Забавной находкой поделился сегодня пользователь fj333 с Reddit. Разбираясь в появившемся год назад проприетарном коде Qualcomm Technologies для Android, он обнаружил, что неизвестный программист решил в production-коде использовать сортировку пузырьком для того, чтобы найти… максимум в массиве.



Посмотреть исходный файл вы сможете по ссылке на Github или же под катом, а оценить его в работе может любой владелец устройства с Qualcomm Snapdragon 200 MSM8610 под управлением Android.



Как известно любому, кто знаком с алгоритмами сортировки, сортировка пузырьком — алгоритм учебный, и в промышленном коде не применяющийся в силу своей неэффективности; дело в том, что в наихудшем и среднем случаях он имеет сложность О(n2), к тому же его емкостная сложность в данном случае — O(n). Кого это не убедило — использовать сортировку пузырьком не рекомендует даже Барак Обама.



И это всё не учитывая того, что для поиска максимума хватило бы и простого перебора.
->

Категория: Программирование

 

Процедурная генерация в Distrust

Автор: admin от 19-07-2017, 12:10, посмотрело: 550

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

Перед вами здание- склад, сгенерированное процедурно:

Процедурная генерация в Distrust

Категория: Веб-разработка, Game Development

 

Опыт Туту.ру: Как устроено расписание электричек

Автор: admin от 18-07-2017, 12:05, посмотрело: 468

Поезда пригородного сообщение — электрички — остаются одним из самых массовых видов пассажирского транспорта в России. За год ими пользуются миллионы пассажиров, которые проезжают суммарно сотни миллиардов километров на тысячах электричек. Только в январе 2017 года, по данным столичного департамента транспорта, опубликованным в едином хранилище данных правительства Москвы (ЕХД), пассажиропоток пригородного железнодорожного транспорта составил 42,6 млн человек. Это выше на 4,1% по сравнению с показателями прошлого года.



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



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



Опыт Туту.ру: Как устроено расписание электричек
График движения поездов — это отображение процесса движения поезда в декартовой системе координат. В таком виде представляется график движения поездов на железной дороге.
->

Категория: Программирование, Веб-разработка