amarao

Чем больше я про это думаю, тем больше я его хочу.

Любое замыкание (в расте) может управлять control flow приложения, но только в смысле panic!. Замыкание не может управлять другим control flow, например, break/continue/return.

Это делает не экивалентным цикл итератора и применение map для того же самого итератора. Несправедливо! Если бы только компилятор понимал управление control flow и мог правильно проверить его совместимость...

Я тут решал какую-то задачу на литкоде, и одна из подзадач была:

Дано строка str1 и строка str2. Надо проверить, что строка str2 состоит из повторов строки str1. По решению большей задачи размер str2 гарантировано является кратным размеру str1, то есть нужно просто проверить, что str1 снова и снова повторяется в str2.

str1 и str2 - это [u8].

Два решения:

Похожий на сишный вариант с двойным циклом

str2.iter().enumerate().all(|(i, &b1)| b1 == str1[i % str2.len()]

Мой вариант:

str2.iter().eq(str1.iter().cycle().take(str2.len()))

В целом, дело не в экономии байт, а в логике: первое делает какую-то низкоуровневую циклическую арифметику с неиллюзорным шансом словить панику на out of bound access, а второе конструирует инвариант: мы сравниваем итераторы по str2 и по циклическому повторению str1 с размером, равным длине str2.

В целом, нам бы мог помочь Iterator.array_chunks, но он не стабильный пока что (то есть его ещё нет в стабильном rust'е).

Всё-таки match в Rust - это киллер-фича. Язык должен был называться Match.

Задача на общую занимаемую площадь двумя прямоугольниками, которые могут перекрываться любым образом.

https://leetcode.com/problems/rectangle-area

Общее решение задачи: сумма площадей минус площадь пересечения. То есть задача на самом деле сводится к площади пересечения двух прямоугольников (я когда решал даже забыл про "общую площадь" и писал только пересечение).

Сначала компактный код решения, в котором "всё понятно".

use std::cmp;

impl Solution {
    pub fn compute_area(ax1: i32, ay1: i32, ax2: i32, ay2: i32, bx1: i32, by1: i32, bx2: i32, by2: i32) -> i32 {        
        let mut combined = (cmp::min(ay2, by2) - cmp::max(ay1, by1)) * (cmp::min(ax2, bx2) - cmp::max(ax1, bx1));
        if by2 < ay1 || ay2 < by1 || bx2 < ax1 || ax2 < bx1 {
            combined = 0;
        }
        (ay2-ay1) * (ax2-ax1) + (by2-by1) * (bx2-bx1) - combined
        
    }
}

А вот моё решение. Оно сильно больше строк занимает, но, надеюсь, оно лучше объясняет суть решения:

#[derive (Copy, Clone, Debug, PartialEq, Eq)]
enum Color {
    Pink,
    Violet
}

#[derive (Copy, Clone, Debug)]
enum State{
    No,
    One(Color), //Single color zone
    Intersection(i32) // two color zone
}


use State::*;
use Color::*;

impl Solution {
    pub fn compute_area(ax1: i32, ay1: i32, ax2: i32, ay2: i32, bx1: i32, by1: i32, bx2: i32, by2: i32) -> i32 {
        fn intersection(a1: i32, a2: i32, b1: i32, b2: i32) -> i32{
            let mut colored_dots = [(a1, Violet), (a2, Violet), (b1, Pink), (b2, Pink)];
            colored_dots.sort_by(|a, b| a.0.cmp(&b.0));
            let mut state = No;
            for dot in colored_dots{
                match (state, dot) {
                    (No, (_, color))  => {
                        state = One(color);
                    },
                    (One(color), (start, new_color)) if color != new_color => {
                        state = Intersection(start);
                    },
                    (Intersection(start), (end, _)) => {
                        return end-start;
                    }
                    _ => { // no intersection
                        return 0;
                    }
                }
            }
            0
        }
        fn area(x1:i32, x2:i32, y1:i32, y2:i32) -> i32 {
            (x2-x1)*(y2-y1)
        }
        let intersection = intersection(ax1, ax2, bx1, bx2) * intersection(ay1, ay2, by1, by2);
        let rect1 = area(ax1, ax2, ay1, ay2);
        let rect2 = area(bx1, bx2, by1, by2);
        rect1 + rect2 - intersection
    }
}

Когда я написал match, это было ощущение "хорошей презентации". Вместо каких-то странных cmp/min/max, я объясняю алгоритм.

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

Идя по всем точкам: для первой точки (state=No), нам важен только цвет. Запомним его.
Далее, для следующей точки, если у нас цвет уже известен, и цвет поменялся, запомним начало пересечения.
Если у нас уже есть пересечение, на следующей точке, вне зависимости от её цвета, находится конец пересечения.

Если нам не удалось найти пересечения, то его нет.

Вот это "вне зависимости от цвета" или "нам важен только цвет первой точки" - это же явно написано. "Оставшееся выбросить". И при написании мы точно знаем, что покрыли все-все варианты, потому что match исчерпывающий.

А вот задачу инвертирования списка я считаю очень и очень полезной для понимания Rust'а. Ощупывание границ того, что можно делать с deconstructed structs - это очень и очень важно.

Об алгоритме.
Есть два алгоритма:

1) Сложить всё в стек и собрать обратно список в другом порядке. При том, что алгоритмически это такой же уровень сложности, на практике - это ~30-кратное замедление из-за необходимости иметь дополнительные аллокации и копирования.

2) Пройти по списку и поменять направление ссылок. Было (val1, Link_to_2) -> (val2, Link_to_2) -> (val3, None), должно стать (val1, None) <- (val2, Link_to_1) <- (val3, Link_to_2).

