3
\$\begingroup\$

The problem

Given an arbitrary collection of objects of some kind, count and report the top k most frequent, together with the associated count. For example, if the input array is {'a', b', 'a', 'c', 'b', 'b'} and for k = 2, the template would return { {b, 3}, {'a', 2} }. The idea for the template it to allow start and ending iterators for any kind of collection for which ::value_type is defined.

The inspiration

Writing this review reminded me that I had, at one point, written a template to solve exactly this kind of problem. So I searched the hard drive, found this, and thought I'd present it here to see if might be critiqued and improved.

Questions

In particular, I'd be interested in any scenario in which the template fails. Additionally, are there any checks that could be made to make sure that only suitable iterators are passed? If so, what might those be?

maxfreq.h

#ifndef MAXFREQ_H
#define MAXFREQ_H
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iterator>

/* 
 * This template takes a start and ending iterator of a collection of
 * some kind.  It counts the number of occurences for each instance and
 * returns a vector of the top `k` instances each with their associated
 * count.
 */
template <class InputIt>
auto most_frequent_k(InputIt first, InputIt last, std::size_t k) -> std::vector<std::pair<typename InputIt::value_type, unsigned>> {
    typedef typename InputIt::value_type T;
    typedef typename std::pair<T, unsigned> Tcount;
    std::unordered_map<T, unsigned> count;
    for (; first != last; ++first) {
        ++count[*first];
    }
    std::vector<Tcount> pairs;
    auto m = count.size();
    pairs.reserve(m);
    k = std::min(k, m);
    std::copy(count.begin(), count.end(), std::back_inserter(pairs));
    std::partial_sort(pairs.begin(), pairs.begin()+k, pairs.end(), [](const Tcount &a, const Tcount &b) {
            return a.second > b.second;
            });
    pairs.erase(pairs.begin()+k, pairs.end());
    return pairs;
}

#endif // MAXFREQ_H

test.cpp

#include "maxfreq.h"
#include <iostream>
#include <sstream>

void test1()
{
    std::cout << "Test 1 {\n";
    std::vector<int> input{1,2,3,4,2,3,4,1,1,2,1,2,1,2,1,3,5};
    auto pairs = most_frequent_k(input.begin() , input.end(), 3);
    for (const auto &p : pairs) {
        std::cout << '\t' << p.first << ", " << p.second << '\n';
    }
    std::cout << "}\n";
}

void test2()
{
    std::cout << "Test 2 {\n";
    std::istringstream woodchuck{"how much wood would a woodchuck chuck if a woodchuck could chuck wood"};
    std::vector<std::string> input{};
    std::copy(std::istream_iterator<std::string>(woodchuck), std::istream_iterator<std::string>(), std::back_inserter(input) );
    auto pairs = most_frequent_k(input.begin() , input.end(), 3);
    for (const auto &p : pairs) {
        std::cout << '\t' << p.first << ", " << p.second << '\n';
    }
    std::cout << "}\n";
}

int main()
{
    test1();
    test2();
}

Output

Output from the test driver above looks like this:

Test 1 {
    1, 6
    2, 5
    3, 3
}
Test 2 {
    chuck, 2
    woodchuck, 2
    wood, 2
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I can think of a simple scenario where this fails: Custom classes with a custom hash function. unordered_map takes Hash, KeyEqual andAllocator functions, which you can take and pass through. Also, currently you don't handle ties very well. std::partial_sort is not stable, so it arbitrarily chooses some values to return in the case of a tie. Maybe include all of the tied values? \$\endgroup\$ – Artyer Jul 9 '17 at 22:33
  • \$\begingroup\$ Ties are resolved by essentially selecting randomly. Whether that's handling them "very well" or not depends on requirements, I suppose. For my purposes, that's the desired behavior. \$\endgroup\$ – Edward Jul 10 '17 at 16:04
3
\$\begingroup\$

Well, nice to see you follow stdlib conventions for your algorithm and accept an iterator-range.
But you really should use std::iterator_traits<It> to query the iterators associated types, as-is you cannot handle pointers.

Let's hope the elements are efficiently copied, or the algorithm is staggeringly inefficient.

Next, the count of unique symbols is often much smaller than k, making first inserting all elements, then sorting and finally removing most quite inefficient.
Consider limiting the result-vector to never grow beyond k elements using a heap.
(The standard provides std::make_heap (and for sorted output alsostd::sort_heap), but not down_heap (a vastly more efficient combination of std::pop_heap and std::push_heap, building-block of make_heap).)

\$\endgroup\$
  • \$\begingroup\$ I'm not quite sure what you mean about pointers. I've successfully used this template with the input being std::vector<const char *>. Can you elaborate? \$\endgroup\$ – Edward Jul 10 '17 at 11:12
  • \$\begingroup\$ Sure. It means that your implementations std::vector doesn't use raw pointers as iterators. T* doesn't have any members, specifically T*::value_type is ill-formed. \$\endgroup\$ – Deduplicator Jul 10 '17 at 11:23
3
\$\begingroup\$

I think you can simplify the generation of the vector from this

std::vector<Tcount> pairs;
auto m = count.size();
pairs.reserve(m);
k = std::min(k, m);
std::copy(count.begin(), count.end(), std::back_inserter(pairs));

to that

std::vector<Tcount> pairs(count.begin(), count.end());

This simplifies your code to

std::vector<Tcount> pairs(count.begin(), count.end());
std::partial_sort(pairs.begin(), pairs.begin()+std::min(k, m), pairs.end(), [](const Tcount &a, const Tcount &b) {
        return a.second > b.second;
        });
pairs.erase(pairs.begin()+k, pairs.end());

With the added benefit, that you can now declare k as const. However, it would be arguable whether you should throw a warning in case k > min.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.