algorithm - サイクルを収集する参照カウントの最も単純な拡張は何ですか?

Question

参照カウントだけではサイクルは収集されませんが、サイクルを収集できる追加の手法もあります。そのような最も簡単なテクニックは何ですか？

拡張参照カウントの複雑さとトレース GC を比較したいと思います。

Answer 1

サイクルフリーでコーディングする方が良いですが、サイクルの場合、E と V を使用してグラフで孤立したサイクルを見つけたい場合は、O(|E| + |V|) かかります。これは、連結要素アルゴリズムを見つけて実行するのと似ています。 BFSでグラフのすべてのサイクルを見つけ、|V|について考えるだけなら （コンパイルされたアセンブリで）非常に重くなる可能性があるため、これを防ぐ方がよいため、開発者に任せました。