Перемешать отсортированные подмассивы - PullRequest
Новая
       22

Перемешать отсортированные подмассивы

1 голос
/ 04 ноября 2011

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

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

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

Ответы [ 3 ]

2 голосов
/ 04 ноября 2011

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

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

1 голос
/ 04 ноября 2011

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

0 голосов
/ 04 ноября 2011

Подумайте о том, что вы пытаетесь сделать, за до вы подумаете о реализации и попытаетесь найти хорошее соответствие из существующих классов 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);
...