Counting the occurrences of bank account numbers for SPOJ challenge

Question

I am solving a problem on SPOJ and am currently unsatisfied with my submission time, given that my fastest time is 0.28s (which ranks me 123/5037) and the leading submission is 0.04s.

The problem is pretty simple: Given a list of bank account numbers, print the bank account number along with the frequency at which it is repeated.

Input

t [the number of tests <= 5]
n [the number of accounts<= 100 000]

[list of accounts]
[empty line]
[next test cases]

Output

[sorted list of accounts with the number of repeated accounts]
[empty line]
[other results]

Example:

Input:
2
6
03 10103538 2222 1233 6160 0142 
03 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 

5
30 10103538 2222 1233 6160 0144 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0145 
30 10103538 2222 1233 6160 0146 
30 10103538 2222 1233 6160 0143 

Output:
03 10103538 2222 1233 6160 0141 1
03 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0141 2
30 10103538 2222 1233 6160 0142 2

30 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0143 1
30 10103538 2222 1233 6160 0144 1
30 10103538 2222 1233 6160 0145 1
30 10103538 2222 1233 6160 0146 1

In order to solve this, I am using a map where the key is the bank account and the value is the frequency of repetition. However, I am first loading the bank accounts into a vector, and I am pretty sure this is one area where I am losing efficiency. I have tried to avoid using the vector, but my efficiency is greatly reduced.

What are some things that I can do to either improve my algorithm, or perhaps increase my I/O speed?

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int t;
  std::cin >> t;
  while (t--) {
    int n, i;
    std::cin >> n;
    std::cin.ignore();
    std::vector<std::string> accounts(n);
    for (i = 0; i < n; ++i) {
      std::getline(std::cin, accounts[i]);
    }
    std::cout << "\n";
    std::map<std::string, int> count;
    for (i = 0; i < accounts.size(); ++i) {
      auto map_it(count.find(accounts[i]));
      if (map_it != count.end()) {
        map_it->second++;
      } else {
        count[accounts[i]] = 1;
      }
    }
    for (auto it = count.begin(); it != count.end(); ++it) {
      std::cout << it->first << it->second << "\n";
    }
    if (t != 0) {
      std::string blank;
      std::getline(std::cin, blank);
    }
  }
  return 0;
}

Answer 1

One area of inefficiency is here:

for (i = 0; i < n; ++i) {
  std::getline(std::cin, accounts[i]);
}
std::cout << "\n";
std::map<std::string, int> count;
for (i = 0; i < accounts.size(); ++i) {
  auto map_it(count.find(accounts[i]));
  if (map_it != count.end()) {
    map_it->second++;
  } else {
    count[accounts[i]] = 1;
  }
}

You're reading each account number, storing them then going back through the data to get the counts. The map class allows for a key that doesn't exist to create an entry on the fly. Using this will eliminate the second loop:

std::string temp = "";
std::map<std::string, int> count;
for (i = 0; i < n; ++i) {
  std::getline(std::cin, temp);
  count[temp]++; 
}
std::cout << "\n";

Answer 2

This is a fairly easy to read straightforward implementation, which is nice to see. Here are a few things you could do to improve it:

Naming

Some of your names like accounts are good, but others of your names are very basic and essentially meaningless. Using i for a loop iterator is fine, but n and t tell me nothing about what they stand for. I would rename t to numTests and n to numAccounts to make it clearer. I would also inline my loop iterator definitions since you're not using them outside of the loops, like this:

for (int i = 0; i < numAccounts; ++i) {

The names it and map_it are really confusing. it could be anything. Since it's an iterator, maybe 2 more characters to make it iter instead? I prefer to use next<whatever> where "whatever" is the thing you are iterating over. In this case it would be nextAccount.

Performance

@tinstaafl had a good suggestion for improving performance in their answer. There are some common themes with these types of problems. One thing that has helped in other tests like this that I've reviewed or done myself is to sort things before counting them. I don't know whether that would be faster in this case or not, but it's worth trying.

What sorting does is makes it much easier to count, and it improves CPU cache coherency. You end up with an array that looks something like this:

a, a, a, b, b, c, c, c, c, c, d, e, e, ... etc.

Now you're always working with one item until you've counted all instances, and then you move on to the next one, and do the same. You're not jumping back and forth in either the array of accounts or the array of counts. This type of memory access is considerably faster for a CPU.

You could either do an insertion sort as you read them from the input (probably not the fastest way), or you could use a faster sort after-the-fact.

Whatever you do, profile your code to see what it is that's slowing you down. You will often be surprised by the result. It could be I/O; it could be the counting; but you won't know until you actually measure it.