dataStructure_外部排序/多路歸并/敗者樹/最佳歸并樹

文章目錄

• ​​外部排序​​

• ​​時間代價:為什麼不用二路歸并​​
• ​​概念​​

• ​​歸并段​​

• ​​小結:每趟歸并需要讀寫磁盤的次數取決于​​

• ​​記憶體工作區​​
• ​​嚴格k叉樹​​
• ​​k叉樹和k路歸并的趟數s與初始歸并段數量m的關系​​

• ​​提高外部排序性能​​

• ​​k路歸并排序所需要的比較次數​​

• ​​每趟k路歸并需要比較的次數T​​
• ​​S趟歸并需要的比較次數​​
• ​​敗者樹LT(LoserTree)​​

• ​​簡單敗者樹示意圖​​
• ​​估算k路歸并敗者樹的高度:​​
• ​​失敗者/勝利者​​

• ​​敗者之間的關系:strongerLoser & weakerLoser​​

• ​​葉結點​​
• ​​内部分支結點​​

• ​​🎈使用敗者樹後S趟比較需要比較的次數​​

• ​​緩沖區和比較路數​​
• ​​其他參考:Tournament Tree​​

• ​​loser tree​​

• ​​置換選擇排序RSS​​

• ​​例​​

• ​​參考資料​​

• ​​相關對象​​
• ​​步驟​​
• ​​算法特點​​

• ​​歸并樹​​

• ​​最佳歸并樹​​
• ​​ref (huffmanTree)​​

• ​​執行個體​​

• ​​添加虛段​​

• ​​樹的基本性質:葉結點和分支結點​​
• ​​嚴格k叉樹:葉子結點和根結點數目關系​​
• ​​補充多少個虛段構成嚴格k叉樹?​​

外部排序

時間代價:為什麼不用二路歸并

• 主要考慮磁盤IO的耗時
• 一般認為,機械IO的耗時遠遠超過記憶體運算的時間
• 我們用一次多路歸并就完成了所有臨時檔案的歸并，而并非按記憶體中的二路歸并那樣，一次歸并兩個子串，耗費$ \log _{2}n$次歸并。

• 外排序中不适用上述方法的原因在于每次讀寫都需要對硬碟進行讀寫，而這是非常緩慢的。
• 是以應該盡可能減小磁盤的讀寫次數。

• 在上述方法中也存在權衡。

• 當臨時檔案（順串）的數量繼續增大時，歸并時每次可從順串中讀入的資料減少了。
• 比如說，50 GB的資料量，100 MB的可用記憶體，

• 這種情況下用一趟多路歸并就顯得不劃算。
• 讀入很多的順串花費的時間占據了排序時間的大部分。
• 這時，我們可以用多次（比如兩次）歸并來解決這個問題。
• 這時排序算法變為下述這樣：

• 第一步不變。
• 将小的順串合并為大一些的順串，适當減小順串的數目。
• 将剩餘的大一些的順串歸并為最終結果。

概念

歸并段

• 外部排序一般采用歸并排序法
• 包括兩個獨立的階段(内部排序+外部歸并)

• 根據記憶體緩沖區的大小,将外部檔案分為k份長度為L的子檔案
• 依次将這些檔案讀入記憶體,就可以使用内部排序算法對這些子檔案進行排序
• 這些被排序後的子檔案,将這些歸并段重新寫回到磁盤(有序子檔案稱為歸并段(順串))
• 這樣,獲得歸并段需要2k次IO
• 對前一個階段或得到歸并段進行**逐趟歸并**,直到得到一個有序的檔案

• 在磁盤上,一個歸并段的大小可能可能占用了多個盤塊

• 如果緩沖區每次隻能夠讀取一個盤塊,那麼一個歸并段中的資料則不能夠被一次性讀取完
• 這意味着需要多次從一個歸并段中讀取資料塊
• “歸并算法”(merge algorithm)對每一個大塊隻是順序地做一輪通路(進行歸并)，每個大塊不用完全載入主存。

• 将兩個有序段歸并成一個有序段的過程,若在記憶體進行，則很簡單(調用merge過程)
• 但是，在外部排序中實作兩兩歸并時，不僅要調用merge過程，而且要進行外存的讀/寫﹐
• 這是由于我們不可能将兩個有序段及歸并結果段同時存放在記憶體中的緣故。
• 計算機對外存上資訊的讀/寫是以“實體塊"為機關的。

