|
|
|
|
|
|
|
Apropos c't, kürzlich am Bahnhof mal wieder eine gekauft. Deutscher Computerjournalismus ist echt kacke.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von RichterSkala
Schon ziemlich cool. Auch dass sie das sehr indirekt, mittels Zählen der verbliebenen Antiwasserstoffe in der Falle, gemessen haben 
| |
Im zugehörigen Nature Paper wird der Lieferant des zugehörigen Lasersystems lobend erwähnt. 
|
|
|
|
|
|
|
|
|
|
|
Passiert wohl nicht so häufig? :P
|
|
|
|
|
|
|
|
|
|
| | Zitat von csde_rats
Nein, kann man nicht.
| |
Alles klar, danke!
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von PutzFrau
| | Zitat von WeGi
Was hast du gegen erlang. 
| |
Heißt die Sprache erlang.?
| |
| | Zitat von csde_rats
Ich benütze ja generell keine Sprachen, deren offizielle Domain ".*-?lang\.[^.]*$" matcht.
| |
-> erlang.org
|
|
|
|
|
|
|
|
|
|
|
|
Kollateralschäden gibt es in jedem Krieg.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von WeGi
| | Zitat von PutzFrau
| | Zitat von WeGi
Was hast du gegen erlang.
| |
Heißt die Sprache erlang.?
| |
| | Zitat von csde_rats
Ich benütze ja generell keine Sprachen, deren offizielle Domain ".*-?lang\.[^.]*$" matcht.
| |
-> erlang.org
| |
Ich weiß auch nicht, wie ich das Wort 'Domain' übersehen konnte.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von Dumenikl
Ich bräuchte also Tips oder auch Literaturhinweise wie man diese Lücke zwischen den Einsteigertutorials und meiner gewünschten Anwendung schließt. Ich habe leider abseits der API keine Verwendung für C und damit auch kein Projekt dem ich mich zuwenden könnte.
| |
Hm, ich kann quasi kein C und deine Api kenne ich auch nicht, dafür habe ich jetzt über 15 Jahre Programmiererfahrung.
Mir persönlich hilft bei Einarbeitung in neue Apis ein Test-Driven-Ansatz.
Das heißt bei mir dann, dass ich mir z. B. eine einzige vielversprechende Api-Methode angucke, und dafür einen Unittest schreibe, damit ich diese Methode wirklich verstehe. Dieser Unittest braucht dann einen sinnvollen Assert, für den man vielleicht die zweite Api-Methode braucht. Total triviales Beispiel, vielleicht passt das ja bei dir:
1. Methode: Erzeuge Ton/Sample mit Frequenz xy
In einen Test bauen, ausführen, anhören, freuen.
2. Methode: Welche Töne werden gerade abgespielt und welche Frequenz haben sie?
In den Test einbauen und auf Frequenz xy testen. Passt das? Yay! Passt das nicht? Wtf, warum nicht?
Das ist jetzt erstmal ziemlich billig und wie gesagt, ich rate in deinem Kontext jetzt nur rum.
Danach lasse ich den Test dann wachsen, auch in Richtung meines eigentlichen Zieles. Z. B. in Richtung:
- Der Ton soll 5x in 10 Sekunden abgespielt werden. Kann ich das sinnvoll überprüfen?
- Der Ton soll mit crazy-shit-effekt-42 verzerrt werden. Kann ich das sinnvoll überprüfen?
Meine Erfahrung ist dabei, dass sich viele Sachen dann automatisch ergeben. Z. B. stellt man dann fest, dass die eine blöde Testmethode gar nicht mehr ausreicht und man das lieber in irgendwelche Klassen/Objekte/sonstwas auslagert. Oder dass man gerade den gleichen Code das dritte Mal getippt hat, und auch das lieber auslagert. Oder dass man den gewünschten Effekt nicht mehr sinnvoll überprüfen kann, und dieser eine Weg vielleicht eine Sackgasse war. An dieser Stelle fehlt die vermutlich die Erfahrung das sofort "zu sehen"... aber das sollte dich erstmal nicht entmutigen. Die kann man eben nur selber erlernen.
Wichtig ist dabei das ständige Feedback an dich, was über den ersten grünen Test bis zu 2+x Stunden Dauergefluche über die verdammte Drecksscheißapi (willkommen in der Programmierwelt!) reicht. Aber du kriegst in kleinen Schritten Erfolgsmeldungen, die dich motivieren, weiter zu machen.
Wenn du also dein großes Ziel vor Augen hast, du also weißt was am Ende rauskommen soll, brich es in kleine Teile und fang mit dem allereinfachste und kleinsten Teil an. Und wenn der so lächerlich wie 1+1 ist. Danach setzt du die nächste Stufe drauf, vielleicht musst du 1000 mal 1+1 in irgendeiner Schleife rechnen. Danach muss die Schleife vielleicht nur unter zwei von drei Bedingungen aufgerufen werden, sonst nicht. Danach ist eine der Bedingungen vielleicht, dass man in deinem Programm einen bestimmten Knopf gedrückt hat, der die Plugin-Api aufrufen kann.
Wenn es dann funktioniert, hast du üblicherweise drei Möglichkeiten:
- Yay, funktioniert. Scheiß auf die Codequalität, Wartung ist nur für Leute die Fehler machen. Arschprüfdaumen und Release! Give me your moneyzzzz!
- Hm, funktioniert zwar, aber das ist ja nur Testcode. Also alles wegschmeißen, komplett und ohne Ausnahme, und mit dem besseren Wissen neu bauen. Hinterher ist man eben schlauer.
- Yay, funktioni... ach verdammt, habe es gerade fertig bei Github/Stackoverflow von jemand anderem in nur 2 Zeilen Code gefunden. Eine Erfahrung reicher für das nächste Projekt.
|
|
|
|
|
|
|
|
|
|
|
Uuuuund ich bin Reviewer nach einem Paper. Und wenn ich jetzt nicht so elend krank wäre, könnte ich das auch schon abhaken und entspannte Weihnachten haben - aber neeeeeeiiiiin.
Und weil ich hier noch nicht damit geprahlt habe: Freitag ist unsere Sommerschule zu QFT mit Mark Srednicki als Hauptdozent erfolgreich zum Abschluss gekommen. Alle waren glücklich und die beteiligten vier Profs, ferner ein Head of School und viele, viele Studenten haben mich für meine Initiative und die großartige Schule gelobt. Die Fragebögen zur Bewertung, die rumgingen, sehen auch super aus. Das geht runter wie Öl.
Jetzt noch die Videoaufnahmen der Vorlesungen sichten und irgendwie veröffentlichen und alles hat mühelos funktioniert.
Unser Crackpotstalker ist dazu übergegangen, das Registrationsformular für seine Briefe zu nutzen und ärgert sich "lautstark" dort, dass wir ihm nicht antworten.
Have you hugged your massive armored battle droid today?
|
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von Wraith of Seth am 22.12.2016 5:35]
|
|
|
|
|
|
|
|
|
| | Zitat von Wraith of Seth
Uuuuund ich bin Reviewer nach einem Paper. Und wenn ich jetzt nicht so elend krank wäre, könnte ich das auch schon abhaken und entspannte Weihnachten haben - aber neeeeeeiiiiin.
| |
Lass halt liegen und hab trotzdem entspannte Weihnachten. Wirst ja wohl keine zwei Wochen Deadline haben. Und selbst wenn doch: die anderen Reviewer werden die auch ignorieren. Hilft also keinem, wenn du das vorher noch machst. 
|
|
|
|
|
|
|
|
|
|
|
Habe fast vier Wochen, aber zu lange liegen lassen will ich es nicht, sonst vergesse ich das. Ich kenne mich doch...
Quoth the raven, "Nevermore!"
|
|
|
|
|
|
|
|
|
|
|
|
Reviewen ist ein oder zweimal spannend, bis es schnell zur zweit lästigsten Aufgabe überhaupt wird, direkt nach Anträge schreiben.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von csde_rats
Ich benütze ja generell keine Sprachen, deren offizielle Domain ".*-?lang\.[^.]*$" matcht.
| |
| | Zitat von csde_rats
Ich benütze
| |
Klar, hier ist nicht der Germanistenthread, aber: Alter! 
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von Oli
Reviewen ist ein oder zweimal spannend, bis es schnell zur zweit lästigsten Aufgabe überhaupt wird, direkt nach Anträge schreiben.
| |
Dafür kann man ungehemmt das Arschloch raushängen lassen... bis man vergisst, den eigenen Namen aus den PDF-Metadaten zu entfernen.
Spaß beiseite, ich finds sehr lehrreich zu dem Thema, wer auch alles nur mit Wasser kocht und was für bescheuerte Fehler selbst gefeierte Koryphäen machen. Gut fürs Selbstwertgefühl. Ansonsten ist es halt nett als Sneak-Preview, was die anderen so treiben. Aber ich nehme auch nur Requests an, bei denen mich das Thema auch wirklich interessiert.
|
|
|
|
|
|
|
|
|
|
|
Habe mich nach einem Jahr arbeiten dafür entschieden, mir doch die dunkle Seite anzuschauen und nicht nur zu haten.
Hatten jetzt auf der Arbeit ein Projekt bei dem wir gesagt haben: "Wir machen's einfach mal selber!" (natürlich mit Unterstützung durch eine Programmierbude) und es ist ein tolles Gefühl, etwas gemacht zu haben, das dann wirklich funktioniert. Das geht dann einfach. Geil.
Berufsbegleitendes Informatikstudium ab kommenden Oktober. Von Februar bis Oktober erstmal 30h bei dem AG neuangstellt, bei dem ich dann auch studieren darf. Und: Wieder mit dem besten Kumpel zusammen. Der geht auch dahin (zurück). Die restlichen 10h/Woche brauch' ich, um Mathe vorzubereiten. In der 9 - 12 war ich in der Schule quasi nicht anwesend.
Bin gespannt.
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von _funktionsdelle am 22.12.2016 22:58]
|
|
|
|
|
|
|
|
|
Nimm die ganzen Leute, die dir sagen, dass du bei Uni-Mathe immer mitmachen musst, immer da sein musst, alle Übungen selber machen / verstehen musst ernst. Tu es. Auf keinen Fall drum herum drücken / "mach ich später". Das bereust du zehntausendfach.
e: Wenn es an deiner Uni einen Mathe-Vorbereitungskurs vor dem ersten Semester gibt -> auf jeden Fall hingehen. Lohnt sich.
Viel Spaß im Studium 
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von csde_rats am 22.12.2016 23:01]
|
|
|
|
|
|
|
|
|
|
Überhaupt alles mitnehmen, was die an Unterstützung für Mathe bieten. Auch Tutorien, betreute Hausaufgaben oder ähnliches .
|
|
|
|
|
|
|
|
|
|
|
Und die Studentinnen. Die sind in Mathe erfahrungsgemäß besser als in Physik oder Informatik.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von PutzFrau
Und die Studentinnen. Die sind in Mathe erfahrungsgemäß besser als in Physik oder Informatik.
| |
Sind sie denn irgendwo schlechter?
|
|
|
|
|
|
|
|
|
|
|
Ich kann die Ingenieursstudiengänge nicht beurteilen, aber das wäre mein einziger Kandidate.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von G-Shocker
Sind sie denn irgendwo schlechter?
| |
Programmieren.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von csde_rats
Nimm die ganzen Leute, die dir sagen, dass du bei Uni-Mathe immer mitmachen musst, immer da sein musst, alle Übungen selber machen / verstehen musst ernst. Tu es. Auf keinen Fall drum herum drücken / "mach ich später". Das bereust du zehntausendfach.
e: Wenn es an deiner Uni einen Mathe-Vorbereitungskurs vor dem ersten Semester gibt -> auf jeden Fall hingehen. Lohnt sich.
Viel Spaß im Studium
| |
Danke. Das mach' ich. Vorbereitungskurse gibt's, aber da muss ich arbeiten. Deswegen - wie gesagt - nur 30/Woche und 10h/Wochte Mathe. 'N Freund hat vor 3(?) Semestern Mathe angefangen und kann mir, denke ich, ganz gut weiterhelfen.
Wir setzen uns jetzt über Weihnachten mal hin und er checkt 'n bisschen ab, wo meine größten Löcher sind und dann habe ich mir so ein Springer-Mathe-Brückenkurs geholt, das ich entsprechend durcharbeiten werde.
| | Zitat von Strahlung-Alpha
Überhaupt alles mitnehmen, was die an Unterstützung für Mathe bieten. Auch Tutorien, betreute Hausaufgaben oder ähnliches .
| |
Das auf jeden Fall. Besagter Kumpel meint das auch. Er ist mindestens reale 40h/Woche an der Uni, um Zeug mit Leuten zu machen und dann nochmal 10h oder so zuhause mit Vor- und Nachbereiten beschäftigt. Und ich schätze ihn schlauer ein als mich. (Er ist aber auch im oberen drittel zu finden). Und dann hat er noch ein (gewolltes) Kind. 
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von _funktionsdelle am 23.12.2016 3:16]
|
|
|
|
|
|
|
|
|
| | Zitat von Oli
Reviewen ist ein oder zweimal spannend, bis es schnell zur zweit lästigsten Aufgabe überhaupt wird, direkt nach Anträge schreiben.
| |
Ob du's glaubst oder nicht, aber DAS ist mir schon lange klar. Gottseidank ist mein Chef supercool und meinte: "Joa, ich gebe dir jetzt mal eine Liste von Standardfloskeln mit und schick mir ruhig deine erste Fassung, dann guck ich da mal drüber."
Das hat er auch bei unserer Postdoc gemacht, die hier in NZ ihre erste Review-Anfrage bekam. Sinngemäß: "Postdocs sind auch nur Studenten - nur lernen sie jetzt halt andere Skills als ein Doktorand. Ich finde, Profs müssen gerade bei Leuten auf ihrer ersten Postdoc-Stelle noch mithelfen, dass sie sich in dem ganzen Bürokratiedschungel, den sie jetzt meistern müssen, zurechtfinden."
Das ist schon eine ziemlich tolle Einstellung.
I'm gonna get some thumbtacks and colored string so we can diagram this.
|
|
|
|
|
|
|
|
|
|
|
Früh um sechs hat man ja bekanntlich die besten Ideen:
Es wurde/wird ja recht lange daran rumgedoktort, effiziente Sortieralgorithmen zu entwickeln.
Was würde denn passieren, wenn man einem Evolutionären Algorithmus als Argumente [1] eine Grammatik einer Programmiersprache*, [2] ein Rand-Int-Array und [3] die Ansage: "Ordne das so schnell wie möglich, mit einem Programm, dass du selbst mit der gegebenen Grammatik geschrieben hast!" mitgibt und das Ding sich dann einfach selber überlässt? Wäre es damit theoretisch(!) möglich (meinetwegen Zeit -> unendlich), einen effizienteren Algorithmus als alles, was es bisher gibt, zu finden?
* Das soll meine Bezeichnung dafür sein, dass der Algorithmus weiß, wie er "korrekte" Sätze in diesr Sprache erzeugen kann.
|
|
[Dieser Beitrag wurde 3 mal editiert; zum letzten Mal von _funktionsdelle am 23.12.2016 6:40]
|
|
|
|
|
|
|
|
|
|
Deine Frage anders formuliert: Gibt es einen Algorithmus aus der Menge aller Sortieralgorithmen, der effizienter für ein (oder alle?) Sortierprobleme arbeitet als alle Algorithmen aus der Menge der bekannten Sortieralgorithmen.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von [smith]
| | Zitat von Dumenikl
Ich bräuchte also Tips oder auch Literaturhinweise wie man diese Lücke zwischen den Einsteigertutorials und meiner gewünschten Anwendung schließt. Ich habe leider abseits der API keine Verwendung für C und damit auch kein Projekt dem ich mich zuwenden könnte.
| |
Hm, ich kann quasi kein C und deine Api kenne ich auch nicht, dafür habe ich jetzt über 15 Jahre Programmiererfahrung.
Mir persönlich hilft bei Einarbeitung in neue Apis ein Test-Driven-Ansatz.
Das heißt bei mir dann, dass ich mir z. B. eine einzige vielversprechende Api-Methode angucke, und dafür einen Unittest schreibe, damit ich diese Methode wirklich verstehe. Dieser Unittest braucht dann einen sinnvollen Assert, für den man vielleicht die zweite Api-Methode braucht. Total triviales Beispiel, vielleicht passt das ja bei dir:
1. Methode: Erzeuge Ton/Sample mit Frequenz xy
In einen Test bauen, ausführen, anhören, freuen.
2. Methode: Welche Töne werden gerade abgespielt und welche Frequenz haben sie?
In den Test einbauen und auf Frequenz xy testen. Passt das? Yay! Passt das nicht? Wtf, warum nicht?
Das ist jetzt erstmal ziemlich billig und wie gesagt, ich rate in deinem Kontext jetzt nur rum.
Danach lasse ich den Test dann wachsen, auch in Richtung meines eigentlichen Zieles. Z. B. in Richtung:
- Der Ton soll 5x in 10 Sekunden abgespielt werden. Kann ich das sinnvoll überprüfen?
- Der Ton soll mit crazy-shit-effekt-42 verzerrt werden. Kann ich das sinnvoll überprüfen?
Meine Erfahrung ist dabei, dass sich viele Sachen dann automatisch ergeben. Z. B. stellt man dann fest, dass die eine blöde Testmethode gar nicht mehr ausreicht und man das lieber in irgendwelche Klassen/Objekte/sonstwas auslagert. Oder dass man gerade den gleichen Code das dritte Mal getippt hat, und auch das lieber auslagert. Oder dass man den gewünschten Effekt nicht mehr sinnvoll überprüfen kann, und dieser eine Weg vielleicht eine Sackgasse war. An dieser Stelle fehlt die vermutlich die Erfahrung das sofort "zu sehen"... aber das sollte dich erstmal nicht entmutigen. Die kann man eben nur selber erlernen.
Wichtig ist dabei das ständige Feedback an dich, was über den ersten grünen Test bis zu 2+x Stunden Dauergefluche über die verdammte Drecksscheißapi (willkommen in der Programmierwelt!) reicht. Aber du kriegst in kleinen Schritten Erfolgsmeldungen, die dich motivieren, weiter zu machen.
Wenn du also dein großes Ziel vor Augen hast, du also weißt was am Ende rauskommen soll, brich es in kleine Teile und fang mit dem allereinfachste und kleinsten Teil an. Und wenn der so lächerlich wie 1+1 ist. Danach setzt du die nächste Stufe drauf, vielleicht musst du 1000 mal 1+1 in irgendeiner Schleife rechnen. Danach muss die Schleife vielleicht nur unter zwei von drei Bedingungen aufgerufen werden, sonst nicht. Danach ist eine der Bedingungen vielleicht, dass man in deinem Programm einen bestimmten Knopf gedrückt hat, der die Plugin-Api aufrufen kann.
Wenn es dann funktioniert, hast du üblicherweise drei Möglichkeiten:
- Yay, funktioniert. Scheiß auf die Codequalität, Wartung ist nur für Leute die Fehler machen. Arschprüfdaumen und Release! Give me your moneyzzzz!
- Hm, funktioniert zwar, aber das ist ja nur Testcode. Also alles wegschmeißen, komplett und ohne Ausnahme, und mit dem besseren Wissen neu bauen. Hinterher ist man eben schlauer.
- Yay, funktioni... ach verdammt, habe es gerade fertig bei Github/Stackoverflow von jemand anderem in nur 2 Zeilen Code gefunden. Eine Erfahrung reicher für das nächste Projekt.
| |
Ich bin ja mit tdd nie so warm geworden..Vielleicht weil ich es bis auf paar mal im Studium nie gemacht habe.... Ich meine..doof gesagt Debugge ich nun meine Tests statt meinen eigentlichen Code... Vielleicht sollte ich mich doch mal dazu zwingen..zumin privat..Vielleicht erschließt es sich mir dann mehr..
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Gepan.3dsvs.com am 23.12.2016 10:01]
|
|
|
|
|
|
|
|
|
| | Zitat von csde_rats
Deine Frage anders formuliert: Gibt es einen Algorithmus aus der Menge aller Sortieralgorithmen, der effizienter für ein (oder alle*?) Sortierprobleme arbeitet als alle Algorithmen aus der Menge der bekannten Sortieralgorithmen.
| |
Danke. Und wie ist die Antwort?
* Ich würde das int-rand-array, sowohl in Länge als auch Grad der "Sortiertheit" ab einem bestimmen Schwellwert von Dauer des Sortierens des aktuellen Arrays ändern. Dsa Ding sollte dann schon recht universell sein.
|
|
|
|
|
|
|
|
|
|
|
Ausm Bauch heraus: "Kann man nicht wissen"
Man weiß, dass die untere Schranke auf jeden so O(n) ist (z.B. Countingsort), intuitiv ist klar, dass es nicht < o(n) geht, man muss jedes Element mindestens mal angeschaut haben. Universelle Sortieralgorithmen (z.B. Timsort) sind O(n log n) worst case. Da ist, zumindest nach Landau, nicht so viel (unendlicher) Platz zur unteren Schranke...
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von csde_rats am 23.12.2016 10:40]
|
|
|
|
|
|
|
|
|
Ganz so einfach ist die Frage nicht zu beantworten, denn man muss sich dazu über einige Begriffe aus der Algorithmik klar werden. Sortieralgorithmen sind das plakative Beipiel, das gerne in Einführungsveranstaltungen verwendet wird, da es sehr intuitiv zu verstehen ist. Ich würde das aber als vom algorithmischen Standpunkt als gelöstes und nicht so sonderlich interessantes Problem bezeichnen.
Zuerst muss man sich darüber klar werden, welche Frage man eigentlich stellt. Wenn man einen Algorithmus möchte, der im Hinblick auf ein spezielles Array schnell sortiert, dann ist die triviale Lösung kaum zu schlagen: Der Algorithmus, der ohne die Eingabe anzusehen einfach das sortiere Array ausgibt. Genauso sieht's aus mit einer endlichen Menge von Eingaben, sagen wir alle int64-Arrays mit maximaler Länge von 10 Milliarden aus. Der triviale Algorithmus, der zu jeder möglichen Eingabe die korrekte Ausgabe kennt wird vermutlich der Schnellste sein. Man braucht also irgendeine Art von Unendlichkeit, um diese Frage wirklich sinnvoll stellen zu können. Normalerweise lässt man beim Sortieren zwei Unendlichkeiten zu: Die Zahlen im Array und die Anzahl der Zahlen dürfe beide beliebig groß sein, aber für jede Eingabe endlich. Dann fragt man, welcher Algorithmus für alle möglichen Suchprobleme der schnellste ist.
Damit eng verbunden ist die frage nach dem Maß. Wann bezeichnet man einen Algorithmus als schneller als einen anderen Algorithmus? Zur Analayse kann man nicht wirklich auf echte Laufzeiten zurückgreifen, denn die sind von viel zu vielen Faktoren abhängig, vor allem von der ausführenden Maschine. Darüber formale Aussagen zu treffen ist schwierig und auch relativ nutzlos, denn auf anderen Maschinen kann die Welt sehr anders aussehen. Deshalb beschränkt man sich normalerweise darauf, sich auf Rechenprimitive zu einigen, von denen man ausgeht, dass ihre Ausführung recht schnell geht, und dann zählt, wie oft sie vom Algorithmus benutzt werden. Bei Sortieralgorithmen verwendet man hierfür im Allgemeinen die Anzahl von notwendigen Vergleichen zwischen Paaren von Elementen. Für einen Algorithmus ist die Laufzeit dann eine Funktion von der Länge der Eingabe zu der Anzahl der benötigten Vergleiche im (je nach dem) schlimmsten oder durchschnittlichen Fall. Man geht dann üblicherweise noch einen Schritt weiter und lässt bei diesen Funktionen Vorfaktoren und dominierte Terme weg. Akademisch hat das seinen Sinn: Angenommen du hast zwei Algorithmen, einer braucht  Vergleiche und einer braucht  Vergleiche. Für kleine Eingaben macht das einen unterschied, aber wenn man nur n groß genug wählt, dann ist für beide Algorithmen eigentlich nur der Term wirklich relevant und sie brauchen irgendwann (näherungsweise) gleich lang. Wenn man einen Algorithmus für sich alleine stehen evaluieren will weiß man ja nun auch nicht, wie lang die Eingaben sein werden, also muss man "vom schlimmsten" ausgehen. Man nennt das dann auch die "(Laufzeit-)Komplexität" eines Algorithmus.
Der Grund für diesen langen Sermon ist nun folgender: Für alle Suchprobleme mit dem üblichen Maß der Komplexität gibt es keinen Algorithmus, der besser wäre als (sagen wir mal) Mergesort. Mergesort braucht im schlimmsten Fall in der Größenordnung von  Vergleiche und man kann beweisen, dass es nicht besser geht. Aus diesem Blickwinkel ist die Antwort auf deine Frage also nein, man kann keinen schnelleren Algorithmus finden.
Wenn man sich jetzt allerdings auf "eche Computer" und "echte Eingaben" beschränkt, also sagen wir mal meinen Laptop und zufälige Arrays die aus irgendeinem Zufallszahlengenerator rausfallen, dann sieht's anders aus. Mein Computer hat nicht genug Speicher um einen Algorithmus auszuführen, der zu jeder Eingabe die Ausgabe kennt, zumindest nicht für "interessante" Eingabegrößen (man merkt, wie's schwammig wird). Deshalb kann man hier schon die Frage stellen, welches (sagen wir mal) C-Programm mit welchem Compiler und welchem Betriebssystem auf meinem Laptop am schnellsten Zahlen sortiert. Da mein Laptop bisher im akademischen Umfeld quasi nicht untersucht wurde, gehe ich einfach mal davon aus, dass diese Frage bisher unbeantwortet geblieben ist. Und ich bin mir sicher, dass es einen Algorithmus gibt, der auf einer sinnvoll gewählten Eingabemenge (zumindest ein wenig) schneller zum Ziel kommt als gängige Sortieralgorithmen.
Wenn man akzeptiert, dass ein solches Programm existiert, dann gibt es einen ganz einfachen Algorithmus, um es in endlicher Zeit zu finden: Man schreibt nach und nach alle möglichen C-Programme und prüft, ob sie die Eingabemenge schneller sortieren als alle anderen Programme, die ich vorher hatte. Das geht, denn es gibt nur aufzählbar viele C-Programme. Eine intuitive Begründung dafür ist, dass jedes C-Programm endliche Länge hat und an jeder Stelle nur endlich viele Zeichen stehen können, also kann ich auch jedem Programm eine Nummer geben, nach der Länge geordnet. Dieser "Aufzählungsalgorithmus" kommt an dem besseren Programm, das nach diesem Schema auch eine Nummer hat, garantiert mal vorbei.
Die letzte Frage die dann noch bleibt, ist, ob dein genetischer Algorithmus mit genügend Zeit irgendwann mal bei jedem Programm vorbei kommt. Wenn das der Fall ist, dann findet auch der genetische Programmierer den besseren Algorithmus für meinen Laptop. Aber keinen besseren Algorithmus für alle möglichen Laptops und alle möglichen Eingaben.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von csde_rats
Man weiß, dass die untere Schranke auf jeden so O(n) ist (z.B. Countingsort), intuitiv ist klar, dass es nicht < o(n) geht, man muss jedes Element mindestens mal angeschaut haben. Universelle Sortieralgorithmen (z.B. Timsort) sind O(n log n) worst case. Da ist, zumindest nach Landau, nicht so viel (unendlicher) Platz zur unteren Schranke...
| |
|
|
|
|
|
|
|
|
| Thema: pOT-lnformatik, Mathematik, Physik XX ( Der XX(X)-Thread. ) |
|
![AUP [smith] 29.07.2010](./avatare/upload/U1066026--zeratul.png)
