解決回圈依賴的演算法？-有解無憂

我想創建一個模塊系統，您可以在其中以回圈方式加載依賴項。原因是，回圈依賴無處不在，就像在 Ruby on Rails 中一樣，在模型類之間的關系中：

# app/models/x.rb
class X < ActiveRecord::Base
  has_many :y
end

# app/models/y.rb
class Y < ActiveRecord::Base
  belongs_to :x
end

這通常在 Ruby on Rails 模型中的作業方式是，它首先加載所有模型，依賴項首先是一個符號或“字串”。然后集中管理器獲取所有這些物件并將字串轉換為相應的類，現在類都已定義。當您將第一個類的關系設定為它們對應的類時，其余的類仍然與字串相關，而第一個類與類相關，因此有一個過渡期，其中一些模型完全決議為類，而其他的仍然是字串，因為演算法正在運行并且尚未完成。一旦所有的字串都決議為它們對應的類，演算法就完成了。

我可以想象一個世界變得更加復雜，創建的回圈不是一對一的回圈依賴，而是中間有很多層，創建了一個 5 節點回圈之類的東西。甚至是模塊之間存在來回依賴關系的模塊，例如：

# file/1.rb
class X
  depends_on A
  depends_on B
end
class Y
  depends_on B
end
class Z
  depends_on Q
end

# file/2.rb
class A
  depends_on Y
end
class B
  depends_on Z
end

# file/3.rb
class Q
  depends_on X
end

要解決此問題：

加載所有檔案 *.rb，depends_on視為字串。現在我們在相應的模塊中有每個類的定義，但使用depends_on字串而不是所需的類。
遍歷檔案并決議類。
對于檔案 1.rb，決議 X... 等。
X 依賴于 A，因此與 2/A 相關聯。
X 也依賴于 B，因此與 2/B 相關聯。
Y 取決于 B，因此與 2/B 相關聯。
Z 取決于 Q，因此與 3/Q 相關聯。
A 取決于 Y，因此與 1/Y 相關聯。
B 取決于 Z，因此與 1/Z 相關聯。
Q 取決于 X，因此與 1/X 相關聯。
完畢。

So basically, there are two "rounds". First round is load all the files, and initialize the classes. Second round is associate the class members with corresponding other classes. Doesn't matter the order.

But can it get any more complex? Requiring more than two rounds to resolve such circular dependencies? I'm not sure. Take for example something like this:

# file/1.rb
class A < A_P
  class AA < A_P::AA_P
    class AAA < A_P::AA_P::AAA_P

    end
  end
end
class B < B_Q
  class BB < B_Q::BB_Q
    class BBB < B_Q::BB_Q::BBB_Q

    end
  end
end

# file/2.rb
class A_P
  class AA_P < B
    class AAA_P < B::BB

    end
  end
end
class B_Q
  class BB_Q < A
    class BBB_Q < A::AA

    end
  end
end

In this contrived case, you have:

A (file/1) depending on A_P (file/2), then:
AA (file/1) depending on A_P and AA_P, then:
AA_P (file/2) depending on B (file/1), then:
B (file/1) depending on B_Q (file/2), etc....

That is, it seems like something weird is going on. I'm not sure, my head starts going in knots.

You can't define what class A is extending until class A_P is fully resolved. You can't define what class AA is until class AA_P is fully resolved, which depends on B being resolved, which depends on B_Q being resolved. Etc..

Is it possible to resolve such circular dependencies? What is the general algorithm for resolving arbitrarily complex circular dependencies? Such that, the end is that all the circular dependencies are wired up with the actual value, not a string or other such symbol representing the actual value. The end result of resolving circular dependencies are that every reference should refer to the actual object.

它總是只是一個簡單的兩遍演算法，首先加載基礎物件，然后決議它們的依賴關系，將依賴關系的“字串”轉換為集合中的基礎物件？

你能想出一個例子，它需要的不僅僅是一個簡單的兩遍演算法嗎？然后描述在這種情況下演算法應該如何解決回圈依賴？或者證明/解釋如何確定只需要一個簡單的兩遍演算法？

另一個例子可能是：

// ./p.jslike
import { method_x } from './q'
import { method_y } from './q'

function method_a() {
  method_x()
}

function method_b() {
  console.log('b')
}

function method_c() {
  method_y()
}

function method_d() {
  console.log('d')
}

// ./q.jslike
import { method_b } from './p'
import { method_d } from './p'

function method_x() {
  method_b()
}

function method_y() {
  method_b()
}

我想那也是兩次通過。

uj5u.com熱心網友回復：

您問題的答案取決于您所說的“解決”是什么意思。

考慮以下情況：

你有三個班，A，B和C，這在回圈方式互相依賴。

第一遍（加載）后，您可以訪問有關每個類的所有資訊，即寫入源檔案中的資訊。

現在，假設您想完全“決議” class A。假裝你現在不關心其他課程。

僅根據檔案中的資訊，是否可以僅針對A?

如果答案是否定的，那么您的問題的答案也是否定的。

如果答案是yes，則意味著兩次pass就足以完全解決每個類。您可以遞回或迭代地執行此操作，并且您可能希望快取完全決議的類以避免多次決議它們，盡管這不是正確性所必需的（這純粹是性能優化）。

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/355679.html

標籤：算法依赖图论循环依赖循环图

上一篇：為什么置換演算法的時間復雜度是n*n！而不是n^3*n！？

下一篇：檢查陣列是否包含某些物件