Eclipse Collections 通过自定义 comparator-like 函数对 IntList 进行排序而不装箱
Eclipse Collections sorting an IntList by a custom comparator-like function without boxing
我正在尝试对一些 (Mutable
)IntList
objects 进行排序。boxing/unboxing 整数的成本与我的程序相关(这正是我使用原始 collections)。我想按以下标准排序:
- 所有负数都在 non-negative 数字之前
- 最小(最接近零)的数字优先
[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));
我正在尝试对一些 (Mutable
)IntList
objects 进行排序。boxing/unboxing 整数的成本与我的程序相关(这正是我使用原始 collections)。我想按以下标准排序:
- 所有负数都在 non-negative 数字之前
- 最小(最接近零)的数字优先
[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));