3. wordcount mit string

wordcount mit string

  • Mod

    Die Aufgabenstellung war eindeutig nur mit Leerzeichen. Aber alle Lösungen, außer Ethons, sind flexibel was die Definition der Trennung angeht und können leicht auf ein isspace umgestellt werden.

    Flexibilität ist übrigens auch bei dir eine Schwäche. Die Lösung des TE (nach Korrektur), meine, krümelkackers (nach Korrektur) und die des Unregs sind auch leicht anpassbar, Satzzeichen nicht als Wörter zu zählen. Bei dir müsste das auch gehen, aber dazu wären wohl tiefgehende Fummeleien in der Locale nötig, die hier im Forum vielleicht ein oder zwei Personen beherrschen. Umgekehrt kann deine Lösung sich gar nicht an die eigentliche Definition (nur Leerzeichen) halten, außer wieder durch fortgeschrittene Locale-Manipulation.

    0
  • ?

    Da ist was wahres dran. Gut, ich nehme alles zurück.

    0
  • K

    SeppJ schrieb:

    krümelkackers (nach Korrektur)

    Tja, boost::adaptors::transformed (Boost 1.53) mag doch tatsächlich keime Lambdas, da sie nicht sowas wie einen result_type -typedef haben. 😞

    0
  • Mod

    krümelkacker schrieb:

    SeppJ schrieb:

    krümelkackers (nach Korrektur)

    Tja, boost::adaptors::transformed (Boost 1.53) mag doch tatsächlich keime Lambdas, da sie nicht sowas wie einen result_type -typedef haben. 😞

    Da ist übrigens noch ein anderer Fehler drin. Aber den editierst du einfach raus, dann erzähle ich auch niemandem, was dir da peinliches passiert ist 😉 .

    edit: Oh, ich sehe, das hattest du ohnehin schon geändert. Dann hat's sich erledigt.

    0
  • ?

    SeppJ schrieb:

    Bei dir müsste das auch gehen, aber dazu wären wohl tiefgehende Fummeleien in der Locale nötig, die hier im Forum vielleicht ein oder zwei Personen beherrschen.

    Das geht zwar (copy/paste von http://en.cppreference.com/w/cpp/locale/ctype_char beherrschen bis auf ein, zwei Personen alle hier im Forum), ist aber nicht mal nötig.

    struct mystr {};
std::istream& operator>>(std::istream& in, mystr&)
{ std::istreambuf_iterator<char> it(in), end;
  std::find_if(std::find_if(it,end,[](char c){return  isspace(c);}),
               end,                [](char c){return !isspace(c);});
  return in;
}
int wordcount_fummler(string satz) {
  istringstream in(satz);
  return distance(istream_iterator<mystr>(in), istream_iterator<mystr>());
}
    0
  • S

    Edit: Yikes! Da hat schon jemand auf eine praktisch gleiche Lösung verlinkt!
    :duck und weg:

    0
  • W

    Uihh! - ein kleiner Programmier-Contest; da darf mein Beitrag nicht fehlen. std::inner_product hat noch keiner:

    #include <functional> // std::plus<>
#include <iostream>
#include <numeric> // std::inner_product
#include <string>
#include <cctype> // std::isalnum, etc.

namespace werner
{
    int wordcount( const std::string& satz )
    {
        return std::inner_product( begin(satz), end(satz)-1, begin(satz)+1, !satz.empty() && std::isalnum( satz.front() )? 1: 0, std::plus< int >(), 
            []( char prev, char next )->int { return std::isspace( prev ) && std::isalnum( next )? 1: 0; } );
    }
}

int main()
{
    using namespace std;
    for( string satz; cout << "\nGeben Sie einen Satz ein: ", getline( cin, satz ) && satz != "x"; )
        cout << "Sie haben " << werner::wordcount( satz ) << " Woerter eingegeben" << endl;
}

    Beispiel:

    Geben Sie einen Satz ein: Karl-Heinz treibt's um 12:00 bunt -    oder ?
Sie haben 6 Woerter eingegeben

Geben Sie einen Satz ein: Hallo Welt, Du grausame    Welt, hast Tabs und auch Zeilen sowie      Steuerzeichen
Sie haben 12 Woerter eingegeben

    Erkennt "Karl-Heinz" als ein Wort; "-" als kein Wort; leider auch "-oder" als kein Wort ... das würde mehr erfordern, als zwei hinter einander stehende Zeichen zu interpretieren.

    Gruß
    Werner

    0
  • W

    Phil123 schrieb:

    Aufgabe:
    Der Funktion wordcount wird ein String als Argument u¨bergeben. ...

    Derartige Aufgabenstellungen schränken doch bereits die Möglichkeiten der Lösung ein. Wieso eigentlich String? Irgendwie muss der Satz doch auch in den Rechner kommen, also per Input - in C++ auch als std::istream bekannt: zunächst mal das main()

    #include <iostream>
#include <locale> // std::ctype<>

struct WordCounter
{
    WordCounter( int& cnt ) : cnt_( cnt ) {}
    friend std::istream& operator>>( std::istream& in, WordCounter wc );
private:
    int& cnt_;
};

int main()
{
    using namespace std;
    for( int words; cout << "\nGeben Sie einen Satz ein: ", cin >> WordCounter( words ); )
        cout << "Sie haben " << words << " Wort(e) eingegeben" << endl;
}

    fehlt noch die Implementierung des Manipulators WordCounter :

    std::istream& operator>>( std::istream& in, WordCounter wc )
{
    std::istream::sentry ok( in );
    if( ok )
    {
        std::ios_base::iostate state = std::ios_base::goodbit;
        try
        {
            enum Mode { Word, Space } mode = Space;
            wc.cnt_ = 0;
            typedef std::istream::traits_type Tr;
            const std::ctype< char >& ct = std::use_facet< std::ctype< char > >( in.getloc() );
            for( char c = 0; c != '\n'; ) // bis EOL; irgendwo muss Schluss sein
            {
                const Tr::int_type m = in.rdbuf()->sbumpc();
                if( Tr::eq_int_type( m, Tr::eof() ) ) // EOF
                {
                    state |= std::ios_base::eofbit;
                    break;
                }
                c = Tr::to_char_type( m );
                if( ct.is( std::ctype_base::alnum, c ) ) // Wort
                {
                    if( mode == Space ) // Wechsel von Space zu Word -> Wortanfang
                        ++wc.cnt_;
                    mode = Word;
                }
                else if( ct.is( std::ctype_base::space, c ) ) // Leerzeichen
                    mode = Space;
            }
        }
        catch( ... )
        {
            state |= std::ios_base::badbit;
            if( in.exceptions() | std::ios_base::badbit )
                throw;
        }
        in.setstate( state );
    }
    return in;
}

    ein wenig länglich, dafür werden keine Umwege über einen String genommen (siehe auch hier).

    Eine hübsche Aufgabe, und eine nette Übung zur Darstellung von Möglichkeiten zur Programmierung 🕶

    Gruß
    Werner

    0
  • Mod

    Werner Salomon schrieb:

    std::inner_product hat noch keiner:

    😃 👍

    Ich werfe als Herausforderung std::set_symmetric_difference in den Raum.

    0
  • ?

    Ich wag ja kaum, eine Lösung fast ohne Hilfenahme der stl zu präsentieren, aber was sagt ihr hierzu?

    template<class Forward1, class Forward2> inline
Forward1 find_first_notof(Forward1 first1, Forward1 last1,
						  Forward2 first2, Forward2 last2) 
{
	for (; first1 != last1; ++first1)
	{       
		Forward2 mid2;
		for (mid2 = first2; mid2 != last2; ++mid2)
			if (*first1 == *mid2)
				break;
		if(mid2==last2)
			return first1;
	}
	return first1;
}

size_t Count(const string& org, const string& separators)
{
	size_t c = 0;
	string::const_iterator en, be=org.begin();
	do
	{
		en=find_first_of(be, org.end(),separators.begin(), separators.end());
		if(be!=en)
			++c;
		be=find_first_notof(en, org.end(), separators.begin(), separators.end());
	} while(be!=org.end());
	return c;
}

int wordcount_fricker(string satz)
{
	return Count(satz," \n\t -;,.:?!:"); // seperators hinzufügen
}
    0
  • ?

    [quote="SeppJ"]

    Werner Salomon schrieb:

    Ich werfe als Herausforderung std::set_symmetric_difference in den Raum.

    Wozu? Es gibt noch genug einfache Lösungen

    std::string tmp = ' '+s+' ';
return (std::unique(tmp.begin(), tmp.end(),
                    [](char c, char d){return isspace(c)!=isspace(d);})
        - tmp.begin() + 1)/2 << '\n';
    0
  • E

    Euch zuliebe hab ich die count-Lösung mal angepasst:

    int wordcount_Ethon(string satz)
{
    return count_if(satz.begin(), satz.end(), [&](char& c) { return &c == satz.c_str() ? !isspace(c) : isalnum(c) && isspace(*(&c - 1)); });
}
    0
  • ?

    Ethon schrieb:

    Euch zuliebe hab ich die count-Lösung mal angepasst:

    Bitte ohne UB.

    0
  • E

    fummler schrieb:

    Ethon schrieb:

    Euch zuliebe hab ich die count-Lösung mal angepasst:

    Bitte ohne UB.

    Seit C++11 doch kein UB mehr? Was stört?

    Und selbst wenn : Geht doch eh nur ums frickeln. 🤡

    0
  • ?

    Habe auch noch eine Lösung gemacht:

    #include <algorithm>
#include <bitset>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void split( const string& text, vector<string>& words )
{
	bitset<255> separator_lookup;
	separator_lookup.flip();

	const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

	for(; *alphabet; ++alphabet)
	{
		separator_lookup[ *alphabet ] = false;
	}

	string::const_iterator start;
	bool word = false;

	for(string::const_iterator it=text.begin(); it!=text.end(); ++it)
	{
		if( separator_lookup[ *it ] )
		{
			if( word )
			{
				words.push_back( string(start,it) );
				word = false;
			}
		}
		else if( !word )
		{
			start = it;
			word = true;
		}
	}

	if( word )
		words.push_back( string(start,text.end()) );
}

unsigned wordcount( const string& text )
{
	vector<string> words;
	split( text, words );
	return words.size();
}

int main()
{
	string text = "   Hallo Welt, Du grausame    Welt , hast Tabs und auch Zeilen sowie      Steuerzeichen Sie haben 12 Woerter eingegeben   ";

	cout << wordcount( text ) << '\n';
}
    0
  • E

    std::array<bool, N> statt std::bitset<N> - Stackspeicher muss sowieso nicht gespart werden und durch das Bits nudeln geht der Performance-Vorteil flöten. 🕶

    0
  • ?

    Ethon schrieb:

    std::array<bool, N> statt std::bitset<N> - Stackspeicher muss sowieso nicht gespart werden und durch das Bits nudeln geht der Performance-Vorteil flöten. 🕶

    :p
    Wenns nun auch um Performance geht... Man hätte natürlich auch einen einfachen Zähler statt std::vector nehmen können. Aber irgendwann kommt wer, und will neben der Anzahl auch noch die einzelnen Wörter haben.:p

    0
  • ?

    Ethon schrieb:

    std::array<bool, N> statt std::bitset<N> - Stackspeicher muss sowieso nicht gespart werden und durch das Bits nudeln geht der Performance-Vorteil flöten. 🕶

    Habs gerade mal getestet. Du hast Recht. std::array<bool,N> ist sogar deutlich schneller.

    #include <algorithm>
#include <bitset>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <cstdlib>
#include <boost/timer.hpp>
using namespace std;

unsigned wordcount_bitset( const string& text )
{
    bitset<255> separator_lookup;
    separator_lookup.flip();

    const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    for(; *alphabet; ++alphabet)
    {
        separator_lookup[ *alphabet ] = false;
    }

    string::const_iterator start;
    bool word = false;
	unsigned counter = 0;

    for(string::const_iterator it=text.begin(); it!=text.end(); ++it)
    {
        if( separator_lookup[ *it ] )
        {
            if( word )
            {
				++counter;
                word = false;
            }
        }
        else if( !word )
        {
            start = it;
            word = true;
        }
    }

    if( word )
		++counter;

	return counter;
}

unsigned wordcount_std_array( const string& text )
{
    std::array<bool,255> separator_lookup;
	separator_lookup.fill(true);

    const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    for(; *alphabet; ++alphabet)
    {
        separator_lookup[ *alphabet ] = false;
    }

    string::const_iterator start;
    bool word = false;
	unsigned counter = 0;

    for(string::const_iterator it=text.begin(); it!=text.end(); ++it)
    {
        if( separator_lookup[ *it ] )
        {
            if( word )
            {
				++counter;
                word = false;
            }
        }
        else if( !word )
        {
            start = it;
            word = true;
        }
    }

    if( word )
		++counter;

	return counter;
}

int main()
{
	srand( time(NULL) );

	const unsigned SIZE = 1000000000; // 1 Mrd.
	string text( SIZE, 'x' );

	for(unsigned i=0; i!=SIZE/100; ++i)
	{
		if( i%100 )
			text[i] = ' ';
	}

	boost::timer timer;

	// wordcount_bitset
	timer.restart();
	unsigned words = wordcount_bitset( text );
	cout << "wordcount_bitset: " << timer.elapsed() << "s  |  Words: " << words << '\n'; // 6,9 Sekunden

	// wordcount_std_array
	timer.restart();
	words = wordcount_std_array( text );
	cout << "wordcount_std_array: " << timer.elapsed() << "s  |  Words: " << words << '\n'; // 1,4 Sekunden
}
    0
  • ?

    Huch, das srand hat da drin natürlich nichts mehr verloren.

    0
  • ?

    Hab das Ganze eben noch mit vector<bool> und vector<char> getestet:

    std::vector<bool>: 2,8 Sekunden
    std::vector<char>: 1,4 Sekunden

    array<bool,255> und vector<char>( 255, true ) sind gleich schnell. 🤡

    0
Anmelden zum Antworten