Poor performance of Graph.replace_vertex/2 for large graphs
Chưa có ai nhận issue này.
Đánh giá
- Độ khó
- 4/5
- Thời gian dự kiến
- 3-5 ngày
- Mức phù hợp với người mới
- 35/100
- Loại issue
- Lỗi
- Độ rõ ràng
- Khá rõ ràng
- Mức độ hoạt động
- Đình trệ
- Công nghệ
- elixir
- Lĩnh vực
- performance
Hướng nghiên cứu
Bắt đầu bằng cách so sánh Graph.replace_vertex/2 với Graph.replace_vertex_old/2 và xem lại issue #80 cùng PR #84 để kiểm tra bản sửa liên quan. Tái hiện benchmark IEx trên một đồ thị có 1.000.000 đỉnh và cạnh, sau đó xác minh định nghĩa của in-edge và out-edge. Được xem là hoàn tất khi thao tác thay thế nhanh hơn đáng kể mà không trộn lẫn các tập cạnh đó.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Mô tả
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.
- Ngôn ngữ chính
- Elixir
- Star
- 571
- Fork
- 76
- Chỉ số merge pull request
- Không có pull request nào được merge trong 30 ngày
Hướng dẫn đóng góp
Chưa lập chỉ mục được hướng dẫn đóng góp cho kho mã nguồn này
Bắt đầu từ đâu
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của bitwalker/libgraph
-
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 35/100
-
Độ khó 4/5 3-5 ngày Mức phù hợp với người mới 35/100
-
Failing tests Đang mở
Độ khó 3/5 1-2 ngày Mức phù hợp với người mới 35/100
-
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 25/100
-
Độ khó 4/5 3-5 ngày Mức phù hợp với người mới 35/100
Tất cả issue của bitwalker/libgraph
Issue tương tự
-
MDEx integration docs tell users to skip `lumis_wasm_*` packages, which mdex_native 0.2.9 made wrong Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 88/100
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 82/100
beyond-all-reason/teiserver#1616 ·
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 75/100
carverauto/serviceradar#4596 ·
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 75/100
-
bug
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 65/100