Блог*

#prog #meme

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

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

Рассмотрим ещё раз оба случая добавления нового элемента. Если он больше максимального — и, следовательно, всех остальных — то мы можем сразу его отбросить и избежать ребалансировки кучи. Если же меньше, то он заменяет один из элементов в куче. Мы не знаем точно, какой именно, но знаем, что текущий максимум точно будет выброшен и потому оптимальным решением было бы... Просто заменить максимальный элемент новым и заново ребалансировать кучу. И в стандартной библиотеке есть для этого подходящий метод — 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>. Интересно, почему.

#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() Можем ли мы сделать ещё лучше? Да — и это связано с тем, что мы можем не безусловно класть новый элемент в кучу, а сначала посмотреть саму кучу. ⬇️⬇️⬇️

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

#meme

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

Там верховный суд США обкурился. 😐 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 Чтож, надеемся на нормальные штатозависимые законы…

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

#prog #rust Конструкторы Mutex, RwLock и CondVar теперь являются const fn и в этом качестве стабилизируются в Rust 1.63.0. github.com/rust-lang/rust/pull/97791

#kids

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

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

#prog #meme

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