Occurence problem: different ideas

U

utab

Dear all,

I tried to solve the occurence problem: to find the distinct occurences
of a word in an input. I know that I could use map and other STD lib
functions. I tried to do it the hard way. I tried sth and it is working
but I could not structure my algorithm very well so I had to add some
more lines after thinking it on a paper draft. I am posting the whole
code and waiting different ideas.
First I sorted them with the sort function, after that they are in
nondecreasing order(and also grouped by this way) and then I have
counted the number of items in these groups by checking whether I am at
the end or not

1 #include <iostream>
2 #include <algorithm>
3 #include <string>
4 #include <vector>
5 int main(){
6
7 std::string x;
8 std::vector<std::string> input;
9 std::vector<std::string> sorted_input;
10 std::vector<std::string> words;
11 std::vector<int> counts;
12 std::vector<std::string>::size_type vec_sz;
13 int count=1;
14
15
16 while(std::cin >> x)
17 input.push_back(x);
18
19 sort(input.begin(),input.end());
20
21 std::string test=input[0];
22
23 vec_sz=input.size();
24
25 for(int i=0;i!=vec_sz;++i)
26 std::cout << input << std::endl;
27
28
29 for(int k=1;k!=vec_sz;++k){
30
31 if(input[k]==test){
32 ++count;
33 if(k==vec_sz-1){
34 words.push_back(test);
35 counts.push_back(count);
36 }
37 }
38 else{
39 words.push_back(test);
40 counts.push_back(count);
41 test=input[k];
42 count=1;
43 if(k==vec_sz-1){
44 words.push_back(test);
45 counts.push_back(count);
46 }
47 }
48 }
49
50 vec_sz=words.size();
51 std::cout << "WORDS" <<"\t"<<"OCCURENCE#"<<std::endl;
52 for(int i=0;i!=vec_sz;++i)
53 std::cout << words<<"\t" << counts<<
std::endl;
54
55 return 0;
56
57 }
 
M

Mike Wahler

utab said:
Dear all,

I tried to solve the occurence problem: to find the distinct occurences
of a word in an input. I know that I could use map and other STD lib
functions.

Then why don't you?
I tried to do it the hard way.
Why?

I tried sth and it is working
but I could not structure my algorithm very well so I had to add some
more lines after thinking it on a paper draft. I am posting the whole
code and waiting different ideas.

My idea is to use those tools suited for a particular purpose,
e.g. a map in this case.
First I sorted them with the sort function, after that they are in
nondecreasing order(and also grouped by this way) and then I have
counted the number of items in these groups by checking whether I am at
the end or not

See below.
1 #include <iostream>
2 #include <algorithm>
3 #include <string>
4 #include <vector>
5 int main(){
6
7 std::string x;
8 std::vector<std::string> input;
9 std::vector<std::string> sorted_input;
10 std::vector<std::string> words;
11 std::vector<int> counts;
12 std::vector<std::string>::size_type vec_sz;
13 int count=1;
14
15
16 while(std::cin >> x)
17 input.push_back(x);
18
19 sort(input.begin(),input.end());
20
21 std::string test=input[0];
22
23 vec_sz=input.size();
24
25 for(int i=0;i!=vec_sz;++i)
26 std::cout << input << std::endl;
27
28
29 for(int k=1;k!=vec_sz;++k){
30
31 if(input[k]==test){
32 ++count;
33 if(k==vec_sz-1){
34 words.push_back(test);
35 counts.push_back(count);
36 }
37 }
38 else{
39 words.push_back(test);
40 counts.push_back(count);
41 test=input[k];
42 count=1;
43 if(k==vec_sz-1){
44 words.push_back(test);
45 counts.push_back(count);
46 }
47 }
48 }
49
50 vec_sz=words.size();
51 std::cout << "WORDS" <<"\t"<<"OCCURENCE#"<<std::endl;
52 for(int i=0;i!=vec_sz;++i)
53 std::cout << words<<"\t" << counts<<
std::endl;
54
55 return 0;
56
57 }


#include <ios>
#include <iostream>
#include <map>
#include <string>

int main()
{
std::map<std::string, std::streamsize> m;
std::string word;

std::cout << "Enter data: ";

while(std::cin >> word)
++m[word];

std::map<std::string, std::streamsize>::
const_iterator it(m.begin());

const
std::map<std::string, std::streamsize>::
const_iterator en(m.end());

while(it !=en)
{
std::cout << it->first << " occurs "
<< it->second << " times.\n";
++it;
}

return 0;
}

Test run:
--------------------------------------------------------------------------------
Enter data: In base class, I have a function "Initialize(int a)". In the
derived

