Java: случайный элемент из самой популярной категории - PullRequest
Новая
       29

Java: случайный элемент из самой популярной категории

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

Мне нужно найти самый эффективный способ найти случайный элемент из самой популярной категории

Из 

4 Cheese
1 Olive
2 Mushroom
4 Ham
2 Chicken
4 Salad

Я хочу либо Cheese, либо Ham, либо * 1008.*.Если есть несколько верхних категорий, мне все равно, из какой категории я получу свой товар.

На входе у меня есть Iterator<Foo>, где Foo реализует 

Interface Foo {
    int getCategory();
}

Мой текущийкод выглядит так: 

Foo getItem(Iterator<Foo> it) {
    Map<Integer, List<Foo>> categoryMap = new HashMap<Integer, List<Foo>>();
    while(it.hasNext()) {
        Foo foo = it.next();
        int category = foo.getCategory();

        List<Foo> l = categoryMap.get(category);
        if(l == null) {
            l = new ArrayList<Foo>();
            categoryMap.put(category, l);
        }

        l.add(foo);
    }

    int longest_list_size = 0;
    int longest_category_id = -1;

    Set<Integer> categories = categoryMap.keySet()

    for(Integer c:  categories ) {
        int list_size = categoryMap.get(c).size();
        if(list_size  > longest_list_size) {
           longest_list_size = list_size;
           longest_category_id = c;
        }
    }

    if(longest_list_size == 0)
        return null;

    int r = new Random().nextInt(longest_list_size);
    return categoryMap.get(c).get(r);
}

Ответы [ 3 ]

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

Вот что я хотел бы сделать:

  1. создать List<Foo> из it
  2. отсортировать список по категории
  3. просмотреть список изначало и сохранение начального и конечного индексов самого длинного интервала с той же категорией
  4. выбор случайного элемента между начальным и конечным индексом

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

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

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

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

  1. Вставка в карту -> O (N)
  2. Расчет максимума -> O (N)

Итого: O (N)

Другие методы:

  1. Очередь приоритетов -> O (N * log (N)) вставка всех элементов + O (1) извлечение головки
  2. Сортировка исходной карты по ключу O (N * log (N)) + O (1) извлечение первой
  3. Если вы знаете интервал подсчета голосов, скажем [0..K], и он меньше или не намного больше, чем N, вы можете выполнить сортировку отсчетов в O (K) + O (1), чтобы получить максимум.

Если вам нужен максимальный поиск только один раз, то ваш метод достаточно хорош, ИМО.

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

Вероятно, быстрее иметь 2 карты: 

Foo getItem(Iterator<Foo> it) {
    Map<Integer, Foo> categoryToFoo = new HashMap<Integer, Foo>();
    Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
    int maxCount = 0;
    while(it.hasNext()) {
        Foo foo = it.next();
        int category = foo.getCategory();
        int categoryCount = 1;
        if ( ! categoryToFoo.contains( category ) ) {
            categoryToFoo.put( category, foo );
        }
        else {
            categoryCount = counts.get( category ) + 1;
        }
        counts.put( category, categoryCount );
        if ( categoryCount > maxCount ) {
            maxCount = categoryCount;
        }
    }

    List<Foo> possible = new ArrayList<Foo>()
    for ( Map.Entry entry : counts.entrySet() ) {
        if ( entry.getValue() == maxCount ) {
            possible.add( categoryToFoo.get( entry.getKey() ) );
        }
    }

    return possible.get( new Random().nextInt( possible.size() ) );
}

Вы можете провести дальнейшую оптимизацию во многих местах, но у вас есть идея.

...