3. Letztes Wort loeschen

Letztes Wort loeschen

  • C

    Ok, danke. Ja, lesbar sollte es schon noch bleiben.

    0
  • Mod

    CppNeuland schrieb:

    Ok, danke. Ja, lesbar sollte es schon noch bleiben.

    Ich habe noch einen Fehler entdeckt und oben eine Erklärung rein editiert, während du meine (uneditierte) Antwort gelesen hast. Den Fehler solltest du dir ansehen.

    0
  • N

    SeppJ schrieb:

    Nein, ist gar nicht ok. pop_back kann die Iteratoren ungültig machen.

    Echt?
    Beim vector bleiben doch Iteratoren nach erase gültig, so lange sie nicht hinter den Bereich zeigen, der gelöscht wird.
    Und string ist doch im Inneren vector. Oder ist da was ganz falsch?

    0
  • ?

    Nathan schrieb:

    SeppJ schrieb:

    Nein, ist gar nicht ok. pop_back kann die Iteratoren ungültig machen.

    Echt?
    Beim vector bleiben doch Iteratoren nach erase gültig, so lange sie nicht hinter den Bereich zeigen, der gelöscht wird.
    Und string ist doch im Inneren vector. Oder ist da was ganz falsch?

    Beim vector ist nachher immer noch alles gültig.

    Das Interface von std::string soll aber SSO-geeignet sein und der Inhalt darf bei pop_back in den String reingepackt werden.

    0
  • Mod

    Nathan schrieb:

    SeppJ schrieb:

    Nein, ist gar nicht ok. pop_back kann die Iteratoren ungültig machen.

    Echt?

    Ja, mich hat's auch überrascht, aber ich habe es extra nochmal nach geguckt.

    mr. wrong schrieb:

    Das Interface von std::string soll aber SSO-geeignet sein und der Inhalt darf bei pop_back in den String reingepackt werden.

    Das wird wohl der Grund sein. Alternativ bei Copy on write Optimierung (also das, was vor C++11 üblich war) gilt das auch. Daher war wohl auch erase beim string immer schon eine Funktion, die alle Iteratoren und Zeiger ungültig macht (pop_back ist neu in C++11).

    0
  • ?

    SeppJ schrieb:

    Der Algorithmus kann nicht wesentlich verbessert werden und die Umsetzung ist ebenfalls gut und lesbar.

    Völlig falsch!

    #include <iostream>
#include <algorithm>
#include <cassert>
#include <string>
#include <chrono>

void neuland(std::string &s)
{
  std::string::reverse_iterator i;
  for(i = s.rbegin(); i != s.rend(); ++i)
    if (*i == ' ')
      break;
  s.erase(i.base()-1, s.end());
}

void mrwrong(std::string& s)
{
  const char x = ' ';
  __m128i zero = _mm_setzero_si128();
  __m128i cx16 = _mm_set1_epi8(x);
  const char *start=s.c_str(), *b = start + s.size();
  for (int i=s.size()%16;i--;)
    if (*--b == x)
      goto end;
  for (b -= 16;; b -= 16) {
    __m128i  x = _mm_loadu_si128((__m128i const *)b);
    unsigned u = _mm_movemask_epi8(_mm_cmpeq_epi8(zero, x));
    unsigned v = _mm_movemask_epi8(_mm_cmpeq_epi8(cx16, x)) & ~u & (u - 1);
    if (v) { b += __builtin_ctz(v); goto end; }
    if (__builtin_expect(b == start,0)) { return; }
  }
 end:
  s.erase(b - start);
}

template <typename F, typename... T>
void mesure(const char *name, F f, T&&... args)
{
  auto start = std::chrono::high_resolution_clock::now();
  f(std::forward<T>(args)...);
  auto stop = std::chrono::high_resolution_clock::now();

  std::cout << name << ": "
            << std::chrono::duration_cast<std::chrono::nanoseconds>(stop-start).count()
            << " ns" << std::endl;
}

