![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
hard problem, part 2
Oct. 31st, 2022 12:21 amЯ решил кучу проблем, включая использование BTree, я понял, что штатный одинокий BTree мне проблему не решит (Ord задан для сегмента, а поиск максимума я хочу за o(1) от sum (другого поля, чем сегмент).
Я подумал, что если я заведу второй BTree, то я смогу в нём сортировать по sum, и тогда будет быстро, но нет, потому что либо быстро по key (координаты сегмента), либо быстро по sum (другому полю).
Получается, что простой BTree меня никак не спасает.
То есть я из решения проблемы подошёл к ... началу решения проблемы. Всё более интригующе и интригующе. Я нашёл ответ на SO, там перечислены несколько структур, но в рамках ментальной дисциплины не буду ходить по ссылкам и попробую придумать своё. Пока что я понял, что это отдельная задача (они прям так и называют его "Segment Tree", возможно задача как раз на знание такой структуры).
Собственно, задача свеласть к тому, что я хочу быстро insert/delete (на самом деле split) по координатам (start, end), а потом я хочу быстро найти start/end для самого жирного элемента.
Хм.. Мне не нужно сортировать! Мне не нужно insert/delete по жирному элементу. Мне нужно просто знать, какой элемент самый жирный. Проблема состоит в том, что я не могу тупо записать "самый жирный" и сравнивать с ним при insert'ах. Точнее, при insert'ах это работает, а при delete'ах нет. Потому что если я убрал самого жирного, какой будет самый жирный после него? Надо всё пересчитывать.
А вот идея:
Давайте хранить данные таким образом:
Segment {
start: usize,
end: usize
}
SegSum{
seg: Segment,
sum: i64
}
(Я пропускаю задачу быстрого поиска места для "разрезания", я её уже решил, хотя и глуповатым образом, я просто сделал так, чтобы BTreeSet.get мне возвращало сегмент из-за Eq с любым индексом изнутри этого сегмента).
только вторая часть, с размерами.
Сегменты хранятся в дереве1. (BTreeMap). Ключом является сегмент, value является его sum.
Мы делаем insert/delete за o(log(n)).
Ещё мы храним BTreeMap дереве2 с key/value в котором key - это sum, а value - число сегментов такого value. Большинство сегментов имеют value: 1, но это не важно.
Когда мы делаем delete для сегмента из дерева1, мы делаем -1 у value для его sum из дерева2. Если value стало равно нулю, мы его delete.
Таким образом, мы можем узнать largest за o(1) (BTreeMap умеет отвечать на этот вопрос за o(1))... Упс, умеет, но в experimental API. Значит, надо что-то другое.
MaxHeap даёт нам o(1) на поиск ответа, O(log n) на вставку, но удаление? Говорят, тоже O(log n). Ага. Тогда мы храним sums как Heap. Проблема состоит в том, что у нас не HeapMap, а просто Heap.
Но Heap может содержать дупликаты! Ура.
Итого: Мы просто храним sums в виде Max-Heap. Push/pop нам стоят 2x O(log(n))... Хотя rust'овая дока утвержает, что ~1, но вчитавшись ещё, я вижу, что worst case это ascending order, а у меня ожидается, что длина уменьшается. А вот pop у меня чаще всего забирает head, то есть log(n). Посмотреть на "самый большой" - o(1).
В целом, все операции получаются быстрее, чем o(n), что мне, собственно, и нужно.
Я подумал, что если я заведу второй BTree, то я смогу в нём сортировать по sum, и тогда будет быстро, но нет, потому что либо быстро по key (координаты сегмента), либо быстро по sum (другому полю).
Получается, что простой BTree меня никак не спасает.
То есть я из решения проблемы подошёл к ... началу решения проблемы. Всё более интригующе и интригующе. Я нашёл ответ на SO, там перечислены несколько структур, но в рамках ментальной дисциплины не буду ходить по ссылкам и попробую придумать своё. Пока что я понял, что это отдельная задача (они прям так и называют его "Segment Tree", возможно задача как раз на знание такой структуры).
Собственно, задача свеласть к тому, что я хочу быстро insert/delete (на самом деле split) по координатам (start, end), а потом я хочу быстро найти start/end для самого жирного элемента.
Хм.. Мне не нужно сортировать! Мне не нужно insert/delete по жирному элементу. Мне нужно просто знать, какой элемент самый жирный. Проблема состоит в том, что я не могу тупо записать "самый жирный" и сравнивать с ним при insert'ах. Точнее, при insert'ах это работает, а при delete'ах нет. Потому что если я убрал самого жирного, какой будет самый жирный после него? Надо всё пересчитывать.
А вот идея:
Давайте хранить данные таким образом:
Segment {
start: usize,
end: usize
}
SegSum{
seg: Segment,
sum: i64
}
(Я пропускаю задачу быстрого поиска места для "разрезания", я её уже решил, хотя и глуповатым образом, я просто сделал так, чтобы BTreeSet.get мне возвращало сегмент из-за Eq с любым индексом изнутри этого сегмента).
только вторая часть, с размерами.
Сегменты хранятся в дереве1. (BTreeMap). Ключом является сегмент, value является его sum.
Мы делаем insert/delete за o(log(n)).
Ещё мы храним BTreeMap дереве2 с key/value в котором key - это sum, а value - число сегментов такого value. Большинство сегментов имеют value: 1, но это не важно.
Когда мы делаем delete для сегмента из дерева1, мы делаем -1 у value для его sum из дерева2. Если value стало равно нулю, мы его delete.
Таким образом, мы можем узнать largest за o(1) (BTreeMap умеет отвечать на этот вопрос за o(1))... Упс, умеет, но в experimental API. Значит, надо что-то другое.
MaxHeap даёт нам o(1) на поиск ответа, O(log n) на вставку, но удаление? Говорят, тоже O(log n). Ага. Тогда мы храним sums как Heap. Проблема состоит в том, что у нас не HeapMap, а просто Heap.
Но Heap может содержать дупликаты! Ура.
Итого: Мы просто храним sums в виде Max-Heap. Push/pop нам стоят 2x O(log(n))... Хотя rust'овая дока утвержает, что ~1, но вчитавшись ещё, я вижу, что worst case это ascending order, а у меня ожидается, что длина уменьшается. А вот pop у меня чаще всего забирает head, то есть log(n). Посмотреть на "самый большой" - o(1).
В целом, все операции получаются быстрее, чем o(n), что мне, собственно, и нужно.