3. [Hilfe] Suchen nach 10stelliger zahl in Text

[Hilfe] Suchen nach 10stelliger zahl in Text

  • ?

    Das dürfte aus dem Kontext her ersichtlich sein. Ich schlage (gegen deine willkürliche Intuition) vor, dir den Code einmal selbst anzuschauen und mal zu sehen, was er bedeutet. Da gibt es ein Variäbelchen 'len', das dürfte vielversprechend sein.

    0
  • ?

    otze schrieb:

    Zum Beispiel dort, wo jetzt die 10 steht?

    Genau, otze. Einfach alle 10er durch 11er ersetzen, dann klappts 😃

    0
  • ?

    ja is klar ich hab mir auch den code angeschaut so is es ja nicht nur geht meine Idee nicht so wirklich siehe..

    #include <iostream>
#include <string>

std::string getNumber(const std::string& str, std::size_t len, std::size_t len2);

int main()
{
    std::string str = "009asbdfap91234usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd";

    std::cout << getNumber(str, 10, 11);
}

std::string getNumber(const std::string& str, std::size_t len, std::size_t len2)
{
    std::size_t newPos = 0, nextPos = 0;

    for (;(newPos = str.find_first_of("0123456789", newPos)) != std::string::npos && (nextPos = str.find_first_not_of("0123456789", newPos)) - newPos != len && newPos != len2 && nextPos != std::string::npos;++newPos);

    if (newPos != std::string::npos && nextPos != std::string::npos)
        return str.substr(newPos, nextPos - newPos);

    return "";
}
    0
  • ?

    Ich hab die Funktion noch etwas angepasst, da sie in einigen Situationen nicht korrekt funktioniert hat.

    Hier das Ergebnis:

    #include <iostream>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
    std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

	for (int i = 0; i <= 30; ++i)
	{
		std::cout << i << " => " << getNumber(str, i) << std::endl;
	}
}

std::string getNumber(const std::string& str, std::size_t len)
{
    std::size_t newPos = 0, nextPos = 0;
	for (;(newPos = str.find_first_of("0123456789", newPos)) != std::string::npos && ((nextPos = (str + "#").find_first_not_of("0123456789", newPos)) - newPos != len); newPos += 1 + (nextPos != std::string::npos ? nextPos - newPos : 0));

    if (newPos != std::string::npos && nextPos != std::string::npos)
        return str.substr(newPos, nextPos - newPos);

    return "";
}

    Die Funktion wird einfach mehrmals aufgerufen, um Zahlen verschiedener Länge zu extrahieren. Das scheint auch alles perfekt zu klappen, aber durch die Verbesserungen wird die Funktion so langsam unübersichtlich. 😉

    0
  • ?

    fghfgh schrieb:

    durch die Verbesserungen wird die Funktion so langsam unübersichtlich. 😉

    Darum:

    #include <iostream>
#include <algorithm>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  for (int i = 0; i <= 30; ++i) {
    std::cout << i << " => " << getNumber(str, i) << std::endl;
  }
}

bool first_is_digit(char c, char) { return std::isdigit(c); }

std::string getNumber(const std::string& str, std::size_t len)
{
  std::string::const_iterator pos = std::search_n(str.begin(), str.end(), len, '\0', first_is_digit);
  if (pos == str.end())
    return "";
  return std::string(pos, pos + len); 
}
    0
  • ?

    westerwello schrieb:

    fghfgh schrieb:

    durch die Verbesserungen wird die Funktion so langsam unübersichtlich. 😉

    Darum:

    #include <iostream>
#include <algorithm>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  for (int i = 0; i <= 30; ++i) {
    std::cout << i << " => " << getNumber(str, i) << std::endl;
  }
}

bool first_is_digit(char c, char) { return std::isdigit(c); }

