#prog #meme

Вынужден признаться, что я сам недалеко ушёл(

#prog #rust #моё

Пусть у нас есть некоторый набор данных, и нам требуется выбрать k наименьших значений из него. Для этого мы... Вызываем vals.select_nth_unstable(k -1).

Ладно, окей, это был простой способ. Но не всегда мы можем собрать все данные в одном слайсе. Если у нас эти данные лежат в, скажем, множестве, было бы довольно расточительно собирать их в вектор просто ради того, чтобы иметь возможность вызвать этот метод. Вдобавок, он слабо применим в случае, если у нас на вход передан лишь итератор и мы не можем прикинуть заранее, сколько в нём элементов.

Что же мы можем использовать? Очередь с приоритетами aka куча, одна из реализация которых есть в стандартной библиотеке Rust. Из последовательности данных мы сначала кладём первые k элементов в кучу, а потом для каждого из оставшихся элементов мы кладём его в кучу и вынимаем оттуда максимальный элемент — это просто сделать, поскольку реализация BinaryHeap — это max heap, то есть с фокусом на максимальный элемент. Обработав все значения, мы получаем в куче k наименьших элементов из набора. Так как каждая операция вставки и удаления занимает время, пропорциональное логарифму от размера кучи, а куча никогда не становится больше k + 1 элементов, общая сложность операции составляет O(n * log(k)), где n — общее число элементов. Так как обычно эта задача решается для небольшого размера k, это вполне приемлемая сложность.

Почему это работает? Докажем по индукции.

После обработки первых k элементов куча, очевидно, содержит k наименьших элементов среди первых k элементов. Это база индукции.

Пусть у нас куча после обработки m элементов содержит k наименьших элементов среди первых m значений. Докажем шаг индукции: после обработки следующего элемента куча содержит k наименьших элементов среди первых m + 1 значений.

Новый элемент либо входит в число k искомых, либо нет. Если не входит, то, очевидно, он больше всех остальных, а потому после добавления он будет на вершине кучи и сразу же будет удалён. Если же он входит в число искомых, то он должен заменить какой-то из предыдущих минимумов. Один из предыдущих минимумов больше и нового элемента, и всех остальных минимумов, а потому в число k минимальных среди первых m + 1 не входит и лежит на вершине кучи. Он и будет удалён после добавления нового элемента. Выходит, что оставшиеся значения формируют искомый набор, QED.

Теперь немного о том, как это выглядит в реализации. Простая реализация выглядит примерно так:

fn k_min<T, I>(k: usize, mut iter: I) -> Vec<I::Item>
where
T: Ord,
I: Iterator<Item = T>,
{
let mut min =
iter.by_ref().take(k).collect::<BinaryHeap<_>>();
for elt in iter {
min.push(elt);
min.pop();
}
min.into()
}

Можем ли мы сделать её лучше? Асимптотически — нет, но мы можем снизить константный множитель. Первая оптимизация — довольно очевидная — заранее аллоцировать кучу. Нам точно известно, что там будет максимум k + 1 элементов. Этим мы слегка ухудшаем использование памяти для случаев, когда значений в итераторе меньше, чем k, но зато для всех остальных избегаем реаллокаций. Второй способ — уже не столь очевидный — использовать метод for_each для обхода итераторов. Этот метод может быть реализован более эффективно, чем просто вызов .next() в цикле — смотри, например, реализацию std::iter::Chain::fold, в терминах которого реализован for_each. Реализация теперь выглядит так (опускаем заголовок и закрывающую скобку):

// защита от случая k == usize::MAX
let cap = k.checked_add(1).expect("capacity overflow");
let mut min = BinaryHeap::with_capacity(cap);
min.extend(iter.by_ref().take(k));
iter.for_each(|elt| {
min.push(elt);
min.pop();
});
min.into()

Можем ли мы сделать ещё лучше? Да — и это связано с тем, что мы можем не безусловно класть новый элемент в кучу, а сначала посмотреть саму кучу.

⬇️⬇️⬇️

Рассмотрим ещё раз оба случая добавления нового элемента. Если он больше максимального — и, следовательно, всех остальных — то мы можем сразу его отбросить и избежать ребалансировки кучи. Если же меньше, то он заменяет один из элементов в куче. Мы не знаем точно, какой именно, но знаем, что текущий максимум точно будет выброшен и потому оптимальным решением было бы... Просто заменить максимальный элемент новым и заново ребалансировать кучу. И в стандартной библиотеке есть для этого подходящий метод — BinaryHeap::peek_mut!

Как в сказано в документации насчёт временной сложности:

> If the item is modified then the worst case time complexity is O(log(n)), otherwise it’s O(1).

Этот метод возвращает не мутабельную ссылку, а (опциональное) значение типа PeekMut. Этот тип умеет Deref-аться в элемент кучи. Как осуществляется гарантия документации? В этом типе есть флаг, сигнализирующий о необходимости ребалансировки. Он не трогается в Deref::deref, но меняется с изначального false на true в DerefMut::deref_mut — или, иными словами, при разыменовывании в мутабельном контексте. В дропе проверяется этот флаг, и если он true, то куча ставит изменённый элемент на место.

Вооружившись этим инструментом, перепишем цикл перебора итератора:

iter.for_each(|elt| {
if let Some(mut largest) = min.peek_mut() {
if elt < *largest {
*largest = elt;
}
}
// largest дропается, куча ребалансируется
});

Отлично, вот теперь мы минимизировали число операций.

P. S.: в стандартной библиотеке C++ аналога BinaryHeap::peek_mut нету — и явно не потому, что это невозможно было бы сделать, ибо уже есть operator[] на std::vector<bool>. Интересно, почему.

А также доступ к форуму сообщества для решения проблем с desktop environment

Не ну вообще-то вполне неплохой бонус

#prog #meme

#prog #rust #article

Unsafe code highlighting with rust-analyzer

#prog #go #article

Data Race Patterns in Go, или как так называемый concurrent programming language провоцирует делать ошибки.

Не, серьёзно, чем больше я узнаю про Go, тем меньше понимаю, как люди вообще на нём пишут, да ещё и добровольно.

Я сделал чтобы оно рисовалось в 60fps с бесконечной глубиной!!!

Теперь вместо того чтобы каждый кадр рисовать фрактал до глубины N, я рисую только один шаг глубины, используя информацию с предыдущего кадра. За счёт такого алгоритма вы можете видеть, что изменение полигона не сразу доезжает до последних веток. Зато вся отрисовка получилась максимально отзывчивой и быстрой. Я увеличил внутреннюю текстуру и добавил антиализинг, а оно всё ещё работает со скоростью 60fps. Так же здесь получается условно бесконечная глубина, потому что чем дольше вы ждёте, тем больше получается глубина отрисовки. А судя по практике, ждать нужно лишь пару секунд.

Можно видеть что кое-где фрактал обрезается, это из-за моего подхода с текстурами. Нужно чтобы фрактал полностью помещался в текстуру, тогда он не будет обрезаться. Но это я могу решить, у меня уже есть идея сделать расчёт 360° bounding-box, который так же будет вычисляться каждый кадр, используя информацию с предыдущего кадра.

Отличные новости про #rust на Windows

# Rustup 1.25 Will Bring Easier MSVC Build Tools Installation

While the MinGW toolchain is nice (if its functionality covers your needs) the MSVC toolchain is native to Windows and thus is selected by default. One of the issues with this is that while rustup has been providing some vague instructions about Visual C++ prerequisites, it was still greatly confusing for beginners - there're like thousands of threads with questions about what exactly should the user install and from where.

So, I'm happy to see that rustup's devs have finally found a way to conveniently install the prerequisites without breaking Microsoft's distribution requirements. It's still optional and requires manual approval from the user but should help to reduce the confusion.

More details in the /r/rust announcement.

Как вы вообще сырки едите, они ж невкусные

#prog #article

embeddedartistry.com/fieldatlas/historical-software-accidents-and-errors

We never learned about significant software accidents and errors during our education or professional careers. Sometimes, we would see an event in the news and follow it, but that was often the extent of our learning. Rarely did we find that lessons were codified and applied to our work.

As our world grows more dependent on software, developers everywhere need to study historical software problems, their causes, and the implications for how we build our software. We cannot afford to keep repeating the same mistakes, especially those that cause harm.

#prog #rust #article

Bugs You'll Probably Only Have in Rust

#prog #article

Two reasons Kubernetes is so complex