hard-Rust'овое
Nov. 1st, 2022 08:21 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoЯ почти-почти-почти решил задачу, но... У 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
и пойду ваять дерево. Совершенно отдельная дисциплина.
Практически, эпик фейл. Теоретически, 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
и пойду ваять дерево. Совершенно отдельная дисциплина.
no subject
Date: 2022-11-01 07:53 pm (UTC)Вот сдается мне, что FingerTree тут было бы самое то. И крейт уже имеется.
no subject
Date: 2022-11-02 11:33 am (UTC)Оно в очереди на изучение. Сначала я решу задачу, а потом пойду смотреть как всё остальное человечество строит велосипеды.
Я тут покумекал, и если уж я свою структуру писать буду, то отвечать на вопросы о максимуме/минимуме отрезка B-Tree будет с тем же успехом, надо просто max'ы размеров сегментов трекать.