什麼是指針追逐以及它如何與BFS相關

Question

在BFS（廣度優先搜索）上閱讀PPT時，我發現可以在我們有「指針追逐」的地方使用BFS。追蹤指標究竟是什麼，它與BFS有什麼關係？

Answer 1

指針指示您的數據的圖表。 BFS（寬度優先搜索）是在該圖中搜索的算法。

指針追逐只是下面大量指針的另一個詞。

Answer 2

我覺得最容易想到Linked List的例子。

可以說我們有一個Linked List 5個元素。要獲得第三個元素，您必須使用Pointer-chasing遍歷元素。

Answer 3

從硬件角度來看，指針追逐對性能不利，因爲內存讀取在CPU中實際上是串行化的（即沒有ILP）。直到前一個完成爲止（因爲先前的加載爲我們提供了下一個加載的地址，因此......），您無法開始讀取（即加載instr）。