В условиях указателей (си-подобный язык) эта задача довольно простая, потому что мы казуально допускаем, что в какой-то момент у нас "всё висит" или есть два указателя на одно и то же место. (ну и чё такого?).

В Rust же всё куда более интригующе. Список - это

pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

При этом настоящий тип списка - это

Option<Box<ListNode>>

Проговорим это:

Список это:

Либо None
Либо enum, который владеет smart pointer'ом на heap, у которого тип Box, внутри которого находится структура ListNode.

Структура ListNode владеет val и next, который и есть остаток списка.

Чувствуете, как всё нюасно стало? Не ссылки, а есть владение. Чтобы взять содержимое val или next мы должны:
1. Деконструировать Option.
2. Деконструировать ListNode.

После того, как мы деконструировали или Option, или ListNode, мы больше не можем передать его куда-то дальше!

То есть наивное: something.next = cur мы не можем сделать! У нас cur больше не существует.

В целом, эта задача была бы не решаема, если бы не возможность "реконструировать" ListNode. Если мы для каждого поля, из которого мы "взяли" значения положим назад значения (move, передадим владение туда), то мы получим "реконтструированную" структуру, которую мы можем передавать дальше.

Деконструированный же Option невозможно реконструировать (его больше нет), вместо этого мы можем создать новый. Что такое "новый Option" и чем он отличается от старого? В целом, ни чем. Я даже не уверен, что это создаст какие-то машинные инструкции, но с точки зрения компилятора новый Some и старый Some (который мы деконструировали) - две совершенно разные вещи.

Вот решение:

pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    while let Some(mut node) = head{
        head = node.next;
        node.next = prev;
        prev = Some(node);
    }
    prev
}

Проговариваю его по шагам:

Мы деконструируем head (если есть что деконструировать), и создаём переменную node, которая получает владением над содержимым head. Option<Box<ListNode>> → Box<ListNode>.

node имеет тип Box - это умный указатель на кучу, который (за вычетом кучи) просто владеет ListNode.

К этому моменту у нас head не имеет значения (мы делали move из него в строчке while let).
Мы передаём в head значение поля node.next. В этот момент node становится частично деконструированной. next из неё забрали, а value всё ещё принадлежит node.

После этого мы перемещаем в node.next значение из prev. prev перестаёт иметь какое-либо значение (т.к. отдал владение значением). Зато node теперь полностью сконструирован, потому что он владеет всеми своими значениями.
Мы создаём новое значение Some(node), забирая значение из переменной node, node перестаёт иметь какое-либо значение (т.к. отдал владение значением в Some), после чего мы отдаём владение Some(node) переменной prev.

К концу цикла у нас: prev - содержит в себе Some(node), next содержит в себе либо None, либо Some со следующим элементом списка, то есть содержит остаток списка), node - не определён. Цикл заканчивается, у node заканчивается область видимости и она (он? оно?) уничтожается. Т.к. значение уже было move, то ничего делать не надо. Начинается следующая итерация.

В конце мы отдаём владение prev, внутри которого владение prev.next, внутри которого prev.next.next и т.д., то есть инвертированный список.

Вот, примерно так устроен процесс думания о Rust программе. Где-то тут был пропущен вопрос, как мы сквозь Box<ListNode> получаем поля ListNode. Я тщательно этот вопрос не продумывал, но насколько я понимаю, это неявно вызываемые функции deref и deref_mut, реализованные через трейты Deref и DeferMut.

Все эти возни на leetcode привели к тому, что я нашёл минималистичную конструкцию для обхода их странного Rc RefCell дерева.

pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    fn dive(t: &Option<Rc<RefCell<TreeNode>>>, acc: &mut Vec<i32>){
        if let Some(rc) = t{
            let node = rc.borrow();
            dive(&node.left, acc);
            dive(&node.right, acc);
            acc.push(node.val);
        }
    }
    let mut acc = Vec::new();
    dive(&root, &mut acc);
    acc
}

Ключевое открытие тут: с любым Rc надо работать только через ref/mut ref. Как только появляется владение Rc, начинаются массовые проблемы, потому что rc.as_ref() создаёт короткоживущий референс и начинаются всякие выкрутасы. А c ref всё очень хорошо. Во-первых &option<T> автоматом конвертируется в & T после `if let Some...`. После того, как у нас появляется &T, простой .borrow() даёт нам правильную сущность с lifetime блока Some. Дальше мы можем обращаться к содержимому по точке, потому что там Deref реализован (насколько я понимаю, это именно Deref).

Вторая штука, которую я подглядел у соседей по решению: вложенные функции очень удобны, потому что находятся внутри Solution и их легко рекурсивно вызывать без Solution:: и т.д. Вложенные функции в Rust довольно банальны и всего лишь "записаны локально". В отличие от питона у них нет никаких признаков захвата замыкания (в питоне вложенные функции - метод создания замыканий), т.е. это исключительно кнопкодавное удобство.

Одна из простых задач, которые сложны в Rust'е: даны числа в виде списка чисел (десятичные знаки в i32), список в обратном порядке
(то есть head списка - самое крупное число). Надо в таком же виде (списка) вернуть сумму этих чисел.

https://leetcode.com/problems/add-two-numbers

Rust'овые проблемы:

1. Чтобы в том же порядке сложить числа, их нужно засовывать в хвост по мере складывания. В Rust значительно проще было бы делать это в обратном порядке, но увы. Засовывание в хвост чревато тем, что мы должны иметь значение головы для возврата, то есть по списку по мере построения мы двигаемся с помощью &mut, что приводит к тому, что нам надо менять head по & mut, а это означает чёрную магию mem::swap. (Магия хоть и чёрная, но safe, ура).

