Java Пользовательский порядок сортировки Круглая сортировка по Робину

Question

Я Java-разработчик, но у меня нет хорошего алгоритма для определенного типа сортировки, который мне нужно сделать.

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

Это просто так:

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

Скажем, данные такие:

А В В С D D

Действительный порядок сортировки для моей цели будет следующим:

A В С D В D A

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

Опять же, я делаю это на Java, но на данный момент я не привязан к определенной структуре данных и т. Д.

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

Спасибо! Том

Answer 1

Вот мое решение.

Это не требует, чтобы входные данные уже были отсортированы.

В основном это создает Map с идентификаторами и количеством их вхождений, затем циклчерез эту карту каждый раз выбирать другой идентификатор, пока карта не станет пустой.

public static void main(String[] args) {
    List<String> ids = Arrays.asList("A", "A", "A", "A", "B", "B", "C", "D", "D");
    List<String> idsOrdered = order(ids);
    idsOrdered.forEach(System.out::println);
}

private static List<String> order(List<String> ids) {
    // create a map with ids and their occurrences
    Map<String, Long> occurs = ids.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

    List<String> idsOrdered = new ArrayList<>();
    while (!occurs.isEmpty()) {
        // add all the ids in the map to the list
        occurs.forEach((k, v) -> idsOrdered.add(k));
        // decrement the counter of all ids
        occurs.replaceAll((k, v) -> v - 1);
        // remove the ids with the counter at 0
        occurs.entrySet().removeIf(e -> e.getValue() == 0);
    }
    return idsOrdered;
}

И вот то же решение, но «старая школа» (без функционального программирования):

private static List<String> order(List<String> ids) {

    // create a map with ids and their occurrences
    Map<String, Integer> occurs = new HashMap<>();
    for (String id : ids) {
        Integer occur = occurs.get(id);
        if (occur != null) {
            occurs.put(id, occur + 1);
        }
        else {
            occurs.put(id, 1);
        }
    }

    List<String> idsOrdered = new ArrayList<>();
    while (!occurs.isEmpty()) {
        // loop through the map
        Iterator<Entry<String, Integer>> it = occurs.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> pair = it.next();

            // add the key to the list
            String key = pair.getKey();
            idsOrdered.add(key);

            // update the occurrences, if 0 then remove the id from the map
            int newOccur = pair.getValue() - 1;
            if (newOccur == 0) {
                it.remove();
            }
            else {
                pair.setValue(newOccur);
            }
        }
    }
    return idsOrdered;
}

Answer 2

1. Группируйте значения в структуру типа LinkedList по любой функции группировки, которую вы хотите.

2. Добавьте их в итоговую результирующую коллекцию, опрашивая каждую группу.

Ex)

Дано:

public class MyObject {

    private String name;

    public MyObject(String name) {
        super();
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

Набор данных:

List<MyObject> objects = new ArrayList<>();


        objects.addAll( Arrays.asList(
            new MyObject("A"),
            new MyObject("C"),
            new MyObject("A"),
            new MyObject("B"),
            new MyObject("B"),
            new MyObject("B"),
            new MyObject("A"),
            new MyObject("A"),
            new MyObject("C"),
            new MyObject("C"),
            new MyObject("A"),
            new MyObject("C")
        ));

И функция:

public static Queue<MyObject> robin(List<MyObject> objects) {

        if(objects.size() == 0) return new LinkedList<>();

        // Group into queues using the getName method
        Map<String, Queue<MyObject>> map = objects.stream()
                .collect(Collectors.groupingBy(MyObject::getName, Collectors.toCollection(LinkedList::new)));

        boolean remaining = true;
        Deque<MyObject> roundRobin = new LinkedList<MyObject>();

        Set<String> keySet = map.keySet();

        // Round robin structure to collect them into a single collection
        while(remaining) {
            remaining = false;
            for(String key : keySet) {
                MyObject obj = map.get(key).poll();
                if(obj == null) continue;
                roundRobin.add(obj);
                remaining = true;
            }
        }

        // Return result
        return roundRobin;
    }

Результирующий заказ:

A B C A B C A B C A C A

Answer 3

Основано на

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

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

Как насчет размещения всех пользователей в LinkedHashMap<User, Integer>, где вы вставляете всех пользователей из вашего запроса, если пользовательуже на карте, вы увеличиваете счетчик.Затем вы будете циклически перемещаться по карте (пользователи теперь всегда в том же порядке), и в каждой записи вы вызываете свою работу, уменьшаете счетчик, и, если счетчик достиг нуля, вы удаляете запись.(завершается, когда карта пуста)

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

Конечно, есть издержки из-за создания нового объекта для каждого пользователя, так что все зависит от среднего значения счетчика на пользователя.