В продолжение темы хочу поделиться своим кодом, который обгоняет std::sort() из актуальных версий GNU C++ Library и (примерно, нет точных данных) повторяет результат "Сортировки Александреску" с CppCon 2019.
Рубрика «Алгоритмы» - 58
«5 копеек» к разговору о Cортировках
2019-09-30 в 11:00, admin, рубрики: C, c++, sort, sorting, Алгоритмы, высокая производительность, Программирование, сортировка, сортировкиАлгоритмы поиска простых чисел
2019-09-30 в 7:53, admin, рубрики: Baillie–PSW, Алгоритмы, криптография, простые числа, решето Аткина, решето Эратосфена, Тест Люка, Тест Миллера-Рабина, числа мерсенна
«Самое большое простое число 232582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс
Число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.
Читать полностью »
Один способ вычисления логарифма по основанию 2
2019-09-29 в 5:50, admin, рубрики: fpga, Алгоритмы, вычисление логарифма, логарифм, математикаВычисление логарифмов довольно распространённая операция в цифровой обработке сигналов. Чаще пожалуй приходится считать только свёртки (умножение с накоплением) и амплитуды с фазами. Как правило для вычисления логарифмов на FPGA применяется алгоритм CORDIC в гиперболическом варианте, требующий только таблицы и простых арифметических операций. Однако это не всегда бывает удобно, особенно если проект большой, кристалл маленький и начинаются танцы с оптимизацией. Именно с такой ситуацией и пришлось мне однажды столкнуться. Оба порта блока RAM (Cyclone IV) уже плотненько были в работе, не оставляя свободных окон. Использовать ещё один блок под гиперболический CORDIC не хотелось. Зато был умножитель, для которого во временной диаграмме получалось приличное свободное окно. Денёк подумав, я сочинил следующий алгоритм, в котором не используется таблиц, но есть умножение, точнее возведение в квадрат. И поскольку схемотехнически возведение в квадрат проще общего случая умножения, возможно этот алгоритм представляет интерес для специализированных микросхем, хотя для FPGA разницы конечно нет. Подробнее под катом.Читать полностью »
Нейросеть для классификации спутниковых снимков с помощью Tensorflow на Python
2019-09-26 в 11:50, admin, рубрики: Алгоритмы, Блог компании Инфосистемы Джет, классификация, машинное обучение, спутниковые снимки
Это пошаговая инструкция по классификации мультиспектральных снимков со спутника Landsat 5. Сегодня в ряде сфер глубокое обучение доминирует как инструмент для решения сложных проблем, в том числе геопространственных. Надеюсь, вы знакомы с датасетами спутниковых снимков, в частности, Landsat 5 TM. Если вы немного разбираетесь в работе алгоритмов машинного обучения, то это поможет вам быстро освоить это руководство. А для тех, кто не разбирается, будет достаточным знать, что, по сути, машинное обучение заключается в установлении взаимосвязей между несколькими характеристиками (набором признаков Х) объекта с другим его свойством (значением или меткой, — целевой переменной Y). Мы подаём на вход модели много объектов, для которых известны признаки и значение целевого показателя/класса объекта (размеченные данные) и обучаем ее так, чтобы она могла спрогнозировать значение целевой переменной Y для новых данных (неразмеченных).
Читать полностью »
Создание пиксельной туманности при помощи шума и Median Cut
2019-09-25 в 13:16, admin, рубрики: dithering, fractional brown motion, perlin noise, pixel-art, Алгоритмы, Дизайн игр, дизеринг, обработка изображений, пиксель-арт, разработка игр, шум перлинаЯ хотел, чтобы в моей игре The Last Boundary была туманность. Они потрясающе выглядят и космос без них не космос, а просто разбросанные по фону белые пиксели. Но так как игру я делаю в стиле «пиксель-арт», то мне нужно было как-то заставить мою библиотеку шума генерировать пикселизированные изображения.
Вот несколько примеров:
Ещё примеры
В одноцветных примера используется 8 цветов, а в других — 16 цветов. В этой статье я расскажу, как создавал пикселизированную туманность для The Last Boundary.
Читать полностью »
End2End-подход в задачах Automatic Speech Recognition
2019-09-25 в 9:54, admin, рубрики: asr, end-to-end, nlu, Алгоритмы, Блог компании МТС, звук, ИИ, искусственный интеллект, машинное обучение, МТС, нейросеть, распознавание речиЧто такое End2End-распознавание речи, и зачем же оно нужно? В чем его отличие от классического подхода? И почему для обучения хорошей модели на основе End2End нам потребуется огромное количество данных — в нашем сегодняшнем посте.
Классический подход к распознаванию речи
Прежде чем рассказать про End2End-подход, стоит сначала поговорить про классический подход к распознаванию речи. Что он из себя представляет?
Как я создал фильтр, не портящий изображение даже после миллиона прогонов — часть 2
2019-09-25 в 9:06, admin, рубрики: H.264, HEVC, lanczos, Алгоритмы, видеокодеки, обработка видео, обработка изображений, Работа с видео, сжатие видео, фильтры изображений
В первой части этого поста я рассказал, как многократное применение стандартных halfpel-фильтров создаёт искажённые изображения, а затем показал новый фильтр, не имеющий данной проблемы.
Он был немного более размытым и это устроит не всех. Однако он был лучше своих альтернатив — на самом деле именно этот фильтр использовался в оригинальной версии Bink 2. Из-за постоянной нагрузки на работе мне никогда не удавалось вернуться к нему снова и исследовать его подробнее.
Но теперь, когда я нашёл время для возврата к этому фильтру и написания статьи о нём, мне наконец стоит задаться вопросом: существует ли менее размывающий фильтр, который всё же сохраняет свойство «бесконечной стабильности»?
Предупреждение о спойлерах: правильный ответ — «вероятно, нет» и «определённо, есть». Но прежде чем мы дойдём до того, почему на этот вопрос есть два ответа и что они означают, давайте получше подготовим испытательный стенд.
Читать полностью »
Превосходный FAQ о квантовом превосходстве от Скотта Ааронсона
2019-09-24 в 14:53, admin, рубрики: Google, Алгоритмы, время знатоков, квантовое превосходство, квантовые вычисления, квантовые технологии, квантовый компьютер, Научно-популярное, физикаПару дней назад в сеть утек черновик статьи от Google о достижения ими квантового превосходства в сверхпроводящем квантовом компьютере. Сам текст быстро убрали, а вокруг него множатся слухи и предположения, в том числе и ошибочные. Автор поста — профессор Скотт Ааронсон — один из главных специалистов по квантовым алгоритмам, и ведет отличный блог. В последнем посте он отвечает на главные вопросы о квантовом превосходстве.
Как я создал фильтр, не портящий изображение даже после миллиона прогонов
2019-09-24 в 6:25, admin, рубрики: H.264, HEVC, lanczos, Алгоритмы, видеокодеки, обработка видео, обработка изображений, Работа с видео, сжатие видео, фильтры изображенийЗавершив создание веб-архитектуры для нашего нового веб-комикса Meow the Infinite, я решил, что самое время написать несколько давно назревших технических статей. Данная статья будет посвящена фильтру, разработанному мной несколько лет назад. Он никогда не обсуждался в области сжатия видео, хотя мне кажется, что это стоит сделать.
В 2011 году я разработал “half-pel filter”. Это особый вид фильтра, который берёт входящее изображение и максимально убедительно отображает, как бы выглядело изображение при сдвиге ровно на полпикселя.
Вероятно, вы задаётесь вопросом, зачем вообще может понадобиться такой фильтр. На самом деле, они достаточно часто встречаются в современных видеокодеках. Видеокодеки используют подобные фильтры, чтобы брать фрагменты предыдущих кадров и использовать их в последующих кадрах. Более старые кодеки перемещали данные кадра только по целому пикселю за раз, однако новые кодеки пошли дальше и для лучшей передачи мелких движений позволяют выполнять сдвиг на половину или даже на четверть пикселя.
При анализе поведения алгоритмов компенсации движения в традиционных halfpel-фильтрах, Джефф Робертс выяснил, что при многократном применении к последовательным кадрам они быстро деградируют, заставляя другие части видеокомпрессора ипользовать для исправления артефактов больше данных, чем необходимо. Если отключить эти исправления и взглянуть на «сырые» результаты halfpel-фильтра, то такое исходное изображение:
превращается вот в такое:
всего спустя одну секунду видео. Как и должно, оно сдвинуто в сторону, потому что каждый кадр сдвигал изображение на полпикселя. Но результат выглядит не как перемещённая версия исходного изображения, он серьёзно искажён.
Читать полностью »
Делись, рыбка, быстро и нацело
2019-09-23 в 19:36, admin, рубрики: asm, c++, Алгоритмы, ассемблер, деление нацело, математика, оптимизация кода
Деление — одна из самых дорогих операций в современных процессорах. За доказательством далеко ходить не нужно: Agner Fog[1] вещает, что на процессорах Intel / AMD мы легко можем получить Latency в 25-119 clock cycles, а reciprocal throughput — 25-120. В переводе на Русский — МЕДЛЕННО! Тем не менее, возможность избежать инструкции деления в вашем коде — есть. И в этой статье, я расскажу как это работает, в частности в современных компиляторах(они то, умеют так уже лет 20 как), а также, расскажу как полученное знание можно использовать для того чтобы сделать код лучше, быстрее, мощнее.
Читать полностью »