Full IntSets?
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 25/100
Direzione di ricerca
La issue non indica file, test o punti di ingresso. Inizia esaminando la rappresentazione esistente di IntSet e considerando il costruttore Full Prefix proposto rispetto a casi d’uso con sequenze contigue come GHC. Per considerare il lavoro completato, sarebbero necessari un design testato e misurazioni nel mondo reale che mostrino se il risparmio di memoria compensi l’overhead aggiuntivo.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
I wonder if it will be useful to add another constructor to IntSet: Full Prefix. This indicates that this is a full tree with a shared prefix.
I expect this to show good improvements for use cases where contiguous runs of Ints are likely. It will also reduce space usage in such cases. For instance, to store [0..n] we will need only $O(\log n)$ memory instead of $O(n)$.
But this would add small overheads in various places, so it will likely not be a clear win in all use cases.
Also, to be clear, this would be small added costs and not a change in the worst case bounds.
For sure we would want to test something like this out on some real world use cases (like GHC, maybe others?) to see how it affects things. Just documenting this idea for now.
- Lingua principale
- Haskell
- Stelle
- 355
- Fork
- 194
- Merge medio
- 2g 6h
- PR unite (30g)
- 5
Preparare l'ambiente
- Nessun Dockerfile né file Docker Compose
- Nessun modello di pull request
- Leggi la guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di haskell/containers
-
unfoldTree is too lazyApertamajor-release strictness Tree
Difficoltà 2/5 1-3 ore Idoneità per principianti 72/100
haskell/containers#1260 ·
-
Difficoltà 5/5 Più di una settimana Idoneità per principianti 35/100
haskell/containers#1261 · 5 commenti ·
-
IntSet low-hanging-fruit performance
Difficoltà 3/5 1-2 giorni Idoneità per principianti 58/100
haskell/containers#1251 ·
-
maintainability major-release
Difficoltà 3/5 1-2 giorni Idoneità per principianti 70/100
haskell/containers#1250 ·
-
PostOrder: foldl and foldr'Apertaperformance Tree
Difficoltà 3/5 1-2 giorni Idoneità per principianti 55/100
haskell/containers#1247 ·
Tutte le issue di haskell/containers
Issue simili
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 82/100
objectionary/phino#1600 ·
I maintainer di solito rispondono entro 1 giorno