В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
В этой части снова сталкиваемся с вложенным в цикл рекурсивным поиском "в ширину".
В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
В этой части рассмотрим некоторые "грабли", на которые можно наступить, реализуя рекурсивные алгоритмы на SQL... Которые иногда можно сделать вовсе нерекурсивными, ускоряя запрос в десятки раз!
Хэширование — простой и надёжный способ проверить целостность данных. Но как быть, если нужно удостовериться, что часть данных принадлежит определённому набору? Например, проверить отдельную транзакцию в блоке Bitcoin или чанк файла в BitTorrent? Для этого используется уникальная структура данных — Merkle-tree. В этой статье вы узнаете, как с её помощью решать задачи проверки данных без доступа к их полному объёму.
Рассмотрен способ приведения судоку: неправильного (со множеством решений) к правильному, то есть к судоку с единственным решением − . (9х9)-матрицей цифр, назначенной для неправильного судоку в качестве «Ответов на судоку». «Правка» неправильного судоку состоит в назначении для него минимального количества дополнительных цифр-подсказок, что не нарушает классической структуры судоку.
Предыстория и казус газетных судоку
Как и прежде, ближе к Новому году в почтовых ящиках жителей нашего городского округа чаще стали появляется номера газеты «Восточный округ» (ВО). И традиционно в конце каждого номера приводится головоломка судоку. И наверное, тоже уже традиционно, эти судоку ̶ неправильные, то есть имеют много решений (ответов), и только одно из них назначено в виде заполненной цифрами таблицы как «Ответы на судоку». На этот раз судоку, попавшееся на глаза (в номере ВО №40 (563)), побило все прежние рекорды по числу решений (их оказалось 83 132), из которых уважаемому читателю предложено как-то угадать единственное, приведённое в газете как «Ответы на судоку». На такой казус газетных судоку я прежде обращал внимание редакции газеты ВО. И на этот раз я не удержался, и не внял просьбе близких: «перестать заниматься ерундой» не тратить время на публикацию в сети. Год назад, анализируя последние номера газеты ВО 2023 года, я предлагал (см. habr.com/ru/articles/787496) «подправлять» подобные неправильные судоку так, чтобы они имели единственное решение. Но предлагаемая тогда «правка» налагала на судоку дополнительные ограничения, меняя их классическую структуру. Например, для судоку №149 из sudoku.bestcrosswords.ru/generator, имеющего 26918 отличных друг от друга решений, предлагалось дополнительно потребовать, чтобы на побочной диагонали матрицы располагался полный набор цифр от 1 до 9. Это дополнительное требование меняло классическую структуру судоку и усложняло восприятие привычной головоломки.
А как дополнить исходную таблицу судоку минимальным числом новых цифр-подсказок, чтобы получилось судоку с классической структурой и единственным решением, например, с тем, что приведено в газете как «Ответы на судоку»? В этом и состоит задача, решение которой позволит преодолеть казус газетных судоку.
Алгоритм Дейкстры долгое время считался самым эффективным способом обхода графа. Теперь исследователи доказали, что он «универсально оптимален».
Если вы долгое время ездите по одному и тому же маршруту, вы, вероятно, считаете его лучшим. Но «лучший» — это относительное понятие. Возможно, однажды произойдёт авария или дорога будет перекрыта, и ваш самый быстрый маршрут станет самым медленным.
Подобные сценарии также являются вызовом для исследователей, которые разрабатывают алгоритмы, пошаговые процедуры, которые компьютеры используют для решения проблем. Множество различных алгоритмов могут решить любую заданную проблему, и вопрос, какой из них лучше, может быть удручающе неоднозначным.
В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
В этой части воспользуемся возможностями линейной генерации и подсчета уникальных значений.
Скретч-лотереяTic Tac Toe («крестики‑нолики»), выпущенная компанией Ontario Lottery в 2003 году обладала интересными правилами: в правой части билета находится игровое поле с числами, в левой — «ваши счастливые числа», скрытые защитным слоем. Игроку предстоит стереть защитный слой и посмотреть, на каких позициях на игровом поле расположены его счастливые числа. Если три счастливых числа образуют линию, то игрок получает соответствующий выигрыш (для каждой линии — свой).
По правилам, игрок может сколько угодно рассматривать лотерейные билеты и покупать лишь те из них, которые кажутся ему выигрышными, возвращая не понравившиеся. Казалось бы, что могло пойти не так — ведь числа в левой части остаются неизвестны до начала игры?
В прошлой статье я разобрал как работают корутины под капотом, однозначно рекомендую ознакомиться прежде чем закапываться дальше. В этой статье мы разберем такую сущность как Job и как на самом деле под капотом отменяются корутины, в общем будет интересно, погнали!
Приветствую, Хабравчане!
Решил сделать цикл статей по написанию на С++, различных небольших программ. Под новые и старые ОС. Мне кажется мы стали забывать как раньше программировали:) Для себя определил несколько важных критериев.
Попалась мне одна интересная задача ,суть которой - найти наибольший отрезок в массиве единиц и нулей ,где суммы их кол-ва равны друг другу. Например ,имеем массив [0, 1, 0, 1, 0]. Длина наибольшего подмассива ,где кол-во нулей равно кол-ву единиц = 4. Под этот критерий подходит подмассив [{0, 1, 0, 1}, 0] ,а так же [0, {1, 0, 1, 0}]. В обоих случаях сумма всех нулей = 2 ,а сумма всех единиц равна тоже 2. Длина такой последовательности = 4 ,и это должно быть ответом.
Сперва можно немного поработать над данными ,чтобы в будущем можно было проще вычислять такие отрезки ,где суммы 1 и 0 равны друг другу. Например ,для отрезка [0, 1, 0, 1] общая сумма значений равна 2 (0 + 1 + 0 + 1). Можно сделать вывод ,что сумма 1 и 0 равна в этом отрезке ,если сумма значений равна половине длины подмассива. Для нашего случая получается ,что (0 + 1 + 0 + 1) = 2 = 4/2 (половина длины подмассива). Но гораздо проще было бы проводить расчеты ,если бы необходимая сумма значений была бы константой ,например 0. В таком случае мы можем заменить все нули на -1 ,и таким образом получим [-1, 1, -1, 1] ,где сумма таких элементов будет равна 0.
На JavaScript это можно сделать следующим образом: arr.map(x => x || -1).
Далее нам потребуется цикл по длине arr:
В ходе обсуждения с товарищем docent2007 статьи о сортировке «Милосердный Сталин» у нас сами собой родились дополнительные, весьма полезные методы сортировки. Эти методы определённо могут пригодиться каждому.
Либеральная сортировка уважает каждое значение и его "право" на место.
def liberal_sort(arr):
# Каждый элемент остается на своём месте, потому что все равны
return arrТо есть массив возвращается таким, какой он есть, без изменений, поскольку "у каждого элемента своё уникальное место, которое нельзя нарушить".
Есть еще вариант Либеральной сортировки, где все элементы группируются по какому-то общему признаку, чтобы "никто не чувствовал себя изолированным". Внутри каждой группы порядок сохраняется.
from collections import defaultdict
def liberal_sort_with_groups(arr, key_func=lambda x: x):
# Группируем элементы по ключу, но внутри групп порядок сохраняется
groups = defaultdict(list)
for item in arr:
groups[key_func(item)].append(item)
result = []
for group in groups.values():
result.extend(group)
return result
arr = [5, 3, 8, 3, 1, 8, 5]
sorted_arr = liberal_sort_with_groups(arr, key_func=lambda x: x % 2)
print(sorted_arr)
# нечетные и затем четные, но порядок в группах сохранен
# -> [5, 3, 3, 1, 5, 8, 8]
Моя основная деятельность — конфиденциальная обработка данных. Это такая развивающаяся область науки и техники, в которой часто возникает что-то новое, поэтому терминология ещё не устоялась. То, чем я занимаюсь, по-английски называется Secure Multi-Party Computation, а на русский переводят как совместные или многосторонние вычисления. Однажды я видел перевод: «многопартийные вычисления», – но, надеюсь, это единичный случай. Лично мне нравится вариант: «конфиденциальные вычисления», который использует википедия. Его буду использовать и я.
Представьте, вы собрали какие-то ценные данные, зашифровали их и сохранили на диске. Таким образом, вы защищаете данные во время хранения (data-at-rest). Далее, предположим, вам нужно передать данные по сети с одного сервера на другой. Серверы устанавливают защищённое соединение и обмениваются данными – снова зашифрованными. Так серверы защищают данные во время передачи (data-in-transit). Пока всё знакомо и понятно. Далее вы собираетесь делать то, ради чего вы эти данные собирали, хранили и передавали: использовать их. Что-нибудь посчитать, агрегат какой-нибудь, статистику или даже модельку обучить. Анализировать зашифрованные данные —, затруднительно, поэтому вы их расшифровываете и… делате беззащитными.
Во-первых, это странно: вы старательно защищали данные, когда хранили и передавали, и вдруг почему-то перестали. Во-вторых, это опасно: атаки, утечки, несанкционированный доступ, всё, что угодно может случиться, когда данные уязвимы. Ну, и в-третьих, расшифровывать не обязательно: существуют методы, защищающие данные, когда они используются (data-in-use). Совместные конфиденциальные вычисления – один из них.
В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
В сегодняшней статье посмотрим, как можно использовать рекурсию для перебора комбинаций.
В прошлой заметке я коснулся принципа работы некоторых популярных алгоритмов неточного решения задачи коммивояжера (TSP). Материал получился объемным и сунуть туда еще одно описание алгоритма было бы чрезмерностью. Тем не менее, считаю важным рассказать еще об одном решении, которое носит название - Алгоритм Кристофидеса-Сердюкова. Причины, по которым мне хочется об этом поговорить следующие:
1. Речь идет про алгоритм, который часто используется в качестве бенчмарка при оценке эффективности поиска решений сетками с использованием трансформеров, например в работе TranSPormer: A Transformer Network for the Travelling Salesman Problem и не только
2. Несмотря на то, что алгоритм назван в честь русского математика в русскоязычном сегменте интернета не так много публикаций на эту тему, можно отметить статью Сердюкова от 1978 и упоминание в Википедии
3. Наконец, алгоритм просто красив. Понимаю, что математическая эстетика – это нечто скрытое в глубине вещей и недоступное суетливому взору, но верю, что и такая категория красоты найдет своего читателя.
Это еще одна статья про демосцену, сайзкодинг, ассемблер, MS‑DOS и ретрокодинг. То есть, о том, как ночами напролет добровольно и бесплатно писать бесполезный и очень трудоемкий код, и получать от этого массу удовольствия (и седую бороду). Даже если вы уже пробовали и вам не понравилось, вам все равно стоит почитать. Возможно, вы что‑то делали не так. Например, использовали не те буквы и цифры. А еще тут есть подборка «демок» размером в 256 байт!
Я люблю работу с изображениями. Не очень разбираюсь, но люблю. Всегда с интересом читаю статьи про методы триангуляции, детектирования границ, фильтры, перцептивные хэши, форматы изображений. Лет 10 назад даже пилил по вечерам конвертер из растра в вектор, но тот проект так и остался незаконченным.
А теперь мы с командой разрабатываем PIM-систему, это инструмент по управлению информацией о товарах. Среди задач в беклоге я нашел задачу себе по душе: попробовать реализовать массовую генерацию инфографики для маркетплейсов. А в этой статье я хочу рассказать о подходе, который я использовал.
Всем привет. Меня зовут Алмаз Хуснутдинов. В этой статье я рассказываю про алгоритм обратного распространения ошибки, который используется для обучения нейросетей.
Содержание: архитектура простой нейросети и инициализация переменных, прямое распространение ручной расчет, вывод производных, вывод алгоритма, обратное распространение ручной расчет, реализация простой архитектуры нейросети и задача «логическое или», реализация класса для многослойной нейросети и изображения MNIST.
За последние годы качество LLM моделей сильно выросло, методы квантизации стали лучше, а видеокарты мощнее. Тем не менее качество генерации все еще напрямую зависит от размера весов и, как следствие, вычислительной сложности.
Кроме того, генерация текста авторегрессионна - токен за токеном по одному, потому ее сложность зависит от размера контекста и количества генерируемых токенов.
Но генерация текста не всегда имеет однородную сложность, так же как мы во многом мыслим идеями, а слова произносим «на автомате». В статье обсудим алгоритмы, позволяющие использовать эту неоднородность для ускорения.
