Improved representation for Set and Map
I maintainer di solito rispondono entro 1 giorno
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 20/100
- Tipo di issue
- Refactoring
- Chiarezza
- Da chiarire
- Stato di attività
- Ferma
- Stack tecnologico
- haskell
- Ambito
- performance
Direzione di ricerca
Esamina innanzitutto le rappresentazioni attuali di Set e Map e la discussione del PR #1069 di containers a cui si fa riferimento; l’issue non identifica file di implementazione né test. Determina quale rappresentazione proposta viene selezionata, quindi convalida gli invarianti e gli effetti dichiarati sulla memoria e sulle prestazioni prima di considerare concluso il lavoro.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
Consider changing the representation to avoid Tips.
Suggested by wrengr in https://github.com/haskell/containers/pull/1069#issuecomment-2504945201
I'm thinking
data Set a
= Bin !Int !a !(Set a) !(Set a)
| Two !a !a
| One !a
| Nil -- Invariant: Never a child of Bin
This hopefully improves performance but certainly improves memory usage. Compared to today, for n elements we can avoid storing ~n Tips and ~n/2-2n/3 Ints.
Alternately, as midway between current and the above,
data Set a
= Bin !Int !a !(Set a) !(Set a)
| One !a
| Tip
-- Invariant: Bin _ x Tip Tip is always replaced with One x
This puts the match-on-singleton idea of #1069 into the type. Avoids storing ~2n/3-n Tips and ~n/3-n/2 Ints.
- Lingua principale
- Haskell
- Stelle
- 355
- Fork
- 194
- Merge medio
- 3g 4h
- PR unite (30g)
- 7
Preparare l'ambiente
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 ·
I maintainer di solito rispondono entro 1 giorno
-
IntSet low-hanging-fruit performance
Difficoltà 3/5 1-2 giorni Idoneità per principianti 58/100
haskell/containers#1251 ·
I maintainer di solito rispondono entro 1 giorno
-
maintainability major-release
Difficoltà 3/5 1-2 giorni Idoneità per principianti 70/100
haskell/containers#1250 ·
I maintainer di solito rispondono entro 1 giorno
-
PostOrder: foldl and foldr'Apertaperformance Tree
Difficoltà 3/5 1-2 giorni Idoneità per principianti 55/100
haskell/containers#1247 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 3-5 giorni Idoneità per principianti 50/100
haskell/containers#1242 ·
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di haskell/containers
Issue simili
-
infrastructure
Difficoltà 1/5 1-3 ore Idoneità per principianti 65/100
alunduil/siren-json.hs#232 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 88/100
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
jgm/asciidoc-hs#14 ·
-
brick-3.0Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
commercialhaskell/stackage#8129 · 2 commenti ·
-
Add DataHaskell ?Aperta
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 76/100
severo/awesome-parquet#50 ·