std::string getNumber(const std::string& str, std::size_t len)
{
  std::string::const_iterator pos = std::search_n(str.begin(), str.end(), len, '\0', first_is_digit);
  if (pos == str.end())
    return "";
  return std::string(pos, pos + len); 
}

    Grundsätzlich: 👍

    Aber, Ausgabe:

    0 =>
    1 => 0
    2 => 00
    3 => 002
    4 => 9123
    5 => 91234
    6 => 987650
    7 => 9876503
    8 => 98765038
    9 => 987650386
    10 => 9876503864
    11 => 92183912839
    12 => 921839128398
    13 => 9218391283981
    14 => 92183912839812
    15 => 921839128398123
    16 => 9218391283981239
    17 => 92183912839812398
    18 => 921839128398123981
    19 => 9218391283981239812
    20 =>
    21 =>
    22 =>
    23 =>
    24 =>
    25 =>
    26 =>
    27 =>
    28 =>
    29 =>
    30 =>

    vs.

    0 =>
    1 => 9
    2 =>
    3 => 002
    4 =>
    5 => 91234
    6 => 123123
    7 => 0123311
    8 =>
    9 =>
    10 => 9876503864
    11 =>
    12 =>
    13 =>
    14 =>
    15 =>
    16 =>
    17 =>
    18 => 129381289381290312
    19 => 9218391283981239812
    20 =>
    21 =>
    22 =>
    23 =>
    24 =>
    25 =>
    26 =>
    27 =>
    28 =>
    29 =>
    30 =>

    0
  • ?

    Grammarnazi schrieb:

    seldon schrieb:

    der Boyer-Moore-Algorithmus oder die Vereinfachung durch Horspool.

    Wenn schon, dann KMP. Den hat man übrigens, wenn man den GCC und strstr verwendet.

    In diesem Fall brauchts aber gar kein Backtracking, da es nur Zahl oder Nichtzahl gibt.

    Das ist so nicht korrekt. Aus den glibc-Sourcen, string/str-two-way.h (diese wird in strstr verwendet):

    /* We use the Two-Way string matching algorithm, which guarantees
   linear complexity with constant space.  Additionally, for long
   needles, we also use a bad character shift table similar to the
   Boyer-Moore algorithm to achieve improved (potentially sub-linear)
   performance.

   See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
   and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
*/

    Generell ist Boyer-Moore KMP in der Regel laufzeittechnisch überlegen (nicht immer aber Boyer-Moore-Horspool!), wenn es nicht gerade um so kurze Textstücke geht, dass der Aufbau der Tabellen für Boyer-Moore ins Gewicht schlägt - daher wird die glibc ihn für strstr auch nicht verwenden, denn da dürfte das häufig der Fall sein.

    Es gibt da einen interessanten Beitrag auf der FreeBSD-Mailingliste vom ursprünglichen Entwickler von GNU Grep, der diese Dinge (mit Bonusfokus auf Dateiverarbeitung) nähere erläutert. Ferner gibt es übrigens eine weitere Verbesserung, die sich (vielleicht etwas prätentiös) Turbo-Boyer-Moore nennt und vom worst-case noch mal ein Drittel absäbelt.

    Wie dem auch sei, ich muss mich insofern entschuldigen, als dass das alles auf die ursprüngliche Aufgabe nur begrenzt passt - ich hatte das so gelesen, dass eine bestimmte zehnstellige Zahl gesucht wird. Allerdings kann man einige der Ideen trotzdem verwenden; praktisch kann man den String als Zeichenkette über ein Alphabet der Größe zwei (Ziffer/Nichtziffer) verstehen. Tabellen aufzustellen lohnt sich dann nicht, aber rumspringen kann man trotzdem, um die Vergleichszahl zu drücken. Ich stelle mir das etwa so vor (jetzt mal einfach hingekladdet):

    #include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string>

int const N = 10;

int ccount = 0;

bool is_digit(char c) {
  ++ccount;
  return std::isdigit(c);
}

