C++Guns – RoboBlog blogging the bot

Die Idee ist von Stephen C. Dewhurst [1] die Abkürzung von mir

FVCRTTPPP - Fancy Variadic Curiously Recurring Template Template Parameter Pack Pattern

Praxisbeispiel:

using FVCRTTPPPScalar = Scalar<int, Ctr, Eq, Rel, Stream>; ! A countable, equal compareable, relational-able, streamable, scalar integer type.
FVCRTTPPPScalar x = 0;

[1] http://stevedewhurst.com/once_weakly/once-weakly20170328/once-weakly20170328.pdf

Der normale dynamic programing Zuker Algorithmus von Faltungen von Sequenzen hat eine Laufzeit von O(n^4), mit zuätzlichen Cache noch O(n^3). Mit der allgemeinen Four-Russians Speedup Methode für dynamic programing Algorithmen ist eine Laufzeit von O(n^3/log n) möglich. Für kleines n also absolut irrelevant. Für großes n halbiert, oder drittelt sogar die Laufzeit. Was dann aber immer noch unheimlich zu lange ist.
Aber was ist die Idee dahinter?
Als erstes wird festgestellt, dass es nicht möglich ist, die Four-Russians Technik auf die klassische Implementation des Zuker anzuwenden. Da die Auswertungsreihenfolge der Matrizen nicht passt. Also wird die Reihenfolge erst mal umgestellt. Erst kommt eine Schleife die nicht von der derzeitigen Spalte j in der Matrix abhängt. Und dann kommt eine 3fach Schleife die abhängt.
In der innersten Schleife findet nun die Optimierung statt. Die Schleife sieht so aus:

S(i,j)=max( S(i,j), S(i,k-1)+S(k,j) )

Für fixes i,j iteriert nur k von i+1 zu j-1. Die Idee ist nun, Indizes zu Gruppe der Größe q zusammen zu fassen. So dass die innerste Schleife nur noch n/q oft läuft.
Nun ja wenn sie meinen. Um das Maximum zu ermitteln, muss man so oder so jeden Wert in der Matrix in diesem Bereich anfassen. Wie die das verhindern wollen, das lese ich aus dem Paper nicht raus.
Zeitverschwendung.

[1] A Simple, Practical and Complete Time Algorithm for RNA Folding Using the Four-Russians Speedup - Yelena Frid and Dan Gusfield

Für die, die es immer noch nicht kapiert haben: Hier noch ein einfachereres Beispiel. Temporäre Objekte, alles klar? Speichert keine Referenzen, es gibt kein Grund das zu tun. Sonst schießt ich euch in den Fuß. In jede Zehe einzeln.

bool alive = true;

struct Foo {
  Foo() { }
  ~Foo() { alive = false; }
};

struct Bar {
  const Foo& dangling;
  
  Bar(const Foo& foo) : dangling(foo) { }
  
  void func() {
    if(alive) {
      cout << "dangling is okay\n";
    } else {
      cout << "dangling is dangling\n";
    }
  }
};

int main() {
  Bar bar{Foo{}};
  bar.func();
  return 0;
}

Ich habe gerade eine einfache Schleife mit 5 Zeilen geschrieben und auf einmal sah ich, dass das doch ein gutes Beispiel für funktionales programmieren wäre.
Gegeben ist ein Datenvector mit custom Typ und gesucht ist ein bestimmtes Datum und, falls vorhanden, davon ein bestimmter Wert. Die Schleife lässt sich von Hand so ausdrücken:

    struct Blah {
        size_t idx;
        int att;
    };

    vector<Blah> data { {2, -1}, {1, -1}, {5, 50}, {3, 10}};

    // skip -1
    size_t start = 0;
    for(size_t i=0; i < data.size(); ++i) {
        int att = data[i].att;
        if(att != -1) {
            start = data[i].idx;
            break;
        }
    }
    cout << "start " << start << "\n"; // print 5

Hier gibt es gleich eine ganze Reihe von Fehlerquellen. Von welchem Typ muss i sein, size_t oder int? Inkrement mit ++i oder i++ ? Ist der operator[] überhaupt vorhanden, und wenn ja auch effizient? Muss der Zugriff ueber const Referenz erfolgen? Und die Schleifen koennen wir beenden beim ersten Treffer, ja sicher oder ist das "break" zufällig da. Fuer alle das, muss man den Code Zeile fuer Zeile lesen und nachvollziehen und verstehen. Wie immer ist das "WAS und nicht WIE" Prinzip verletzte. Denn der Code sagt nicht, WAS er macht, sondern nur WIE. Ich hätte auch range-for nehmen können. Aber das ändert am Prinzip nichts.

Aus funktionaler Sicht ist die Schleife ja ein Muster fuer "find_if_apply" oder "apply_if_find" je nachdem ^^ Ob es in der funktionalen Welt so eine Funktion gibt, und wie sie genau heißt, weiß ich nicht. Aber ich probier mal meine eigene Version. Ich wäle den Namen "find_if_apply", da es schon eine C++ Funktion std::find_if gibt, und erweitere sie um eine "apply" componente.

template<class Container, class UnaryPredicate, class UnaryFunction>
void find_if_apply(const Container& data, UnaryPredicate p, UnaryFunction f) {
    for(const auto& x : data) {
        if(p(x)) {
            f(x);
            break;
        }
    }
}

size_t start = 0;
find_if_apply(data,
              [](const Blah& x) { return x.att != -1; },
              [&start](const Blah& x) { start = x.idx; }
              );
cout << "start " << start << "\n"; // print 5

Die Funktion find_if_apply nimmt zwei den Datensatz und zwei Funktionen. Die erste ist fuer find, und die zweite fuer apply.
Also die template Funktion selbst ist wirklich überraschend erstauling elegant einfach. Die Anwendung davon ist auch okay. Zwei einzeiler Funktionen sind noch lesbar.

Übrigends, std::find_if alleine hätte nichts geholfen. Da ein Iterator zurueck gegeben wird der wieder den Scope voll müllt und manuell auf Gültigkeit geprüft werden muss. Mit std::find_if wäre die Schleife und das if() weg gekapselt, aber gebracht hätte es nichts.

Noch eine Bemerkung: Die Variable idx in dem Beispiel ist explizit angegeben. Überwiegend kommt das in unseren Datenstrukturen und Algorithmen aber nicht vor. Dort ist die Position im Array der Index. Und schon funktioniert der funktionale Ansatz wieder nicht. Man könnte find_if_apply natürlich so erstellen und dokumentieren, dass das erste Argument der Lambdas der Laufindex ist. Aber nicht immer wird er auch in den Lambdas benötigt. Da mit Overloads und sonstige Tricks kommen macht alles wieder nur viel zu kompliziert. Noch dazu hat nicht jeder Container auch ein Laufindex. Bei Listen funktioniert es ist nicht, und da ist es dann Datenstruktur abhängig, wo der Index des Datums steht.