catch missbrauchen

Situation: Ich will solange irgendetwas berechnen, bis ich das Resultat gefunden habe. Den Fall habe ich öfters, beim Suchen in Datenstrukturen, beim Simulieren bis zu einer bestimmten Genauigkeit, etc.

Es gibt nun 2 Möglichkeiten, die Abbruchbedingung zu formulieren: Mit Exceptions oder mit true/false.

Mir wird immer gelehrt, Exceptions nur in Ausnahmefällen zu gebrauchen. In meinen Fällen würden sie den Code schöner und gleichzeitig schneller machen. Aber sie sind keine "unerwarteten Ausnahmen" im herkömmlichen Sinne mehr.

struct found {};
void f_(int s, int l, int r)
{
  if (r - l == 1) {
    if (s == l)
      throw found();
  } else {
    f_(s, l, (l+r)/2);
    f_(s, (l+r)/2, r);
  }
}
bool f(int s, int l, int r)
{
  try {
    f_(s,l,r);
  } catch (found&) {
    return true;
  }
  return false;
}

bool g(int s, int l, int r)
{
  if (r - l == 1)
    return s == l;

  if (g(s, l, (l+r)/2)) return true;
  if (g(s, (l+r)/2, r)) return true;
  return false;
}

int main()
{
  int c,s,l,r;
  std::cin >> c >> s >> l >> r;

  if (c==0) std::cout << std::boolalpha << g(s,l,r) << '\n'; 
  else      std::cout << std::boolalpha << f(s,l,r) << '\n'; 
}

g() dauert 8.43s, f() dauert 6.82s.

Findet ihr das eine valide Option, Exceptions für solche Fälle zu missbrauchen, oder sollte man sie strikt nur wirkliche Ausnahmen einsetzen?

Wenn nein, wie kann ich die sonst Geschwindigkeit und den kurzen Code erreichen?
Wenn ja, was ist das Kriterium? Es gibt noch viele weitere Fälle (erwartete Parserfehler, Protokollabbruch, Spezialfall x=0, etc.).

EOP

Die Funktionen sind nicht identisch, ein Vergleich ist deshalb nicht sinnvoll.

theta

catchme schrieb:

Findet ihr das eine valide Option, Exceptions für solche Fälle zu missbrauchen, oder sollte man sie strikt nur wirkliche Ausnahmen einsetzen?

Nein. Ja.

catchme schrieb:

Wenn nein, wie kann ich die sonst Geschwindigkeit und den kurzen Code erreichen?

Einen Profiler benutzen (Visual Studio, Valgrind/Cachegrind, Intel VTune...).

EOP schrieb:

Die Funktionen sind nicht identisch, ein Vergleich ist deshalb nicht sinnvoll.

Sie sind identisch.

theta schrieb:

catchme schrieb:

Wenn nein, wie kann ich die sonst Geschwindigkeit und den kurzen Code erreichen?

Einen Profiler benutzen (Visual Studio, Valgrind/Cachegrind, Intel VTune...).

?

theta

Hast du ein konkrete Frage zu meiner Antwort bezüglich Profiler?

MichelRT

catchme schrieb:

EOP schrieb:

Die Funktionen sind nicht identisch, ein Vergleich ist deshalb nicht sinnvoll.

Sie sind identisch.

Nein, sind sie nicht.

Sone

catchme schrieb:

EOP schrieb:

Die Funktionen sind nicht identisch, ein Vergleich ist deshalb nicht sinnvoll.

Sie sind identisch.

Nein, das sind sie nicht. Vielleicht sind sie das von der Signatur und vom Verhalten.

theta schrieb:

catchme schrieb:

Wenn nein, wie kann ich die sonst Geschwindigkeit und den kurzen Code erreichen?

Einen Profiler benutzen (Visual Studio, Valgrind/Cachegrind, Intel VTune...).

?

Edit: Was rede ich da. Jetzt verstehe ich theta schon sowieso nicht - was hat da ein Profiler verloren (ich dachte es geht um Geschwindigkeitsmessung)

g() dauert 8.43s, f() dauert 6.82s.

Optimierungslevel?

bool h(int s, int l, int r)
{
    return l<s && s<r;
}

Dauert bei mir 0.00 s (auf 2 Stellen genau ). Ist O(1) und nicht O(ld n), wie bei Deinem Ansatz

catchme schrieb:

Wenn nein, wie kann ich die sonst Geschwindigkeit und den kurzen Code erreichen?

Mal abgesehen davon, dass g kuerzer und leichter zu lesen ist: Rekursion ist hier sicher nicht der Beste Weg das zu loesen. Du verlierst mit den ganzen rekursiven Aufrufen viel mehr Zeit, als Du mit Deinem catch gewinnen kannst. Wahrscheinlich liegt da auch der Gewinn des catch gegenueber dem "normalen" Funktionsaufruf: Beim Ruecksprung wird die Zeit gespart.

knivil

Nun, habe natuerlich mal von einer Suche in Baemen gehoert, die mittels Exception bei gefundenem Eintrag auffhoerte. War schneller und war in Java. C++ bietet fuer non-local-exit als einziges Mittel nur Exceptions an. Schade, andere Sprachen bieten Continuations :). Da hier keine lokalen Objekte erzeugt werden, koennte man was mit setjmp, longjmp machen. Vielleicht bietet Boost.Context auch was an. Dazu muesste aber das ganze Problem dargestellt werden und entsprechend nachgemessen werden.

Btw.: Ich mag call/cc.

Rekursion ist hier sicher nicht der Beste Weg das zu loesen. Du verlierst mit den ganzen rekursiven Aufrufen viel mehr Zeit, als Du mit Deinem catch gewinnen kannst.

Es fehlen Begruendungen fuer deine Aussagen. Normalerweise schafft der Compiler die Rekursion aufzuloesen.

Ansonsten ist die Impelementierung natuerlich suboptimal:

bool g(int s, int l, int r) 
{ 
  if (r - l == 1) 
    return s == l; 

  return g(s, l, (l+r)/2)) || g(s, (l+r)/2, r);
}

Und wenn es sowieso folgendes die Loesung ist:

bool h(int s, int l, int r) 
{ 
    return l<s && s<r; 
}

Wieso dann ueberhaupt den ganzen Aufwand?

g() dauert 8.43s, f() dauert 6.82s

Es fehlen Angaben zu Compileroptionen.

Wenn nein, wie kann ich die sonst Geschwindigkeit und den kurzen Code erreichen?

Durch nachdenken.

Ansonsten: Hier wuerde ich auf Exceptions verzichten.

hustbaer

Findet ihr das eine valide Option, Exceptions für solche Fälle zu missbrauchen, oder sollte man sie strikt nur wirkliche Ausnahmen einsetzen?

Wenn ...
* der Speedup wirklich merkbar ist,
* der Speedup wirklich gebraucht wird,
* die Funktion, inklusive aller von ihr (direkt oder indirekt) aufgerufenen Funktionen ausreichend klein (überschaubar) ist,
* man es gut dokumentiert,
* es die Ausnahme bleibt und nicht an 100 Stellen wiederholt wird
und
* es mit vertretbarem Aufwand nicht möglich ist eine "bessere" Lösung zu bauen,
dann würde ich diese "Hack" nicht als grundsätzlich verwerflich einstufen.

Aber versuch mal ein Beispiel zu machen das auch wirklich irgendwas tut was man nicht trivial zu einer O(1) Funktion zusammenkürzen kann. Würde mich eher wundern wenn der Unterschied dann immer noch so deutlich ausfallen würde.

Wenn nein, wie kann ich die sonst Geschwindigkeit und den kurzen Code erreichen?

Die Funktion so umschreiben dass sie iterativ statt rekursiv arbeitet. Dadurch wird die vermutlich auch um einiges schneller - u.U. sogar schneller als die Exception-Trick Variante.

Wenn ja, was ist das Kriterium? Es gibt noch viele weitere Fälle (erwartete Parserfehler, Protokollabbruch, Spezialfall x=0, etc.).

Ich würde das immer im Einzelfall entscheiden.
Code der im Normalbetrieb keine Exceptions wirft ist u.A. angenehmer zu debuggen als Code wo dauernd irgendwelche Exceptions rumfliegen.
Und natürlich verletzt man mit solchen Tricks das principle of least astonishment, was generell keine gute Idee ist.

Bevor man sich aber das Leben zur Hölle macht, nur weil man auf den "Misbrauch" von Exceptions/setjmp-longjmp/... verzichtet ...

Helmut.Jakoby

Also ich breche Schleifen mit break ab.

hustbaer

Welche Schleife?