2. Когда мы ползём по списку, мы не можем казуально заглядывать в tail полученного списка несколько раз, т.к. происходит move (передача владения), в момент заглядывания. Обходные пути через ссылки не очень работают, потому что компилятор не понимает, можно ли нам верить с сроком жизни полученных ссылок (точнее, он знает, что верить нельзя).

Получается такое:

    pub fn add_two_numbers(
        mut l1: Option<Box<ListNode>>,
        mut l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut carry = 0;
        let mut result = None;
        let mut tail = &mut result;
        while l1.is_some() || l2.is_some() || carry > 0 {
            let (n1, next_l1) = l1.map_or((0, None), |n| (n.val, n.next));
            let (n2, next_l2) = l2.map_or((0, None), |n| (n.val, n.next));
            let sum = n1 + n2 + carry;
            let mut new_node = Some(Box::new(ListNode {
                next: None,
                val: sum % 10,
            }));
            std::mem::swap(tail, &mut new_node);
            tail = &mut (tail.as_mut().unwrap().next);
            carry = sum / 10;
            l1 = next_l1;
            l2 = next_l2;
        }
        result
    }

трюки:

1. mem::swap для того, чтобы поменять &mut (ведущий на None) на новое значение.
2. синхронное выковыривание val & next в одну строчку.

Алготримическое:

While зависит от обоих цифр и carry. Это позволяет элегантно решать проблему последнего символа.

Я думал, что это у меня кривые руки и задача решается проще, но не нашёл ни одного соседнего решения, которое было бы элегантным. Пока что основное, что я видел, то предсоздание в качестве result '0' вместо None (что, соотственно, IRL ломает инвариант для add_two_numbers(None, None), который должен сделать None, хотя тут задача становится мутной, потому что 1 + None - это сколько?).

За что мне при этом дали 31мс решения я не понял, кажется, это флуктуации.

В рамках гольфа: Если гоняться за оптимизацией памяти, то мы можем переиспользовать полученные l1/l2 для новых нод, таким образом, экономя на аллокациях.

В рамках экономии строк: если n1/n2 декларировать над циклом, то можно будет делать n1, l1 = ...., без временных переменных и let.

Upd: могу, но не могу. Моя версия Rust это уже умеет, leetcode'овская утверждает, что destructuring assignments are unstable.

!markdown

А вот я и дошёл до странной проблемы, которую я не могу понять.

#[derive (Debug)]
struct Count{
    from: u32,
    to: u32
}

#[derive (Debug)]
struct CountIterator<'a>{
    params: &'a Count,
    cur: u32
}

impl Count{
    pub fn new(from: u32, to: u32) -> Self {
        Count{from, to}
    }
}

impl<'a> Iterator for CountIterator<'a>{
    type Item = u32;
    fn next(&mut self) -> Option<Self::Item> {
        if self.cur < self.params.to{
            self.cur += 1;
            Some(self.cur)
        }else{
            None
        }
    }
}

impl<'a> IntoIterator for Count{
    type Item = u32;
    type IntoIter = CountIterator<'a>;
    fn into_iter(&'a self) -> Self::IntoIter {
        CountIterator{params: self, cur: self.from}
    }

}

И этот код неправильный, потому что

222 | impl<'a> IntoIterator for Count{
| ^^ unconstrained lifetime parameter

И я не понимаю, почему так. И оно неприятно щекочет где-то в районе type parameters, потому что редактор подсказывает, что на месте IntoIter = надо писать

type IntoIter: Iterator<Item = Self::Item> = .....;

И я ни черта не понимаю в написанном. Либо это RLS фигню пишет, либо я что-то глубоко не понимаю. Иду пересматривать про итераторы. Что-то я упускаю...

И оказалось, что обойти без рекурсии дерево - это не так уж просто. Обход в ширину (мне показался) проще.

Я попробовал написать 80-строчного монстра, он дерево обходил, но закцикливался (уходил в лево после обхода в право, уходил вправо, после обхода в лево).

... Я сделал шаг назад и написал рекурсивную реализацию. 6 строк.

fn rec_pre_order(t: &Tree) {
    if let Some(node) = t.as_ref().cloned() {
        rec_pre_order(&node.borrow().left.as_ref().cloned());
        println!("{}", node.borrow().val);
        rec_pre_order(&node.borrow().right.as_ref().cloned());
    }
}

напоминаю, что:

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

type Tree = Option<Rc<RefCell<TreeNode>>>;

И да, я устал от всех этих Ref'ов и as_ref'ов, но таковы условия задачи.

Честный pre_order. Если подвинуть println! в начало (над первым вызовом rec_pre_order), то получится in-order. Если сдвинуть в конец - будет post-order.

А теперь задача, взять этот изящный рекурсивный код и превратить его в итератор. Я понимаю, что это возможно, но с ходу не могу придумать как. Альтернативно: штурмовать loop-версию, пытаясь воспроизвести рекурсию на доморощенном стеке данных.

Пожалуй, я пока займусь идеей итератора из рекурсии. Может быть, это не самая дурная идея?

А вот я думал, что задачу symmetric tree я решу в пол-пинка. (Задача: по заданному дереву сказать, симметричное ли оно).

Теоретическое решение: pre_walk() == post_walk().

Практические проблемы: наивные методы обхода дерева используют рекурсию, а использовать рекурсию при параллельном обходе дерева двумя разными способами - себе дороже.

Выгрузка обоих деревьев в список и сравнение - уровень сложности алгоритма `o(позор)`.

Правильное решение: реализовать стеки из вектора и обходить в цикле. Но два обхода в одной функции уродливо, так что идиоматический подход должен реализовать итератор pre_walk(), итератор post_walk(), и потом просто сравнить их. (то есть решение будет `pre_walk(&tree) == post_walk(&tree)`).

А вот над реализацией нерекурсивного обхода дерева я сейчас буду думать. Теоретически, ничего сложного, но масса эргономических нюансиков (например, как хранить направление движения (влево или вправо)? Надо ли его хранить или оно само получится?).