• 假設外部檔案含有記錄,劃分為10個歸并段,每段條記錄,

• 10個初始歸并段到一個有序檔案,共進行了4趟歸并,每一趟從m個歸并段得到個歸并段。

• 這種歸并方法稱為2-路平衡歸并。

• 如果每個實體塊可以容納200個記錄(每個段R要占用$\frac{1000}{200}=$5個塊)，則每一趟歸并需進行5*10=50次“讀”和50次“寫”
• 4趟歸(400次IO)并加上内部排序(100次IO得到10個有序歸并段檔案)時所需進行的讀/寫使得在外排中總共需進行500次的讀/寫。

小結:每趟歸并需要讀寫磁盤的次數取決于

• 計算機對外存上資訊的讀/寫是以“實體塊"為機關的

• 這意味着,盡管記憶體足夠大,通路磁盤的次數卻不會減小
• 但是記憶體夠大,可以為改進提供優化空間

• 對于k路歸并,我們可以讀入k個不同歸并段的磁盤資料塊
• 以此減少歸并趟數,進而減少IO次數

• 待排序檔案的記錄數量NumberOfRecords=n
• 磁盤塊能夠容納的記錄數量blockSizeOfRecords=m
• 待排總記錄數占用的塊數為(也就是讀磁盤的次數,同時等于寫磁盤的次數)
• 是以讀寫磁盤的總次數為
• …(或者更多的限制,比如記憶體緩沖區)

記憶體工作區

• 對于一個含有2000記錄的檔案,存儲在盤塊可容納125條記錄的磁盤上
• 先通過8次内部排序,得到8個有序子檔案(歸并段)

• 将他們分别記為
• 每個段含有記錄125條

• 在記憶體工作區中分為等分三個緩沖區:

• 兩個輸入緩沖區A&B(用以讀入歸并段)
• 一個輸出緩沖區(儲存歸并結果)

• 在記憶體執行2路歸并排序
• 排完序後放入輸出緩沖區C中

• 緩沖區C滿時,則将内容順序寫入歸并段
• 清空輸出緩沖區

• 當某個輸入緩沖區中内容為空的時候,繼續讀入歸并段/檔案的下一個塊
• 當兩個輸入歸并段的資料塊都被讀入完,而且歸并完成,則開始處理其他歸并段

嚴格k叉樹

• 隻有0度和k度結點的k叉樹

• 例如一棵一般的(非完全滿的嚴格二叉樹)

• 隻有0度葉子(7個)和2度分支結點(6個)

• 

• 又比如haffman樹

k叉樹和k路歸并的趟數s與初始歸并段數量m的關系

• 對于同一檔案而言,進行外部排序所需要的IO次數和歸并的趟數s成正比
• 對于m個初始歸并段,做k路平衡歸并,歸并的趟數s滿足

• s就是歸并k叉樹的高度

• 下面分析為什麼是這樣的

• 對于m=10段初始歸并段,采用k=3路歸并進行外部歸并

• 從圖中可以看出,執行了3趟歸并
• 如果m=9,則隻需要2趟歸并
• 對于滿k叉樹,第h層的結點數(葉子結點)數m量最多為個

• 現在我們回到歸并趟數s和k叉樹的高度關系之間的讨論

• 從上圖的例子中可以看出,葉子結點的所在層(歸并段)歸并成倒二層(最後一層分支結點層)
• 從倒二層一直統計到根結點層,就可以統計出發生了多少趟歸并
• 不過更加直接的了解是,自根結點向葉子結點開始統計

• 處理根結點不在繼續歸并,其餘所有層都要執行歸并
• 是以歸并趟數是層數h-1,即s=h-1

• 也就是葉子結點到根結點的**路徑長度(路徑邊數)**表示它參與的歸并趟數

• 進而得到歸并趟數s和歸并路數以及初始歸并段數m之間的關系!🎈

• 用上面的例子代入體驗一下公式:(m=10,k=3)

• 可見,至少需3趟歸并操作,和示例中的情況相符合
• 如果取m=9,k=3,那麼隻需要執行2趟歸并

提高外部排序性能

• 從上面的分析可以看出:

• 減少歸并排序趟數s,可以減少IO次數

• 可以通過增加歸并路數k來減小s

• 撲克牌玩家增加到k位🎈

• 或者通過減小初始歸并段數m,也可以減小s

• 需要設法加長初始歸并段

k路歸并排序所需要的比較次數

• 和2路歸并排序的過程相比,k路歸并需要比較的次數要多

• 如果用傳統的辦法确定最小值
• 如果引入敗者樹可以解決這個問題

每趟k路歸并需要比較的次數T

• 對k路有序序列進行歸并,就是要依次逐個的确定k個有序序列最小元素

• 也就是,從k個有序序列的最小值的各自的最小元素中選擇最小的元素
• 過程有點像簡單選擇排序,總共需要比較的次數為k-1次
• 如果想要歸并得到u個有序記錄(u為全部的待歸并元素),在大緻需要比較次

• 實際上,就算是最壞的情況也不會達到這個次數
• 但是可以大緻估計出來(特别是u/k比較)
• 一個可以參考的(主觀的最壞情況的比較次數):

• 次

S趟歸并需要的比較次數

• T表示TotalComparisons
• m表示初始歸并段數量m

• 由換底公式,
• 是以
• 我們需要設法減小後面的因子

敗者樹LT(LoserTree)

• 也叫k路歸并敗者樹

• k展現在葉子結點有k個
• 這和待歸并的歸并段數量k一緻

• 利用敗者樹來減少由于增大k帶來的比較次數的增多
• 能夠使得内部k路歸并不受到k的增大的影響
• 敗者樹是樹形選擇排序的一種變體,視為一棵完全二叉樹(CBT(complete BinaryTree))

簡單敗者樹示意圖

• 上面是k=4路歸并敗者樹(k取決于葉子結點數)
• 首先敗者樹的下方的幾個序列分别表示獨立的歸并段B1~B4
• 葉子結點表示各個歸并段目前參與比較的元素
• 而L0結點可以了解為虛拟結點,用來表示本輪比較出來的最小值
• 這樣一來上面的樹包含兩層分支結點和一層葉子結點

• 分支總是儲存某兩個葉子結點之間的失敗者(元素較大者)所屬的段号
• 比如:

• 6>0,将6所屬段的段号B1(可以簡記為1)寫入L2分支結點中
• 9>8,将9所屬段的段号B4(簡記為4)寫入寫入到L3分支結點中
• 現在子樹L2和L3的葉子結點中的勝利者分别是0,8
• 将兩個勝利加賽區分:

• 8>0,是以8所屬段号B3(簡記為3)寫入分支結點L1中

• 最終的勝利者元素0被确定出來了,将0所屬的段号B2寫入L0中
• 本輪操作屬于初始化敗者樹操作,需要比較次

• 在第二輪選擇最小元素的過程中,我們将看到,比較次數比單純的使用選擇排序中的方法要少

• 這是因為,分支結點記住了上一輪比較的階段性結果,我們利用其這些分支結點,達到減少重複比較的目的
• 在第一趟中,元素0被确定為第一輪的最小者(總冠軍)
• 于是第二輪中,0的後繼元素12接替了0的位置,開始參與比較
• 主需要看12所在結點的雙親結點中的段号,令12和雙親結點所指段号(B1)的目前待比較元素(6)比較

• 12>6,于是L2被修改為B2

• 6繼續和它爺結點(L1)所指段B3的目前元素8進行比較:

• 因為L1記錄這上一輪比較中,子敗者樹L3下的所有葉子結點中的最小值(所屬段号B3)
• 第二輪比較中,上一輪的勝者子樹的最小者和L3所指的元素比較後,得到的較小者可直接認定為第二輪的最小元素
• 現在,由于8>6,于是此次比較的敗者依然是8,是以L1就不需要更改
• 同時,第二輪比較的出來的最小值也被确定下來,就是6

• 本輪比較中,我們發現:完全二叉樹根結點L1(不包括虛拟的L0)的右子樹L3沒有元素發生變動,不需要重新比較
• 這個例子中,經過第一輪(k-1=8-1=7次比較後),最小者(總冠軍)在L2子樹側
• 那麼L3子樹側的最小值則被記錄在最後一個記錄敗者的分支結點L1上

