Алгоритмы *

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. Есть же и другие и другие распространенные типы ошибок и подходы к их выявлению.

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

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

Собеседование по алгоритмам: разноцветные соседи

Есть двадцать клеток, каждая из которых либо белая, либо чёрная. Известно, что самая левая клетка имеет белый цвет, а самая правая — чёрный. Цвета всех остальных клеток скрыты. Вы можете кликнуть на любую клетку, чтобы узнать её цвет. Ваша цель — найти пару соседних клеток разных цветов. Попробуйте!

Например, можно просто кликать на клетки слева направо. Но может оказаться, что слева много белых клеток, и вам тогда придётся потратить довольно много кликов.

Оказывается, можно найти такую пару всего за пять кликов! Сможете?

Опубликую решение в комментариях через пару дней.