Плюс rust'овая машинерия для итераторов, которая выглядит ясной и простой, пока туда lifetimes для захваченных ref не появятся.

Короче, задача сводится к pre_order walk через итератор. Решу её, дальше тривиально. Традиционно, сначала решаю, потом читаю умные тексты.

Интернеты говорят, что во-первых Rc<RefCell> не идиоматично для Rust (деревья правильно держать как банальные вектора, содержащие в себе вектора векторов). Во-вторых, я, в целом, всё правильно сделал.

После некоторого кумекания получилось вот так вот, и я не вижу как его сделать существенно компактнее. Может быть, можно уйти от Enum и бального true/false хватит?

Да, получилось.

fn mktree(source: &[Option<i32>]) -> Tree {
    if source.is_empty() || source[0].is_none() {
        return None;
    }
    let tree: Tree = new_tree(source[0].unwrap());
    let mut buff = VecDeque::new();
    buff.push_back((tree.as_ref().cloned(), false));
    for val in source[1..].into_iter() {
        let subtree = val.and_then(|val| {
            let subtree = new_tree(val);
            buff.push_back((subtree.as_ref().cloned(), false));
            subtree
        });
        let (node, is_last) = buff.pop_front().unwrap();
        if is_last {
            node.unwrap().borrow_mut().right = subtree;
        } else {
            node.as_ref().unwrap().borrow_mut().left = subtree;
            buff.push_front((node.as_ref().cloned(), true));
        }
    }
    tree
}

Что меня смущает? Изобилие as_ref().cloned(). Ща буду думать...

Я научился из списка leetcode'а делать дерево! Это было невероятно тяжело, и Rust в этом месте показал learning curve в районе over 60°. Зато к финалу я стал много лучше чувствовать ownership/borrow, особенно, в контексте Rc/RefCell.

Примерно через три часа размышлений о том, как совместить VecDeqeue.get и VecDequeue.pop_front, я понял, что я не могу решать проблему, игнория существование и свойства Rc<RefCell<TreeNode>>. До этого момента я пытался обойтись голым Option, не используя свойства Rc.

Потом я написал функцию mktreefull, которая не умеет несбалансированные деревья (то есть у каждой ноды заполнены оба потомка). В этот момент я почувствовал свет истины.

Потом я ушёл писать walk, чтобы проверить, что я написал правильно, и опять застрял в "получении значения из Rc<RefCell> без .borrow()". И вот тут-то на меня снизошло понимание, что нельзя их использовать без borrow, и все мои выкрутасы тут - фигня.

Я на 99% уверен, что мой алгоритм настолько далёк от компактного, насколько можно, но вот он в двух словах.

У нас есть тип (дерева):

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

type Tree = Option<Rc<RefCell<TreeNode>>>;

Нам надо читая список вида

Some(1),
Some(2), Some(3),
Some(4), None, None, Some(7),
Some(8),

Собрать дерево. Вот такое:

1
2 3
4 None None 7
8 None None None
None None

(каждая строка - уровень дерева) Можно заметить, что вывод похож на вход, хотя None больше, потому что в компактном вводе "оставшиеся None" не указываются.

Идея, которая у меня не взлетела - класть в VecDeque left и right ноды (None) и заменять из с помощью mem::swap.
Новая идея, которая сработала: вместо сохранения потомков у узла, сохранять сам узел, и обрабатывать его дважды (для левой и правой части). Грубо говоря, для левой части мы делаем push_back(cur.left), push_front(cur). А когда делаем push_back(curl.right), то не делать push_front(cur). Когда мы обрабатываем новое значение, мы смотрим на текущее значение curl.left, и если оно пустое, то это обработка левого поддерва, если не пустое - правого.

Это работало для сбалансированного дерева. Для несбалансированного дерева мы, обрабатывая значения можем получить None, то есть "левый лист не нужен". В этой ситуации, если мы сделаем в следующю итерацию проверку на cur.left.is_none, то получим, что left is none, то есть надо идти на лево, хотя надо было на право.

Чтобы решить эту проблему я сделал enum для состояния узла в VecDeque:

enum NodeState {
    Left(Tree),
    Right(Tree),
}

impl NodeState {
    fn new(t: &Tree) -> Self {
        NodeState::Left(t.as_ref().cloned())
    }
}

Заметим, тут же происходит магия Rc/RefCell, я использую t.as_ref.cloned.

напоминаю, что

type Tree = Option<Rc<RefCell<TreeNode>>>;

то есть t.as_ref превращает &Option<Rc<RefCell<TreeNode>>> в Option<&Rc<RefCell<TreeNode>>>.
Потом мы дёргаем cloned, что проходит в Rc (сквозь Option за счёт трейта Deref, насколько я понимаю) и это делает магию Rc, то есть приводит к появлению +1 на счётчике и ещё одной ссылки (вместо клонирования содержимого). Я вытащил этот самый as_ref().cloned() в реализацию NodeState просто, чтобы сэкономить нажатие кнопок в основной функции.

Дальше у нас простая state machine:

let cur = buff.pop_front().unwrap();
match cur {
NodeState::Left(Some(node)) => {...},
NodeState::Right(Some(node)) => {...},
  _ => {panic!();}
}
 
 

В которой у нас разное поведение для left и right. Если мы в left, то мы кладём в конец новый узел, а в голову возвращаем текущую ноду, но в состоянии 'Right'.
В Right мы кладём новый узел в голову, а текущий узел уже никуда не добавляем.

Ну, и, разумеется, в текущей ноде поддеревья попадают в разные стороны.

Процесс модификации текущей ноды целиком зависит от магии Rc (мы делаем borrow_mut из немутабельной ссылки):

