Алгоритмы *

Напишем код для управления пушкой, сбивающей корабли пришельцев!

Планирую несколько постов о разных технических решениях на моём (теперь опенсорсном!) сайте 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)

1. Регуляризация (Regularization): Использование методов регуляризации, таких как L1 или L2 регуляризация, может помочь снизить переобучение и улучшить стабильность модели. Регуляризация контролирует сложность модели и снижает чувствительность к малым изменениям в данных.

   t.me/DenoiseLAB (Еесли вы хотите быть в курсе всех последних новостей и знаний в области анализа данных);

❓100 Вопросов по Машинному обучению (Machine Learning) - Вопрос_12

?Вопрос_12: Expectation-Maximization (EM) ?

Expectation-Maximization (EM) - это итерационный алгоритм, который используется для оценки параметров вероятностных моделей, когда некоторые данные являются наблюдаемыми, а другие данные являются скрытыми или неполными. EM-алгоритм часто применяется в статистике и машинном обучении для обучения моделей с неизвестными параметрами.

EM-алгоритм состоит из двух основных шагов: шага ожидания (Expectation) и шага максимизации (Maximization).

1. Шаг ожидания (Expectation step, E-шаг): На этом шаге вычисляются ожидаемые значения скрытых переменных (или "ответственностей") в соответствии с текущими значениями параметров модели. Это делается путем вычисления условного математического ожидания скрытых переменных при условии наблюдаемых данных и текущих параметров модели.

2. Шаг максимизации (Maximization step, M-шаг): На этом шаге обновляются параметры модели, чтобы максимизировать ожидаемое правдоподобие, полученное на E-шаге. Обновление параметров происходит путем решения оптимизационной задачи, которая может включать максимизацию правдоподобия или минимизацию ошибки между наблюдаемыми данными и ожидаемыми значениями.

   t.me/DenoiseLAB (Еесли вы хотите быть в курсе всех последних новостей и знаний в области анализа данных);

   https://boosty.to/denoise_lab (Если вы хотите поддержать проект, или получить более модные фишки по коду и продвижению подписывайтесь).

❓100 Вопросов по Машинному обучению (Machine Learning) - Вопрос_6

?Вопрос_6: Всегда ли PCA спасает от проблеммы "проклятие размерности" и если нет, то что можно использовать вместо него ?

✔️Ответ:
РСА не всегда спасает от проклятия размерности, однако существует несколько продвинутых алгоримов для решения данной проблеммы:

• t-SNE (t-Distributed Stochastic Neighbor Embedding): Этот алгоритм позволяет визуализировать данные высокой размерности в двух или трех измерениях, сохраняя при этом их локальную и глобальную структуру. Он основан на вероятностной модели, которая пытается сохранить близость между объектами в исходном пространстве и их представлением в пространстве меньшей размерности.

• LLE (Locally Linear Embedding): LLE ищет линейные зависимости между соседними точками данных и пытается сохранить эти зависимости при снижении размерности. Алгоритм строит локальные линейные модели для каждой точки данных и затем находит низкоразмерное представление, которое наилучшим образом воспроизводит эти локальные модели.

• UMAP (Uniform Manifold Approximation and Projection): UMAP является относительно новым алгоритмом снижения размерности, который сочетает в себе методы локальной связности и глобальной структуры данных. Он строит граф связности между точками данных и затем находит низкоразмерное представление, которое сохраняет геометрическую структуру данных.

  Кроме того, в ряде задач применяются: Isomap, MDS, Random Projection, Sparse Coding, NMF.

  https://t.me/DenoiseLAB
  

Youtube-канал ones and zeros опубликовал визуализации нахождения маршрута между двумя точками в реальных городах (Чикаго и Рим) при помощи A*. Алгоритм A* — это рекурсивный алгоритм поиска пути в графах на основе эвристик, изобретённый в 1968 году как усовершенствованная версия алгоритма Дейкстры. Этот алгоритм активно применяется в разработке игр.

Статья про A* в Википедии: ссылка

Пара статей на Хабре с объяснением работы алгоритма: 1, 2

Для решения задачи наименьших квадратов с двумя переменными предлагается круговой метод оптимизации. Задано отображение из плоскости в m-мерное пространство, координатные функции которого могут удовлетворять, например, свойству покоординатной монотонности, а также свойству замедления роста: каждая координата растет тем слабее, чем больше ее величина. Задача наименьших квадратов состоит в минимизации суммы квадратов m функций, зависящих от двух переменных.

Цель - найти все оптимумы, не вычисляя производные. Пусть задано два начальных приближения a, b. Первый шаг алгоритма: найти решение линеаризованной задачи наименьших квадратов в этом направлении. В результате получится точка c. Второй шаг алгоритма: решить задачу линейного поиска относительно угла. Развернем вектор bc на такой угол, в котором значение целевой функции станет локально минимальным. Для решения этой задачи можно использовать метод парабол, если вычислить значения целевой функции при развороте вектора, скажем, на ±5° и приблизить зависимость от угла многочленом второй степени. Далее полученная точка становится вторым приближением, а второе приближение с предыдущего шага - первым.

Метод вырезает на плоскости треугольники, в которых не должно оказаться оптимума, хотя этот вопрос открыт. Таким образом, запустив алгоритм из всех углов объемлющего прямоугольника, можно получить информацию о том, где уже не следует искать оптимумы. Алгоритм удобен нормированностью углов и может быть обобщен на более высокие размерности.

Вакуум популярности

Сейчас рекомендательные алгоритмы социальных сетей и медиа настолько крутые и умные, что реально подсовывают тот контент, который нам интересен и релевантен в данный момент.

Из-за этого может сложиться мнение о каком-то информационном шуме, которого по факту нет. Точнее он есть, но только у определенной аудитории. И потом человек в беседе с друзьями говорит «Даааа, крутую фичу встроили в новый iPhone!» А его друзья хлопают глазами и вообще не в контексте.

А дело все в том, что главный персонаж этой истории пользуется продуктами Apple, подписан на блогеров, которые делают обзоры этой техники, читает новости об этом и подписан на паблики компании в социальных сетях. А его друзья пользуются Самсунгами, смотрят фильмы Кубрика и читают лонгриды про ЗОЖ (все совпадения партеров ЦА случайны ?).

Поэтому стоит держать у себя в голове, что какой-то информационный шум или повод может быть (даже скорее всего не является) не общим, а локальным, только для одной конкретной ЦА. И это инструмент маркетинга, который нужно использовать ? Можно называть это «прогревом», конечно, а можно «вакуум популярности продукта/бренда/персоны».

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

Про математические основы самого подхода вычисления контрольного числа писать не буду, кому интересно, можно почитать например тут: The Mathematics of Identification Numbers.

В частности в статье отмечалось, что классический алгоритм Луна не выявляет некоторые типы ошибок, например ошибку перестановки чисел 09->90. Есть же и другие и другие распространенные типы ошибок и подходы к их выявлению.

В статье встретилась интересная таблица с результатами исследования - статистика распределения типовых ошибок ввода числовых последовательностей, которой захотелось поделится:

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