Ну как я и говорил

О, а первую книгу таки перевели на русский

Да фигли вы китов и хот-доги ставите?

#prog #meme

немецкие студенты придумали скрасить ожидание светофора тем, чтобы играть в понг с человеком на другой стороне перехода

прототип из 2012 года, который всё ещё выглядит круто

Очень жизненный #meme

#prog #rust

Конструкторы Mutex, RwLock и CondVar теперь являются const fn и в этом качестве стабилизируются в Rust 1.63.0. 🎉

github.com/rust-lang/rust/pull/97791

Мальчик: посылает дикпик

Мужчина: арестовывает мальчика за распространение детской порнографии

Там верховный суд США обкурился. 😐

https://meduza.io/news/2022/06/24/verhovnyy-sud-ssha-otmenil-reshenie-1973-goda-kotoroe-sdelalo-pravo-na-abort-konstitutsionnym-preryvanie-beremennosti-stanet-nezakonnym-vo-mnogih-shtatah

Чтож, надеемся на нормальные штатозависимые законы…

В опросе Stackoverflow #Rust уже седьмой год подряд удерживает место самого любимого языка программирования

#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