Сортировка массива double по количеству знаков после запятой
Возможно ли быстро отсортировать массив типа double по количеству знаков после запятой? Изначально хотела использовать словарь, где хранились бы сами числа и соответствующее количество знаков, но может есть способ проще?
Ответы (2 шт):
Сортировать массив примитивных значений (double[], int[], long[] и т.п.) можно только в "естественном" порядке. Для необычной сортировки как в данном случае по длине дробной части потребуется либо использовать массив соответствующих классов-обёрток, т.е. Double[], к которому можно применить метод Arrays::sort(T[] a, Comparator<? super T> comp), либо преобразовать с помощью Stream API.
(Обновление) Для корректной сортировки нужно обеспечить ненулевое значение в старшем разряде (спасибо @Stanislav Volodarskiy).
Также потребуется обеспечить корректное форматирование некоторых чисел (спасибо @siarhei987), поскольку они могут быть по умолчанию преобразованы в строку с "научной" записью с указанием экспоненты.
Так как double может хранить до 17 значащих цифр, потребуется отформатировать каждое число, убрав нули в конце. При форматировании следует принять во внимание локаль, чтобы корректно обрабатывался десятичный разделитель
Double[] arr = {
1.234, 1.2, 22d, 1.001, 23.41, 10.00456, 3.1415, Math.PI
};
Arrays.sort(arr, Comparator.comparingLong(x -> {
String s = String.format(Locale.US, "%.17f", x).replaceAll("0+$", "");
return Long.parseLong(1 + s.substring(s.indexOf(".") + 1));
}));
System.out.println(Arrays.toString(arr));
// -> [22.0, 1.2, 23.41, 1.001, 1.234, 3.1415, 10.00456, 3.141592653589793]
Аналогично:
double[] arr = {
1.234, 1.2, 22, 1.001, 23.41, 10.00456, 3.1415, 11.21, Math.PI,
10.234, 1238.41,
12345678.02, // 10 знаков 8+2
12345678901234.5678, // 18 знаков 14+4
1234567890999.56789, // 18 знаков 13+5
-.123456789012345678, // 18 знаков 0+18
-12.3456789012345678, // 18 знаков 2+16
987654321012345678.91 // 20 знаков 18+2
};
arr = Arrays.stream(arr)
.boxed()
.sorted(Comparator.comparingLong(
x -> Long.parseLong(1 + String.format(Locale.US, "%.17f", x)
.replaceAll("0+$", "") // удалить 0 в конце
.replaceAll("^.*\\.", "") // удалить всё до точки в начале
)
))
.mapToDouble(x -> x)
.toArray();
for (double d : arr) {
System.out.println(String.format(Locale.US, "%.17f", d).replaceAll("\\.?0+$", ""));
}
Некоторые числа будут округлены, так как у типа double не хватает точности
22
987654321012345730
1.2
12345678.02
11.21
23.41
1238.41
1.001
1.234
10.234
12345678901234.568
3.1415
1234567890999.5679
10.00456
3.141592653589793
-12.345678901234567
-0.12345678901234568
fracLength вычисляет длину дробной части числа. format переводит double в десятичную дробь. 330 - волшебная константа: самое маленькое значение double - 4.9E-324, значит трехсот тридцати знаков будет достаточно для любого конечного значения. Первый replaceFirst удаляет знак, целую часть и десятичную точку. Второй удаляет хвост из нулей. Длина остатка - то что нам нужно:
private static int fracLength(double d) {
return String
.format("%.330f", d)
.replaceFirst(".*\\.", "")
.replaceFirst("0*$", "")
.length();
}
Java умеет сортировать double[] только по значениям. А нам нужно по ключу. Массив можно обернуть в список List<Double>. Приятно, что данные не надо копировать: новый список - интерфейс к массиву, не более:
private static List<Double> wrap(double[] a) {
return new AbstractList<Double>() {
@Override
public Double get(int index) {
return a[index];
}
@Override public int size() {
return a.length;
}
@Override
public Double set(int index, Double element) {
final double previous = a[index];
a[index] = element;
return previous;
}
};
}
Список уже можно сортировать по ключу. В результате сортируется сам массив:
private static void sortByFracLength(double[] a) {
Collections.sort(wrap(a), Comparator.comparingInt(d -> fracLength(d)));
}
Тестируем решение:
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Temp {
private static List<Double> wrap(double[] a) {
return new AbstractList<Double>() {
@Override
public Double get(int index) {
return a[index];
}
@Override public int size() {
return a.length;
}
@Override
public Double set(int index, Double element) {
final double previous = a[index];
a[index] = element;
return previous;
}
};
}
private static int fracLength(double d) {
return String
.format("%.330f", d)
.replaceFirst(".*\\.", "")
.replaceFirst("0*$", "")
.length();
}
private static void sortByFracLength(double[] a) {
Collections.sort(wrap(a), Comparator.comparingInt(d -> fracLength(d)));
}
public static void main(String[] args) {
double[] a = {
Double.MIN_VALUE,
Double.MAX_VALUE,
10.2,
10.0001,
1234,
1234.01234
};
System.out.println(Arrays.toString(a));
sortByFracLength(a);
System.out.println(Arrays.toString(a));
}
}
$ javac Temp.java && java Temp [4.9E-324, 1.7976931348623157E308, 10.2, 10.0001, 1234.0, 1234.01234] [1.7976931348623157E308, 1234.0, 10.2, 10.0001, 1234.01234, 4.9E-324]