node.borrow_mut().left = subtree;

Повторю, я на 100% уверен, что есть более элегантные решения, но у этого есть неоспоримое достоинство - я его сам думал целиком, а заодно учился жить с Rc/RefCell.

Код: https://github.com/amarao/leetcode-tree-build/blob/master/src/main.rs#L41

А вот теперь, я пойду читать как эту проблему решают взрослые мальчики.

Вот я прям питон начинаю не любить. Казалось бы, утиная типизация и всеобщая приятность. Никакого фашизма, всё можно.

А вот вам простая задачка, которую на rust'е generic'и решают в одну строчку, а на питоне я не знаю как (в разумные усилия).

Есть функция, которая читает вывод (утилиты) и возвращает распашенный json. Она достаточно generic, чтобы в зависимости от вывода утилиты вернуть list или dict.

Теперь я хочу добавить фэнсервиса - если вывод пустой, то возвращать пустой элемент (список или словарь). Как? КАК?

>>> class foo(dict,list):
... pass
...
Traceback (most recent call last):
File "", line 1, in
TypeError: multiple bases have instance lay-out conflict

Моя hard task свелась к проблеме поиска структуры, которая есть в стандартной библиотеке, и которая даёт мне возможность вставлять, удалять и находить максимум быстрее, чем o(n). Кроме того, структура должна поддерживать дубликаты. Rust пока не даёт 'first/last' для BTree, так что приходится думать самому.

Правильный ответ - binary search tree, но у меня не хватает сейчас мозгов его хорошо написать, и я не хочу туда коммититься.

Вот что я придумал "их того что было и палок".

объём данных: n
k = sqrt(n) (квадратный корень из n)

Создадим Vec (массив) и VecDeque (double ended queue) - такие есть в в стандартной библиотеке. Всего будет k (напоминаю, sqrt(n)) Vec'ов при ожидаемом размере каждого элемента - k. Получается sqrt(n) * sqrt(n) = n.

Все элементы хранятся упорядоченно. Каждый VecDeque упорядочен от младшего к старшему, каждый элемент Vec содержит в себе VecDeque, которые так же полностью упорядочены.

Вставка:

Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию, либо дописать слева/справа. o(log(k))
Вставить элемент в указанный индекс. Сложность o(k/2), с поправкой на облечение "вставки в начало" (т.к. VecDeque).
После этого произойдёт переполнение VecDeque (размер станет больше k), и надо будет перекинуть элемент вверх или вниз. Возможно, в худшем случае вставка потребует перекидывать элементы между каждой "строкой" (VecDeque), так что худший случай - o(k) pop_back, o(k) push_front. в среднем o(k) операций.

Сложность: log(k) + log(k) + o(k/2) + o(k/2) + k + k =~= k

Удаление:

Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию o(log(k))
Перенормировать длины: 2*o(k)

Сложность: o(k)

Поиск максимума o(1) - последний элемент последней строки.

Теперь, вспомним, что k - это sqrt(n), и получаем, что сложность вставки/удаления - sqrt(n), что лучше, чем n.

При использовании внутри алгоритма со сложностью n*log(n), получаем n*log(n)*sqrt(n), ~n^1.5, что лучше, чем o(n).

Не фонтан, но...

Вопрос: не могу ли я расширить этот подход на более чем одно измерение? Теоретически, в пределе должно получиться как раз log(n).

Фактически, я хочу сделать дерево, в котором у меня в векторе хранятся вектора, внутри которых хранятся вектора... и так пока я не дойду до самого дна, то есть до leaf'а. Одним из интересных улучшений в рамках задачи является то, что я знаю максимальный размер (n) заранее и могу посчитать оптимальную глубину в момент создания, то есть мне не нужно пересчитывать глубины.

"дерево на векторах" мне кажется куда интереснее, чем обычный struct с left/right (как обычно дерево описывается).

Я сейчас попробую изобрести такое дерево, если не получится, попробую штурмовать задачу с n^(1.5) сложностью решения. Цена вопроса - для 10000 элементов квадратичное решение - это 100 миллионов операций, а 1.5 - это миллион. 100-кратное ускорение. Для 100k элементов - 100 миллиардов против 31 миллиона, 300-кратное ускорение.

Итак, как будет устроено DQTree? По аналогии с btree, я хочу ограничить глубину сканирования эффективным коэфицентом. Допустим, я выбираю коэфицент B (16).

У меня N элементов, и мне нужно посчитать, сколько слоёв нужно в дереве. log₁₆N, округлённый вверх. Допустим, у меня 333333 элементов. Это 5 слоёв (из значения логарифма 4.58..)

В первом слое у меня B элементов (Vec), во втором слое у меня B элементов (тоже Vec), в третьем слое у меня B элементов, в четвёртом у меня B элементов, в пятом у меня Deque... А нужно ли оно тут? Если у меня там up to 16 элементов, то любой insert в него будет константным. Так что просто Vec. Все слои, кроме нижнего, содержат в себе только Vec следующего уровня. Нижний Vec содержит в себе числа.

Переименовываем стуктуру в VecTree.

Создание: Аллоцирвать все Vec'и. WUT? Это же o(n) операций. Нет.

Вместо Vec у нас появляется Option... При создании VecTree мы ничего не аллоцируем.

Вставка:

Дойти до нижнего элемента за o(log n), вставиться в него за o(B) времени (то есть за o(1)).
Каким образом я знаю, в какой элемент вставляться? Если это первый элемент, то понятно, самая левая ветка.

А если, допустим, у нас целиком уровень забит Vec'ами? Как нам понять, в какой Vec ходить?

Допустим, мы будем хранить min/max для обслуживаемого диапазона.

Итак, пройтись по элементам, выбрать подходящий диапазон. Если слишком маленький - расширить диапазон левого значения, если слишком большой - правого.