int main() {
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  int i, j, k;

  for(k = i = N - 1; i < str.size(); k = i = k + N) {
    if(is_digit(str[i])) {
      for(j = i - 1; j > i - N && is_digit(str[j]); --j)
        ;

      if(j + N < str.size()) {
        for(k = j + N; k != i && is_digit(str[k]); --k)
          ;

        if(k == i) {
          std::copy(str.begin()     + 1 + j,
                    str.begin() + N + 1 + j,
                    std::ostream_iterator<char>(std::cout, ""));
          std::cout << std::endl;
          break;
        }
      }
    }
  }

  std::cout << ccount << " Vergleiche wurden benötigt." <<  std::endl;
}
    0
  • ?

    Ich hab noch mal in Ruhe drüber nachgedacht, und da lässt sich noch was drehen. Man kann die doppelte Prüfung einzelner Zeichen vermeiden, indem man sich bereits geprüfte Bereiche merkt, und man kann große Teile überspringen, indem man sich zunutze macht, dass das Ende eines Strings von 10 Ziffern keinesfalls in den neun Zeichen hinter einer Nicht-Ziffer liegen kann.

    Auf die Art kann ich bei einem Eingabestring der Länge n garantieren, dass ncith mehr als n Vergleiche benutzt werden - worst-case ist ein String der Form

    std::string str = 
    "x012345678"
    "xx012345678"
    "xx012345678"
    "xx012345678"
    "xx1234567890";

    Im besten Fall befindet sich die Vergleichszahl bei etwa p / 10 + 10, wobei p die Position der gesuchten Nadel im Heuhaufen ist, weil in Blöcken von bis zu zehn Zeichen übersprungen werden kann.

    Der Algorithmus sieht dann so aus:

    #include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string>

int const N = 10;

class counting_digit_predicate {
public:
  counting_digit_predicate() : ccount_(0) { }

  bool operator()(char c) {
    ++ccount_;
    return std::isdigit(c) != 0;
  }

  int counter() const { return ccount_; }

private:
  int ccount_;
};

int main() {
  std::string str = "002asbdfap91234usdfha9sdfuasdfa9shf9876503864x123123x9218391283981239812x129381289381290312xasd0123311";

  counting_digit_predicate is_digit;
  int i, j, k, l;

  for(i = N - 1, k = l = -1; i < str.size(); i = k + N) {
    if(!is_digit(str[i])) {
      k = i;
      continue;
    }

    for(j     = i - 1; j > l && is_digit(str[j]); --j) ;
    if(j == l) j = k;
    for(k = l = j + N; k > i && is_digit(str[k]); --k) ;

    if(k == i) {
      std::copy(str.begin()     + 1 + j,
		str.begin() + N + 1 + j,
		std::ostream_iterator<char>(std::cout, ""));
      std::cout << std::endl;
      break;
    }
  }

  std::cout << is_digit.counter() << " Vergleiche wurden benötigt." <<  std::endl;
}

    ...ein vernünftiges Interface drumherumzuschustern, sie dem Leser als Übungsaufgabe überlassen. 😉

    0
  • P

    Wenn der Text lang genug ist, lohnt sich eine Vorverarbeitung. Danach kann man in garantierter linearer Zeit alles finden.

    0
  • E

    Falls es immer noch um das Problem geht, sollte so funktionieren (ungetestet):

    #include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

int main()
{
    std::string str("002asbdfap91234usdfha9sdfuasdfa9");
    auto iter = std::search_n(str.begin(), str.end(), 9, char(), [](char, char cur) { return std::isdigit(cur); });
    iter == str.end() ? std::cout << "No match" : std::cout << "Match at " << iter - str.begin();
}
    0
  • ?

    C++Guid schrieb:

    fghfgh schrieb:

    #include <iostream>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
	std::string str = "009asbdfap91234usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd";

	std::cout << getNumber(str, 10);
}

std::string getNumber(const std::string& str, std::size_t len)
{
	std::size_t newPos = 0, nextPos = 0;

	for (;(newPos = str.find_first_of("0123456789", newPos)) != std::string::npos && (nextPos = str.find_first_not_of("0123456789", newPos)) - newPos != len && nextPos != std::string::npos;++newPos);

	if (newPos != std::string::npos && nextPos != std::string::npos)
		return str.substr(newPos, nextPos - newPos);

	return "";
}

    Eine spontane Idee. :xmas1:

    genau sowas suche ich danke jetzt noch eine kleine frage was ist wenn ich gleichzeitig wieder selbe Problem nur jetzt 10 und 11 stellige zahlen codes... wo gib ich das am besten an?

    MFG

    Hallo

    Ich hab bezüglich des Codes nur eine kleine Frage:
    Ist es nicht so, dass schlussendlich die Funktionen find_first_of und find_first_not_of im Hintergrund ähnlich den String durchlaufen wie von der Anfangsidee des TE und damit vom Rechenaufwand ähnlich wäre? Oder irre ich mich bei diesem Gedanken?

    Vielen Dank! 🙂

    Gruss,
    Vfrg

    0
  • ?

    find_first_of und find_first_not_of sind Funktionen, die aus einer Zeichenkette einfach jedes Zeichen berücksichtigen, anstatt wie bei find nur eines.

    0
  • ?

    Vfrg schrieb:

    C++Guid schrieb:

    fghfgh schrieb:

    #include <iostream>
