從整數到整數的高效稀疏映射

我正在實現一個使用有限自動機的專門構建的正則表達式引擎。我將不得不存儲數千個狀態，每個狀態都有自己的從unicode代碼點（或UTF-16代碼單元;我還沒有決定）的轉換表到狀態ID。從整數到整數的高效稀疏映射

在很多情況下，表格將非常稀疏，但在其他情況下，表格會基本滿。在大多數情況下，大多數條目將落入具有相同值的幾個連續範圍。

最簡單的實現將是一個查找表，但每個這樣的表將佔用大量的空間。（範圍，值）對的列表將會小得多，但速度會更慢。二叉搜索樹會比列表快。

有沒有更好的方法，可能是利用內置功能？

2017-05-02 Thom Smith

由於（現代）的JavaScript數組本身_sparse_，應該不是內存問題http://stackoverflow.com/questions/4524067/if-i-set-only-a-high-index-in-an-陣列 - 做它浪費內存;許多數組元素也可以引用相同的對象，這會在遇到範圍時爲您節省大量空間。 –

@StephenP雖然問題是關於映射到整數。你必須包裝整數才能引用它們（因爲它們是原始類型），所以引用實際上會更慢。 –

拍完@Aurel –

不幸的是，JavaScript的內置數據類型 - 尤其是Map - 對完成此任務並不是很有幫助，因爲它們缺少相關方法。

在大多數情況下，大多數條目將落入多個連續的範圍內，具有相同的值。

但是，我們可以利用這個並在排序數組上使用二分搜索策略，假設轉換表不會經常修改。

通過將每個輸入範圍的最低值存儲在排序數組中，對連續輸入範圍進行編碼，從而導致相同的狀態。保持狀態在一個單獨的數組對應的指標：

let inputs = [0, 5, 10]; // Input ranges [0,4], [5,9], [10,∞) 
let states = [0, 1, 0 ]; // Inputs [0,4] lead to state 0, [5,9] to 1, [10,∞) to 0

現在，給定一個輸入，則需要進行輸入陣列類似的二進制搜索到Java's floorEntry(k)：

// Returns the index of the greatest element less than or equal to 
 
// the given element, or undefined if there is no such element: 
 
function floorIndex(sorted, element) { 
 
    let low = 0; 
 
    let high = sorted.length - 1; 
 
    while (low <= high) { 
 
    let mid = low + high >> 1; 
 
    if (sorted[mid] > element) { 
 
     high = mid - 1; 
 
    } else if (sorted[mid] < element) { 
 
     low = mid + 1; 
 
    } else { 
 
     return mid 
 
    } 
 
    } 
 
    return low - 1; 
 
} 
 

 
// Example: Transition to 1 for emoticons in range 1F600 - 1F64F: 
 
let transitions = { 
 
    inputs: [0x00000, 0x1F600, 0x1F650], 
 
    states: [0,  1,  0  ] 
 
}; 
 
let input = 0x1F60B; // 
 
let next = transitions.states[floorIndex(transitions.inputs, input)]; 
 

 
console.log(`transition to ${next}`);

此搜索在O（log n）步驟中完成，其中n是連續輸入範圍的數目。單個狀態的轉換表則具有O（n）的空間要求。只要我們的初始假設 - 導致相同狀態的連續輸入範圍的數量很小，這種方法對於稀疏和密集轉換表格同樣適用。

來源

2017-05-02 22:12:42

聽起來像你有兩個非常不同的情況（「在很多情況下，表格將非常稀疏，但在其他情況下，它會幾乎滿）」。

對於稀疏情況，您可能會有一個單獨的稀疏索引（或幾層索引），那麼您的實際數據可以存儲在一個類型數組中。因爲索引將從整數映射到整數，所以它們也可以表示爲類型化數組。

仰望的值應該是這樣的：

二進制搜索索引。索引將對存儲爲類型數組中的連續條目 - 第一個元素是搜索值，第二個元素是數據集（或下一個索引）中的位置。
如果您有多個索引，請根據需要重複1。
開始在最後一個索引給定的位置迭代數據集。由於索引是稀疏的，因此該位置可能不是存儲該值的位置，但這是一個很好的起點，因爲正確的值保證在附近。
數據集本身表示爲一個類型數組，其中連續的對保存鍵和值。

我想不出任何更好用的JavaScript。類型化數組非常快，並且索引應該可以大大提高速度。話雖如此，如果你只有幾千個條目，不要打擾索引，直接在類型化數組上進行二進制搜索（如上面4所述）。

對於密集的情況，我不確定。如果密集情況恰好是密鑰範圍內可能出現重複值的情況，請考慮使用類似於run-length encoding的東西 - 相同的連續值僅表示爲出現次數，然後是實際值。再次使用類型化數組和二進制搜索，甚至可能使索引更快。

來源

2017-05-02 18:49:47

從整數到整數的高效稀疏映射

回答

相關問題