template <typename F>
void test(const char *name, F f)
{
  const int size=10000000;
  static std::string s; s.clear();
  while (s.size() < size)
    s.push_back(rand()%26 + 'a');
  unsigned x = rand()%16;
  s[x] = ' ';
  mesure(name, f, s);
  assert(s.size() == x);
}

int main()
{
  srand(0);
  for (int i=0; i<16; ++i) {
    test("mrwrong", [](std::string&s){mrwrong(s);});
    test("neuland", [](std::string&s){neuland(s);});
  }
}

    erzeugt bei mir:

    mrwrong: 4629926 ns
neuland: 15678281 ns
mrwrong: 3502405 ns
neuland: 15370140 ns
mrwrong: 3446578 ns
neuland: 15330838 ns
mrwrong: 3500771 ns
neuland: 15379725 ns
mrwrong: 3590104 ns
neuland: 15347023 ns
mrwrong: 3565236 ns
neuland: 15342064 ns
mrwrong: 3580317 ns
neuland: 15345939 ns
mrwrong: 3636245 ns
neuland: 15349274 ns
...

    Also Faktor 5 Unterschied. Der Unterschied dürfte bei neueren Prozessoren mit mehr SSE-Unterstützung noch grösser sein.

    Etwa gleich schnell ist

    void alternative(std::string &s)
{
  s.erase(strrchr(s.c_str(), ' ') - s.c_str());
}

    aber nur, wenn der Character ' ' am Anfang ist, im anzunehmenden Fall, dass das Whitespace eher am Ende zu finden ist, ist das sogar schlechter als die neuland-Variante.

    0
  • N

    mr. wrong schrieb:

    void mrwrong(std::string& s)
{
  const char x = ' ';
  __m128i zero = _mm_setzero_si128();
  __m128i cx16 = _mm_set1_epi8(x);
  const char *start=s.c_str(), *b = start + s.size();
  for (int i=s.size()%16;i--;)
    if (*--b == x)
      goto end;
  for (b -= 16;; b -= 16) {
    __m128i  x = _mm_loadu_si128((__m128i const *)b);
    unsigned u = _mm_movemask_epi8(_mm_cmpeq_epi8(zero, x));
    unsigned v = _mm_movemask_epi8(_mm_cmpeq_epi8(cx16, x)) & ~u & (u - 1);
    if (v) { b += __builtin_ctz(v); goto end; }
    if (__builtin_expect(b == start,0)) { return; }
  }
 end:
  s.erase(b - start);
}

    👍

    0
  • C

    Das muss ich erst mal verdauen, da lernt man doch die Profis schätzen. 😮

    0
  • M

    bedenke aber, dass der Code mr. wongs code plattform- und compilerabhängig ist.
    Wenn es weiterhin unabhängig sein soll, musst du schon mit präprozessorcommandos etwas basteln, um im Notfall auf deine alte Methode zurückzuspringen.

    0
  • C

    Unabhängig vom OS sollte es schon sein. Ich programmiere mit dem Qt-Creator unter OSX und die Sachen sollten dann aber auch unter Linux, Windows und Android laufen.

    Nichts desto Trotz ist die Lösung von MrWrong schon beeindruckend. Ich habe früher auf dem Amiga mit dem Seka-Assembler so Demos programmiert und daher ist eine Restfaszination für die einzig reale Computersprache immer noch da.

    Mittlerweile bin ich aber über die vielen Abstraktionsebenen doch froh 😃

    EDIT: So, ohne Spezialfälle habe ich es jetzt so gelöst. Gibt es damit auch Probleme?

    _text.erase(_text.find_last_of(' '));
    0
  • ?

    CppNeuland schrieb:

    EDIT: So, ohne Spezialfälle habe ich es jetzt so gelöst. Gibt es damit auch Probleme?

    _text.erase(_text.find_last_of(' '));

    Ja, string::erase() löst eine out_of_range exception aus falls im string kein Leerzeichen gefunden wird (find_last_of() == string::npos).

    - osdt

    0
  • ?

    Nathan schrieb:

    mr. wrong schrieb:

    void mrwrong(std::string& s)
{
  const char x = ' ';
  __m128i zero = _mm_setzero_si128();
  __m128i cx16 = _mm_set1_epi8(x);
  const char *start=s.c_str(), *b = start + s.size();
  for (int i=s.size()%16;i--;)
    if (*--b == x)
      goto end;
  for (b -= 16;; b -= 16) {
    __m128i  x = _mm_loadu_si128((__m128i const *)b);
    unsigned u = _mm_movemask_epi8(_mm_cmpeq_epi8(zero, x));
    unsigned v = _mm_movemask_epi8(_mm_cmpeq_epi8(cx16, x)) & ~u & (u - 1);
    if (v) { b += __builtin_ctz(v); goto end; }
    if (__builtin_expect(b == start,0)) { return; }
  }
 end:
  s.erase(b - start);
}

    👍

    Ich dachte bis jetzt "goto" soll man nicht verwenden?

    0
  • Mod 

    mrwrong: 1531876 ns
