In article <39b8cf06$1@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> #include <iostream>
> #include <map>
> #include <string>
> using namespace std;
> int main()
> { typedef map<string,unsigned> wlist_t;
>   wlist_t words;
>   string word;
>   while(cin) { cin >> word; words[word]++; }
>   for(wlist_t::iterator i=words.begin(); i!=words.end(); i++)
>     cout << i->first << ": " << i->second << endl;
> }

The return is missing...

>
>   It reads words from the standard input (a word is limited by whitespaces)
> and then outputs an alphabetically ordered list of the words and a number
> indicating the amount of times the word appears in the text.
>
>   Try to make that without using any STL. It must be at least as fast as
> this one.
>   How many code lines do you need? How much time do you need to make it?

Hmm, lets see, you need (runtimes from the C++ Prog. Lang 3rd Ed. page
464)...

For inserting:       O(n * log(n))
For retrieval:       O(n * log(n))
Total:               O(n * log(n) + n * log(n))


I can get:

For inserting:       O(n)
For sorting *:       O(n * log(n))
For retrieval:       O(n)
Total:               O(2 * n + n * log(n))

* No fancy algorithm, just quicksort.


How?  That is simple:  I read in the words. Then sort them and then just
count when retrieving.

Of course I can do this using the STL (see below)!  But your example shows
something dangerous you forgot:  the STL can trick you into thinking you
have found a good algorithm, but in fact yours is nearly log(n) times slower
than mine for most cases (for log(n) > 2)!

The condensed version (readable version at the end):

#include <iostream>
#include <list>
#include <string>
using namespace std;
void main() {
    typedef list<string> wlist_t;
    wlist_t words;
    string word;
    while(cin) { cin >> word; words.push_back(word); }
    words.sort();
    for(wlist_t::iterator i = words.begin(); i != words.end();) {
        wlist_t::iterator temp = i; int cnt = 0;
        for(; i != words.end(); i++, cnt++) if(*i != *temp) break;
        cout << *temp << ": " << cnt << endl;
}   }


Note that I can also provide a standard C only version which is less than
twice the length, supports dynamic string length and should be slightly
faster that this version by using some tricks.


      Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org




The more readable version of my program:


#include <iostream>
#include <list>
#include <string>

using namespace std;

void main()
{
    typedef list<string> wlist_t;
    wlist_t words;
    string word;

    while(cin)
    {
        cin >> word;
        words.push_back(word);
    }

    words.sort();

    for(wlist_t::iterator i = words.begin(); i != words.end();)
    {
        wlist_t::iterator temp = i;
        int cnt = 0;

        for(; i != words.end(); i++, cnt++)
        {
         if(*i != *temp)
          break;
        }
        cout << *temp << ": " << cnt << endl;
    }
}

Post a reply to this message