可复现 SLF-Killer 图及性能优化实验
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 20/100
- Tipo di issue
- Funzionalità
- Chiarezza
- Da chiarire
- Stato di attività
- Ferma
- Stack tecnologico
- cpp
- Ambito
- data, performance
Direzione di ricerca
La issue non indica file del repository, test o punti di ingresso. Inizia richiedendo il generatore di grafi SLF-Killer su piccola scala promesso e un obiettivo di integrazione preciso per JFR; il lavoro sarebbe considerato completato con un benchmark riproducibile e un ambito di implementazione concordato.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
您好 ，
我近期在研究图算法性能极限，尤其关注 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日
- Lingua principale
- C++
- Stelle
- 3.6k
- Fork
- 470
- Metriche di merge delle PR
- Nessuna PR unita negli ultimi 30g
Preparare l'ambiente
Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.
- Nessun Dockerfile né file Docker Compose
- Ha un modello di pull request
- Leggi la guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di alibaba/GraphScope
-
[BUG] Failed archive extraction deletes the dataset cacheForse già presa @dajiaohuang l’ha presa 6 giorni fa. Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
alibaba/GraphScope#4674 ·
-
Please add multi-tenancyApertastale
Difficoltà 5/5 Più di una settimana Idoneità per principianti 25/100
alibaba/GraphScope#4655 · 2 commenti ·
-
stale
Difficoltà 5/5 Più di una settimana Idoneità per principianti 38/100
alibaba/GraphScope#4654 · 2 commenti ·
-
stale
Difficoltà 4/5 3-5 giorni Idoneità per principianti 45/100
alibaba/GraphScope#4647 · 3 commenti ·
-
[BUG] IC14无法用Cypher执行Apertastale
Difficoltà 4/5 3-5 giorni Idoneità per principianti 30/100
alibaba/GraphScope#4639 · 2 commenti ·
Tutte le issue di alibaba/GraphScope
Issue simili
-
Shell: serve the home app's Cookie Policy on a hard reloadForse già presa @2001anshkaushik l’ha presa oggi. Apertafeature module:ai
Difficoltà 2/5 1-3 ore Idoneità per principianti 88/100
rocketride-org/rocketride-server#2899 · 1 commento ·
I maintainer di solito rispondono entro 2 giorni
-
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 85/100
rice-solar-physics/HYDRAD#113 ·
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
I maintainer di solito rispondono entro 3 giorni
-
status:needs-triage
Difficoltà 2/5 1-3 ore Idoneità per principianti 76/100
PX4/PX4-Autopilot#29496 ·
I maintainer di solito rispondono entro 1 giorno
-
Missing icon for .cpp2 filesAperta
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 66/100
madskristensen/FileIcons#385 ·