#include <string>

std::string getNumber(const std::string& str, std::size_t len);

int main()
{
	std::string str = "009asbdfap91234usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd";

	std::cout << getNumber(str, 10);
}

std::string getNumber(const std::string& str, std::size_t len)
{
	std::size_t newPos = 0, nextPos = 0;

	for (;(newPos = str.find_first_of("0123456789", newPos)) != std::string::npos && (nextPos = str.find_first_not_of("0123456789", newPos)) - newPos != len && nextPos != std::string::npos;++newPos);

	if (newPos != std::string::npos && nextPos != std::string::npos)
		return str.substr(newPos, nextPos - newPos);

	return "";
}

    Eine spontane Idee. :xmas1:

    genau sowas suche ich danke jetzt noch eine kleine frage was ist wenn ich gleichzeitig wieder selbe Problem nur jetzt 10 und 11 stellige zahlen codes... wo gib ich das am besten an?

    MFG

    Hallo

    Ich hab bezüglich des Codes nur eine kleine Frage:
    Ist es nicht so, dass schlussendlich die Funktionen find_first_of und find_first_not_of im Hintergrund ähnlich den String durchlaufen wie von der Anfangsidee des TE und damit vom Rechenaufwand ähnlich wäre? Oder irre ich mich bei diesem Gedanken?

    Vielen Dank! 🙂

    Gruss,
    Vfrg

    Ja, damit hast du recht. Allerdings kann es natürlich sein, dass diese Funktionen optimierter sind, als hätte man es von Hand geschrieben. Im einfachsten Fall läuft es aber auf das gleiche hinaus.

    0
  • ?

    Ja, damit hast du recht. Allerdings kann es natürlich sein, dass diese Funktionen optimierter sind, als hätte man es von Hand geschrieben. Im einfachsten Fall läuft es aber auf das gleiche hinaus.

    Danke für die Erklärung! 😃

    Gruss,
    Vfrg

    0
  • W

    Ich hatte den Thread schon vor drei Tagen mit Interesse verfolgt, aber bisher keine Gelegenheit darauf zu antworten. Dass std::search_n das Mittel der Wahl ist, wurde bereits erwähnt. Und natürlich benutzen die Implementierungen ähnliche Strategien wie den 'Boyer-Moore-Algorithmus'.

    Wichtig zu wissen ist aber noch, dass die Implementierung im Visual Studio 2005 buggy ist!
    Ich habe mal einen kleinen Iteratorwrapper gebastelt um deutlich zu machen, was da passiert. Im 2008'er und jüngeren Versionen ist das Problem behoben.

    #include <iostream>
#include <string>
#include <cassert>
#include <algorithm> // std::search_n
#include <locale>
#include <iomanip> // std:.setw

#include <boost/iterator/iterator_adaptor.hpp>

template< typename Base >
class AccessViewer : public boost::iterator_adaptor< AccessViewer< Base >, Base >
{
public:
    AccessViewer()
        : iterator_adaptor_()
        , m_idx()
    {}
    AccessViewer( Base cur, Base begin )
        : iterator_adaptor_( cur )
        , m_idx( std::distance( begin, cur ) )
    {}
    void increment() { ++m_idx; ++base_reference();  }
    void decrement() { --m_idx; --base_reference();  }
    void advance( typename Base::difference_type n )
    {
        m_idx += n;
        std::advance( base_reference(), n );
    }
    typename Base::reference dereference() const
    {
        std::clog << std::setw( std::streamsize( m_idx + 1 ) ) << "^" << std::endl;
        return *base();
    }
private:
    typename Base::difference_type m_idx;
};
template< typename Base >
AccessViewer< Base > access_viewer( Base cur, Base begin )
{
    return AccessViewer< Base >( cur, begin );
}

