Блог

Допустим, у меня есть объект с одним значимым критерием и, возможно, с некоторыми другими данными.

 class MyObject {
    int criteria;
    String otherData;
}
  

Я хочу «отсортировать в случайном порядке» список таким образом, чтобы с учетом данных x, y, так что x является критерием, а y — другими данными, все похожие x группируются (и сортируются), но внутри подгруппы они перемешиваются

Моя цель, учитывая последовательные запуски, может дать следующие результаты

 / 1s first|/ 2s next |/ then 3s 
-----------------------------------
1,a 1,b 1,c 2,d 2,e 2,f 3,g 3,h 3,i // other data is in
1,a 1,c 1,b 2,e 2,d 2,f 3,i 3,h 3,g // a random order
1,c 1,a 1,b 2,d 2,f 2,e 3,h 3,i 3,g // within the subgroup
1,b 1,c 1,c 2,e 2,d 2,f 3,g 3,h 3,i 
  

Мой текущий план состоит в том, чтобы создать сопоставимый, который сравнивает только первые критерии. Тогда моя «сортировка в случайном порядке» могла бы просто

 list.shuffle(); // get a random ordering
list.sort(); // now group by criteria, leaving the others in a still random state
  

Мой вопрос в том, является ли это наиболее эффективным способом сделать это? Действительно ли это достигнет моей цели? Есть ли какой-то шаблон, который может возникнуть из этого? Если да, то что?

Я считаю, что это сработает и является асимптотически оптимальным. Это проще всего анализировать, если вы убедитесь, что используете стабильную сортировку, но я думаю, что фаза группировки не приведет к смещению независимо.

Если вы хотите написать код, который более явно выражает ваши намерения, вы можете вставить значения в TreeMap<Integer, List<MyObject>> , сгруппировав все значения данного целого числа в один список. Затем выполните итерацию по содержимому карты в порядке следования ключей (от наименьшего к наибольшему), перетасовывая каждый подсписок, а затем сбрасывая его содержимое в конечный выходной список. На мой взгляд, этот подход более «очевидно правильный», но я считаю, что ваш работает так же хорошо.

Единственная оптимизация, которую я вижу в вашем подходе, заключалась бы в использовании какого-то итератора перетасовки вместо фактического перетасовки данных. Но это не изменит сложность вашего алгоритма, потому что стоимость перетасовки в худшем случае линейна, а сортировка в лучшем случае равна n log (n)

Подумайте о том, что вы пытаетесь сделать, прежде чем думать о реализации, и попытайтесь найти подходящее из существующих классов JDK.

Я бы использовал, Map<Integer, List<MyObject>> который сразу решил бы проблему группировки, тогда я мог бы Collections.shuffle() списки, и если бы я действительно хотел единый список, я мог бы сбросить списки в значениях карты в один список:

 Map<Integer, List<MyObject>> map = new HashMap<Integer, List<MyObject>>();
...
List oneList = new ArrayList<MyObject>(map.values());
for (List<?> list : map.values())
    oneList.addAll(list);