Класс полезности счетчика частоты

Некоторые очень распространенные задачи, которые появляются из времени:

  • Найдите наиболее частое что-то в коллекции вещей
  • ... или подсчет этой вещи
  • ... или оба (элемент и его счет)
  • Получить список отдельных элементов с их счетчиками, отсортированными по их подсчетам
  • Получите N наиболее часто используемых элементов с их подсчетами

Чтобы избежать повторного ввода одного и того же типа частотного счетного кода, Я придумал это:

public class FrequencyCounter<T> {

    private final Map<T, Integer> frequencyMap = new HashMap<>();

    private final Comparator<T> countComparator = (o1, o2) -> Integer.compare(frequencyMap.get(o1), frequencyMap.get(o2));

    public void add(T item) {
        Integer count = frequencyMap.get(item);
        if (count == null) {
            count = 0;
        }
        frequencyMap.put(item, count + 1);
    }

    public void addAll(Collection<T> items) {
        items.forEach(this::add);
    }

    public T getMostFrequentItem() {
        return toSortedMap().lastKey();
    }

    public int getMostFrequentCount() {
        SortedMap<T, Integer> sortedMap = toSortedMap();
        T lastKey = sortedMap.lastKey();
        return sortedMap.get(lastKey);
    }

    private SortedMap<T, Integer> toSortedMap(Comparator<T> comparator) {
        SortedMap<T, Integer> sortedMap = new TreeMap<>(comparator);
        sortedMap.putAll(frequencyMap);
        return sortedMap;
    }

    public SortedMap<T, Integer> toSortedMap() {
        return toSortedMap(countComparator);
    }

    public SortedMap<T, Integer> toReversedMap() {
        return toSortedMap(Collections.reverseOrder(countComparator));
    }

    private List<T> toSortedList(Comparator<T> comparator) {
        List<T> list = new ArrayList<>(frequencyMap.keySet());
        Collections.sort(list, comparator);
        return list;
    }

    public List<T> toSortedList() {
        return toSortedList(countComparator);
    }

    public List<T> toReversedList() {
        return toSortedList(Collections.reverseOrder(countComparator));
    }
}

Единичные тесты:

public class FrequencyCounterTest {
    @Test
    public void test_getMostFrequentItem() {
        FrequencyCounter<Integer> counter = new FrequencyCounter<>();
        counter.addAll(Arrays.asList(1, 4, 9, 3, 4, 5, 4, 9));
        assertEquals(new Integer(4), counter.getMostFrequentItem());
    }

    @Test
    public void test_getMostFrequentCount() {
        FrequencyCounter<Integer> counter = new FrequencyCounter<>();
        counter.addAll(Arrays.asList(1, 4, 9, 3, 4, 5, 4, 9));
        assertEquals(3, counter.getMostFrequentCount());
    }

    @Test
    public void test_getMostFrequentLetter() {
        FrequencyCounter<Character> counter = new FrequencyCounter<>();
        String text = "Lorem ipsum dolor sit amet, consectetur adipisicing elit, " +
                "sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. " +
                "Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris " +
                "nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in " +
                "reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla " +
                "pariatur. Excepteur sint occaecat cupidatat non proident, sunt in " +
                "culpa qui officia deserunt mollit anim id est laborum.";

        for (char c : text.replace(" ", "").toCharArray()) {
            counter.add(c);
        }
        assertEquals(new Character('i'), counter.getMostFrequentItem());
    }

    @Test
    public void test_map_hi_hi_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        assertEquals("{hello=1, hi=2}", counter.toSortedMap().toString());
    }

    @Test
    public void test_map_hello_hi_hi() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        assertEquals("{hello=1, hi=2}", counter.toSortedMap().toString());
    }

    @Test
    public void test_map_hello_hi_hi_hello_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        assertEquals("{hi=2, hello=3}", counter.toSortedMap().toString());
    }

    @Test
    public void test_sortedList_hi_hi_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        assertEquals("[hello, hi]", counter.toSortedList().toString());
    }

    @Test
    public void test_sortedList_hello_hi_hi() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        assertEquals("[hello, hi]", counter.toSortedList().toString());
    }

    @Test
    public void test_sortedList_hello_hi_hi_hello_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        assertEquals("[hi, hello]", counter.toSortedList().toString());
    }

    @Test
    public void test_reversedList_hi_hi_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        assertEquals("[hi, hello]", counter.toReversedList().toString());
    }

    @Test
    public void test_reversedList_hello_hi_hi() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        assertEquals("[hi, hello]", counter.toReversedList().toString());
    }

    @Test
    public void test_reversedList_hello_hi_hi_hello_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        assertEquals("[hello, hi]", counter.toReversedList().toString());
    }

    @Test
    public void test_reversedList_hello_hi_hi_hello_hello_null() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        counter.add(null);
        assertEquals("[hello, hi, null]", counter.toReversedList().toString());
    }
}