arcoth: 3441873 ns
neuland: 5500253 ns
[...]
mrwrong: 968054  ns
arcoth : 3047209 ns
neuland: 4573583 ns
mrwrong: 958147  ns
arcoth : 3222022 ns
neuland: 4567348 ns

    Die Ausgabe bekomme ich, wenn ich mrwrongs, CppNeulands neuesten und meinen Code, der im Übrigen - soweit ich sehe - plattformunabhängig ist, vergleiche. Am meisten unnötige Zeit schluckt wohl die Funktion

    qword qword_from( char const* p )
{
	return  *p
	       | ( qword(p[1]) << 8 )
	       | ( qword(p[2]) << 16 )
	       | ( qword(p[3]) << 24 )
	       | ( qword(p[4]) << 32 )
	       | ( qword(p[5]) << 40 )
	       | ( qword(p[6]) << 48 )
	       | ( qword(p[7]) << 56 );
}

    , dafür nimmt mrwrong in seiner Variante natürlich _mm_loadu_si128 . Wenn ich stattdessen die UB-Methode nehme,

    qword qword_from( char const* p )
{
	return *reinterpret_cast<qword const*>(p);
}

    bekomme ich etwa

    mrwrong: 1502699 ns
arcoth : 1395314 ns
neuland: 7582803 ns
[...]
mrwrong: 981523  ns
arcoth : 1093849 ns
neuland: 4553076 ns
mrwrong: 887963  ns
arcoth : 1098256 ns
neuland: 4938181 ns

    Ich dachte bis jetzt "goto" soll man nicht verwenden?

    Das ist nur eine Faustregel, um Spaghetti-Code zu vermeiden. Hier vereinfacht es den Code.

    0
  • C

    osdt schrieb:

    CppNeuland schrieb:

    EDIT: So, ohne Spezialfälle habe ich es jetzt so gelöst. Gibt es damit auch Probleme?

    _text.erase(_text.find_last_of(' '));

    Ja, string::erase() löst eine out_of_range exception aus falls im string kein Leerzeichen gefunden wird (find_last_of() == string::npos).

    - osdt

    Aja, na dann versuche ich es mal so:

    size_t pos = _text.find_last_of(' ');
        if ( pos != string::npos )
            _text.erase(pos);
    0
  • ?

    Und wenn der ganze String ein Wort ist?

    0
  • C

    Spezialfälle habe ich jetzt nicht mit drin, aber in diesem Fall wird ja erase übersprungen. Die ganze Sache ist eh nur um das Command Pattern mal an einem konkreten Minimalbeispiel mir klar zu machen. Das wird also nie so irgendwie produktiv laufen.

    Ich hatte halt zwei Beispielklassen mit Text, eine kann Zeichen hinzufügen und das letzte Zeichen löschen und eine kann dies mit Worten tun. Und beim Wort löschen kam ich dann auf die erste Lösung hier...der Rest ist bekannt.

    0
Anmelden zum Antworten