Oℕ
RAFIZ
ключи понятно - кладутся в красно-чёрное дерево. а значения куда кладутся?как это работает?
как и во всех других языках в КЧД кладутся пары, а сравнение по ключам происходит
Size: a a a
2020 October 14
R
ну и тогда. чтобы всю мапу распечатать, нужно просто отсортировать ключи (значения рядом с ними окажутся, как выяснилось), а это за O(n) делается (pre-order-traversing называется), дополнительный логарифм там непонятно откуда взялся
Oℕ
RAFIZ
ну и тогда. чтобы всю мапу распечатать, нужно просто отсортировать ключи (значения рядом с ними окажутся, как выяснилось), а это за O(n) делается (pre-order-traversing называется), дополнительный логарифм там непонятно откуда взялся
Ещё раз, это если нормально, но в скале по-моему сделано в стиле (1 until size) map apply
R
ну вообще для обхода RBT нужна линейная сложность, но в скале по-моему там хуже
понятно. то есть скорее всего, как я и предполагал - линейное?
Oℕ
RAFIZ
понятно. то есть скорее всего, как я и предполагал - линейное?
нет, если мне не изменяет память n log n
R
Ещё раз, это если нормально, но в скале по-моему сделано в стиле (1 until size) map apply
да я уже увидел сообщение выше
Oℕ
Но я давно смотрел
λ
RAFIZ
ну и тогда. чтобы всю мапу распечатать, нужно просто отсортировать ключи (значения рядом с ними окажутся, как выяснилось), а это за O(n) делается (pre-order-traversing называется), дополнительный логарифм там непонятно откуда взялся
Сортировка за O(n)? Круто
R
ну как бы тогда совсем странно получается. что каждый раз для того чтобы вызвать toString надо потратить время как на сортировку слиянием (это многовато), какая-то неоптимальная коллекция получается(
R
Сортировка за O(n)? Круто
не знали?)
λ
Конечно не знал, потому что нет таких алгоритмов сортировки
λ
RAFIZ
ну как бы тогда совсем странно получается. что каждый раз для того чтобы вызвать toString надо потратить время как на сортировку слиянием (это многовато), какая-то неоптимальная коллекция получается(
Не надо, дерево уже сбалансированное и отсортированное
Oℕ
RAFIZ
да я уже увидел сообщение выше
https://github.com/scala/scala/blob/v2.13.3/src/library/scala/collection/immutable/RedBlackTree.scala#L418
нет, я ошибся сейчас сложность O(n), как Вы и писали
нет, я ошибся сейчас сложность O(n), как Вы и писали
R
Конечно не знал, потому что нет таких алгоритмов сортировки
почитайте получше как отсортировать бинарное дерево поиска (например) ))☺️
Oℕ
RAFIZ
почитайте получше как отсортировать бинарное дерево поиска (например) ))☺️
не спорьте с ним, он не понял просто, что вы имели в виду
R
не спорьте с ним, он не понял просто, что вы имели в виду
да :)
R
https://github.com/scala/scala/blob/v2.13.3/src/library/scala/collection/immutable/RedBlackTree.scala#L418
нет, я ошибся сейчас сложность O(n), как Вы и писали
нет, я ошибся сейчас сложность O(n), как Вы и писали
спасибо за ссылку. вот её и искал (что-то подобное)
λ
не спорьте с ним, он не понял просто, что вы имели в виду
Что он имел ввиду?
R
Что он имел ввиду?
что влетать в разговор в токсик-стиле не войдя в контекст - такое себе
λ
Нет, я лишь увидел неправильное утверждение