Добрый день! У меня есть следующая задача. Есть Итератор. Этот Итератор изнутри

Question

Добрый день! У меня есть следующая задача. Есть Итератор. Этот Итератор изнутри

использует RangeMut(которым он владеет) по значениям BTreeMap(которым он НЕ владеет). Итератор возвращает значения, связанные временем жизни с BTreeMap, которым он не владеет.

В ряде случаев мне нужно, чтобы Итератор продвигал RangeMut к заданному известному ключу.

У RangeMut нет такого функционала. Тривиальное рашение этой задачи — это просто в цикле вызывать next() у итератора RangeMut. Но в этом случае эффективность продвижения будет O(m), где m — число элементов, которые я заскипал. Это решение, на первый взгляд, неэффективно, так как BTreeMap, вообще говоря, это коллекция с бинарным поиском. То есть продвинуться, теоретически, можно было бы за логарифмическое время от m, а не за линейное. И хотелось бы так и сделать.

Чтобы перепрыгнуть за логарифмическое время можно было бы пересоздать RangeMut, но я этого сделать не могу, так как Итератор не владеет исходным BTreeMap.

Как эту задачу можно было бы решить?

#backend #embedded #programming #russian #rust

0

04.07.2022

7 ответов

6 просмотров

Ilya Lakhin Автор вопроса

Сергей
Монжо например не пользоваться итераторами, просто...

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

0

04.07.2022

Сергей

Ilya Lakhin
Интересная мысль, но доступ по индексу будет кажды...

А ты уверен, что итерация не log(n)?

0

04.07.2022

Ilya Lakhin Автор вопроса

Сергей
А ты уверен, что итерация не log(n)?

Абсолютно уверен. Это же BTree+

0

04.07.2022

Alexander

Сергей
А ты уверен, что итерация не log(n)?

O(log(n)) вызов next в худшем случае, но O(1) в среднем И O(log(n) + k) на вызов next k раз подряд

0

04.07.2022

Сергей

Ilya Lakhin
Абсолютно уверен. Это же BTree+

Тогда всё будет зависеть от того, сколько ты скипаешь и сколько итерируешь. Если например скипаешь большие интервалы, может есть смысл пересоздавать итератор, чтобы по тем, которые НЕ скипаешь идти за O(1). Ну и может на другую структуру тоже есть смысл посмотреть. Сортированный вектор например.

0

04.07.2022

Ilya Lakhin Автор вопроса

Сергей
Тогда всё будет зависеть от того, сколько ты скипа...

Спасибо за содержательный ответ )

0

04.07.2022

Сергей · Accepted Answer

Сергей

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

0

04.07.2022

172 похожих чатов

Добрый день! У меня есть следующая задача. Есть Итератор. Этот Итератор изнутри

7 ответов

Похожие вопросы