Обновление и ускорение моего GA для FlappyBird!
Теперь все птицы запускаются одновременно, поэтому обучение ускорилось с ~3-5 часов до 5-10 минут при запуске на CPU, то есть в 50 раз!
Большинство университетских профессоров в мире - ленивые. Как выдумали в 1970-е годы преподавать дизайн конечных автоматов примером FSM для светофора (Traffic Light Controller FSM), так и тянут эту бодягу и по 21-му веку. При том, что современные дизайнеры чипов не светофоры конструируют, а ускорители тренировки нейросетей.
Короче мы на Школе Синтеза Цифровых Схем решили преломить эту дурную традицию (которая встречается от Южной Америки до Средней Азии и Филиппин, с провинциальными вузами в Штатах включительно) и ввести в преподавание современный хардкор. То есть сделать домашку с конструированием FSM для управления блоками FPU выдранными из современного реального открытого RISC-V процессора.
По сложности начинается не сложнее светофора, зато куда ближе к реальности и можно сделать миллион вариантов домашек и экзаменов, чтобы студенты друг у друга не списывали один и тот же светофор.
Пример домашки: сконструировать FSM (а потом и конвейер) для вычисления такого-то ряда Маклорена (для синуса, экспоненты итд), имея в наличии N блоков умножения, M сложения и R деления с плавающей точкой - с разными латентностями.
При обсуждении такой домашки возник вопрос нужно ли для операций с плавающей точкой устанавливать флаг error для нечисел и бесконечностей. Конечно нужно, потому что это удобный повод рассказать про концепцию NaN и Infinity. Полез в википедию и в шоке обнаружил, что статья IEEE_754 на русском отсутствует, хотя есть на украинском. Это непорядок, нужно срочно поправить!
Тестировал всякое для ATARI XL/XE и написал небольшую демку в 106 Байт.
Чтобы понимать куда именно смотреть - тут экран 48х24, то есть 1152 байта, но в ОЗУ весь экран представлен всего 48 байтами, еще 78 байт (кто захочет посчитать 48+78=126, тут просто кодом реализованы однотипные строки) для программирования видеочипа, которому объяснено, что каждая строка на экране смотрит на одну и ту же часть ОЗУ, так мы заполняем весь экран. Для получения нестандартного узора используется 8 байт и перепрограммирование таблицы символов. Рисунок изначально подбирается так чтобы формировался равномерный узор. Для плавности движения используется VSYNC, анимация реализована битовым сдвигом.
.include "atari.asm"
*= $3000
lda #48
?copy
sta screen-1, y
dey
bpl ?copy
; ldy #$00
iny
?copydl
lda #$42
sta dlist2, y
iny
lda #<screen
sta dlist2, y
iny
lda #>screen
sta dlist2, y
iny
cpy #72
bne ?copydl
lda #>font_data
sta CHBAS
lda #$23
sta SDMCTL
lda #<dlist
sta SDLSTL
lda #>dlist
sta SDLSTL+1
?main
ldx #1
?start
lda RTCLOK+2
?wait
cmp RTCLOK+2
beq ?wait
dex
bpl ?start
?ring
lda font_data, x
asl
adc #00
sta font_data, x
inx
cpx #08
bne ?ring
beq ?main
dlist
.byte $70, $70, $70
dlist2
*= dlist2+72
.byte $41, <dlist, >dlist
screen
*= $7400
font_data
.byte ~11000011
.byte ~10011001
.byte ~00100100
.byte ~01000010
.byte ~01000010
.byte ~00100100
.byte ~10011001
.byte ~11000011upd: -1 байт от @vadimr
upd: -1
Продолжаем разбираться с алгоритмами DFS и BFS.
В прошлый раз мы знакомились с тем, как работают алгоритмы поиска по N-деревьям. А в новом ролике Артур Михайлов, head of iOS в Технократии, показывает, как применять эти алгоритмы на практике.
Полезно как для тех, кто готовится к собеседованиям, так и тем, кто применяет алгоритмы в работе.
Интересный механизм генерации экрана для ATARI XL/XE. Из-за особенности работы видеочипа мы можем для каждой строки сканирования указать видеорежим и то, с какого участка памяти брать данные для строки.
На картинке можно увидеть зоны хода луча, когда он выключен, это Horizontal Retrace и Vertical Retrace, соответственно интервал между строками и между следующими кадрами. В эти интервалы можно выполнять код, который будет делать что-то интересное для нас. Тут будем переключать таблицы символов. Зачем это нужно? Есть текстовый режим графики 40х24 с пятью цветами, который можно использовать для игр, но мы сильно ограничены в рисовании контента динамически, так как это по сути спрайты ориентированные по знакоместам. Символы в XL/XE представлены таблицей в 128 штук (1024 байт) и мы можем рисовать изображение внутри кодовой таблицы, а потом выводить символы в виде текста. Кажется, что 128 символов не хватит чтобы заполнить экран в 40х24=960 байт, вот тут мы и получаем профит.
Новый экран будет (условно) выглядеть так:
ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$И так 24 раза. После каждых 8 строк сканирования (1 знакоместо) мы сдвигаем кодовую таблицу на 40*8 байт, где уже готово изображение для второй порции строк и т.д. То есть рисуем в памяти где участок для кодовой таблицы, а видеочип рисует их как символы. Мы получаем динамическую генерацию экрана и 5 цветов.
Когда я такое придумал, то думал, что это изобретение века, но потом нашёл информацию о таком способе: Источник 1, источник 2.
Разбираемся, как работают алгоритмы BFS и DFS. Конечно, в «Алгоритмической качалке»
В этот раз Артур показывает, как работают алгоритмы поиска по N-деревьям. Такими алгоритмами, кстати, пользуются дата-сайентисты, инженеры-электроники, сетевые инженеры и, само собой, программисты.
Так что знания максимально полезные. Переходите по ссылке и не забывайте поставить лайк и написать комментарий — это очень помогает нам продвигать контент.
Напишем код для управления пушкой, сбивающей корабли пришельцев!
Планирую несколько постов о разных технических решениях на моём (теперь опенсорсном!) сайте CodeAbbey. Но начать хочется с чего‑нибудь весёлого — поэтому начнем не по порядку, а с краткого рассказа о сравнительно новом типе задач.
Упражнения на сайте устроены так, что решать можно на любом языке — отправляем код решения и результат вычислений — но проверяется только результат (а код просто чтобы не потерялся). Но хотелось добавить и какой‑нибудь «интерактив» — и один из типов интерактивных задач — это игры, для которых пользователь пишет код выполняемый «с двух сторон»:
в браузере, чтобы игру и решение пользователя тут же визуализировать
на сервере, чтобы проверить насколько хорошо код пользователя работает
Первой идеей приходит сделать такие задачи на JavaScript — но т.к. сайт учебный, популярен здесь Python (больше 40% используют его). Пробовал реализации Питона на JS (Skulpt, позже Brython) — но у них есть недостатки... Короче, остановился на Lua — с одной стороны она похожа на Питон, но даже попроще, так что любой освоит в нужном для задачи объёме за 10–15 минут (есть инструкция). С другой — я её смог скомпилировать в JS (с помощью EMCC — вот на github).
Пример кода который пытается сбивать пришельцев «не глядя» — занимает 10–12 строк — он есть в тексте задачи. Есть и предыдущая задача попроще — определять попадание в пришельца. Было бы интересно услышать отзыв того, кто попробует решать не имея опыта в Lua!
Задачка от Т-Банка, тоже с собеседования - по сравнению с предыдущей что я показывал, от Яндекса, эта кажется ещё менее актуальной для рекрутинга в энтерпрайз - но я просто порадовался что смог её решить в live-coding режиме. Судите сами - хотели бы вы подобное встретить на собесе или нет :)))
Галя приехала на учёбу в большой университет в большом городе. Кампус расположен вдоль дороги, так что иногда между разными корпусами приходится ездить на автобусе. Галя студентка экономная и думает, как минимизировать стоимость билетов, если:
разовый билет стоит 5 копеек
безлимитный проездной на 2 дня - 18 копеек
проездной на 3 дня с лимитом 6 поездок - 22 копейки
Входные данные - массив - сколько поездок пришлось на каждый день в месяце, например:
2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 4
(здесь ответ 51)
Как это решается? Если вы знаете про "динамическое программирование" (ДП) то наверное уже поняли что задача об этом - поэтому я и удивился встретив такую задачу на собесе - скорее всего нам это не понадобится в энтерпрайзе (хотя в олимпиадных задачках популярно). Если не знаете про ДП, представьте рекурсию - вы пробуете в цикле каждый из трёх типов билетов, ездите сколько он позволяет - и дальше снова вызываете эту функцию для оставшихся поездок. Просто с рекурсией вы не дождётесь окончания работы, но с "мемоизацией" получите то же ДП "навывоворот". Я возился минут 30, но повтороив задачу у себя на сайте увидел что друзья решают аж в 3-4 строчки (ну, на питоне с @cache).
Задачка с собеседования от Яндекса. Скептически отношусь к ценности таких задачек при собеседовании сеньоров в обычный энтерпрайз - они скорее хороши на районном этапе школьной олимпиады. Но может я не прав? Итак задачка - из 4х предложенных над этой я думал дольше других:
В массиве целых чисел нужно найти фрагмент с заданной суммой.
Например, дан массив a = [4, 3, -8, 4, -1, 12, -5, 2] и целевая сумма 5 - тогда ответом будет фрагмент начиная с 3 и заканчивая -5, то есть в синтаксисе Питона sum(a[1:7]) = 5
В чем тут сложность? Сложность во "временной сложности" - требуется чтобы на массиве из миллиона чисел вычисление не занимало минуты. Поэтому наивный вариант не годится:
target = 5
for i in range(len(a)):
for j in range(i+1, len(a)+1):
if sum(a[i:j]) == target:
print(i, j)Здесь два вложенных цикла - каждый в среднем совершает число итераций сравнимое с длиной массива. Но функция sum(...) внутри тоже бежит по массиву - итого время выполнения пропорционально длине массива в кубе O(N*N*N)
Одно из усовершенствований заключается в том чтобы построить второй массив, в котором хранить сумму от начала массива до i-го элемента. Это позволит считать sum(i, j) не пробегая массив. Улучшение - теперь время пропорционально квадрату.
Можно решить и за "линейное" время - т.е. пропорциональное размеру массива без всякой степени. Когда я сообразил, то сказал "да это же старая задачка на новый лад". Попробуйте - вдруг пригодится на собесе :)
ZPAQ - консольный append-only архиватор, способный эффективно снапшотить целые директории с тысячами файлов и/или BLOBы в десятки ГБ (хоть с целыми ФС внутри) в один единственный файл. В процессе архивирования используется дедупликация на уровне фрагментов данных, сохраняющая только уникальные последовательности, а сжатие осуществляется адаптивным алгоритмом, который подстраивается под характер самих данных. Поддержка шифрования тоже имеется.
Внутри архива могут содержаться тысячи снапшотов, любой из них может быть извлечен, новые - всегда дописываются только в конец, а удалять из такого архива ничего нельзя. Можно сказать, что zpaq это такой своеобразный single-file git репозиторий для бинарных данных, стремящийся к максимальной компрессии.
Пример (не мой):
~7GB of Thunderbird mbox become ~6MB (!) in ~4 minutes.
Подход append-only архивирования zpaq, в сочетании с rsync --append дает возможность вывести инкрементальное резервное копирование на новый уровень (даже для такого простого в использовании инструмента) и приблизиться к теоретическому пределу эффективности сжатия на реальных задачах, по сравнению с классическими архивами.
Разработка не новая, оригинальный проект zpaq более не развивается, но присутствует в некоторых дистрибутивах. А также существует вполне живой форк, совместимость формата архива с оригинальным zpaq сохранена: https://github.com/fcorbelli/zpaqfranz
Tg: lomalkin_log
🧠Разомнём мозги: алгоритмическая задача
Ваш друг загадал число от 0 до 100 включительно, которое вам надо угадать. Каждый раз он отвечает либо «угадал», либо «моё число больше», «моё число меньше». Вы знаете, что он перезагадывает число до тех пор, пока может это делать, не прибегая ко лжи.
Сколько попыток потребуется в худшем случае, чтоб загнать его в угол и угадать число?
Варианты ответа:
1) Это невозможно
2) 101
3) 52
4) 13
5) 7
6) 1
Ждём ваших ответов в комментариях к посту👇
Как применять бинарный поиск для решения задач с LeetCode
Привет, давно не виделись! Мы не просто так отсутствовали какое-то время с «Алгоритмической качалкой», а все пытались записать ролик, на который договорились с аудиторией. То Казань превращались в Венецию, то больное горло давало о себе знать.
Но наконец-то мы справились и смогли записаться в парке Черное озеро с мороженым на перевес.
Как написать алгоритм работы «критического удара» для компьютерной игры
Нет, мы не начали внезапно заниматься геймдевом. Тренер «Алгоритмической качалки» Артур — давний фанат РПГ-игр, и ему интересно было разобраться в том, как работает такая механика, как «критический удар».
В новом ролике Артур покажет два варианта реализации алгоритма работы «крита». Переходите по ссылке, ставьте лайки и рассказывайте в комментариях свои идеи реализации.
Ближайшие события
Впечатлилися случайно найденным ресурсом и убил час, чтобы(, несмотря на кривое юзабилити,) найти оглавление. Вот оно:
https://opendsa-server.cs.vt.edu/home/books
(Sample OpenDSA eTextbooks)
Это один из (потенциально многих) несвязанных инстансов открытого движка для прохождения курсов по Computer Science и создания новых. Крутая его фишка: визуализация алгоритмов, структур данных и концепций, таких как стили вызовов функций - ещё и с упражнениями для закрепления.
Контента бездна, рекомендую прокликать ссылки.
В пятой серии «Антологии Технологий» специалисты «Яндекс Такси» рассказали, как устроена служба поддержки сервиса, как там работают умные технологии, которые позволяют поддержке отвечать практически на любое обращение за несколько минут.
Каждую неделю в поддержку «Яндекс Такси» поступает около 1,5 млн обращений от пассажиров и партнёров сервиса. Это очень малая часть от всех поездок «Яндекс Такси», но весьма ощутимая в масштабах одного отдела техподдержки компании.
Специалисты «Яндекс Такси» раскрыли детали распределения самых запутанных обращений по темам и попытки призывать для ответа на них нужных специалистов.
В компании рассказали, что на многие обращения безошибочно отвечает искусственный интеллект, большинство авторов обращений даже считают, что с пользователями разговаривает обычный человек.
В «Яндекс Такси» признали, что техподдержка сервиса не может оперативно работать без умных алгоритмов, а определённую роль и всё больше более востребованную роль в сервисе играет фирменная нейросеть.
Go: Раскрытие потенциала скорости
Я всегда борюсь за скорость. Началось это все с того, как я прочитал книгу “Грокаем алгоритмы” и меня заинтересовало измерение скорости выполнения. Потом, решая задачи на LeetCode я расстраивался, если алгоритм получался медленным. Недавно мне пришла идея написать пост на эту тему, а во время написания изучить этот вопрос получше. Я прочитал не мало статьей, большинство из которых - англоязычные.Так что вот советы по увеличению скорости Вашего приложения на Golang :
1. Выделять ёмкость для среза с помощью make
При создании среза выделяйте ёмкость с помощью make, так Вы избавитесь от перераспределений
2. При возвращении указателя, объявлять его при создании переменной
func (r Ruleset) Match(path string) (*Rule, error) {
for i := len(r) - 1; i >= 0; i-- {
rule := r[i] //так НЕ надо
rule := &r[i] //так надо
match, err := rule.Match(path)
if match || err != nil {
return &rule, err //так НЕ надо
return rule, err //так надо
}
}
return nil, nil
}3. Пишите бенчмарки
Пишите бенчмарки для вашего приложения, так Вы поймете, в каком месте оно работает медленнее всего. Источник для того, чтобы научиться писать бенчмарки: https://dave.cheney.net/2013/06/30/how-to-write-benchmarks-in-go и др.
4. Используйте горутины!
Когда есть возможность, используйте горутины. Например, когда результат 2-х операций не зависит друг от друга, можете использовать горутины. Думаю, доказывать, что таким образом приложение становится быстрее, не надо :)
Как решить задачу 3Sum на Python: видеоинструкция для начинающих
Давно мы не публиковали «Алгоритмическую качалку» на Хабре — исправляемся. В новом ролике главная по прокачке алгоритмических мышц Альбина показывает, как решить задачу Three Sum на языке Python.
Будем рады вашим решениям в комментариях, а также лайкам и комментариям на YouTube.
Google представила открытую библиотеку jpegli с реализацией кодировщика и декодировщика изображений в формате JPEG.
Библиотека включает дополнительные оптимизации для повышения эффективности кодирования, позволяющие на 35% увеличить степень сжатия высококачественных изображений, по сравнению с традиционными кодеками JPEG.
В сравнении с libjpeg-turbo проект jpegli позволяет добиться аналогичного уровня качества при снижении битрейта на 32%. На уровне API и ABI библиотека полностью совместима с libjpeg62 и может применяться для её прозрачной замены. Код jpegli написан на языке С++ и распространяется под лицензией BSD.
Библиотека jpegli позволяет кодировать изображения с выделением 10 и более битов на цветовой компонент. При этом результат работы алгоритмов кодирования адаптируется для традиционной для формата JPEG модели, допускающей использование только 8 бит на цветовой компонент. Подобная особенность позволяет сохранить совместимость с уже существующими декодировщиками, рассчитанными на 8-битовое представление цветовых составляющих.
Кодируемые при помощи jpegli изображения полностью соответствуют стандарту JPEG, не требуют специфичных декодировщиков и могут просматриваться в существующих просмотрщиках JPEG и веб‑браузерах. Применение для распаковки изображений, сжатых при помощи jpegli, собственного декодировщика позволяет добиться дополнительного снижения артефактов. Скорость кодирования при помощи jpegli сопоставима с библиотеками libjpeg‑turbo и MozJPEG.
Источник: OpenNET.
Фильтры Throttling VS Debounce
Оказывается, они работают по-разному )
Еще посты об IT в ИТ БД → t.me/it_bd
Оба этих фильтра используются для того, чтобы не дублировать события.
Например, пользователь злостно и быстро кликает на кнопку «Обновить» десять раз подряд.
Но нам достаточно сделать один запрос к беку вместо десяти, чтобы получить актуальное значение.
В этом случае нужно отфильтровать лишние события, то есть пропустить лишние клики, обработав лишь 1 событие.
И тут есть два подхода:
Throttling — пропускает первое событие и игнорирует остальные N миллисекунд
Например, если установить Throttling = 500мс, то обработается первый клик, а все следующие 500мс клики будут игнорироваться.
Debounce — отсчитывает N миллисекунд после последнего события и только после этого пропускает последнее событие.
Например, если установить Debounce = 500мс, то клики будут игнорироваться, пока пользователь не сделает перерыв в 500мс. После 500мс простоя последнее событие обработается.
❓100 Вопросов по Машинному обучению (Machine Learning) - Вопрос_14 (Часть_2)
Регуляризация (Regularization): Использование методов регуляризации, таких как L1 или L2 регуляризация, может помочь снизить переобучение и улучшить стабильность модели. Регуляризация контролирует сложность модели и снижает чувствительность к малым изменениям в данных.
t.me/DenoiseLAB (Еесли вы хотите быть в курсе всех последних новостей и знаний в области анализа данных);