两套之间的匹配数字

我有两个数字键的大数据集（每个数以百万计的条目），需要建立一个数据结构，我可以快速识别两组之间的关键匹配，从而允许一些固定的变化。例如，如果在一组中有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

两套之间的匹配数字

回答

相关问题