к
с мапой нет
можно взять [(k, v)] и тогда можно будет, но поиск за n
можно взять [(k, v)] и тогда можно будет, но поиск за n
с мапой нет
можно взять [(k, v)] и тогда можно будет, но поиск за n
Size: a a a
2021 February 08
AK
А почему с ней нельзя? У меня же не fromList, а fromAscList. Может есть подобные ленивые структуры с логарифмическим поиском?
к
А почему с ней нельзя? У меня же не fromList, а fromAscList. Может есть подобные ленивые структуры с логарифмическим поиском?
мапа это дерево, длина пути до ноды все равно будет зависеть от размера дерева, получается чтобы вычислить путь до любой ноды, нужно знать как минимум количество элементов, что равносильно чтению всего файла
к
раз ключи упорядоченны, то можно взять [(k, v)], искать бинарным поиском (что все равно будет за O(n), ведь это список, но меньше сравнений), но весь файл читать не придется при этом
AK
мапа это дерево, длина пути до ноды все равно будет зависеть от размера дерева, получается чтобы вычислить путь до любой ноды, нужно знать как минимум количество элементов, что равносильно чтению всего файла
То есть в реализации из Data.Map ноды хранятся не по отдельности, а в одном масиве?
к
нет, ноды хранятся в дереве. Там буквально дерево
когда делаем лукап,
- если Tip, то элемента нет
- если Bin k a _ _, и k - нужный ключ, то a
- если Bin k _ l r, и k > нужного ключа, то ищем в l
- иначе ищем в r
lookup :: Ord k => k -> Map k a -> Maybe a
lookup = go
where
go !_ Tip = Nothing
go k (Bin _ kx x l r) = case compare k kx of
LT -> go k l
GT -> go k r
EQ -> Just x
data Map k a
= Bin k a (Map k a) (Map k a)
| Tipкогда делаем лукап,
- если Tip, то элемента нет
- если Bin k a _ _, и k - нужный ключ, то a
- если Bin k _ l r, и k > нужного ключа, то ищем в l
- иначе ищем в r
lookup :: Ord k => k -> Map k a -> Maybe a
lookup = go
where
go !_ Tip = Nothing
go k (Bin _ kx x l r) = case compare k kx of
LT -> go k l
GT -> go k r
EQ -> Just x
к
пока мы не знаем количество элементов мапы, мы не знаем, какая у дерева будет глубина, значит не сможем и найти путь
к
поэтому мапы и сеты в такой реализации не могут быть бесконечными например
к
точнее могут, если напрямую дерево строить бесконечное, но не могут быть получены из бесконечного списка
к
какие-то альтернативы разумные для бесконечных мапов я не нашел, я все еще думаю, что в таких кейсах лучше всего использовать просто [(k, v)]
AK
пока мы не знаем количество элементов мапы, мы не знаем, какая у дерева будет глубина, значит не сможем и найти путь
Все равно не понимаю. Зачем мне путь в полном дереве? Почему не прочитать только кусок добавляя каждую ноду из списка к пустому дереву? Тогда полным оно будет только тогда (и если) потребуется последний элемент.
к
Все равно не понимаю. Зачем мне путь в полном дереве? Почему не прочитать только кусок добавляя каждую ноду из списка к пустому дереву? Тогда полным оно будет только тогда (и если) потребуется последний элемент.
1
---
2
/
1
---
2
/ \
1 3
---
3
/ \
2 4
/
1
---
2
/
1
---
2
/ \
1 3
---
3
/ \
2 4
/
1
к
с разным числом элементов путь до 1 меняется
к
пока неизвестна глубина дерева, путь тоже неизвестен
к
нужно или заранее знать хотя бы число элементов (этого хватит, если заранее известно, что список пар точно отсортирован), или не балансировать дерево
к
если не балансировать, то это просто обычный список пар и выйдет
1
\
2
\
3
\
4
или
4
/
3
/
2
/
1
1
\
2
\
3
\
4
или
4
/
3
/
2
/
1
ВЩ
Кстати, строение мапы можно напечатать
AK
нужно или заранее знать хотя бы число элементов (этого хватит, если заранее известно, что список пар точно отсортирован), или не балансировать дерево
Балансировка же при каждом добавлении производится. Вот только тут уже нужна мутабельность
к
Балансировка же при каждом добавлении производится. Вот только тут уже нужна мутабельность
1. зачем мутабельность, эти мапы успешно балансируются без всякой мутабельности
2. а построение мапы из списка это не добавление?
2. а построение мапы из списка это не добавление?
AK
1. зачем мутабельность, эти мапы успешно балансируются без всякой мутабельности
2. а построение мапы из списка это не добавление?
2. а построение мапы из списка это не добавление?
1. Чтобы поменять ссылки в нодах. 2. Не знаю как в хаскеле