• 這一性質對于所有敗者樹都适用
• 并且,是以條性質,從第二輪開始,比較次數會得到比第一趟所需的次數(k-1)來的小
• 上一趟比較彈出的冠軍(前冠軍)的後繼元素進入葉子結點後,隻會影響前冠軍所在的那一側子樹
• 另一側不會發生變化,不需要再次比較
• 在每層都是如此,隻影響一側

• 那麼,對于敗者樹,(自第二趟确定最小元素)的過程中,最多隻需要比較敗者樹高度相當的次數

• 例如前總冠軍0被替換為12後,發生如下比較

• 記為某個分支結點所指段号的目前參與比較的元素

• 隻比較了3次,這恰好是敗者樹的非(外部)葉子結點高度

估算k路歸并敗者樹的高度:

失敗者/勝利者

• 了解為百米沖刺用時成績
• 兩個數中較大的為失敗者
• 較小的為勝利者

敗者之間的關系:strongerLoser & weakerLoser

• 為了更好的描述不同輪次失敗者之間的關系,引入兩個稱呼
• 在LT中,同一個子樹根結點的各層分支結點中儲存的敗者結點(所屬段的段号)存在一定關系
• 從算法的執行過程中可以看到,高層的分支結點(strongerLoser)對應的敗者葉結點的值是較低層分支結點(weakerLoser)來的強

• 就是說,strongerLoser vs weakerLoser,勝利的會是前者

• 回到歸并排序,為了更加形象的了解歸并段号和段内目前參與比較元素的關系:

• 可以将歸并段了解為國家隊
• 将歸并段目前參與比較元素了解為目前派出場的賽跑選手

葉結點

• k個葉結點分别存放k個歸并段在歸并過程中目前參與比較的記錄

内部分支結點

• 用來記憶子樹中的失敗者(勝利者向上繼續比較,知道根結點)

• 勝利者(葉子結點)類似于守擂台,直到有比自己更小的上層葉結點,自己才轉為失敗者

• 在敗者樹中,較晚失敗的結點相對于早早失敗的結點來的強

• 相應的,較強的結點(所在的歸并段的段号)也較靠後移入才移入到分支結點
• 低層的分支結點是留給較早失敗的結點所歸屬的段号

• 敗者樹的子樹也是敗者樹

• 記敗者樹LT的根結點R:

• 目前冠軍結點所在子樹為CCLT(champion child loser Tree)
• 另一顆子樹為FCLT(Faild Child Loser Tree)

• 那麼R中儲存的總是FCLT子樹的最小葉子結點(所在的歸并段的段号)
• 每一層的分支結點(子樹根結點)都有這樣的規律
• 是以敗者樹的效率比直接比較最小值要高

🎈使用敗者樹後S趟比較需要比較的次數

• 直接比較:
• 🎈🎈進而得到

• 該公式僅包含了:

• 初始歸并段數m
• 待歸并總記錄數n
• (而于歸并路數k無關)

• 進而消除了k增大帶來的内部歸并排序比較次數的增多.

緩沖區和比較路數

• 由于增大歸并路數,需要相應數量的輸入緩沖區來支援
• 如果可用的記憶體空間有限(不變),那麼增加k,會導緻每個緩沖區的容量的減小

• 可能導緻内外存交換資料的次數增大

• 是以,k增大來來達到歸并次數s減少,讀寫外存的次數還可能增加

其他參考:Tournament Tree

• The Tournament Tree is based onan elimination tournament, as in sports competitions.

• In each game, two of the input elements compete.
• The winner is promoted to the next round.
• Therefore, we get a​​binary tree​​ of games.
• The list is sorted in ascending order, so the winner of a game is the smaller one of both elements.

loser tree

• For k-way merging, it is more efficient to only store the loser of each game (see image).