Спуститься на уровень ниже. Повторить.

Пока не прийдём к нижнему слою.

Двоичным поиском найти нужное место, вставиться.

После вставки мы проверяем размер Vec'а и думаем, что с этим делать. Если размер меньше B, то "и пофигу".

Если размер больше B, то надо вынуть элемент в ставить "куда" следует:

Если у нас нет соседа слева, то надо убирать правый элемент.
Если у нас нет соседа справа, то надо убирать левый элемент.

А если есть оба соседа? Как понять в какую сторону значение надо двигать? По-идее надо двигать в ту сторону, в которой меньше всего элементов.

Для этого мы записываем число элементов для каджого Vec'а. (не число элементов в Vec, а число элементов в Vec в Vec в Vec ... до самого дна).

То есть обычная (не leaf) нода выглядит так:

min
max
count

При спуске на слой ниже мы смотрим на предпочтения по перекидыванию значений. Для этого мы считаем число элементов в остальных элементах слоя (кроме того, в который мы погружаемся) и вычисляем left_count и right_count, который и известен следующему слою.

Когда слой решает, какой элемент удалять при переполнении, он смотрит какой меньше и с той стороны удаляет элемент. (Будет обидно, если удаляют элемент, который только что был вставлен... не создаст ли это бесконечный цикл? Удалённый элемент при ребалансировке надо вставлять... Это особый случай и нам надо проверять, к какому потомку мы посылаем элемент, если элемент на границе диапазона - к тому, у которого это будет "левое" значение или правое). Мы на эти вопросы всё равно смотрим, потому что двигаем min/max у элемента. У кого count меньше, того и элемент.

