Re: C++ programming challenge
Peter Jansson wrote:
Dear news group,
I have created a small programming challenge for those of you who are
interested in challenging your Standard C++ programming skills. The
challenge is about counting character frequency in large texts,
perhaps useful for spam filtering or classical crypto analysis. You
can read more about it here:
http://blog.p-jansson.com/2009/06/programming-challenge-letter-
frequency.html
With kind regards,
Peter Jansson
Lets see how the std algorithms measure up to the rest (only tested on
its own source so far):
#include <fstream>
#include <iostream>
#include <numeric>
#include <map>
#include <ctype.h>
#include <iterator>
#include <algorithm>
#include <time.h>
struct accum_original
{
std::map<char, long> counts;
long total;
accum_original() : counts(), total(0) {}
void count_char(char c)
{
total++;
counts[tolower((unsigned char)c)]++;
}
const std::map<char, long>& getCounts()
{
return counts;
}
long getTotal()
{
return total;
}
};
struct accum_fast
{
struct data {
std::map<char, long> counts;
long total;
int refcount;
data() : counts(), total(0), refcount(1) {}
}* payload;
accum_fast() : payload(new data) {}
accum_fast(const accum_fast& other) : payload(other.payload) {
payload->refcount++; }
~accum_fast() { if (--payload->refcount == 0) { delete payload; } }
void swap(accum_fast& other)
{
data* temp(other.payload);
other.payload = payload;
payload = temp;
}
accum_fast& operator=(accum_fast rhs)
{
swap(rhs);
return *this;
}
void count_char(char c)
{
payload->total++;
payload->counts[tolower((unsigned char)c)]++;
}
const std::map<char, long>& getCounts()
{
return payload->counts;
}
long getTotal()
{
return payload->total;
}
};
typedef accum_fast accum;
accum count_chars(accum acc, char c)
{
acc.count_char(c);
return acc;
}
struct scaler
{
long total;
scaler(long total_) : total(total_) {}
std::pair<const char, double> operator()(std::pair<const char, long>
value)
{
return std::pair<const char, double>(value.first,
(100.0*value.second)/total);
}
};
namespace std {
ostream& operator<<(ostream& os, const pair<const char, double>& value)
{
os << '\'' << value.first << "' " << value.second << "%\n";
return os;
}
}
int main(int argc, char** argv)
{
clock_t time1, time2;
accum acc;
if (argc < 2)
{
time1 = clock();
acc = std::accumulate(std::istream_iterator<char>(std::cin),
std::istream_iterator<char>(), acc, count_chars);
}
else
{
time1 = clock();
std::ifstream file(argv[1]);
acc = std::accumulate(std::istream_iterator<char>(file),
std::istream_iterator<char>(), acc, count_chars);
}
std::transform(acc.getCounts().begin(), acc.getCounts().end(),
std::ostream_iterator<std::pair<const char, double>
(std::cout, ""),
scaler(acc.getTotal()));
time2 = clock();
std::cout << "Time taken: " << (time2 - time1) << " clock ticks = " <<
(time2 - time1)*1.0/CLOCKS_PER_SEC << " seconds" << std::endl;
}
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://c-faq.com/
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/