• The data structure is therefore called a loser tree.
• When building the tree or replacing an element with the next one from its list, we still promote the winner of the game to the top.
• The tree is filled like in a sports match but the nodes only store the loser.
• Usually, an additional node above the root is added that represents the overall winner.
• Every leaf stores a pointer to one of the input arrays. Every inner node stores a value and an index.
• The index of an inner node indicates which input array the value comes from.
• The value contains a copy of the first element of the corresponding input array.The algorithm iteratively appends the minimum element to the result and then removes the element from the corresponding input list. It updates the nodes on the path from the updated leaf to the root (replacement selection).
• The removed element is the overall winner. Therefore, it has won each game on the path from the input array to the root. When selecting a new element from the input array, the element needs to compete against the previous losers on the path to the root. When using a loser tree, the partner for replaying the games is already stored in the nodes.
• The loser of each replayed game is written to the node and the winner is iteratively promoted to the top. When the root is reached, the new overall winner was found and can be used in the next round of merging.The images of the tournament tree and the loser tree in this section use the same data and can be compared to understand the way a loser tree works.

• For the most part, loser trees and heaps are quite similar.

• However, there are a few important distinctions.
• The loser tree, because it provides the loser of each match,will contain repeat nodes.
• Since theheapis a data-storing structure, it won’t contain these redundancies.
• Another difference between the two is that the loser tree must bea full binary tree(because it is a type of tournament tree),
• but the heap does not necessarily have to be binary.

• Finally, to understand a specific quality of the loser tree, consider the following problem:

• Suppose we have k sequences, each of which is sorted in nondecreasing order, that are to be merged into one sequence in nondecreasing order.
• This can be achieved by repeatedly transferring the element withthe smallest keyto an output array.
• The smallest key has to be found from the leading elements in the k sequences.
• Ordinarily, this would require k − 1 comparisons for each element transferred.
• However, with a loser tree, this can be reduced to log2 k comparisons per element.

置換選擇排序RSS

• 置換-選擇排序(Replacement-Selection Sorting)是在樹形選擇排序的基礎上得來的,
• 它的特點是:

• 在整個排序(得到所有初始歸并段)的過程中,選擇最小(或最大)關鍵字
• 輸入&輸出交叉或平行進行。

例

• 已知初始檔案含有24個記錄v它們的關鍵字分别為
• 51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76
• 假設記憶體工作區可容納6個記錄,按照

• 普通的簡單選擇排序可求得如下4個初始歸并段:(每段長度6)

• (51,49,39,46,38,29,)(14,61,15,30,1,48),(52,3,63,27,4,13),(89,24,46,58,33,76)
• RUN1:29,38,39,46.49,51
• RUN2:1,14,15,30,48,61
• RUN3 :3,4,13,27,52,63
• RUN4 :24,33,46,58,76,89

• 若按置換-選擇進行排序,則可求得如下3個初始歸并段:

• 51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76

• 緩沖區大小為6
• 讀入前6個數到緩沖區WA,計算min(WA)=29
• …

• RUN1:29,38,39,46,49,51,61
• RUN2:1,3,14,15,27 ,30,48,52,63,89
• RUN3 ; 4,13,24,33,46,58,76

參考資料

• 為了增加每一個有序的臨時檔案的長度，可以采用​​置換選擇排序​​（Replacement selection sorting）。
• 它可以産生大于記憶體大小的順串。
• 具體方法是在記憶體中使用一個​​最小堆​​進行排序

• 設該最小堆的大小為M。算法描述如下：

1. 初始時将輸入檔案讀入記憶體，建立最小堆。
2. 将堆頂元素輸出至輸出緩沖區。然後讀入下一個記錄：

1. 若該元素的關鍵碼值不小于剛輸出的關鍵碼值，将其作為堆頂元素并調整堆，使之滿足堆的性質；
2. 否則将新元素放入堆底位置，将堆的大小減1。

1. 重複第2步，直至堆大小變為0。
2. 此時一個順串已經産生。将堆中的所有元素建堆，開始生成下一個順串。[​​3]​​

此方法能生成平均長度為2M的順串，可以進一步減少通路外部存儲器的次數，節約時間，提高算法效率。

相關對象

• 待排檔案FI

• 可以是無序的

• 初始歸并段輸出檔案FO

• 初始為0
• 輸出區中的元素是有序的

• 記憶體工作區WA

• 可以容納w個記錄(初始為空)
• 當RSS算法處理完所有w中的記錄,得到所有歸并段,算法将結束

步驟

1. FI輸入w個元素到WA
2. 計算WA中最小元素M=Min(WA)

1. 這個問題模型符合敗者樹模型,利用敗者樹來計算更好

1. 輸出M到FO
2. 判斷FI是為空,否則在輸入一個元素到WA(補償)
3. 再次計算M’=min(greaterThan(M)),如果存在M’,那麼M=M’

