Poor performance of Graph.replace_vertex/2 for large graphs
还没有人认领这个 Issue。
评估
- 难度
- 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 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 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 一周以上 新手友好度 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 ·