chord[函式]

chord[函式]
chord[函式]
更多義項 ▼ 收起列表 ▲

chord是一個函式,可以用來尋找線段與橢圓之間的區域,即“弦”。

API函式

VB聲明

Declare Function Chord Lib "gdi32" (ByVal hdc As Long, ByVal X1 As Long, ByVal Y1 As Long, ByVal X2 As Long, ByVal Y2 As Long, ByVal X3 As Long, ByVal Y3 As Long, ByVal X4 As Long, ByVal Y4 As Long) As Long

API函式

易語言聲明

.版本 2

.DLL命令 Chord, 整數型, "gdi32", "Chord", 公開

.參數 hdc, 整數型

.參數 X1, 整數型

.參數 Y1, 整數型

.參數 X2, 整數型

.參數 Y2, 整數型

.參數 X3, 整數型

.參數 Y3, 整數型

.參數 X4, 整數型

.參數 Y4, 整數型

說明

像註解中那樣畫一個弦。(X1,Y1)和(X2,Y2)定義了橢圓的一個範圍(約束)矩形。點(X3,Y3)和點(X4,Y4)定義了一條線段。該線段與橢圓之間的區域就是“弦”

參數表

X1,Y1 ---------- Long,指定圍繞橢圓的一個矩形的左上角位置

X2,Y2 ---------- Long,指定圍繞橢圓的一個矩形的右下角位置

X3,Y3 ---------- Long,指定與橢圓相交的一條線的一個點

X4,Y4 ---------- Long,指定與橢圓相交的一條線的另一個點

返回值

Long,非零表示成功,零表示失敗。會設定GetLastError

其它

在win16和win95中,約束矩形的寬度和高度必須在3——32766個單位之間。請參考Arc獲得更詳細的圖例

chord 協定

Chord在2001年由麻省理工學院提出(參見0),其核心思想就是要解決在P2P套用中遇到的基本問題:如何在P2P網路中找到存有特定數據的節點。Chord專門為P2P套用設計,因此考慮了在P2P套用中可能遇到的特殊問題,這些內容將在路由的部分進行討論。

哈希算法

Chord使用一致性哈希作為哈希算法。在一致性哈希協定中並沒有定義具體的算法,在Chord協定中將其規定為SHA-1。

路由算法

Chord在一致性哈希的基礎上提供了最佳化的路由算法:

在Chord中,每個節點同樣需要存儲m個其他節點的信息,這些信息的集合被稱為查詢表(Finger Table)。一致性哈希中的節點同樣具有這樣的表格,但在Chord中,表格中的節點不再是直接相鄰的節點,它們的間距(ID間隔)將成2i 的關係排列(i 表示表中的數組下標)。這樣形成的節點之間路由關係實際上就是折半查找算法需要的排列關係。

在查詢的過程中,查詢節點將請求傳送到與鍵值最接近的節點上。收到查詢請求的節點如果發現自身存儲了被查詢的信息,可以直接回應查詢節點(這與一致性哈希完全相同);如果被查詢的信息不在本地,就根據查詢表將請求轉發到與鍵值最接近的節點上。這樣的過程一直持續到找到相應的節點為止。不難看出,查詢過程實際上就是折半查找的過程。

經過Chord的最佳化後,查詢需要的跳數由O ( N)減少到O(log(N))。這樣即使在大規模的P2P網路中(例如N=100,000,000),查詢的跳數也僅為O(8),每個節點僅需存儲27個(log2100000000)其他節點的信息。

Chord還考慮到多個節點同時加入系統的情況並對節點加入/退出算法作了最佳化。

討論

Chord算法本身具有如下優點:

負載平衡

這一優點來自於一致性哈希,也就是一致性哈希中提到的平衡性。所有的節點以同等的機率分擔系統負荷,從而可以避免某些節點負載過大的情況。

分布性

Chord是純分散式系統,節點之間完全平等並完成同樣的工作。這使得Chord具有很高的魯棒性,可以抵禦DoS攻擊。

可擴展性

Chord協定的開銷隨著系統規模(結點總數N)的增加而按照O(logN)的比例增加。因此Chord可以用於大規模的系統。

可用性

Chord協定要求節點根據網路的變化動態的更新查詢表,因此能夠及時恢復路由關係,使得查詢可以可靠地進行。

命名的靈活性

Chord並未限制查詢內容的結構,因此套用層可以靈活的將內容映射到鍵值空間而不受協定的限制

相關詞條

相關搜尋

熱門詞條

聯絡我們