• 其中,greaterThan(M)表示WA中大于M的元素(有可能找不到這樣的元素)
• 隻有這樣,才能夠確定FO中的暫存的歸并段序列是有序!🎈

1. 重複3~5步驟,直到找不到M’可以移到FO中,那麼輸出一個結束标記(比如​

   ​#​

   ​),表示歸并段結束

• 至此産生一個歸并段檔案
• 而後就是下一個歸并段的計算

1. 重複2~6,直到WA為空

• 斷言,所有初始歸并段被處理完畢

算法特點

• 從上面的算法可以了解到,RSS算法得到的長度是不保證等長度的
• 為了組織不等長度的歸并段的歸并(順序),引入歸并樹和完美歸并樹概念

歸并樹

歸并樹的各個葉結點表示歸并段

• 葉權值表示歸并段長度
• 葉結點到根的路徑長度表示其參與的歸并趟數
• 分支結點表示每次歸并産生的新歸并段
• 樹的帶權路徑長WPL(Tree)為歸并過程中的讀取的總記錄數

• WPL(Tree):樹中所有葉子結點的帶權路徑長度之和
• 記為WPL(Weighted Path Length ((of Tree))

• IO次數為2WPL(讀的次數和寫的次數一緻)

最佳歸并樹

• 檔案經過​

  ​置換-選擇排序​

  ​後,得到的是長度不等的初始歸并段
• 為了使得IO次數最少,引入​

  ​最佳歸并樹​

  ​來指導進行組織長度不等的初始歸并段的歸并順序

ref (huffmanTree)

執行個體

• 給定序列2,3,6,9,12,17,18,24,30

• 以它們為葉子結點建構的最優3叉樹如下(同一結點的子樹交換位置不影響最優性)
• 但總是具有最短路徑長度:

• IO總次數為次

添加虛段

• 并不是任意結點數都是可以構成嚴格m叉樹

• 例如,隻給你2個葉子結點,讓你建構樣3叉樹是做不到的
• 但是可以通過添加虛段,将葉子結點數補充到滿足建構嚴格m叉樹的條件而且不丢失資訊

• 如果給定的葉子結點(歸并段)不足以構成一棵嚴格m叉樹,那麼需要進行​

  ​虛段補充​

  ​
• 使得虛段數量剛好可以構成一棵嚴格k叉樹,也就便于計算​

  ​最優歸并樹​

  ​
• 不同于最優二叉樹,任意給定超過2個的葉子結點總是可以通過huffman建立最優二叉樹的方法建立嚴格2叉樹
• 如果想要建構最優m叉樹,需要在確定給定的葉子結點數量滿足一定規律(嚴格m叉樹)

• 假設給定的帶權葉子結點是有n個,且不能夠剛好以它們構成一棵嚴格m叉樹
• 那麼由于我們是從葉子結點開始向根結點的方向建構m叉樹,在最後,靠近根結點的時候,根結點度數不滿m

• 假設此時的WPL記為S1

• 而我們知道,根結點的孩子結點是存放帶權結點的好地方,因為路徑長度短(僅有1)
• 我們總是能夠通過從其他地方遷移過來一個帶權結點,使得新計算的WPL<S1

• 而且如果遷移過來的結點越大,wpL越小
• 可以通過驗證執行個體來說明這一點:

• 将上面的例子中的序列中的權為30的結點删除計算S1
• 在向序列中補充一個0(虛段),重新結算WPL,和比較S1比價之

• 從上面的分析來看,為了從給定的序列建構出最優m叉樹,我們可以先補充合适數量的0權結點(虛段)
• 使得這個補充過虛段的序列建構出來的嚴格m叉樹是具有最短路徑長度的最優m叉樹

樹的基本性質:葉結點和分支結點

• 對于一般的樹,滿足基本規律:

• 設結點數為n

• 總結點數

• 邊數為e:

嚴格k叉樹:葉子結點和根結點數目關系

• 即:
• 或:

補充多少個虛段構成嚴格k叉樹?

• 顯然,如果商恰好為整數的時候,個歸并段(葉結點)恰好可以構成嚴格k叉樹
• 否則,需要通過補償個結點,使得能夠整除

• 或者說
• 記餘數

• 是以: