java - 通过有效的加入和见面操作来代表反链

一些信息
我正在开发一个适用于基本设置和反链的程序。
Antichains是一个集合的幂集的子集，因此该子集中的任何两个元素(集)都不是该子集中的另一个元素(集)的子集。例如{{1}，{1,2}}不是反链，因为{1}⊆{1,2}。
在反链A和B上一些最重要的操作可以定义为

a.join(b)= sup(a∪b)

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

其中sup是反链的supremum，表示大于给定集合的最小反链。
到目前为止的代表性
基本集合由类似于bitarray的long表示。这意味着该位集合中的每个元素在位数组中均由1表示。例如，集合{1,2,3}由7(位阵列111)表示，集合{1,2,4}由11(位阵列1011)表示，依此类推。
现在，我想提升这种表示方式，以类似的方式表示反链。这意味着我可以在位数组中将反链{{1}，{2,3}}表示为1000010，因为存储集{1}的长值是1，而对于{2,3}来说，长值是6(位数组中为1)。
除非找到更好的替代方法，否则我将使用BitSet -class来处理此位数组，以期节省使用任何Collection<T>的时间。
我已经设法定义和优化了前面提到的大多数基本操作，但是在较旧的实现中，仅使用了TreeSet对它们进行了优化，因此并未针对使用位数组进行优化。
我的问题

现在，我的问题是BitSet是否是最佳表示形式，因为每当向起始集合中添加元素时，这些bitarray-presentations的大小就会加倍。例如，我还想到了BigInteger，它具有可比的优势(我也需要)。

我也想知道是否有人已经做过一些事情，并且知道如何使用bitarray-properties实现联接并有效地开会。

提前致谢。

编辑:
目前，我加入和见面的代码如下所示:

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
}

最佳答案

这听起来是错误的:{{1, 64}}呢？ IIUYC索引是2 ** 63 +1，对于BitSet来说太大了。如果您要对此进行优化表示，请考虑一些原始的长集合(trove4j，colt，hppc等)。



最有效的方法肯定是避免转换。可以对BitSet进行迭代(双向)，因此您可以直接进行字典比较。

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)。

关于java - 通过有效的加入和见面操作来代表反链，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28743659/