Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Optimizing DFS in Data.Graph

Aperta
  • Qualcosa non va?
#882 5 commenti 0 reazioni 0 assegnatari Vedi su GitHub

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
25/100
Tipo di issue
Refactoring
Chiarezza
Abbastanza chiara
Stato di attività
Ferma
Stack tecnologico
haskell
Ambito
performance

Direzione di ricerca

Iniziate esaminando l’implementazione di dfs di Data.Graph e gli helper generate, prune e chop descritti nell’issue. Confrontate l’approccio dfsGraph proposto con dfs, topSort, scc e bcc, usando i benchmark elencati come riferimento. Il lavoro sarà completato quando saranno rimossi gli alberi intermedi non necessari, mantenendo al contempo gli algoritmi sui grafi interessati.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

Graph performance

dfs is the core function in Data.Graph that all other algorithms (topSort, scc, bcc, etc) are based on. It takes a Graph and generates a [Tree Vertex].

dfs makes use of generate, prune and chop to generate a [Tree Vertex] and chop it into the returned [Tree Vertex].

Other functions further transform this [Tree Vertex], for example topSort flattens the [Tree Vertex] into a [Vertex].

These intermediate trees are unnecessary.

  • The trees generated by generate are immediately chopped into other trees.
  • For topSort, the trees returned by dfs are immediately turned into a list.

There is no reason we need to create these trees in memory.

I propose combining the existing generate, prune, and chop function into a new core function that eliminates the intermediate trees from generate and also allows us to choose what to build from the DFS.

dfsGraph :: (Vertex -> a -> b) -> (b -> a -> a) -> a -> Graph -> [Vertex] -> a

Then we can define, for example

dfs = dfsGraph Node (:) []
topSort = dfsGraph <build the list directly>

Benchmarks on a random graph with 10,000 vertices and 100,000 edges:

  dfs:            OK (0.90s)
    3.51 ms ±  79 μs, 57% less than baseline
  topSort:        OK (0.47s)
    3.60 ms ± 107 μs, 59% less than baseline

Other function such as scc and bcc should also benefit, I've not implemented them yet.

Thoughts? I can clean up my code into a PR if this sounds good.

Lingua principale
Haskell
Stelle
355
Fork
194
Merge medio
3g 4h
PR unite (30g)
7

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di haskell/containers

Tutte le issue di haskell/containers

Issue simili

Altre issue su Haskell

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.