java - 用高效的加入和满足操作来代表反链

Question

一些信息

我正在开发一个适用于基本集合和反链的程序。

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

反链A和B上的一些最重要的操作可以定义为

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

其中 sup 是 supremum反链的，意味着比给定集合大的最小反链。

到目前为止的表现

基本集由 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 ，因此未针对使用位数组进行优化。

我的问题

1. 我现在的问题是 BitSet 是否是最佳表示，因为每次向起始集中添加一个元素时，这些位数组表示的大小都会加倍。我也想到了BigInteger例如，具有可比较的优势(我也需要)。
2. 我还想知道是否有人已经做了一些可能的事情并且知道如何使用 bitarray-properties 有效地实现连接和 session 。

提前致谢。

---

编辑:

目前，我的加入和聚会代码如下所示:

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

Now I wanted to lift this representation to represent the antichains in a similar way. This means I could represent the antichain {{1},{2,3}} as 1000010 in a bitarray, because the long storing the set {1} is 1 and for {2,3} it is 6 (the indices of the 1's in the bitarray).

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

3. In order to be able to compare my bitarrays, are there any more efficient ways to convert a BitSet to a BigInteger?

最有效的方法肯定是避免转换。 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) .