Разбирая одну олимпиадную задачу мы отправимся по петляющим коридорам генерации лабиринтов и их прохождения, а также увидим, что на языке Julia простота реализаций алгоритмов граничит с их псевдокодом.
Рубрика «ненормальное программирование» - 30
Джулия в лабиринте
2019-05-17 в 6:07, admin, рубрики: astar, Julia, алгоритм Прима, Лабиринты, ненормальное программирование, олимпиадные задачи, поиск в глубину, Программирование, Спортивное программированиеПро подсчёт битов, беззнаковые типы в Kotlin и про ситуации, когда экономия на спичках оправдана
2019-05-16 в 7:26, admin, рубрики: kotlin, Блог компании FunCorp, ненормальное программирование, оптимизация кода
К написанию статьи подтолкнул вот этот комментарий. А точнее, одна фраза из него.
… расходовать память или такты процессора на элементы в миллиардных объёмах — это нехорошо…
Так сложилось, что в последнее время мне именно этим и пришлось заниматься. И, хотя, случай, который я рассмотрю в статье, довольно частный — выводы и применённые решения могут быть кому-нибудь полезны.
Немного контекста
Приложение iFunny имеет дело с колоссальным объёмом графического и видеоконтента, а нечёткий поиск дубликатов является одной из очень важных задач. Сама по себе это большая тема, заслуживающая отдельной статьи, но сегодня я просто немного расскажу о некоторых подходах к обсчёту очень больших массивов чисел, применительно к этому поиску. Конечно же, у всех разное понимание «очень больших массивов», и тягаться с Адронным коллайдером было бы глупо, но всё же. :)
Если совсем коротко про алгоритм, то для каждого изображения создаётся его цифровая подпись (сигнатура) из 968 целых чисел, а сравнение производится путем нахождения «расстояния» между двумя сигнатурами. Учитывая, что объём контента только за два последних месяца составил порядка 10 миллионов изображений, то, как легко прикинет в уме внимательный читатель, — это как раз те самые «элементы в миллиардных объёмах». Кому интересно — добро пожаловать под кат.
Читать полностью »
Принимаем участие в недавнем Telegram Contest, пишем крутое OpenGL ES приложение и выигрываем ничего
2019-05-14 в 4:35, admin, рубрики: telegram contest, высокая производительность, Занимательные задачки, наедалово, негодование, ненормальное программирование, Разработка под android, соревнования по программированию
Забегая вперед, хотелось бы обратить внимание на сумбурную ситуацию с победителем первого этапа конкурса. Победитель забрал 50К американских президентов. НО, был как минимум, еще один разработчик, который написал идентичное приложение и не был никак вознагражден. Он даже последнего места не занял. Этот разработчик публично, через свой сайт — https://tgcontest.braychuk.com/, обратился к команде Telegram с вопросами. Если кто-нибудь, что-нибудь знает об этом, напишите пожалуйста в комментариях.
Итак, приступим. Читать полностью »
Виртуальный 4-битный микроконтроллер с программированием тремя кнопками и четырьмя переключателями
2019-05-14 в 3:59, admin, рубрики: 4 бита, ATmega4809, DIY, diy или сделай сам, гаджеты, микроконтроллер, ненормальное программирование, программирование микроконтроллеров, ретрокомпьютинг
Предлагаемое устройство эмулирует на микроконтроллере ATmega4809 абстрактный 4-битный микроконтроллер с адресным пространством в 256 байт, который можно программировать тремя кнопками и четырьмя переключателями.Читать полностью »
QEMU.js: теперь по-серьёзному и с WASM
2019-05-12 в 15:31, admin, рубрики: C, javascript, jit, qemu, qemu.js, tcg, wasm, webassembly, виртуализация, ненормальное программированиеКогда-то давно я смеха ради решил доказать обратимость процесса и научиться генерировать JavaScript (а точнее, Asm.js) из машинного кода. Для эксперимента был выбран QEMU, некоторое время спустя была написана статья на Хабр. В комментариях мне посоветовали переделать проект на WebAssembly, да и самому бросать почти законченный проект как-то не хотелось… Работа шла, но уж очень медленно, и вот, недавно в той статье появился комментарий на тему «Так и чем всё закончилось?». На мой развёрнутый ответ я услышал «Это тянет на статью». Ну, раз тянет, то будет статья. Может, кому пригодится. Из неё читатель узнает некоторые факты про устройство бекендов кодогенерации QEMU, а также как написать Just-in-Time компилятор для веб-приложения.
Интро Newton Protocol: что можно уместить в 4 килобайта
2019-05-06 в 4:54, admin, рубрики: demo, demoscene, javascript, ray tracing, revision, WebGL, Демосцена, ненормальное программирование, Работа с 3D-графикой, разработка игр, соревнования по программированию
Недавно я участвовал соревнованиях демосцены Revision 2019 в категории «PC 4k intro», и моё интро выиграло первое место. Я занимался кодингом и графикой, а dixan сочинял музыку. Основное правило соревнования — необходимо создать исполняемый файл или веб-сайт, имеющий размер всего 4096 байта. Это означает, что всё приходится генерировать с помощью математики и алгоритмов; никаким другим способом не получится ужать изображения, видео и аудио в такой крошечный объём памяти. В этой статье я расскажу о конвейере рендеринга своего интро Newton Protocol. Ниже можно посмотреть готовый результат, или нажать сюда, чтобы посмотреть как оно выглядело вживую на Revision, или зайти на pouet, чтобы прокомментировать и скачать участвовавшее в конкурсе интро. О работах конкурентов и об исправлениях можно прочитать здесь.
Втиснуть Бейсик в 768 байт
2019-05-06 в 4:00, admin, рубрики: 768 байт, бейсик, ненормальное программирование, ретрокомпьютинг, старое железо
Тем, кому посчастливилось написать свою первую программу на Бейсике в конце восьмидесятых, объём интерпретатора в 16 килобайт кажется вполне естественным. Так было не всегда, известны интерпретаторы объёмом в 8 и 4 килобайта, конечно, с более скромным набором функций. Но в этот раз сделано, казалось бы, невозможное — интерпретатор ужат до 722 байт. Это меньше, чем 768, а значит, его получится поместить не в четыре, а в три микросхемы ПЗУ по 256 байт. Да, были и такие!
А 768 байт — это, между прочим, в 21,(3) раза меньше, чем 16384.Читать полностью »
С сожалением об отсутствии в C++ полноценного static if или…
2019-04-23 в 9:29, admin, рубрики: c++, C++14, c++17, ненормальное программирование, Программирование… как наполнить шаблонный класс разным содержимым в зависимости от значений параметров шаблона?
Когда-то, уже довольно давно, язык D начали делать как "правильный C++" с учетом накопившегося в C++ опыта. Со временем D стал не менее сложным и более выразительным языком, чем C++. И уже C++ стал подсматривать за D. Например, появившийся в C++17 if constexpr, на мой взгляд, — это прямое заимствование из D, прототипом которому послужил D-шный static if.
К моему сожалению, if constexpr в С++ не обладает такой же мощью, как static if в D. Тому есть свои причины, но все-таки бывают случаи, когда остается только пожалеть, что if constexpr в C++ не позволяет управлять наполнением C++ного класса. Об одном из таких случаев и хочется поговорить.
Речь пойдет о том, как сделать шаблонный класс, содержимое которого (т.е. состав методов и логика работы некоторых из методов) менялось бы в зависимости от того, какие параметры были переданы этому шаблонному классу. Пример взят из реальной жизни, из опыта разработки новой версии SObjectizer-а.
Задача, которую требуется решить
Требуется создать хитрый вариант "умного указателя" для хранения объектов-сообщений. Чтобы можно было написать что-то вроде:
Как рассадить всех по науке и не превратить кабинет в рассадник ненависти
2019-04-19 в 8:33, admin, рубрики: python, Блог компании Инфосистемы Джет, будущее здесь, изобрел велосипед, ненормальное программирование, офис, простое сложно, управление, управление персоналом
Рано или поздно в жизни большинства команд наступает он — переезд. Вас приводят в чистое пустое помещение, которому предстоит стать местом, где вы будете проводить большую часть своей жизни. Если вы дизайнер, то первым делом придумаете, как развесить картины и поставить цветы, чтобы помещение заиграло новыми красками. Если вы опытный офисный самурай, то сразу наметанным глазом определите наилучшее место и первым заявите на него права. Если вы руководитель отдела, то вас наверняка посетит головная боль по поводу рассадки всех сотрудников. Но если вы при этом возглавляете команду датасайентистов, то монетка Python вам в помощь.
Читать полностью »
Можно ли рендерить реалистичные изображения без чисел с плавающей запятой?
2019-04-19 в 4:53, admin, рубрики: c++, Алгоритмы, ненормальное программирование, Работа с 3D-графикой, рациональные дроби, рендеринг графики, трассировка пути, целочисленная арифметика, числа с плавающей точкой/запятойВведение
«Что получится, если мы заменим числа с плавающей запятой на рациональные числа и попытаемся отрендерить изображение?»
Такой вопрос я задал себе после размышлений над твитом исследователя и преподавателя компьютерной графики Моргана Макгвайра. Он рассуждал о том, насколько сильно студенты компьютерных наук удивляются, когда впервые узнают, что для хранения привычных нам чисел с плавающей запятой в современных компьютерах нужно идти на компромиссы. И эти компромиссы делают сложными простые задачи, например, проверку принадлежности точки треугольнику. Проблема, разумеется, заключается в том, что проверка нахождения четырёх точек в одной плоскости (копланарности) с помощью определителя или какого-нибудь векторного умножения (а на самом деле это одно и то же) никогда не даст значение, точно равное нулю, чего требуют эти математические методы. Даже если бы настоящие вычисления нахождения на одной плоскости были бы точны, те же компромиссы с точностью почти с вероятностью в 1,0 дали бы ответ, что сами четыре точки не копланарны.
Это зародило во мне мысль — если допустить, что все входящие данные рендерера (координаты вершин, 3D-преобразования и т.д.) были бы заданы как рациональные числа, то создавали бы все операции, от создания луча, обхода ускоряющей структуры и до пересечения лучей с треугольниками только рациональные числа? Если это было бы так, то мы бы смогли выполнять проверку копланарности совершенно точно! Возможно, вы зададитесь вопросом, почему 3D-сцена, выраженная в рациональных числах должна давать результаты тоже только в рациональных числах…
Простая сцена, трассировка пути в которой выполнена рациональной арифметикой. Здесь используется система чисел «с плавающей чертой дроби», а не числа с плавающей запятой.
Читать полностью »