通过有效的连接和满足操作来代表反链

Question

一些信息

我正在研究一个适用于基本集和反链的程序.

Antichains是集合的powerset的子集,因此该子集中没有两个元素(集合)是该子集中的另一个元素(集合)的子集.例如,{{1},{1,2}}不是一个反链,因为{1}⊆{1,2}.

关于抗原A和B的一些最重要的操作可以定义为

1. a.join(b)= sup(a∪b)
2. a.meet(b)= sup({X∩Y|X∈a和Y∈b})

sup是antihain的上限,意味着最小的antichain比给定的set更大.

到目前为止的代表

基本集由a long,bitarray-like组成.这意味着该组的每个元素在比特阵列中由1表示.例如,集合{1,2,3}由7(比特阵列111)表示,集合{1,2,4}由11(比特阵列1011)表示,依此类推.

现在我想提升这种表示以类似的方式表示反链.这意味着我可以在一个bitarray中将antichain {{1},{2,3}}表示为1000010,因为存储集合{1}的长整数是1而对于{2,3}它是6(指数是比特币中的1.
除非我找到更好的替代方案,否则我使用BitSet -class来处理这个bitarray,希望节省一些时间来处理任何问题Collection<T>.

我已经设法定义和优化之前陈述的大多数基本操作,但它们在较旧的实现中进行了优化,只需使用a TreeSet,因此未针对使用bitarray进行优化.

我的问题

1. 我现在的问题是BitSet是否是最佳表示,知道每次添加到起始集的元素时这些比特表示的大小加倍.我也想过,BigInteger例如,具有可比性的优势(我也需要).
2. 此外,我想知道是否有人已经做了一些可能的事情,并且知道如何使用bitarray属性实现连接并有效地满足.

提前致谢.

---

编辑:

我的加入和见面的代码目前看起来像这样:

public AntiChain join(AntiChain ac) {
    AntiChain res = new AntiChain(this);
    for(int i = ac.bitset.nextSetBit(0); i >= 0; i = ac.bitset.nextSetBit(i+1)) {
        res.addAndMakeAntiChain(new BasicSet(i));
    }
    return res;
}

public AntiChain meet(AntiChain ac) {
        AntiChain res = AntiChain.emptyAntiChain(this.getUniverse());
        for(int i = bitset.nextSetBit(0); i >= 0; i = bitset.nextSetBit(i+1))
            for(int j = ac.bitset.nextSetBit(0); j >= 0; j = ac.bitset.nextSetBit(j+1)) 
                res.addAndMakeAntiChain(new BasicSet(j).intersection(new BasicSet(i)));
        return res;
    }

private void addAndMakeAntiChain(BasicSet x) {
    for(int k = bitset.nextSetBit(0); k >= 0; k = bitset.nextSetBit(k+1)) {
        BasicSet a = new BasicSet(k);                         //new BasicSet(7) = {1,2,3}
        if(a.hasAsSubset(x)) return;
        if(x.hasAsSubset(a)) bitset.set(k, false);
    }
    bitset.set(x.toIntRepresentation());                      //{1,2,3}.toLong() = 7
}

Answer 1

现在我想提升这个表示以类似的方式表示反链。这意味着我可以将反链 {{1},{2,3}} 在位数组中表示为 1000010，因为集合 {1} 的长存储为 1，而 {2,3} 的长存储为 6（位数组中为 1）。

这听起来是错误的：那又如何呢{{1, 64}}？IIUYC 索引是 2**63 + 1，对于BitSet. 如果您想要对此进行优化表示，请考虑一些原始的长集合（trove4j、colt、hppc，...）。

3. 为了能够比较我的位数组，是否有更有效的方法将 BitSet 转换为 BigInteger？

最有效的方法肯定是避免转换。ABitSet可以迭代（双向），因此可以直接进行字典顺序比较。

BigInteger result = BigInteger.ZERO;
for(int i = theAntiChain.nextSetBit(0); i >= 0; i = theAntiChain.nextSetBit(i+1))
    result = result.setBit(i);
return result;

这是非常低效的，您可以创建一个byte[]，填充它，然后使用new BigInteger(int signum, byte[] magnitude).