Выборка из коллекции по определенным полям с ограничениями

Question

Подскажите, пожалуйста, как реализовать такую идею:

Есть лист продуктов: List<Product> products = new ArrayList<>();

Предположим, что их там миллион.

У продукта есть: id, name, price(float); У продуктов могут быть одинаковые id.

Необходимо сделать выборку из 1000 самых дешевых продуктов, но при этом в выборке должно быть не более 20 продуктов с одинаковым идентификатором.

Начал с сортировки цены:

products.sort(new Comparator<Product>() {
                @Override
                public int compare(Product o1, Product o2) {
                    return Float.compare(o1.getPrice(), o2.getPrice());
                }
            });

Если с сортировкой у меня правильно, подскажите, как в итоге можно сделать такую выборку с такими ограничениями? Больше вызывает смущения, как организовать проверку, чтобы id в выборке не повторялись более 20 раз.

Answer 1

Пробегитесь с Map<String, Integer> по листу и подсчитайте, сколько по каждому id продуктов. Пробегаясь используйте переменную, которую увеличивайте с каждым новым элементом, входящим в мапу с менее 20 элементов. Выходите из цикла по достижении ей значения 1000(и по кол-ву просмотренных объектов, если не хотите получить бесконечный цикл в перспективе). После удалите все те пары ключ-значение(id-кол-во), у которых значение более 20(используйте .entrySet() для получения всех пар ключ-значение). Затем прогоните n элементов, проверяя, есть ли id в мапе. Если есть, то это искомый элемент.

P.S.: Для увеличения производительности можно сначала прогнать по мапе 1000 элементов, затем проверить мапу на превышение кол-ва элементов(20) каждого id, а потом продолжить прогонять(если такие превышения были) уже по выше описанному алгоритму.

public static void main(String[] args) {
    final int toGetContainers = 100;
    final int idCount = 10;
    final int criticalCount = 10;
    List<IDContainer> containers = new ArrayList<IDContainer>(toGetContainers * 3);
    Random random = new Random(System.currentTimeMillis());
    Map<Integer, Integer> counter = new HashMap<Integer, Integer>(7);
    int countSeen = 0;
    for(int i = 0; i < toGetContainers * 4; i++) {
        containers.add(new IDContainer(random.nextInt(idCount)));
    }
    for(int i = 0; countSeen < containers.size() && (i < toGetContainers); i++, countSeen++) {
        counter.put(containers.get(countSeen).getID(), counter.getOrDefault(containers.get(countSeen).getID(), 0) + 1);
        if(counter.get(containers.get(countSeen).getID()) > criticalCount) {
            i--;
        }
    }
    counter.entrySet().forEach((Map.Entry<Integer, Integer> entry) -> System.out.println(entry.getKey() + " " + entry.getValue()));
    List<Integer> normalIDs = new ArrayList<Integer>();
    for(Map.Entry<Integer, Integer> entry : counter.entrySet()) {
        if(entry.getValue() <= criticalCount) {
            normalIDs.add(entry.getKey());
        }
    }
    normalIDs.forEach((Integer id) -> System.out.println("normal id: " + id));
    List<IDContainer> withNormalID = new ArrayList<IDContainer>(countSeen);
    for(int i = 0; i < countSeen; i++) {
        if(normalIDs.contains(containers.get(i).getID())) {
            withNormalID.add(containers.get(i));
        }
    }
    withNormalID.forEach((IDContainer idContainer) -> System.out.println(idContainer.getID()));
    System.out.println(countSeen);



}

static class IDContainer {
    private int id;

    public IDContainer(int id) {
        this.id = id;
    }

    public int getID() {
        return id;
    }
}

Вывод(Не должен совпадать - рандом же):

0 16
1 19
2 11
3 19
4 14
5 16
6 12
7 10
8 15
9 17
normal id: 7
7
7
7
7
7
7
7
7
7
7
149

Answer 2

@miron к сожалению, у меня не хватает пока знаний, чтобы легко воспринять то, что Вы мне посоветовали. Остановился пока на таком варианте:

 for (int i = 0; i < products.size(); i++) {
            map.put(products.get(i).getId(), map.getOrDefault(products.get(i).getId(), num) + 1);
        }

        for (int i = 0; i < 1000; i++){
            for (Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext(); ) {
                Map.Entry<Integer, Integer> entry = it.next();
                if (entry.getValue() > 20) {
                    it.remove();
                    i--;
                    continue;
                }
                finalProds.add(products.get(i));
            }
        }
        return finalProds;
    }

БЛОГ НА HUSL

Выборка из коллекции по определенным полям с ограничениями

Ответы (2 шт):