Poor performance of Graph.replace_vertex/2 for large graphs
まだ誰も着手していません。
評価
- 難易度
- 4/5
- 見積もり時間
- 3〜5日
- 初心者へのやさしさ
- 35/100
- issue の種類
- バグ
- 明瞭さ
- おおむね明確
- 活発さ
- 停滞
- 技術スタック
- elixir
- 領域
- performance
調査の方向性
まず Graph.replace_vertex/2 と Graph.replace_vertex_old/2 を比較し、関連する修正について issue #80 と PR #84 を確認します。1,000,000 個の頂点と辺を持つグラフで IEx ベンチマークを再現し、その後 in-edge と out-edge の定義を検証します。これらの辺集合を混在させずに、置換が大幅に高速化されていれば完了です。
索引モデルが issue の本文から書いたものです。
説明
Similar to #80 with likely similar fix. ~25x speedup for graph with 1M vertices/edges in iex for:
g = (Graph.new() |> Graph.add_edges(Enum.map(1..1_000_000, fn i -> {i, 1_000_000 - i} end)))
:timer.tc(fn -> Graph.replace_vertex(g, Enum.random(1..1_000_000), 1_000_001) end, :millisecond)
# {56, #Graph<type: directed, num_vertices: 999897, num_edges: 1000000>}
:timer.tc(fn -> Graph.replace_vertex_old(g, Enum.random(1..1_000_000), 1_000_001) end, :millisecond)
# {1399, #Graph<type: directed, num_vertices: 999897, num_edges: 1000000>}
Will add to PR #84 as related issues. Would like someone to double check that I haven't mixed up the in-edges and out-edges definitions.
- 主要言語
- Elixir
- スター
- 571
- フォーク
- 76
- PR マージ指標
- 30日以内にマージされた PR はありません
コントリビューションガイド
このリポジトリのコントリビューションガイドは索引されていません
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
bitwalker/libgraph のほかの issue
-
難易度 1/5 1時間未満 初心者へのやさしさ 35/100
-
難易度 4/5 3〜5日 初心者へのやさしさ 35/100
-
Failing tests オープン
難易度 3/5 1〜2日 初心者へのやさしさ 35/100
-
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
-
難易度 4/5 3〜5日 初心者へのやさしさ 35/100
bitwalker/libgraph の issue をすべて見る
似ている issue
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
agentjido/jido_harness#80 ·
-
難易度 2/5 1〜3時間 初心者へのやさしさ 70/100
sevenseacat/cinder#235 ·
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 85/100
-
難易度 2/5 1〜3時間 初心者へのやさしさ 84/100
phoenixframework/phoenix#6847 ·