可复现 SLF-Killer 图及性能优化实验
Chưa có ai nhận issue này.
Đánh giá
- Độ khó
- 5/5
- Thời gian dự kiến
- Hơn một tuần
- Mức phù hợp với người mới
- 20/100
- Loại issue
- Tính năng
- Độ rõ ràng
- Cần làm rõ
- Mức độ hoạt động
- Đình trệ
- Công nghệ
- cpp
- Lĩnh vực
- data, performance
Hướng nghiên cứu
Issue không nêu tệp nào trong repository, test hay entry point. Trước tiên, hãy yêu cầu graph generator SLF-Killer quy mô nhỏ đã được hứa và một mục tiêu tích hợp chính xác cho JFR; để được coi là hoàn tất, cần có một benchmark có thể tái lập và phạm vi triển khai đã được thống nhất.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Mô tả
您好 ，
我近期在研究图算法性能极限，尤其关注 SPFA-SLF 在负权图上的最坏情况。为此，我构造了一类可稳定复现的 SLF-Killer 图结构（多跳负权 + 正回边震荡链），该结构会持续触发 SPFA-SLF 的队列误前送与震荡问题。
在该类图上，我测试了 SPFA-SLF 与自己开发的原型算法 JFR，部分测试结果如下：
- 1,000 节点：SPFA-SLF 116.94 ms / 5,825,085 次松弛；JFR 33.16 ms / 175,261 次松弛 → 加速 3.5×
- 10,000 节点：SPFA-SLF 3,692.72 ms / 172,614,311 次松弛；JFR 268.06 ms / 1,191,920 次松弛 → 加速 13.7×
- 50,0000 节点：SPFA-SLF 约 2,540,664.68 ms (~42 分钟) / 93,295,674,368 次松弛；JFR 19,522.09 ms / 74,102,531 次松弛 → 加速 130×
- 100,000 节点：SPFA-SLF 9,885.89 ms / 416,604,533 次松弛；JFR 3,825.38 ms / 15,720,612 次松弛 → 加速 2.58×
算法特点及瓶颈：
- 跳过震荡区段保持局部稳定
- 在负权密集、多跳边图上性能显著优于 SPFA-SLF
- 超大规模图 (>50万节点、数十亿边) 仍需优化内存访问与并行处理
- 算法可进一步结合并行或增量松弛策略提速
该图结构可作为 SPFA-SLF 类算法的最坏情况检测器、图计算系统压力测试及负权系统稳定性验证基准。
如果您对这套算法或压力图生成器感兴趣，我可以提供小规模测试示例，并非常希望能听到您的建议或意见。
此致
敬礼
Jerry
2025年11月25日
- Ngôn ngữ chính
- C++
- Star
- 3.6k
- Fork
- 470
- Chỉ số merge pull request
- Không có pull request nào được merge trong 30 ngày
Chuẩn bị môi trường
Khởi chạy dev container của dự án ngay trên trình duyệt, bằng tài khoản GitHub của bạn.
- Không có Dockerfile hay tệp Docker Compose
- Có mẫu pull request
- Đọc hướng dẫn đóng góp
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 alibaba/GraphScope
-
[BUG] Failed archive extraction deletes the dataset cacheCó thể đã có người làm @dajiaohuang đã nhận 6 ngày trước. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
alibaba/GraphScope#4674 ·
-
Please add multi-tenancyĐang mởstale
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 25/100
alibaba/GraphScope#4655 · 2 bình luận ·
-
stale
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 38/100
alibaba/GraphScope#4654 · 2 bình luận ·
-
stale
Độ khó 4/5 3-5 ngày Mức phù hợp với người mới 45/100
alibaba/GraphScope#4647 · 3 bình luận ·
-
[BUG] IC14无法用Cypher执行Đang mởstale
Độ khó 4/5 3-5 ngày Mức phù hợp với người mới 30/100
alibaba/GraphScope#4639 · 2 bình luận ·
Tất cả issue của alibaba/GraphScope
Issue tương tự
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
Maintainer thường phản hồi trong vòng 3 ngày
-
status:needs-triage
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 76/100
PX4/PX4-Autopilot#29496 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
Missing icon for .cpp2 filesĐang mở
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 66/100
madskristensen/FileIcons#385 ·
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 62/100
microsoft/SysmonCommon#26 ·
-
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 90/100
espressif/esp-matter#1913 ·