檢視朱迪矩陣的原始碼

'''朱迪矩陣'''（'''Judy array'''）是一个電腦科學佮軟體工程學中的名詞，是一種高效能、低記持體消磨的資料結構，實現關聯陣列的功能。佮普通陣列無仝，Judy array 會當是疏櫳，這點閣親像雜鬥表示，毋是陣列。Judy array 會當用規形或者是字串作做鍵值來儲存、查詢資料，伊上大的優勢是會當動態自動擴充，高效能，節省記憶體並且使用。

因為 Judy array 佇咧操作速度佮記持的使用攏非常的高效，同時並無需要特殊組態抑是初化，予伊會當用來替換掉加種捷見資料結構，譬如講一跳動列表，連結串列，二箍樹，B 樹，雜鬥表，而且 judy array 佇咧海量的資料集頂頭的表現比遐的資料結構閣較好。

粗略咧講，Judy array 像講是一个懸度最佳化的兩百五十六叉樹，為著省記憶體，伊使用超過二十種無仝的壓縮技術來壓縮樹節點。.

Judy array 是 Douglas Baskins 發明的，伊用家己小妹的號名矣這種資料結構。

==術語==

容量、用量、密度這三个概念叫做傳統樹形結構足少使用，猶毋過佇 Judy array 中央使用的。
這个的概念的定義如下：

一 . _ 容量 _ 會當理解為 Judy Array 佇無擴充記持體使用的情形下所會用維護的資料量，嘛會當是某一个點，視頂下文。
二 . _ 用量 _ 已經儲存的資料量，既然會當描寫這个規个 Judy Array 的資料量，嘛會當是某一个點落的。
三 . _ 密度 _ 用來描述資料儲存的密集程度，密度=用量 / 容量

==優勢==

===記持體分配===

Judy array 是無容量限制的，所以嘛毋免事先分配好儲存空間，伊會當根據用量動態決定生長抑是收縮記憶體使用，來支撐海量的資料儲存。其儲存能力干焦受著電腦記憶體容量的限制。Judy array 的記持體用量佮儉存的資料用量基本呈線性關係。

===速度===

Judy array 佇設計上就力共保持閣較懸的 CPU 緊取命中率，欲達成這个目標，其內部演算法十分複雜。因為有這个針對性的最佳化，予得 Judy array 佇執行速度頂懸十分高效，有時甚至超過雜鬥表，尤其是佇咧處理大數據集的時陣。因為 Judy array 是寄託樹仔 ( 資料結構 ) 形結構設計的，其記憶體消磨比雜鬥陣細足濟，仝款是拜樹形結構所賜，予伊會當完成鍵值的順序遍歷，這點咧雜鬥表中是無可能的。

==演算法==

對 Judy array 的發明者所編寫的簡介佮其他一寡相關的中文論文中看，設計中使用濟款的壓縮思想佮壓縮演算法，根據無仝款的密度狀況，選擇無仝款的壓縮方式，依期儘可能省記持體，降低實際儲存內底的疏櫳情形，我咧臆，這會當佇咧緊取命中率上帶來袂少提升，進一步提升效率。

看著的演算法思路包括：

* 密度足懸的，這空洞真少的節點，使用點陣圖（bitmap）來儉。
* 對密度真低的狀況，只儲存出現的這个鍵值
* 對密度真低的狀況，使用類似字典樹的結構，跨層壓縮資料。

==參考文獻==

==外部連結==

* Main Judy arrays site
* How Judy arrays work and why they are so fast
* A complete technical description of Judy arrays
* An independent performance comparison of Judy to Hash Tables
* A compact implementation of Judy arrays in 一 K lines of C code

[[分類: 待校正]]