java - 如何仅在 Java 中将相同长度的 BitSet 设置为 true 的索引处对 int[] 进行排序

Question

虽然在 Java 中对连续子数组进行排序没有问题，但我还没有找到任何关于如何仅在由另一个数据结构指定的某些(非连续)索引处对数组进行排序的信息，例如。一个 BitSet。

具体来说，给定一个数组，例如

int[] x = {5,1,8,6,7,0,2,3,9,4};

和一个指定要排序的位置的 BitSet

BitSet pos = new BitSet(10);
pos.set(0);
pos.set(2);
pos.set(5);
pos.set(6);
pos.set(9); // i.e. pos = {1,0,1,0,0,1,1,0,0,1}

我想仅在掩码 pos 为 1 的位置对 x 进行内联排序，同时忽略其余索引，即

SortOnIndices(x,pos);

应该导致

x = {0,1,2,6,7,4,5,3,9,8}

是否有无需实现自定义排序解决方案即可有效归档的方法？这可以用 JAVA 8 流来完成吗？

编辑:更正了示例中 BitSet 的使用。

Answer 1

首先，BitSet.valueOf(long[]) 无法按照您尝试使用的方式工作。 long[] 数组的每个元素代表 64 位而不是一个位。事实上，将您的 1,0,1,0,0,1,1,0,0,1 表示转换为 BitSet 是第一个挑战:

BitSet pos = BitSet.valueOf(new long[] { Integer.reverse(0b1010011001)>>>22 });

然后，我们遇到了一个问题，即 Java API 的每个可自定义排序实现都与对象一起工作，这将需要装箱并将源表示为数组或 List。为原始类型提供的方法都固定为自然顺序。

尝试创建一个 List 位置或类似的，动态映射到源数组的，在找到由位集引起的正确数组位置时，会受到非随机访问的影响。但是 List.sort 的 default 实现通过将列表内容复制到数组中来规避这一点。这甚至适用于使操作看起来流畅但在幕后创建中间数组的所有 Stream 方法(并且还支持仅用于装箱值的自定义 Comparator)。

所以当你想避免额外的内存分配时，任何内置的排序工具都无济于事。最简单、高效和节省内存的方法是

BitSet ordered = new BitSet();
pos.stream().forEach(ix -> ordered.set(x[ix]));
PrimitiveIterator.OfInt it = ordered.stream().iterator();
pos.stream().forEachOrdered(ix -> x[ix]=it.next());
assert !it.hasNext();

但这仅在源数组不包含负数或重复项的情况下才有效，例如在您的示例数据集中。

解除这些限制需要更多的努力和更多的内存:

IntSummaryStatistics stats = pos.stream().map(ix -> x[ix]).summaryStatistics();
int min = stats.getMin(), max = stats.getMax();
int[] counts = new int[max-min+1];
pos.stream().forEach(ix -> counts[x[ix]-min]++);
PrimitiveIterator.OfInt it
  = IntStream.rangeClosed(min, max)
             .flatMap(val -> IntStream.range(0, counts[val-min]).map(ix -> val))
             .iterator();
pos.stream().forEachOrdered(ix -> x[ix]=it.next());
assert !it.hasNext();

这种计数排序的变体仍然是 O(n)，但它的内存消耗取决于要排序的数字集中最小和最大数字之间的差值。但这是你能得到的最好的，除非你想实现你自己的快速排序或类似的。或者，如果最小值和最大值之间的差异太大，您可以求助于让 JRE 提供的算法对副本进行排序:

int[] tmp = pos.stream().map(p -> x[p]).toArray();
Arrays.sort(tmp);
PrimitiveIterator.OfInt it = Arrays.stream(tmp).iterator();
pos.stream().forEachOrdered(ix -> x[ix]=it.next());
assert !it.hasNext();

您甚至可以使用第二个变体的统计信息来使用需要较少内存的变体

PrimitiveIterator.OfInt it;
IntSummaryStatistics stats = pos.stream().map(ix -> x[ix]).summaryStatistics();
int min = stats.getMin(), max = stats.getMax();
if(max-min < stats.getCount()) {
    int[] counts = new int[max-min+1];
    pos.stream().forEach(ix -> counts[x[ix]-min]++);
    it = IntStream.rangeClosed(min, max)
                  .flatMap(val -> IntStream.range(0, counts[val-min]).map(ix -> val))
                  .iterator();
}
else {
    int[] tmp = pos.stream().map(p -> x[p]).toArray();
    Arrays.sort(tmp);
    it = Arrays.stream(tmp).iterator();
}
pos.stream().forEachOrdered(ix -> x[ix]=it.next());
assert !it.hasNext();