Top 5 most frequent from an array c++

Question

Hi i've an array and im looking to get the top 5 most frequently occuring from this array.

static std::string pickRandomStockSymbol()
{
    static std::string stockSymbols[] = {"SIRI", "INTC", "ZNGA", "BBRY", "MSFT", 
        "QQQ", "CSCO", "FB", "MU", "DELL", "AMAT", "NWSA", "AAPL", "AFFY", "ORCL", 
        "YHOO", "GRPN", "MDLZ", "VOD", "CMCSA" };

    return stockSymbols[rand() % 20];

^^ this is the array i will be using.

the transactions are randomly created using this struct:

struct Transaction
{
string stockSymbol;     // String containing the stock symbol, e.g. "AAPL"
string buyerName;       // String containing the buyer's name e.g. "Mr Brown"
int buyerAccount;       // Integer containing an eight digit account code
int numShares;          // Integer containing the number of sold shares
int pricePerShare;      // Integer containing the buy price per share
};

it is within this function i plan to do this in, i just dont really know what way i approach this:

string* Analyser::topFiveStocks()
{

return new string[5];
}

is there anyone out there willing to show me how i could run through the transactions to get these top 5 occuring elements?

if there would be any more information needed i'll be more than happy to provide.

Thanks in advance, Andrew

Very very close to this previous thread http://stackoverflow.com/questions/12049352/determining-most-freq-char-element-in-a-vectorchar — Shafik Yaghmour, Mar 19 '13 at 13:13
What if the frequency is the same for all of them? How do you determine which 5 to choose? — Peter Wood, Mar 19 '13 at 13:21

Some programmer dude · Answer 1 · 2013-03-19T13:54:30.060

You could use a std::unordered_map with the stock symbol as the key, and the transaction count as the value. Then just put the five highest in a std::vector and return that.

As for putting the top N in the vector, you could keep it sorted, and re-sort it after every insert so that the stock with the highest transaction count is first. Then it's easy to see if the current stock when iterating over the map has a higher transaction count than the last item in the vector (which is the item in the vector with the smallest transaction count), then add it to the vector and re-sort it.

You could also just add all stocks from the map into a vector, and then sort it using the value in the map, and get the first five entries in the vector.

This can be something like this:

using transaction_map_type = std::unordered_map<std::string, unsigned int>;

transaction_map_type transactions;

// ...

std::vector<std::string> topFiveStocks()
{

    std::vector<transaction_map_type::value_type> all_trans;

    // Copy all transaction into our vector
    std::copy(std::begin(transactions), std::end(transactions),
              std::back_inserter(all_trans));

    // Now sort the transactions
    std::sort(std::begin(all_trans), std::end(all_trans),
              [](const transaction_map_type::value_type& t1,
                 const transaction_map_type::value_type& t2)
              { return t1.second > t2.second; });

    // And get the top five (or less) results into a separate vector
    std::vector<std::string> top_five;

    auto count = std::min(5UL, all_trans.size());
    for (unsigned i = 0; i < count; i++)
        top_five.push_back(all_trans[i].first);

    return top_five;
}

Also, remember to increase the counter for the transactions in the map whenever you do a transaction.

Note: This solution not tested, just written in the browser. May not even compile.

how do i go about doing this? im just learning at the moment and my math isn't really the best in the world. its a random question thats came up online and its would be a useful algorithm to have i recon — Andrew Glass, Mar 19 '13 at 13:24
@AndrewGlass There is very little maths involved here, maybe some addition. — Peter Wood, Mar 19 '13 at 13:27
the way as to which it is performed i think is confusing. can some1 even provide me with an example i could work off? — Andrew Glass, Mar 19 '13 at 13:31
is there a way of doing this without changing it to a vector? like could there not be a loop of some kind which would total each share and if its greater than the previous put it to the top, otherwise place it below the greater?? — Andrew Glass, Mar 19 '13 at 13:53

score 0 · Answer 2 · answered Mar 19 '13 at 13:13

0

Just sort the array and then loop over it to calculate longest interval of elements which are equal.

answered Mar 19 '13 at 13:13

artahian

2,093
14
17

how do i go about doing this? im just learning at the moment and my math isn't really the best in the world. its a random question thats came up online and its would be a useful algorithm to have i recon – Andrew Glass Mar 19 '13 at 13:18

score 0 · Answer 3 · answered Mar 19 '13 at 13:25

0

Accumulate the stock symbols:

the counts into a map<string, int>
the highest 5 symbols into a set<string>
the lowest frequency of the highest 5 symbols into an int
the lowest of the highest 5 symbols into a string

answered Mar 19 '13 at 13:25

Peter Wood

23,859
5
60
99

the way as to which it is performed i think is confusing. can some1 even provide me with an example i could work off? – Andrew Glass Mar 19 '13 at 13:32
I'm not sure I like having messages copied and pasted at me; I'm not a machine. It doesn't look like you're putting much effort into solving this problem for yourself. The problem is, you need to write some code, and not say "I don't know what to write". Write some code and try to get it working. Write the simplest thing you can think of, and try to understand if it doesn't work. Then you can ask far more specific questions than "can you write this for me". – Peter Wood Mar 19 '13 at 13:58
sorry i didnt mean to offend you. – Andrew Glass Mar 19 '13 at 14:06

Top 5 most frequent from an array c++

3 Answers3