Сортировка списка из наименьших по размеру наименьших в Java

Question

Я пытаюсь сортировать набор данных, чтобы он выглядел как гистограмма функции распределения вероятности (я предполагаю, что на данный момент нормально распределен).

У меня есть список записей:

private static final class SortableDatasetEntry{ 
    Number value; 
    Comparable key; 
    public SortableDatasetEntry(Number value, Comparable key){ 
     this.value = value; 
     this.key = key; 
    } 
} 

пример: У меня есть вопросы: {1,2,3,4,5,6,7,8,9}

EDIT: отсортированный список, который я хотел бы: {1,3,5,7,9,8,6,4,2} (или что-то подобное) число, не всегда будет настолько опрятным (т.е. просто сортировка по нечетным/даже не работает). У меня есть частичное решение, которое включает сортировку по регулярному порядку (от самого низкого до самого высокого), а затем копирование этого списка в другой, вставляя их в середину каждый раз, таким образом, последний элемент, вставленный (в середину), является самым большим. Мне все равно хотелось бы найти способ сделать это с помощью компаратора.

Это довольно сложно, потому что его не отсортирован по абсолютной величине value, но на расстоянии от среднего ( value) в наборе, а затем каким-то образом перемещается так, эти значения ближе всего к виду центрированы. Я знаю, что функция compareTo должна быть «обратимой» (я забыл правильный термин).

Бонусные баллы: Как определить правильное распределение данных (т. Е. Если это не нормально, как предполагалось).

Answer 1

Сначала вычислите среднее значение и сохраните его в переменной с именем say mean. Затем, когда вы вставляете записи в свой SortableDatasetEntry, используйте value - mean в качестве фактического значения для каждой записи, а не value.

Answer 2

Для чего я вижу, вы, вероятно, хотите получить кортеж «среднего расстояния», значение и отсортировать список кортежей с первой записью «среднее расстояние».

Answer 3

Вам будет проще построить свою гистограмму как Map.

public static Map<Integer, List<Number>> histogram(List<Number> values, int nBuckets) { 
    // Get stats on the values. 
    DoubleSummaryStatistics stats = values.stream().mapToDouble((x) -> x.doubleValue()).summaryStatistics(); 
    // How big must each bucket be? 
    int bucketSize = (int) (stats.getMax() - stats.getMin())/nBuckets; 
    // Roll them all into buckets. 
    return values.stream().collect(Collectors.groupingBy((n) -> (int) ((n.doubleValue() - stats.getMin())/bucketSize))); 
} 

Примечание намерение в Histogram

Для построения гистограммы, первый шаг должен «бин» диапазон значений, то есть, разбить весь диапазон значений в серии небольшие интервалы - и затем подсчитывайте, сколько значений попадает в каждый интервал.

Answer 4

Would что-то вроде:

public List<Integer> customSort(List<Integer> list) { 
    Collections.sort(list); 
    List<Integer> newList = new ArrayList<Integer>(); 
    for (int i = 0; i < list.size(); i += 2) { 
     newList.add(list.get(i)); 
    } 
    if (list.size() % 2 == 0) { 
     for (int i = 1; i < list.size(); i += 2) { 
      newList.add(list.get(list.size() - i)); 
     } 
    } else { 
     for (int i = 1; i < list.size(); i += 2) { 
      newList.add(list.get(list.size() - i - 1)); 
     } 
    } 
    return newList; 
} 

работы? Я положил {1,2,3,4,5,6,7,8,9} и получил {1,3,5,7,9,8,6,4,2}, а {1,2,3,4,5,6,7,8} дал {1,3,5,7,8,6,4,2}.

Answer 5

Вы не можете выполнить это в одном виде только с помощью настраиваемого Comparator.

Однако это все еще возможно сделать это на месте, без дополнительной информации.

Ваш нынешний подход не на месте, но, вероятно, проще всего реализовать и понять.Если размер коллекции в памяти не вызывает беспокойства, подумайте о том, чтобы остаться с вашим текущим подходом.

Пользовательский компаратор в одном роде

Ваш желаемый порядок зависит от порядка возрастания. Учитывая несортированные данные, ваш Comparator не имеет возрастающего порядка при первом сортировке.

В месте подходы

Вы можете создать свой желаемый порядок на месте.

Что следует из предположений 0-индексов.

Один подход будет использовать два вида. Сначала сортируйте в порядке возрастания. Отметьте каждый объект своим индексом. В компараторе второго сорта все объекты с четными индексами будут меньше всех объектов с нечетными индексами. Объекты с четными индексами будут упорядочены в порядке возрастания. Объекты с нечетными индексами будут упорядочены в порядке убывания.

Другим подходом будет пользовательский алгоритм сортировки, поддерживающий отображение из виртуальных в физические индексы. Алгоритм сортировки создавал бы возрастающий порядок в пространстве виртуального индекса. Ваше индексное сопоставление будет размещено в физической памяти в желаемом порядке. Вот непроверенный эскиз отображения индекса:

private int mapVirtualToPhysical(int virtualIndex, int countElements) { 
    boolean isEvenIndex = (0 == (index % 2)); 
    int physicalIndex = isEvenIndex ? (index/2) : (countElements - (index/2) - 1); 
    return physicalIndex; 
} 

Предпочтительнее либо из них будет первоначальный сорт с последующей O (N) серией свопы. Однако я еще не определил последовательность свопов. Лучшее, что я придумал до сих пор, по порядку имеет левый хвост, но правый хвост требует следующего сортировки или стека.

Answer 6

Для больших наборов данных, вы можете использовать подход, когда SortableEntry конструктор определяет, какая сторона диаграммы (влево или вправо до самого высокого) эта конкретная запись будет занимать, используя генератор случайных чисел:

static final class SortableEntry<T>{ 

    Number value; 
    Comparable<T> key; 
    int hr; 
    static Random rnd = new Random(); 

    public SortableEntry(Number value, Comparable<T> key){ 
     this.value = value; 
     this.key = key; 
     this.hr = rnd.nextInt(2) == 0 ? -1 : 1; // here 
    } 
} 

Точкой дополнительной переменной hr является то, что любая «правильная» запись будет больше, чем любая «левая» и наоборот. Если hr из двух сравниваемых записей одинаковы, сравнить по фактической key с учетом знака hr:

static final class SortableEntryComparator<T> implements Comparator<SortableEntry<T>> { 

    @Override 
    public int compare(SortableEntry<T> e1, SortableEntry<T> e2) { 
     if (e1.hr == e2.hr) 
      return e1.hr < 0 ? e1.key.compareTo((T) e2.key) : e2.key.compareTo((T) e1.key); 
     else 
      return e1.hr - e2.hr; 
    } 
} 

Теперь небольшой тест:

@Test 
public void testSort() { 
    List<Integer> keys = Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 
             12, 25, 31, 33, 34, 36, 39, 41, 26, 49, 
             52, 52, 58, 61, 63, 69, 74, 83, 92, 98); 
    List<SortableEntry<Integer>> entries = new ArrayList<>(); 
    for (Integer k : keys) { 
     entries.add(new SortableEntry<Integer>(0, k)); 
    } 
    entries.sort(new SortableEntryComparator<Integer>()); 
    System.out.println(entries); 
} 
// output: 
// [12, 26, 33, 36, 39, 40, 49, 50, 52, 60, 61, 63, 80, 90, 98, 100, 92, 83, 74, 70, 69, 58, 52, 41, 34, 31, 30, 25, 20, 10] 
// the highest key (100) is not precisely in the center, 
// but it will tend to occur in the center when dataset is large.