|
|
|
|
| Zitat von Rufus
| Zitat von Oli
Außerdem: 5N ist immer schlechter als N. Als Informatiker mag das äquivalent sein, aber ...
| |
Komplexitätsbegriff der Informatiker außer Acht lassen? Ganz wie du willst: Dann soll dein Anwender halt schnellere Hardware kaufen.
| |
Auch auf schnellerer Hardware ist 5N schlechter als N.
|
|
|
|
|
|
|
Apropos, meine Newtonverfahren konvergieren nicht...
|
|
|
|
|
|
|
| Zitat von Olschi
Danke.
Vielleicht kann ich dann wieder in Ruhe penen.
| | Relativ einfach erklärt ist noch das hier: Grob gesagt behauptet man dass die Existenz der Cesaro-Summe bedeutet dass die Folge gegen diesen Wert konvergiert. Ist aber nicht so, und damit stimmt das erste Gleichheitszeichen nicht und reißt den Rest der Rechnung mit in den Abgrund.
|
|
|
|
|
|
|
| Zitat von Virtus
| Zitat von Rufus
| Zitat von Oli
Außerdem: 5N ist immer schlechter als N. Als Informatiker mag das äquivalent sein, aber ...
| |
Komplexitätsbegriff der Informatiker außer Acht lassen? Ganz wie du willst: Dann soll dein Anwender halt schnellere Hardware kaufen.
| |
Auch auf schnellerer Hardware ist 5N schlechter als N.
| |
Ja is schon klar. Ich würde Oli auch lieber mögen als mich.
|
|
|
|
|
|
|
| Zitat von Wraith of Seth
Apropos, meine Newtonverfahren konvergieren nicht...
| |
Newton verfahren versagt gerne, wenn deine funktion ne Art Plateau hat. Bei Nullstellen suche, hab ich immer Bisektion gemacht, das klappt viel besser und da kann man auch eklige Sachen reinwerfen, bevor das numerisch nicht mehr einwandfrei funktioniert.
|
|
|
|
|
|
|
| Zitat von Rufus
Ja is schon klar. Ich würde Oli auch lieber mögen als mich.
| | wat? Depri Samstag?
|
|
|
|
|
|
|
Realism Sunday
|
|
|
|
|
|
|
|
|
|
|
| Zitat von Oli
| Zitat von Rufus
Ja is schon klar. Ich würde Oli auch lieber mögen als mich.
| | wat? Depri Samstag?
| |
Meine Hardware schafft nur 3N.
|
|
|
|
|
|
|
| Zitat von Rufus
Ich überlege die ganze Zeit, ob nlogn möglich wäre, aber ich bezweifle es irgendwie.
| |
Eine Lösung in O(n) ist eine Lösung in O(n log n). Ich nehme an du meinst eine Lösung in O(log n), was maximal möglich wäre wenn du die Länge der Eingabe im Voraus kennst, sonst kannst du ja nichtmal z.B. eine binäre Suche machen.
Ich gehe jedoch stark davon aus dass die O(n) Grenze auch im anderen Fall "scharf" ist, aber ich werde mal etwas drüber nachdenken, wenn das auch nicht sonderlich wohldefiniert ist.
Was mir spontan einfällt sind "Intervallbäume" (augmentierte balancierte Binärbäume), bei denen immerhin Lookups in O(log n) gehen, was interessant ist wenn sich diese Liste ändert. Aber hier dauert das Bauen natürlich auch mindestens O(n).
---
Tut mir Leid dass ich hier mal den Fachnazi spielen muss.
| Zitat von Oli
Außerdem: 5N ist immer schlechter als N. Als Informatiker mag das äquivalent sein, aber ein Anwender freut sich auch über einen konstanten Faktor in der Geschwindigkeit. Wenn meine Simulationen anstatt in einer Woche an einem Tag durchlaufen würden, schwebte ich auf Wolke 7.
| |
Das ist so nicht ganz richtig. Komplexität von Programmen sind asymptotische Aussagen. Es mag schon sein, dass ein Algorithmus für beliebig große Eingaben schneller ist als ein anderer, aber das heißt nicht, dass das auch für "realistische" Eingaben der Fall ist. Ein Standardbeispiel sind hierfür zwei Algorithmen, die die folgenden Zeitschranken haben:
T(n) = log n + 10^6 in O(log n)
T'(n) = n in O(n)
Und dennoch ist der zweite Algorithmus für Eingaben bis zur Größe eine Million besser.
Klar wirkt dieses Beispiel kontrutiert, aber es gibt viele Algorithmen bei denen das eine Rolle spielt.
Was ich damit sagen will: Wenn man sich schon Konstanten anschaut, was seeeehr fragwürdig ist weil keiner weiß ob drei Schleifen im Code auch drei Schleifen im Assembler sind, aber wenn schon dann muss man etwas genauer hinsehen.
e/ Eine "Rechtfertigung" warum man sich in der Theorie an Asymptotische Betrachtungen hält ist übrigens das linear speedup theorem.
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von B0rG* am 23.03.2014 15:36]
|
|
|
|
|
|
| Zitat von B0rG*
Was ich damit sagen will: Wenn man sich schon Konstanten anschaut, was seeeehr fragwürdig ist weil keiner weiß ob drei Schleifen im Code auch drei Schleifen im Assembler sind, aber wenn schon dann muss man schon etwas genauer hinsehen.
| |
Ich habe extra keine O Notation verwendet, um so eine Erbsenzählerei zu vermeiden. Fakt ist, für mich zählen die Konstanten Faktoren, besonders weil die Mainloops in meinen Simulationen _sehr_ häufig durchlaufen. Wenn man da ein bisschen sparen kann, dann freue ich mich immer.
|
|
|
|
|
|
|
Es scheint mir einer von euch redet von einem konstanten Faktor, der andere von einem konstanten additiven Term.
Edit: WoS, mal andere Startwerte ausprobiert? Das hilft schonmal. Sonst wie oben erwaent Bisektion und dann gegebenenfalls noch auf Newton wechseln fuer mehr (schnellere) Genauigkeit.
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von _abyss am 23.03.2014 15:44]
|
|
|
|
|
|
Klar sind Vorfaktoren wichtig in konkreten Fällen, aber die Aussage "Dieser Algorithmus läuft in 'O(5n)'" ist einfach sehr haltlos da sie von so vielen Faktoren abhängt.
e/ Speziell vielleicht zur Beschwichtigung, Oli, ich weiß schon was du meinst, aber: Rufus' Argument dass man sich andere Hardware kaufen soll ist in diesem Falle höchst Relevant da lineare Vorfaktoren zentral von der verwendeten Hardware abhängen.
---
Der additive Term ist nur ein Beispiel, das man schnell versteht.
|
[Dieser Beitrag wurde 3 mal editiert; zum letzten Mal von B0rG* am 23.03.2014 15:54]
|
|
|
|
|
|
| Zitat von B0rG*
was maximal möglich wäre wenn du die Länge der Eingabe im Voraus kennst, sonst kannst du ja nichtmal z.B. eine binäre Suche machen.
| |
doch, kann man, in O(logn)
|
|
|
|
|
|
|
Woher weißt du wo die Mitte ist?
e/ Ich lasse mit mir reden dass man in O(log n) die Mitte finden kann wenn man O(1) Zugriff auf Elemente Hat, was aber z.B. bei Turingmaschinen nicht der Fall ist. Hach, diese Abhängigkeiten von der Maschine.
e2/ Wiederum Beschwichtigung: Ich hätte mich klarer Ausdrücken sollen mit "Die binäre Suche die in O(log n) geht wird dann jedoch evtl dominiert vom Finden der Mitte.".
|
[Dieser Beitrag wurde 3 mal editiert; zum letzten Mal von B0rG* am 23.03.2014 16:00]
|
|
|
|
|
|
Danzelot verfolgt die Diskussion sicher interessiert.
|
|
|
|
|
|
|
| Zitat von B0rG*
Ich gehe jedoch stark davon aus dass die O(n) Grenze auch im anderen Fall "scharf" ist, aber ich werde mal etwas drüber nachdenken, wenn das auch nicht sonderlich wohldefiniert ist.
| |
Ich denke dass die Eingabe [1 0 0 1 0 0 1 0 0 1 ...] ein Beispiel dafür ist, dass es keinen Algorithmus geben kann der schneller ist als O(n), da man hier tatsächlich jedes Bit anschauen muss und nicht sich von einer Ansammlung von Einsen ausbreiten kann.
|
|
|
|
|
|
|
| Zitat von SilentAssassin
| Zitat von Wraith of Seth
Apropos, meine Newtonverfahren konvergieren nicht...
| |
Newton verfahren versagt gerne, wenn deine funktion ne Art Plateau hat. Bei Nullstellen suche, hab ich immer Bisektion gemacht, das klappt viel besser und da kann man auch eklige Sachen reinwerfen, bevor das numerisch nicht mehr einwandfrei funktioniert.
| |
Soweit ich das sehe, ist das erstmal ein Verfahren für skalare Funktionen (allerdings bin ich gerade zuhause und weiß nicht, ob in meinen schlauen Büchern im Büro noch multidimensionale Verfahren schlummern). Außerdem kann ich nicht garantieren, dass die "Randwerte", die ich habe, verschiedene Vorzeichen haben - zumindest, wenn ich jede Komponente meiner Vektoren einzeln als skalare Funktion betrachte.
Und ich glaube, heute sammel ich nur Idee, was ich morgen machen kann, um das Verfahren zu retten. Zwischen Donnerstag und Samstag habe ich irgendwas zwischen 38h und 45h im Büro verbracht. Das neue Medikament hilft mir zwar massiv überhaupt produktiv zu arbeiten, aber macht mich auch nicht beliebig frustresistent...
Proposal concept #30: You propose at a close friends funeral. - Next.
|
|
|
|
|
|
|
Kann hier wer mal gerade unter Sage in der Cloud testen, ob im Terminal die eckige Klammer [ funktioniert? Konkret habe ich gerade nur einen Rechner, auf dem ich das testen kann - aber dort ist es unabhängig vom Browser so, dass AltGr+8, aka [, im Terminal dem Backspace entspricht. In den Cloud-Editoren für .sage oder .tex oder was auch immer nicht.
WTF? Ist das nur bei mir so?
Ohne dieses Feature ist es gerade etwas... ...schwer, Listen zu verwenden...
That is what a 404 error feels like.
|
|
|
|
|
|
|
Tastaturbelegung auf "englisch" umstellen und "[" "ü" drücken.
|
|
|
|
|
|
|
| Zitat von Virtus
Tastaturbelegung auf "englisch" umstellen und "[" "ü" drücken.
| |
Erklärt nicht, warum ich bei einer deutschen Tastaturbelegung unter Linux nie Probleme habe.
*grübel* Aber dabei fällt mir auf, dass ich nciht weiß, ob ich jemals unter Windows auf die Cloud zugegriffen habe.
Trotzdem würde mich interessieren, ob das Problem auch andere haben.
Es wird einen Edit geben, wenn es unter einer englischen Tastatur weiterbesteht.
Problem vorerst gelöst. Aber warum hatte ich das sonst nie mit einer deutschen Tastaturbelegung?
Why can't we piss off a fuzzy planet? Still dangerous, but hey, bunnies.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Wraith of Seth am 23.03.2014 22:54]
|
|
|
|
|
|
| Zitat von B0rG*
| Zitat von B0rG*
Ich gehe jedoch stark davon aus dass die O(n) Grenze auch im anderen Fall "scharf" ist, aber ich werde mal etwas drüber nachdenken, wenn das auch nicht sonderlich wohldefiniert ist.
| |
Ich denke dass die Eingabe [1 0 0 1 0 0 1 0 0 1 ...] ein Beispiel dafür ist, dass es keinen Algorithmus geben kann der schneller ist als O(n), da man hier tatsächlich jedes Bit anschauen muss und nicht sich von einer Ansammlung von Einsen ausbreiten kann.
| |
Das O Kalkül bezieht sich aber im Normalfall nicht auf die Abhängigkeit von Bits, sondern einer größeren logischen Einheit.
|
|
|
|
|
|
|
Ich nehme an du meinst man betrachtet nicht unbedingt Bits sondern z.b. die Zahlen die sie kodieren, dann kommt's halt drauf an (tm) was einem gerade wichtig ist (z.B. Stichwort Pseudopolynomiell).
Hier meine ich die Wahrheitswerte die im Vektor gespeichert werden, dabei ist n die Länge des Vektors.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von B0rG* am 23.03.2014 23:26]
|
|
|
|
|
|
| Dear Peter Higgs and Researchers in the CERN!
Your "discovered boson" which was detected in the LHC, is simply one Xenon atom of the 1 trillion 167 billion 20 million Xenon atoms which there are in the LHC! | |
Ich dachte ich lass euch das mal hier
|
|
|
|
|
|
|
Hätten sie da mal dran gedacht. Was für eine riesen Eselei!
Jesus, das ist Gold!
In hungary the people say: One swallow don’t makes summer.
How was informed the Higgs boson that (s)he is wanted in the LHC? In
what place were the other Higgs bosons? Only one Higgs boson received
invitation for the collisions?
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von Oli am 24.03.2014 13:20]
|
|
|
|
|
|
Ich habe ein paar Data Mapper die meine Domain Models wegspeichern. Nun sind davon zwei abhängig, einer speichert Teile in einen SOAP-Service, der andere Teile in eine Datenbank. Wenn einer von beiden schief geht, soll der andere natürlich nicht speichern. Gibs da irgendwas feines als Pattern?
|
|
|
|
|
|
|
Hm, ein wenig mehr Kontext wäre nett, was hast du denn zur Verfügung?
Meine erste spontane Idee wäre ein CDI-Event, denn da fliegen mögliche Exception des Observers auch auf der fire()-Seite (siehe CDI-Spec).
|
|
|
|
|
|
|
Gerade ist mein gordischer Knoten mit der Elliptizität der äußeren Ableitung zerfetzt worden. Von mir. Mit einem Schwert. Boah, was ein geiles Gefühl, als ich begriffen habe, was die Bündel sind, um die es hier geht und wie deren Dimension aussieht...
Geiles. Gefühl.
Vielleicht habe ich ja doch noch eine Chance, mein Mathediplom zu schaffen.
What is it? More work? That's it, I'm dead.
|
|
|
|
|
|
|
| Zitat von [smith]
Hm, ein wenig mehr Kontext wäre nett, was hast du denn zur Verfügung?
Meine erste spontane Idee wäre ein CDI-Event, denn da fliegen mögliche Exception des Observers auch auf der fire()-Seite (siehe CDI-Spec).
| |
Meinst du mich?
|
|
|
|
|
|
|
Oh oh oh, level up!
|
|
|
|
|
|
Thema: pOT-lnformatik, Mathematik, Physik XVI ( Ship painting activities ) |