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

Автор: admin от Сегодня, 11:05, посмотрело: 0

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

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



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



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

->

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

 

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

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

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




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

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

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



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



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



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

->

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

 

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

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

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


Для кодов, описанных в предыдущей статье про восстановление данных, предполагалась постановка задачи, при которой минимизируется количество дисков, необходимых при операции восстановления. В [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, посмотрело: 72

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



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



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



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

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

 

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

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

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

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

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

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

 

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

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

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



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



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



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

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

 

Постквантовая реинкарнация алгоритма Диффи-Хеллмана: вероятное будущее (изогении)

Автор: admin от 17-07-2017, 20:05, посмотрело: 25

Постквантовая реинкарнация алгоритма Диффи-Хеллмана: вероятное будущее (изогении)


Сегодня мы снова поговорим про протокол Диффи-Хеллмана, но уже построенный на более необычных конструкциях — изогениях, которые признаны устойчивыми к атакам на будущем квантовом компьютере. Квантовый компьютер, который сможет удержать в связанном состоянии порядка нескольких тысяч кубит, позволит находить закрытые ключи по открытым ключам у всех используемых сейчас асимметричных криптосистем. Число кубит для взлома RSA равно удвоенному числу бит в модуле (т.е. для разложения на множители модуля RSA длиной 2048 бит потребуется 4096 кубит). Для взлома эллиптических кривых необходимы более скромные мощности «квантового железа»: для решения задачи ECDLP для кривых над простым полем (такие кривые есть и в отечественном стандарте подписи ГОСТ Р 34.10-2012 и в американском ECDSS) c модулем кривой длиной n бит требуется 6n кубит (т. е. для модуля в 256 бит надо ~ 1536 кубит, а для 512 бит ~ 3072 кубит). На днях российско-американская группа ученых установила мировой рекорд, удержав в связанном состоянии 51 кубит. Так что у нас есть еще немного времени для изучения изогений (а также решеток, кодов, multivariate и подписей, основанных на хэшах).

Кстати, изогении считаются одним из наиболее вероятных кандидатов на победу на конкурсе NIST постквантовых алгоритмов для замены RSA и эллиптических кривых в ближайшие несколько лет. ->

Категория: Информационная безопасность, Криптография

 

Снимаем “4D видео” с помощью depth-сенсора и триангуляции Делоне

Автор: admin от 17-07-2017, 18:15, посмотрело: 28

Снимаем “4D видео” с помощью depth-сенсора и триангуляции Делоне

Привет Хабр! Это заметка о небольшом хобби-проекте, которым я занимался в свободное время. Я расскажу, как с помощью несложных алгоритмов превращать карты глубины от depth-сенсоров в забавный вид контента — динамические 3D сцены (их ещё называют 4D video, volumetric capture или free-viewpoint video). Моя любимая часть в этой работе — алгоритм триангуляции Делоне, который позволяет превращать разреженные облака точек в плотную полигональную сетку. Приглашаю всех, кому интересно почитать про алгоритмы, самописные велосипеды на C++11, и, конечно же, посмотреть на трёхмерных котиков.

Для затравки: вот что получается при использовании RealSense R200: skfb.ly/6snzt (подождите несколько секунд для загрузки текстур, а затем используйте мышку, чтобы поворачивать сцену). Под катом есть ещё!
Обладатели лимитированных тарифов, будьте осторожны. В статье много разных изображений и иллюстраций.

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

 

Применение преобразования Фурье для создания гитарного тюнера на Android. Часть 1

Автор: admin от 17-07-2017, 16:25, посмотрело: 28

Применение преобразования Фурье для создания гитарного тюнера на Android. Часть 1

В основе спектрального анализа звуковых данных лежит алгоритм, который носит название преобразование Фурье. При раскладывании исходного звукового сигнала на частотные составляющие, отдельные частоты называются гармониками. Основная гармоника определяет высоту звучания, а второстепенные гармоники определяют его тембр. Есть достаточно много мобильных приложений, которые используют преобразование Фурье для того, чтобы отобразить весь спектр частот (гармоник). Так же, есть мобильные приложения, которые служат для настройки гитар. Они работают по принципу: основная гармоника находится по самому высокому значению амплитуды в спектре. Такое утверждение не совсем верно, потому что основная гармоника определяется самой наименьшей из всех кратных этой гармонике, либо шагом между гармониками. Возникает необходимость найти способ, который позволит отобразить значение основной гармоники в спектре звукового сигнала.

В первой части статьи мы рассмотрим принцип работы дискретного преобразование Фурье, а также возможность записывать звуковые данные с Android устройства с помощью класса AudioRecord.

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

 

Метод BFGS или один из самых эффективных методов оптимизации. Пример реализации на Python

Автор: admin от 16-07-2017, 07:40, посмотрело: 43

Метод BFGS или один из самых эффективных методов оптимизации. Пример реализации на Python


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

Существует несколько модификаций метода:
L-BFGS (ограниченное использование памяти) — используется в случае большого количества неизвестных.
L-BFGS-B — модификация с ограниченным использованием памяти в многомерном кубе.

Метод эффективен и устойчив, поэтому зачастую применяется в функциях оптимизации. Например в SciPy, популярной библиотеки для языка python, в функции optimize по умолчанию применяется BFGS, L-BFGS-B.

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

 
Назад Вперед