可复现 SLF-Killer 图及性能优化实验
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 20/100
- issue の種類
- 機能追加
- 明瞭さ
- 説明が足りない
- 活発さ
- 停滞
- 技術スタック
- cpp
- 領域
- data, performance
調査の方向性
この Issue には、リポジトリのファイル、テスト、エントリポイントが記載されていません。まず、約束されている小規模な SLF-Killer グラフジェネレーターと、JFR の正確な統合対象を依頼してください。完了とするには、再現可能なベンチマークと、合意された実装スコープが必要です。
索引モデルが issue の本文から書いたものです。
説明
您好 ，
我近期在研究图算法性能极限，尤其关注 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日
- 主要言語
- C++
- スター
- 3.6k
- フォーク
- 470
- PR マージ指標
- 30日以内にマージされた PR はありません
環境構築
このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートあり
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
alibaba/GraphScope のほかの issue
-
[BUG] Failed archive extraction deletes the dataset cache対応中かも @dajiaohuang が 6 日前に担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
alibaba/GraphScope#4674 ·
-
stale
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
alibaba/GraphScope#4655 · コメント 2 件 ·
-
stale
難易度 5/5 1週間以上 初心者へのやさしさ 38/100
alibaba/GraphScope#4654 · コメント 2 件 ·
-
stale
難易度 4/5 3〜5日 初心者へのやさしさ 45/100
alibaba/GraphScope#4647 · コメント 3 件 ·
-
stale
難易度 4/5 3〜5日 初心者へのやさしさ 30/100
alibaba/GraphScope#4639 · コメント 2 件 ·
alibaba/GraphScope の issue をすべて見る
似ている issue
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
メンテナーはふだん 1 日以内に返信
-
enhancement Ready for final check
難易度 2/5 1〜3時間 初心者へのやさしさ 79/100
mpogue2/SquareDesk#1818 · コメント 1 件 ·
-
launch-client --save-creds creates creds/<account>/ with mode 755, not 700対応中かも @metis-sprock が今日担当しました。 オープンbacklog bug
難易度 2/5 1〜3時間 初心者へのやさしさ 74/100
EchoTools/nevr-runtime#1471 ·
メンテナーはふだん 1 日以内に返信
-
難易度 1/5 1時間未満 初心者へのやさしさ 66/100
メンテナーはふだん 2 日以内に返信
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
iamankushpandit/Gume#231 ·
メンテナーはふだん 1 日以内に返信