class , I need the funciton "Initialized" to do more things, therefore
I redefined the function as "Initialize(int a, int b)".

Now I want the Derived::initialize to include all the operations
contained in Base::initialize. Are there and simple ways to do that?
Currently, I just copy all the codes in Base::initialize to
Derived::initialize.

Thanks.
^Z
"Initialize(int occurs 2 times.
"Initialized" occurs 1 times.
, occurs 1 times.
Are occurs 1 times.
Base::initialize occurs 1 times.
Base::initialize. occurs 1 times.
Currently, occurs 1 times.
Derived::initialize occurs 1 times.
Derived::initialize. occurs 1 times.
I occurs 5 times.
In occurs 2 times.
Now occurs 1 times.
Thanks. occurs 1 times.
a occurs 1 times.
a)". occurs 1 times.
a, occurs 1 times.
all occurs 2 times.
and occurs 1 times.
as occurs 1 times.
b)". occurs 1 times.
base occurs 1 times.
class occurs 1 times.
class, occurs 1 times.
codes occurs 1 times.
contained occurs 1 times.
copy occurs 1 times.
derived occurs 1 times.
do occurs 2 times.
funciton occurs 1 times.
function occurs 2 times.
have occurs 1 times.
in occurs 2 times.
include occurs 1 times.
int occurs 1 times.
just occurs 1 times.
more occurs 1 times.
need occurs 1 times.
operations occurs 1 times.
redefined occurs 1 times.
simple occurs 1 times.
that? occurs 1 times.
the occurs 6 times.
there occurs 1 times.
therefore occurs 1 times.
things, occurs 1 times.
to occurs 4 times.
want occurs 1 times.
ways occurs 1 times.
--------------------------------------------------------------------------------
-Mike


P.S. BTW if you want help, you should make it
easy for folks to help. With those line numbers
we can't paste and compile your code. It was
far easier for me to show you how I would do it
than to try to make your code compilable. (imo
your code is far more complicated than need be
anyway).
 
D

Daniel T.

"utab said:
Dear all,

I tried to solve the occurence problem: to find the distinct occurences
of a word in an input. I know that I could use map and other STD lib
functions. I tried to do it the hard way.

You could have made it much harder on yourself and not used vector. Why
are you willing to use vector but not map or set?

I tried sth and it is working
but I could not structure my algorithm very well so I had to add some
more lines after thinking it on a paper draft. I am posting the whole
code and waiting different ideas.

Here's one solution:

struct word_count
{
word_count( string w, int c ): word( w ), count( c ) { }
string word;
int count;
};

struct word_is : unary_function<word_count, bool >
{
string word;
word_is( string w ): word( w ) { }
bool operator()( word_count wc ) const
{
return wc.word == word;
}
};

template < typename container >
void count_input_words( istream& is, container& c )
{
string s;
while ( is >> s ) {
word_count wc( s, 1 );
typename container::iterator it =
find_if( c.begin(), c.end(), word_is( s ) );
if ( it == c.end() )
c.push_back( wc );
else
++it->count;
}
}

ostream& operator<<( ostream& os, word_count wc )
{
return os << wc.word << "\t" << wc.count;
}

int main()
{
vector<word_count> result;
count_input_words( cin, result );
std::cout << "WORDS\tOCCURENCE#\n";
copy( result.begin(), result.end(),
ostream_iterator<word_count>( cout, "\r" ) );
}

Seems pretty easy to understand, we have only one function with a
Cyclomatic Complexity over 1, and it only has a CC of 3. Compare that to
your code with a CC of 8.

Of course my code doesn't sort the words. That may be part of the
requirements, and would probably also speed up the algorithm by reducing
search time.

It's a simple change. Just change out "word_is" for a StrictWeakOrdering
comparison functor, and switch out the "find_if" for "lower_bound". That
and a minor change to the "if" statement and you are good to go. (I'll
leave it as an exorcise for the reader to implement though. :)
 
P

Pavel

utab said:
Dear all,
It is difficult to change your code to better without knowing where you
plan to move with it. If you want to create a useful word counting
class, you may consider methods for inputting another word, getting word
counter for a given word, getting an iterator for word counters for all
words etc.. If this is just a sample program, nothing is particularly
wrong (except for not processing the case where there is no words on the
strandard input..).

As for the selected data structure, yours will probably be the fastest
of suggested alternatives (linear search and ordered map as far as I
could understand), especially if you have a good idea about the target
size for your vector and reserve it in the beginning. Hashmap could be
even faster in most of the cases (depending on the implementation and
words on the input stream); it is coming into the Standard from TR1 as
std::tr1::unordered_set..

Hope this will help,
Pavel
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top