Der normale dynamic programing Zuker Algorithmus von Faltungen von Sequenzen hat eine Laufzeit von O(n^4), mit zu\u00e4tzlichen Cache noch O(n^3). Mit der allgemeinen Four-Russians Speedup Methode f\u00fcr dynamic programing Algorithmen ist eine Laufzeit von O(n^3\/log n) m\u00f6glich. F\u00fcr kleines n also absolut irrelevant. F\u00fcr gro\u00dfes n halbiert, oder drittelt sogar die Laufzeit. Was dann aber immer noch unheimlich zu lange ist.
\nAber was ist die Idee dahinter?
\nAls erstes wird festgestellt, dass es nicht m\u00f6glich 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\u00e4ngt. Und dann kommt eine 3fach Schleife die abh\u00e4ngt.
\nIn der innersten Schleife findet nun die Optimierung statt. Die Schleife sieht so aus:<\/p>\n
S(i,j)=max( S(i,j), S(i,k-1)+S(k,j) )<\/p><\/blockquote>\n
F\u00fcr fixes i,j iteriert nur k von i+1 zu j-1. Die Idee ist nun, Indizes zu Gruppe der Gr\u00f6\u00dfe q zusammen zu fassen. So dass die innerste Schleife nur noch n\/q oft l\u00e4uft.
\nNun 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.
\nZeitverschwendung.<\/p>\n[1] A Simple, Practical and Complete Time Algorithm for RNA Folding Using the Four-Russians Speedup - Yelena Frid and Dan Gusfield<\/p>\n","protected":false},"excerpt":{"rendered":"
Der normale dynamic programing Zuker Algorithmus von Faltungen von Sequenzen hat eine Laufzeit von O(n^4), mit zu\u00e4tzlichen Cache noch O(n^3). Mit der allgemeinen Four-Russians Speedup Methode f\u00fcr dynamic programing Algorithmen ist eine Laufzeit von O(n^3\/log n) m\u00f6glich. F\u00fcr kleines n also absolut irrelevant. F\u00fcr gro\u00dfes n halbiert, oder drittelt sogar die Laufzeit. Was dann aber […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17],"class_list":["post-2950","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2950","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2950"}],"version-history":[{"count":1,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2950\/revisions"}],"predecessor-version":[{"id":2951,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/2950\/revisions\/2951"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2950"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2950"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2950"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}