Eclipse Collections 通过自定义 comparator-like 函数对 IntList 进行排序而不装箱

Eclipse Collections sorting an IntList by a custom comparator-like function without boxing

我正在尝试对一些 (Mutable)IntList objects 进行排序。boxing/unboxing 整数的成本与我的程序相关(这正是我使用原始 collections)。我想按以下标准排序:

[1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]

Eclipse Collections 库中的 IntList class 是否有允许自定义比较器的排序方法?到目前为止我还没有找到它,但是定义符号的列表很大,搜索框只匹配精确的字符串并且文档几乎不存在(我相信大部分是从方法签名自动生成的)。

我最后的办法是编写自己的 int-int 比较器和排序函数,这没什么大不了的,但我宁愿不这样做。

请不要浪费时间编写概念验证排序器,我将不胜感激。我知道如何对列表进行排序,只是不知道如何在 Eclipse 中定位内容Collections 文档。如果您可以提供帮助,请随时将其包含在您的回答中。

IntList是MutableIntList和ImmutableIntList扩展的接口。

我看到有一个实现 class 在这种情况下可能对您有所帮助 IntArrayList,它是 MutableIntList 的实现。

有一个 sortThis() 方法正在执行

Arrays.sort(this.items, 0, this.size);

所以对于你的例子,它会 return -9, -3, 0, 1, 7

但我注意到您想要 -3、-9、0、1、7。我不确定这是打字错误还是必需的。等你查了再讨论

因为这里也没有'quick'答案,所以我继续自己实现了这样一个排序设备。

public class IntListUtils {
    public interface IntIntComparator {
        int compare(int a, int b);
    }

    public static void sort(MutableIntList subject, IntIntComparator comparator) {
        quicksort(subject, 0, subject.size() - 1, comparator);
    }

    public static void quicksort(MutableIntList subject, int low, int high, IntIntComparator comparator) {
        if (low >= high) { return; }
        int pivot = partition(subject, low, high, comparator);
        quicksort(subject, low, pivot - 1, comparator);
        quicksort(subject, pivot, high, comparator);
    }

    private static int partition(MutableIntList subject, int low, int high, IntIntComparator comparator) {
        int pivot = subject.get(high);
        int i = low;
        for (int j = low; j <= high - 1; j++) {
            if (comparator.compare(subject.get(j), pivot) < 0) {
                int t = subject.get(i);
                subject.set(i, subject.get(j));
                subject.set(j, t);
                i += 1;
            }
        }
        int t = subject.get(i);
        subject.set(i, subject.get(high));
        subject.set(high, t);
        return i;
    }
}

可以用来实现我上面描述的排序顺序:

MutableIntList list = ...;
IntListUtils.sort(list, (a, b) -> {
    // negative before non-negative
    // otherwise, smallest numbers first
    if (a == b) { return 0; }
    if (a < 0 && b < 0) {
        return (a < b) ? 1 : -1;
    }
    return (a < b) ? -1 : 1;
});

编辑:我意识到这种快速排序不是目前最快的排序方法,但它所要做的就是比将我的整个 IntList 转换为 List<Integer> 并在排序后返回更快,它分配 O(n) 内存(n 很大),而这种排序方法就地发生。

从版本 10.3 开始,Eclipse 集合中引入了对原始集合的间接排序支持。它在可变原始集合上受支持。您可以在此处查看更多详细信息和用法示例 https://medium.com/javarevisited/eclipse-collections-now-supports-indirect-sorting-of-primitive-lists-e2447ca5dbc3

OP 示例如下所示:

@Test
public void soTest()
{
    // [1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]
    MutableIntList list = IntLists.mutable.of(1, 7, 0, -9, -3);

    list.sortThis((a, b) -> {
        // negative before non-negative
        // otherwise, smallest numbers first
        if (a == b) { return 0; }
        if (a < 0 && b < 0) {
            return (a < b) ? 1 : -1;
        }
        return (a < b) ? -1 : 1;}
    );

    Assert.assertEquals(IntLists.immutable.of(-3, -9, 0, 1, 7), list);
}

比较器 lambda 可以简化为:

list.sortThis((a, b) ->
        (a < 0 && b < 0) ? Integer.compare(b, a) : Integer.compare(a, b));