algorithm - (不相交)集合的数据结构

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

给每个集合添加一个给定的整数。

删除每个包含(或不包含)给定整数的集合，或者至少将关联的double设置为0。

合并两个 map ，将同时出现在两个 map 中的集合的 double 加在一起。

将所有 double 数乘以给定的 double 数。

很少会遍历整个 map 。

在以下条件下:

整数将落在一个受限制的范围内(介于1到10,000之间)。确切的范围将在编译时知道。

永远不会使用(80-90％)范围内的大多数整数，但是直到计算结束，才容易确定哪些整数。

使用的整数数量几乎总是仍然超过100。

许多集合将非常相似，仅相差几个元素。

可以识别某些仅按顺序出现的整数整数组:例如，如果一个集合包含整数27和29，那么它(几乎吗？)当然也包含28。

可以在运行计算之前识别这些组。

这些组通常将包含100个左右的整数。

我已经考虑过尝试，但是我看不到处理“删除包含给定整数的每个集合”操作的好方法。

该数据结构的目的是表示离散的随机变量，并允许对其进行加法，乘法和标量乘法运算。通过将这些操作应用于固定的(在编译时)一组独立的Bernoulli随机变量(即，每个概率为1或0的值)，最终将创建这些离散变量中的每一个。

被建模的系统几乎可以表示为时间不均匀的马尔可夫链(这当然会极大地简化这一过程)，但是不幸的是，跟踪各种过渡以来的持续时间是必不可少的。

最佳答案

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

对于此说明，我将其称为 BitmapArray 。

考虑一下，显然对于您已经描述的操作来说，是一个排序的数组，将位图作为键，将权重(您的 double )作为值将是非常有效的。

位图是保持集合中成员身份的对象。由于您说的是集合中整数的范围在1-10,000之间，因此我们可以维护有关长度为10,000的位图的任何集合的信息。

排序键可能高达2 ^ 10000的数组会很困难，但是您可以通过以下方式聪明地实现比较功能:

在两个位图上从左到右迭代

对每个索引

的位进行XOR

假设您在第ith个位置获得1

在第i个位置上有1的位图都更大

如果您从未获得1，则等于

我知道这仍然是一个比较慢的比较。
但不是太慢，Here是我对长度为10000的位图所做的基准测试。
这是用Java语言编写的，如果您要用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可以，那么效率会更高。如果要删除给定集合中具有任何元素的所有集合，这也非常容易。

两个 map 的联合:最坏情况O(N1 + N2)时间。就像合并两个排序的数组一样，只是您必须再次对比较有所了解。

将所有 double 数乘以给定的 double :最差/最佳情况O(N)时间。迭代每个值并将其乘以输入double。

遍历BitmapArray :下一个元素的最坏/最佳情况O(1)时间。