|
![](/i/fill.gif) |
In article <39b8cf06$1@news.povray.org> , Warp <war### [at] tag povray org> 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] trf de
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
|
![](/i/fill.gif) |