int main()
{
    using namespace std;
    string txt = "009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd";
    for( int n = 2; n < 15; n == 2? n = 10: n == 10? n = 12: n = 99 )
    {
        clog << "\n" << txt << endl;
        string::iterator found = std::search_n( access_viewer( txt.begin(), txt.begin() ), access_viewer( txt.end(), txt.begin() ), n, locale(), &std::isdigit<char> ).base();
        cout << n << " digits: " << txt.substr( distance( txt.begin(), found ), min( distance( found, txt.end() ), n ) )<< endl;
    }
    return 0;
}

    Die Ausgabe sieht im Gutfall so aus (mit VS 2008 Express):

    009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd
^
 ^
2 digits: 00

009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd
^
 ^
  ^
   ^
    ^
              ^
                        ^
                                  ^
                                 ^
                                ^
                               ^
                              ^
                                   ^
                                    ^
                                     ^
                                      ^
                                       ^
                                        ^
10 digits: 9876503864

009asbdfap9usdfha9sdfuasdfa9shf9876503864a98sdbf98abdasd
^
 ^
  ^
   ^
    ^
                ^
                            ^
                                        ^
                                       ^
                                      ^
                                     ^
                                    ^
                                   ^
                                  ^
                                 ^
                                ^
                               ^
                              ^
                                         ^
                                          ^
                                           ^
                                            ^
12 digits:

    Bei jedem Zugriff auf ein Element durch den Algorithmus wird eine Zeile ausgegeben. Der 'Pfeil nach oben' zeigt jeweils an an welcher Stelle gerade zugegriffen wird. Man sieht sehr schön, wie der Algorithmus zwar vorn anfängt, dann aber in n'er Schritten weiter sucht, den Anfang der Ziffernkette sucht, um anschließend den Rest der n Zeichen zu prüfen.
    Es fällt noch auf, dass am Anfang immer ein Zeichen mehr geprüft wird als notwendig.

    Wer noch über ein Visual Studio 2005 verfügt, möge es da mal mit probieren.

    Gruß
    Werner

    0
  • P

    Hallo,

    Werner's Boyer Moore dürfte neben heuristischen Methoden (die nur möglich sind, wenn man etwas mehr über den string weiß) die schnellste sein, mit einer Änderung: man fängt beim 10. char an, nicht beim Ersten!

    Immer 10 springen und rückwärtssuchen.
    Nach dem Sprung kann man in sofern noch abkürzen, wenn man im vorherigen rückwärtssuchen n gefunden hat braucht man bei folgenden rückwärtssuchen nur noch 10-n finden.

    Ich denke, dass search_n mit Boyer Moore arbeitet, aber der Fakt dass alles zahlen sind, nicht berücksichtigen kann. Es wird eine Gruppe aus Zahlen gesucht, nicht ein string im string. Somit ist das gleichzustellen mit alle Buchstaben werden zu "b" und alle Zahlen werden zu "z" und es muss nach "zzzzzzzzzz" gesucht werden. Jetzt wenn man den Boyer Moore anwendet merkt man schnell, dass manche Vergleiche zu viel sind:

    v        v
zzzzbbzbzbzbzzzzzbzzzzzzzzzzbzbzbzzzzb
zzzzzzzzz[u]z[/u]
          zzzzzzzzz[u]z[/u]
          zzzzzzzz[u]z[/u]z
          zzzzzzz[u]z[/u]zz
                  zzzzzzzzz[u]z[/u]
                  zzzzzzzz[u]z[/u]z
                  zzzzzzz[u]z[/u]zz
                  zzzzzz[u]z[/u]zzz
                  zzzzz[u]z[/u]zzzz
                  zzzz[u]z[/u]zzzzz
                  zzz[u]z[/u]zzzzzz
                  zz[u]z[/u]zzzzzzz // Hier endet ein schlauer Algorithmus, denn es wurden bereits 2x "z" gefunden
                  z[u]z[/u]zzzzzzzz
                  [u]z[/u]zzzzzzzzz // Hier endet erst der Bayor Moore

    Viel Spass damit, ich hoffe ich keine Denkfehler habe!
    gruß Philipp

    0
Anmelden zum Antworten