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

Question

一些信息

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

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

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

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

其中 sup 是反链的 supremum，表示比给定集合大的最小反链。

到目前为止的表现

基本集用long、bitarray-alike表示。这意味着集合中的每个元素都由位数组中的 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-representations 的大小都会加倍。我还想到了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
}

Answer 1

好吧，我可以想到一种更好的方式来存储你的反链（仍在 BitSets 中）。目前，您的集合非常稀疏 -- 高 0:1 比率。

我只是将它们连接起来。每个都保证小于 64 位长，因为您用 long 值表示它们，所以我会做这样的事情

public static void put(BitSet antiChain, long value) {
    int len = antiChain.length();
    antiChain.clear(antiChain.size() - 1);
    len -= len % 64;
    for (int i = 0; i < 64; i++)
        if ((value & (1 << i)) != 0) antiChain.set(len + i);
    antiChain.set(antiChain.size());
}
public static long get(BitSet antiChain, int index) {
    long value = 0;
    for (int i = 0; i < 64; i++)
        if (antiChain.get(index * 6 + i)) value |= (1 << i);
    return value;
}
public static boolean contains(BitSet antiChain, long value) {
    for (int i = 0; i < antiChain.size() / 64; i++) {
        if (get(antiChain, i) == value) return true;
    }
    return false;
}

不管怎样都在末尾包含一个集合位，以确保包含的集合数是明确的；即 {} != {{}}

举个具体的例子，{{1},{2,3}} 会发生什么。（注意 s(n) 指的是 n 指的集合。

{{1},{2,3},{4,5}} = {s(0b10), s(0b110), s(0b110000)} = {s(2), s(6), s(48)}
put 函数会将其编码为 2*2^(64*0) + 6 * 2^(64*1) + 48*2^(64*2)（其中 ^ 表示求幂，而不是 XOR）。
代表这个的BitSet是{1, 33, 64, 65, 66, 97, 98, 128, 132, 133, 164, 165, 256}

此外，无论将 BitSet 转换为 BigInteger 的效率如何，compare 仍将在 O(L) 时间内发生，其中 L是你的反链的长度。你可能过得更好

如果每个反链进行多次比较：只需调用 toLongArray() 并手动比较 long 值
如果每个反链比较一次：手动从高位循环到低位并检查。

Answer 2

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 等）。

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

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

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

Represent antichains with efficient join and meet operations

java

math

optimization

performance

data-structures

一些信息

到目前为止的表现

我的问题

编辑：