一组(非不相交)集的数据结构

Question

我正在寻找一个大致对应的数据结构(用Java术语)Map<Set<int>, double>.基本上是一组标记的大理石,其中每组大理石与标量相关联.我希望它能够有效地处理以下操作:

• 为每个集添加一个给定的整数.
• 删除包含(或不包含)给定整数的每个集合,或者至少将关联的double设置为0.
• 联合两个地图,将两个中出现的集合的双打加在一起.
• 将所有双打乘以给定的双精度数.
• 很少,迭代整个地图.

在以下条件下:

• 整数将在一个约束范围内(1到10,000左右); 确切的范围将在编译时知道.
• 范围内的大多数整数(80-90%)将永远不会被使用,但是在计算结束之前哪些整数将不容易确定.
  • 使用的整数数量几乎总是超过100.
• 许多集合将非常相似,只有少数几个元素不同.
• 有可能识别经常仅按顺序出现的某些整数组:例如,如果一个集合包含整数27和29,那么它(几乎？)当然也包含28.
  • 可以在运行计算之前识别这些组.
  • 这些组通常有100个左右的整数.

我已经考虑过尝试,但是我没有看到处理"删除包含给定整数的每个集合"操作的好方法.

此数据结构的目的是表示离散随机变量,并允许对它们进行加法,乘法和标量乘法运算.这些离散随机变量中的每一个最终都是通过将这些操作应用于固定的(在编译时)一组独立的伯努利随机变量(即每个以一定概率取值1或0)来创建的.

被建模的系统接近于可表示为时间不均匀的马尔可夫链(当然这将极大地简化)但不幸的是,跟踪各种转换以来的持续时间是必要的.

Answer 1

这是一个数据结构，可以非常有效地完成所有操作：

为了进行解释，我将把它称为 BitmapArray 。

考虑一下，显然对于您描述的以位图作为键、以权重（双精度）作为值的排序数组的操作来说，将非常有效。

位图用于维护集合中的成员资格。既然你说集合中的整数范围在 1-10,000 之间，我们就可以用长度为 10,000 的位图来维护任何集合的信息。

对键可能大到 2^10000 的数组进行排序会很困难，但您可以通过以下方式聪明地实现比较函数：

• 在两个位图上从左到右迭代
• 对每个索引上的位进行异或
• 假设你在第 i 个位置得到 1
• 哪个位图第 i 个位置为 1 较大
• 如果你从未得到 1，那么它们是相等的

我知道这仍然是一个缓慢的比较。但不要太慢，这是我在长度为 10000 的位图上做的基准小提琴。这是用 Javascript 编写的，如果你要用 Java 编写，它会表现得更好。

    function runTest() {
    var num = document.getElementById("txtValue").value;
    num = isNaN(num * 1) ? 0 : num * 1;

    /*For integers in the range 1-10,000 the worst case for comparison are any equal integers which will cause the comparision to iterate over the whole BitArray*/
    bitmap1 = convertToBitmap(10000, num);
    bitmap2 = convertToBitmap(10000, num);

    before = new Date().getMilliseconds();
    var result = firstIsGreater(bitmap1, bitmap2, 10000);
    after = new Date().getMilliseconds();
    alert(result + " in time: " + (after-before) + " ms");

}


function convertToBitmap(size, number) {
    var bits = new Array();
    var q = number;
    do {
        bits.push(q % 2);
        q = Math.floor(q / 2);
    } while (q > 0);


    xbitArray = new Array();
    for (var i = 0; i < size; i++) {
        xbitArray.push(0);
    }

    var j = xbitArray.length - 1;
    for (var i = bits.length - 1; i >= 0; i--) {
        xbitArray[j] = bits[i];
        j--
    }
    return xbitArray;
}

function firstIsGreater(bitArray1, bitArray2, lengthOfArrays) {
    for (var i = 0; i < lengthOfArrays; i++) {
        if (bitArray1[i] ^ bitArray2[i]) {
            if (bitArray1[i]) return true;
            else return false;
        }
    }
    return false;
}

document.getElementById("btnTest").onclick = function (e) {
    runTest();
};

另外，请记住，在构建 BitmapArray（或在取并集时）时，您只需执行一次此操作，然后对于您最常执行的操作来说，它将变得非常高效：

注意：N 是 BitmapArray 的长度。

将整数添加到每个集合：最坏/最好情况 O(N) 时间。将每个位图中的 0 翻转为 1。

删除包含给定整数的每个集合：最坏情况 O(N) 时间。

• 对于每个位图，检查表示给定整数的位，如果 1 则标记其索引。
• 通过删除所有标记的索引来压缩数组。

如果您同意将权重设置为 0，那么效率会更高。如果您想删除给定集合中包含任何元素的所有集合，这也变得非常容易。

两个映射的并集：最坏情况 O(N1+N2) 时间。就像合并两个已排序的数组一样，只不过您必须再次聪明地进行比较。

将所有双精度数乘以给定的双精度数：最坏/最好情况 O(N) 时间。迭代每个值并将其乘以输入双精度值。

迭代 BitmapArray：下一个元素的最坏/最好情况 O(1) 时间。