Как вы думаете?

  • Что-нибудь улучшить или странно выглядеть?
  • Я изобретаю колесо? Есть ли что-то существующее, которое я могу использовать вместо этого?
  • Является ли это полезным, эргономичным, или может быть лучше?
11 голосов | спросил janos 5 MaramThu, 05 Mar 2015 02:42:55 +03002015-03-05T02:42:55+03:0002 2015, 02:42:55

2 ответа


3

@Simon имеет хороший ответ о некоторых проблемах юзабилити, но я хочу сосредоточиться на аспектах производительности и памяти.

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

Рассмотрим класс:

public class Counter (

    private long count = 0;

    public long increment() {
        return ++count;
    }

    public long get() {
        return count;
    }
}

Теперь создайте свою внутреннюю карту как:

private final Map<T, Counter> frequencyMap = new HashMap<>();

В вашем методе add():

public void add(T item) {
    frequencyMap.computeIfAbsent(item, k -> new Counter()).increment();
}

Используя счетчик, вы значительно уменьшаете количество отбросов памяти на карте и можете легко преобразовать ее в отчетный экземпляр Long при экстернализации значений.

ответил rolfl 5 MarpmThu, 05 Mar 2015 17:30:38 +03002015-03-05T17:30:38+03:0005 2015, 17:30:38
5

Поток, поток, поток

Похоже, что создать FrequencyCounter из Collection, так почему бы не сделать его статическим заводским методом?

public static <T> FrequencyCounter<T> fromCollection(Collection<T> values) {
    FrequencyCounter<T> result = new FrequencyCounter<>();
    result.addAll(values);
    return result;
}

Или, если вы переключите Map<T, Integer> на Map<T, Long>, как насчет из потока, используя некоторую магию потока?

private FrequencyCounter(Map<T, Long> frequencyMap) {
    this.frequencyMap = frequencyMap;
    this.countComparator = (o1, o2) -> Long.compare(frequencyMap.get(o1), frequencyMap.get(o2));
}

public static <T> FrequencyCounter<T> fromStream(Stream<T> stream) {
    Map<T, Long> frequencies = stream.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
    return new FrequencyCounter<>(frequencies);
}

Я считаю, что эта линия примерно так же близка к уже существующему колесу, что и вы:

Map<T, Long> frequencies = stream.collect(Collectors.groupingBy(e -> e, Collectors.counting()));

В вашем test_getMostFrequentLetter вы можете:

counter = FrequencyCounter.fromStream(text.chars().filter(i -> i != ' ')
    .mapToObj(i -> (char) i));

И в другом тесте:

FrequencyCounter<String> counter = FrequencyCounter.fromStream(Stream.of("hi", "hi", "hello"));

поток, поток, поток, все, что вам нужно сделать, это Stream ...

Неизменность?

Подумайте о том, чтобы сделать FrequencyCounter неизменяемым или иметь отдельный FrequencyCount, который просто содержит результат из FrequencyCounter (тогда вам также просто нужно вызвать toSortedMap один раз)

Добавление слияния

Ваш метод add может быть довольно упрощен при использовании merge:

public void add(T item) {
    frequencyMap.merge(item, 1L, (oldValue, value) -> oldValue + value);
}

Получить методы

Давайте посмотрим на ваши методы get ...

public T getMostFrequentItem()
public int getMostFrequentCount()
public SortedMap<T, Integer> toSortedMap()
public SortedMap<T, Integer> toReversedMap()
public List<T> toSortedList()
public List<T> toReversedList()

Как насчет int getFrequency(T item)?

Или каким-либо другим способом получить доступ к уже существующему Map<T, Long> без накладных расходов, превратив его в SortedMap?

Конец края

Рассмотрим этот код:

FrequencyCounter<String> counter = new FrequencyCounter<>();
String mostUsed = counter.getMostFrequentItem();
int count = counter.getMostFrequentCount();

Это вызовет 2x исключение NullPointerException. Чаще всего нет предметов. Чаще всего нет.

Я ожидал бы counter.getMostFrequentCount(), чтобы вернуть 0 в этом случае, и я, вероятно, сделаю counter.getMostFrequentItem() return null. В любом случае, это крайний случай, который я не думаю, что вы рассмотрели. Это зависит от вас, как вы справитесь с этим:)

ответил Simon Forsberg 5 MaramThu, 05 Mar 2015 04:25:58 +03002015-03-05T04:25:58+03:0004 2015, 04:25:58

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132