兩套之間的匹配數字

我有兩個數字鍵的大數據集（每個數以百萬計的條目），需要建立一個數據結構，我可以快速識別兩組之間的關鍵匹配，從而允許一些固定的變化。例如，如果在一組中有356個值，我想在其他組中找到任何355,356或357的實例。我最初的想法是設置兩個HashMap，用最少的鍵遍歷一個，然後查詢範圍較大的那個（查詢較大地圖中的355,356或357）。兩套之間的匹配數字

是否有一個特定的數據結構/數值匹配算法，我應該看看？

來源

2014-05-14 Anthony Wong

排序後的數組。 –

所以你想要一對一的匹配？ –

這是作業嗎，還是可以使用已經爲你做過的圖書館？ – shoover

我建議你從Java Set開始。你正在尋找的「兩組之間的匹配」聽起來很像一組交集。

請參閱API for set operations in Java?並查看retainAll的說明。

來源

2014-05-14 20:48:31 rajah9

謝謝拉惹。我對集合有點熟悉，但我主要關心的不僅僅是交集，而是與變化的匹配。所以在我上面的例子中，關鍵是我不僅知道另一組中是否存在356，而且還存在355或357。 –

也許java BitSet在這種情況下可能會有用。下面是一個使用規模的BitSet = 1000000，範圍= 5，從第一組辦圍繞每個值檢查進入第二代碼示例：

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class CheckRange 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     int range = 5; 
     int maxSize = 1000000; 

     // Prepare the main BitSet (bs) 
     BitSet bs = new BitSet(maxSize); 
     bs.set(357); 
     bs.set(599001); 
     bs.set(123456); 
     // ... 

     // Prepare the BitSet to check in 
     BitSet bs2 = new BitSet(maxSize); 
     bs2.set(5688); 
     bs2.set(566685); 
     bs2.set(988562); 
     // ... 

     for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { 
      // Compute the ranges, checking the boundaries 
      int minIndex = Math.max(i - range, 0); 
      int maxIndex = Math.min(i + range, maxSize); 

      // Extract the matching subset 
      BitSet subset = bs2.get(minIndex, maxIndex); 

      // Print the number of bits set 
      System.out.println("Number of bit set int bs2 from bs at index " + i + " is " + subset.cardinality()); 
     } 
    } 
}

來源

2014-05-14 20:53:40 slaadvak

+1：如果鍵基本上是連續的，這將工作得很好。 – Nuclearman

我會試着總結一下一點點。

選項一 - 排序數組。通過二分法搜索，您將能夠找到具有O(log N)複雜度的精確值（這裏和下面的N是結構中的一些元素）。所以，爲您的操作 - log n (search in the first set) + log n (search in the second) + constant (check what you called variation)，這是2 * log N + constant這是O(log N)。如果收藏中的數據發生變化，您必須花費O(log N)，使用類似的二進制搜索將其插入適當的位置。

選項二 - 使用Java Set。 O(log N)爲.contains()致電+您必須致電.contains()爲變異的每個元素，所以我們有O(|V| * log N)，其中|V|是變異大小。您還可以添加O(log N)的元素。

決定：我會選擇java集，因爲有很多發燒代碼要寫，而且您不需要調試搜索/添加元素的代碼。

來源

2014-05-14 21:19:10

兩套之間的匹配數字

回答

相關問題