(возвращаемся к ребалансировке "лишнего" значения с нижнего слоя 'leaf'ов').

Итак, мы знаем с какой стороны удаляем лишнее значение. Мы его удаляем (размер становится B), после чего мы возвращаемся на уровень выше и вставляем значение в элемент с соотв стороны.

Это может вызвать ребалансировку в следующий элемент. Можно представить себе крайне неприятную ситуацию, при которой мы проходим все N/B-1 элементы, то есть получаем ребалансировку за o(n). Плохо-плохо.

А как мы к такой беде пришли? Потому что в старом коде с k=sqrt(n) нужно было не более чем 2*k операций на Dequeue, чтобы ребалансировать всё. Почему так? Потому что при ребалансировке у меня 2 операции на "псевдолиф" (pop_front/push_back).

А в VTree у меня мало того, что на каждый leaf B операций на вставку, то ещё и надо потенциально пройтись по всем значенниям. И переходов o(n). А было o(sqrt(n)), потому что я променял sqrt n на B, когда делал размер leaf'а снизу. Почему я это сделал? Чтобы сделать вставку дешевле. у старого кода вставка была дорогой o(k), и ребалансировка тоже дорогой. o(k). Получалось, что две условно дорогие операции дешевле, чем, казалось бы, быстрая вставка за o(log(n)), но очень дорогая ребалансировка за n.

Мы так не договаривались.

Окей, шаг назад. У нас есть sqrt(n). Там есть Vec>. Если мы сделаем Vec

( Error: Irreparable invalid markup in entry. Raw contents behind the cut. )

Я почти-почти-почти решил задачу, но... У BinaryHeap нет remove. pop убирает только самый большой элемент.

Практически, эпик фейл. Теоретически, BST решает проблему, но в стандартной библиотке нет BST, а есть только "просто дерево" (и BTree).

Я пока не готов коммититься на написание дерева (кроме того, я знаю, что растовая реализация BTree на много голов выше любой моей наивной реализации).

Видимо, я пока признаю своё поражение, и использую внешний крейт с binary_search_tree.

(обидно, потому что first/last для BTreeMap/Set уже стабилизировано, но ещё не зарелижено. Увы).

UPD: его стабилизируют в 1.66, 1.65 выходит послезавтра, а сколько ждать до 1.66 - даже не известно. Увы, binary_search_tree.

UPD2: на leetcode нет крейта binary_search_tree. Либо писать своё дерево (конкретно binary search tree), либо писать всю структуру с нуля.

Мой хак состоял в том, чтобы переопределить Ord таким образом, чтобы точка была равна range в который она попадает. Это позволяло извлекать range по точке из range'а. Если писать свою структуру, хак тут не нужен.

Пока что сохраняю для истории версию с (unstable) BTreeSet.first(): https://gist.github.com/amarao/9126e51f9587186fc95a79e3339bf884

и пойду ваять дерево. Совершенно отдельная дисциплина.

Я тут решаю одну hard problem на leetcode (в leetcod'овском смысле 'hard', не NP-hard). Я думаю, что я её уже решил оптимально (спустя ~10 исписанных бумажек), но я не знаю как её запрограммировать на Rust. Списки и деревья - моя слабость в Rust, потому что "всё понимает, а сказать не может".

Итак, задача: https://leetcode.com/problems/maximum-segment-sum-after-removals/

Дан массив положительных чисел и массив со списком позиций для удаления чисел. Нужно заменять в первом массиве (чисел) позицию из второго списка нулём. После этого нужно смотреть на массив чисел и отвечать какая сумма сегмента там самая большая. Сегмент - непрерывная последовательность чисел без нулей. Эти суммы надо записать в результат (для каждого удаления - максимальный размер сегмента в после данного удаления).

Т.е. после каждого удаления старый сегмент может оказаться поделен на два, и возможно что какой-то другой сегмент теперь больший.

Всего для массива в N чисел будет N удалений.

Решение в лоб тривиальное - заменяем элемент в массиве, считаем какой сегмент максимальный. Сложность n², потому что у нас надо N раз посчитать максимальный сегмент среди N чисел.

Дальше спойлер

( Read more... )

Одна из непроговоренных особенностей Раста состоит в том, что функция - это big deal. В питоне почти любой кусок кода можно вынуть и положить в функцию. После появления yield from, таких кусков стало ещё больше. Фактически, в питоне нельзя вынести в отдельную функцию только control flow (return/break/continue) внутри блоков. Всё остальное - можно.

В Rust функция, хоть и является существенно более дешёвой (из-за того что у функции неиллюзорные шансы быть inline), вынесение кода в функцию не всегда возможно. Функции нужны сигнатуры, а некотрые сигнатуры чертовски тяжело написать, и даже если это возможно, сложность "думания" в этот момент в разы выше. В Расте постепенно появляются всякие безумия с GAT'ами, которые расширяют список того, что может быть функцией ... точнее, методом, но общий принцип раста - не всё возможно.

В целом, я бы сказал, что это именно набор ограничений. Берём условный язык опасно близкий к ассеблеру, натягиваем на него вкусный синтаксический сахар, который его превращает в язык высокого уровня, а потом запрещаем крупными мазками "чаще всего плохие вещи". В замен мы получаем песочницу для программиста (где большая часть опасностей предотвращена), массу подсказок для компилятора для оптимизации последствий песочницы. Но ещё при этом получаем запрет на, казалось бы, нормальные вещи. Некоторые из которых - скрытая опасность (и за это хвалят Rust), а некоторые - вполне себе sound код, но "ну так получилось".

С каждой версией в Rust'е всё больше "ну так получилось" убирают, добавляя механизмы для sound & safe реализации новых нюансов.

Но сам принцип "denied by default" остаётся, то есть с точки зрения программиста Rust куда более ограничивающий язык, чем большинство языков низкого уровня и языков с расслабленной типизацией (к которой относится и Питон).

Соответственно, это приводит к двум отношениям с языком:

Пишу как хочу и не думаю, если ошибусь, компилятор поймает (и может даже, предложит исправление). Это основной режим, no thinking required. Точнее, думать можно уже не о языке, а о решаемой проблеме, а всю рутину язык либо сам сделает. Это выведение типов, AsRef/Borrow/Copy трейты, generic'и, которые "сами всё делают", как .collect(). Последний я как раз считаю ярчайшим примером "магии раста". Итератор сам превращается в нужный тип, причём практически любой возможный.

Второе отношение с языком: "да что за хрень?". ~70% этой хрени по делу, то есть компилятор конкретно запрещает делать unsound вещи (например, менять вектор, по которому итерация, или вызывать второй раз FnOnce функцию). Примерно 5-7% - это мелкие придирки (Пиши `foo as i64`, когда `foo: i32`) или шероховатости типов (например type(&str[0]) != char).

Оставшиеся 20-25% режима "что за хрень", это праведное возмущение, потому что я знаю, что так можно, а компилятор мне не верит, или я хочу, но не могу написать (сигнатуру для замыкания). С временем эта область подсокращается (чаще всего через сложные механизмы для тех, кто очень хорошо знает язык, те же GAT'ы), но в целом она есть и никогда не исчезнет.

Это сильно противоречит питону или C, где практически нет мест, где "нельзя написать". Можно, но последствия остаются на совести написавшего, а иногда бывает так, что написать можно, а написать sound (непротиворечиво) нельзя, и языку пофиг.

(уклонился от исходной темы).

Так вот, функции в rust - это big deal. Если пишешь функцию, это контракт, интерфейс, на написание которого может уйти больше времени, чем на сам код (самой функции и кода, который эту функцию вызывает). Более того, однажды написанный контракт (сигнатура функции) потом давлеет, и шаг влево/шаг вправо вызывает необходимость изменять сигнатуру функции, что автоматически приводит к необходимости думать про все места использования функции... Это частично обходится generic'ами, но generic'и повышают уровень "думания", и часто уводят в те самые углы, где "компилятор неправ" (например, если он выбирает неправильный метод построения generic'а и не хочет вывести типы корректно, то есть ругается при компиляции).

С другой стороны, когда знаешь, что пишешь, написанные сигнатуры - 80% программы. Дальше каждый кусок пишется под сигнатуру в режиме "no thinking required". Если оно по типам сходится, значит всё в программе правильно. Может быть ошибочный алгоритм (об этом думать надо), но код функции точно делает то, что написано в сигнатуре.

Это очень сильно меняет процесс программирования, особенно, если кода много. Я ещё не дошёл до того уровня, в котором могу планировать модули (не хватает интуиции и практики), но написать парочку трейтов для структуры ещё до написания полей самой структуры - это да, это совершенно другой уровень программирования.

Задача: конвертация из числа в roman numerals:

impl Solution {
    fn next_biggest(num: i32) -> (&'static [u8], i32) {
        match num {
            1000.. => (b"M", 1000),
            900.. => (b"CM", 900),
            500.. => (b"D", 500),
            400.. => (b"CD", 400),
            100.. => (b"C", 100),
            90.. => (b"XC", 90),
            50.. => (b"L", 50),
            40.. => (b"XL", 40),
            10.. => (b"X", 10),
            9.. => (b"IX", 9),
            5.. => (b"V", 5),
            4.. => (b"IV", 4),
            1.. => (b"I", 1),
            _ => unimplemented!("Unable to represent in Roman")
        }
    }
    pub fn int_to_roman(mut num: i32) -> String {
        let mut acc = Vec::new();
        while num > 0{
            let (rom, value) = Self::next_biggest(num);
            acc.extend_from_slice(rom);
            num -= value;
        }
        String::from_utf8(acc).unwrap()
    }
}

Ключевое know-how: Возвращать reference'ы на &'static [u8], который на самом деле кусок будущей строки и использовать "байтовые строки" для констант (b"str_content").

Не то, чтобы это был Trait Science, но любые другие выкрутасы с String или Vec<char> были бы куда более уродливыми или неэффективными. А тут я беру и возвращаю указатели на статические строки (которые и так и так у меня в .data будут), и из них мирно собираю строку. Точнее, я собираю в [u8], которую потом копирую в String.

Возможно, вместо while можно было бы иметь итератор, но я не уверен в выполнимости этого.
Ещё одно место "думать" - в районе extend_from_slice, т.к. я могу вызывать несколько реаллоакций в процессе 'extend', а мне по-хорошему надо было бы знать длину строки с самого начала. Но это отдельная интересная задача - определить размер строки для roman numeral по числовому значению.

А вот тут у меня спор с автором ripgrep'а: надо ли уважать TERM? Всем понятно, что TERM=dumb надо уважать. А вот какой-нибудь t10, который от dumb отличается едва-едва, надо?

https://www.reddit.com/r/rust/comments/y0oz86/comment/irvo53s/?utm_source=share&utm_medium=web2x&context=3

Говорит, что не надо, иначе никакого спасения от всяких TERM=screen.linux.

А вот мне кажется, что надо уважать. Не только от практичности, но и с целью закрыть все corner case'ы. По крайней мере, для меня тотальность и отсутствие исключений - это привлекательные черты раста.

Некоторые задачи на leetcode доставляют трушное настоящее удовольствие.

https://leetcode.com/problems/break-a-palindrome/

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

тесткейсы:

"" => ""
"a" => ""
"aa" => "ab"
"zz" => "az"
"aba" => "abb" (самый сложный случай, на котором я сначала попался).

Я получил реальное неиллюзорное удовольствие от языка и от задачи. Я не уверен, что на питоне у меня бы получилось компактнее и выразительнее

    pub fn break_palindrome(palindrome: String) -> String {
        let mut bytes = palindrome.into_bytes();
        let len = bytes.len();
        if len < 2 {
            String::from("")
        } else {
            let mid = len / 2;
            let odd = (len % 2) == 1;
            let last = len - 1;
            for (idx, c) in bytes.iter_mut().enumerate() {
                match c {
                    b'a' if idx == last => *c = b'b',
                    b'a' => {}
                    _ if odd && idx == mid => {} // mid char, can't change
                    _ => {
                        *c = b'a';
                        break;
                    }
                }
            }
            String::from_utf8(bytes).unwrap()
        }
    }

Усилиями r/rust с Реддита (note: реддит живее, чем SO, причём не только в программировании) проблема quick fail была решена, причём идиоматически. Исчезли две аллокации (из четырёх), и как мне кажется, алгоритмически его быстрее уже не сделать. (Да, я понимаю про идею использовать буквы из шаблона как индексы, но на практике это потребует аллокации вектора букв, и врят ли будет лучше).

Задача: https://leetcode.com/problems/word-pattern/submissions/

В двух словах: дана строка из букв и из слов, надо ответить, эквивалентны ли они друг другу в режиме "шаблона" : "aab" эвивалентна "dog dog cat", "abca" эвивалентна "foo bar baz foo".

(предыдущее обсуждение и текст полный задачи: https://amarao.dreamwidth.org/45539.html)

К предыдущему решению претензия была в отсутствии quick fail, то есть если с самого начала строки различаются, старый алгоритм продолжал "варить" до упора. (aaaaaaaaaaa и "foo bar bar bar bar bar"). Плюс, две аллокации для output.

r/rust был более чем любезен указать на две важные детали:

1. Можно возвращать итераторы вместо векторов.
2. Итераторы лего сравнить.

Кроме того, можно требовать не Iterator, а IntoIterator, так что можно передать любой "итрабельный" объект без вызова его iter(), хотя в конкретном этом случае это не работает, потому что итераторы у строки и шаблона разные и странные (split_whitespace и chars).

Получившийся код для меня находится чуть выше моего свободного понимания Rust: я его могу прочитать, но второй такой же не напишу (или уже напишу после этой истории?):

use std::hash::Hash;
use std::collections::HashMap;

impl Solution {
    fn abstract_iterator(input: impl IntoIterator<Item = impl Hash + Eq>) -> impl Iterator<Item = usize> 
    {
        let mut dict = HashMap::new();
        input
            .into_iter()
            .map(move |elem| {
                let id = dict.len();
                *dict.entry(elem).or_insert(id)
        })
    }

    pub fn word_pattern(pattern: String, s: String) -> bool {
        Self::abstract_iterator(pattern.chars()).eq(
            Self::abstract_iterator(s.split_whitespace())
        )
    }
}

Глядя на этот код, мне немного не нравится word_pattern своей некрасивостью.

Наверное, лучше было бы написать свой трейт, чтобы функция стала такой:

        pattern
            .chars()
            .abstract_iterator()
            .eq(
               s
                .split_whitespace()
                .abstract_iterator()
             )

Но в целом - это огонь. Это совсем не похоже на "низкоуровневый язык,
соревнующийся С++ за системность и поглядывающий на лавры С".

Profile

amarao

June 2025

S	M	T	W	T	F	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Syndicate

Page Summary

Style Credit

Style: Pink Panther for Lefty by sarken

Expand Cut Tags

No cut tags

Page generated Jun. 13th, 2025 06:43 pm

Entries tagged with rust

Navigation

Control flow as a type

Проверка на цикличность строки

magical match

list inversion

tree traversal

add two numbers

итераторы

древесное

обходы дерева

post-tree

Древесные истории

Вернуть пустое

Rust hard task sqrt(n)

hard-Rust'овое

Деревья и Rust

Растовое

Мой раст становится лучше

уважать ли TERM?

I f.. love it

The программирование, часть вторая