|
|
|
|
| Zitat von wuSel
Morsezeichen ordnet man bitte in einem Baum an, ja!? Danke!
| |
bisschen overkill für die aufgabe, oder nicht? ein array wie bluay sagt reicht vollkommen aus und ist anschaulich denke ich verständlicher. ist denke ich auch einfacher zu implementieren als ein binärbaum incl. suche
was ich meine:
char tabelle [26][2] = {{a,.-},{b,-...},...};
oder muss man "a" benutzen ?
|
|
|
|
|
|
|
| Zitat von wuSel
Morsezeichen ordnet man bitte in einem Baum an, ja!? Danke!
| |
So und nicht anders. Stichwort: BST
|
|
|
|
|
|
|
Er soll doch was lernen, also kann er es auch gleich so machen wie man es wirklich machen würde und da ist es eben ein Baum.
Da ist dann auch die Suche / der Vergleich um EINIGES schneller als Stringvergleiche!
|
|
|
|
|
|
|
| Zitat von wuSel
Er soll doch was lernen, also kann er es auch gleich so machen wie man es wirklich machen würde und da ist es eben ein Baum.
Da ist dann auch die Suche / der Vergleich um EINIGES schneller als Stringvergleiche!
| |
Kannst du das etwas ausführlicher beschreiben?
/EDIT: kann damit momentan nichts anfangen...
/EDIT2:
| Zitat von NRG_Mash
was ich meine:
char tabelle [26][2] = {{a,.-},{b,-...},...};
oder muss man "a" benutzen ?
| |
Morsezeichen und Buchstaben in der selben tabelle?!
Und bedeutet die [2] nicht das in meinem Array nur 2 Zeichen platz haben?! (Es stehen allerdings bis zu 5 Zeichen drin?
Irgendwie bin ich gerade etwas überfordert....
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von otters am 26.04.2011 19:55]
|
|
|
|
|
|
|
|
|
|
| Zitat von otters
| Zitat von wuSel
Er soll doch was lernen, also kann er es auch gleich so machen wie man es wirklich machen würde und da ist es eben ein Baum.
Da ist dann auch die Suche / der Vergleich um EINIGES schneller als Stringvergleiche!
| |
Kannst du das etwas ausführlicher beschreiben?
/EDIT: kann damit momentan nichts anfangen...
| |
Wie im Wiki-Link beschrieben - es gibt ja immer nur 2 Möglichkeiten was nach . oder - kommen kann. Nämlich . oder -. Und wenn du dich dann am Baum entlang hangelst bist du immer in wenigen Schritten beim Ergebnis, der Aufwand entspricht also der Länge des Morsezeichens und du musst nicht so komplizierte Stringvergleiche fahren.
E: Außerdem ist das gleich eine schöne Übung einen Baum zu implementieren.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von wuSel am 26.04.2011 19:54]
|
|
|
|
|
|
| Zitat von wuSel
Er soll doch was lernen, also kann er es auch gleich so machen wie man es wirklich machen würde und da ist es eben ein Baum.
Da ist dann auch die Suche / der Vergleich um EINIGES schneller als Stringvergleiche!
| |
ja stimmt. aber so wie es für mich klang fängt er grade an in c zu programmieren und da gleich ein binärbaum programmieren zu lassen finde ich ein bisschen heftig. meine variante ist da einfacher und anschaulicher. deine methode ist natürlich effezienter aber um einiges schwerer zu programmieren, vorallem finde ich pointer am anfang schwerer zu verstehen als array und meine methode kommt ohne pointer aus, wenn ich mich nicht irre.
/btw: wie soll das mit dem baum funktionieren, wenn er alphabet -> morsezeichen machen will?
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von NRG_Mash am 26.04.2011 19:58]
|
|
|
|
|
|
Aber die Performance! Da muss schon ein wait-free HAT Trie her. Darunter geht's mal gar nicht.
|
|
|
|
|
|
|
| Zitat von NRG_Mash
| Zitat von wuSel
Er soll doch was lernen, also kann er es auch gleich so machen wie man es wirklich machen würde und da ist es eben ein Baum.
Da ist dann auch die Suche / der Vergleich um EINIGES schneller als Stringvergleiche!
| |
ja stimmt. aber so wie es für mich klang fängt er grade an in c zu programmieren und da gleich ein binärbaum programmieren zu lassen finde ich ein bisschen heftig. meine variante ist da einfacher und anschaulicher. deine methode ist natürlich effezienter aber um einiges schwerer zu programmieren, vorallem finde ich pointer am anfang schwerer zu verstehen als array und meine methode kommt ohne pointer aus, wenn ich mich nicht irre.
| |
siehe oben, bin selbst mit deiner methode schon etwas überfordert
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von otters am 26.04.2011 19:59]
|
|
|
|
|
|
| Zitat von [Dicope]
Aber die Performance! Da muss schon ein wait-free HAT Trie her. Darunter geht's mal gar nicht.
| |
Schöne Argumentation von Leuten die keine Lust haben sauber zu programmieren: "Aber ich brauch in meinem Beispiel keine Performance!"
Ja, eben... es ist ein verdammtes Beispiel. Ich hab ihm nur erklären wollen wie er es richtig macht und wie er es bei großen Problemen dann später auch angehen soll. Wenn es zu schwer ist, kann er immernoch auf die Array-Version umschwenken.
|
|
|
|
|
|
|
Ooooder aber eine implizite Baumstruktur. Die Idee gefällt mir sogar gerade ganz gut.
l = Länge des zu übersetzenden Morsecodes
m = Morsecode (z.B. 1101 für ..-.)
int idx = 0;
for(int i = 0; i < l; ++i) {
idx += i * m[i];
}
idx += (int)pow(2, l) - 2;
idx hat dann den Index in deiner Übersetzungstabelle, die wie folgt aufgebaut ist:
-|.|--|-.|... (siehe die farbige Tabelle unter http://de.wikipedia.org/wiki/Morsecode)
Kann ich gerne noch etwas mehr zu erzählen wenn es interessiert.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von [Dicope] am 26.04.2011 20:12]
|
|
|
|
|
|
| Zitat von wuSel
| Zitat von [Dicope]
Aber die Performance! Da muss schon ein wait-free HAT Trie her. Darunter geht's mal gar nicht.
| |
Schöne Argumentation von Leuten die keine Lust haben sauber zu programmieren: "Aber ich brauch in meinem Beispiel keine Performance!"
Ja, eben... es ist ein verdammtes Beispiel. Ich hab ihm nur erklären wollen wie er es richtig macht und wie er es bei großen Problemen dann später auch angehen soll. Wenn es zu schwer ist, kann er immernoch auf die Array-Version umschwenken.
| |
Du hast den Ironiesmilie gesehen, ja? Das es eine beknackte Idee ist, hier überhaupt über Thread safety und ähnliches nachzudenken ist mir auch klar.
|
|
|
|
|
|
|
| Zitat von otters
| Zitat von NRG_Mash
| Zitat von wuSel
Er soll doch was lernen, also kann er es auch gleich so machen wie man es wirklich machen würde und da ist es eben ein Baum.
Da ist dann auch die Suche / der Vergleich um EINIGES schneller als Stringvergleiche!
| |
ja stimmt. aber so wie es für mich klang fängt er grade an in c zu programmieren und da gleich ein binärbaum programmieren zu lassen finde ich ein bisschen heftig. meine variante ist da einfacher und anschaulicher. deine methode ist natürlich effezienter aber um einiges schwerer zu programmieren, vorallem finde ich pointer am anfang schwerer zu verstehen als array und meine methode kommt ohne pointer aus, wenn ich mich nicht irre.
| |
siehe oben, bin selbst mit deiner methode schon etwas überfordert
| |
ok dann probier ich es etwas verständlicher:
du hat ein char array aus 26x2 datenfeldern. stell die eine liste mit 2 spalten und 26 zeilen vor: in der ersten spalte steht z.b. der morsecode in der zweiten der entsprechende alphabet buchstabe z.b.:
usw.
hast du jetzt ein morsezeichen für das du den entschsprechenden buchstaben finden willst machst du ne schleife über die 1. spalte und vergleichst es mit den einträgen. dann hast du den index gefunden. dann musst du nur noch auf das element [index][1] zugreifen und hast deinen buchstaben. verstanden?
/e: c ist total der krampf, wenn man c++ gewöhnt ist
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von NRG_Mash am 26.04.2011 20:17]
|
|
|
|
|
|
| Zitat von [Dicope]
| Zitat von wuSel
| Zitat von [Dicope]
Aber die Performance! Da muss schon ein wait-free HAT Trie her. Darunter geht's mal gar nicht.
| |
Schöne Argumentation von Leuten die keine Lust haben sauber zu programmieren: "Aber ich brauch in meinem Beispiel keine Performance!"
Ja, eben... es ist ein verdammtes Beispiel. Ich hab ihm nur erklären wollen wie er es richtig macht und wie er es bei großen Problemen dann später auch angehen soll. Wenn es zu schwer ist, kann er immernoch auf die Array-Version umschwenken.
| |
Du hast den Ironiesmilie gesehen, ja? Das es eine beknackte Idee ist, hier überhaupt über Thread safety und ähnliches nachzudenken ist mir auch klar.
| |
Den Smilie macht doch hier jeder Depp neuerdings über jeden Post, danach kann man ja echt nichtmehr gehen.
Nein, hab ich nicht gesehen.
|
|
|
|
|
|
|
Ach ja - mein Vorschlag nennt sich übrigens Binary Heap.
Man könnte ja mal einen Wettbewerb starten, wer es am schnellsten schafft, X GB Morsedaten in einen String zu konvertieren. Das schreit ja geradezu nach SSE.
|
|
|
|
|
|
|
| Zitat von NRG_Mash
| Zitat von otters
| Zitat von NRG_Mash
| Zitat von wuSel
Er soll doch was lernen, also kann er es auch gleich so machen wie man es wirklich machen würde und da ist es eben ein Baum.
Da ist dann auch die Suche / der Vergleich um EINIGES schneller als Stringvergleiche!
| |
ja stimmt. aber so wie es für mich klang fängt er grade an in c zu programmieren und da gleich ein binärbaum programmieren zu lassen finde ich ein bisschen heftig. meine variante ist da einfacher und anschaulicher. deine methode ist natürlich effezienter aber um einiges schwerer zu programmieren, vorallem finde ich pointer am anfang schwerer zu verstehen als array und meine methode kommt ohne pointer aus, wenn ich mich nicht irre.
| |
siehe oben, bin selbst mit deiner methode schon etwas überfordert
| |
ok dann probier ich es etwas verständlicher:
du hat ein char array aus 26x2 datenfeldern. stell die eine liste mit 2 spalten und 26 zeilen vor: in der ersten spalte steht z.b. der morsecode in der zweiten der entsprechende alphabet buchstabe z.b.:
usw.
hast du jetzt ein morsezeichen für das du den entschsprechenden buchstaben finden willst machst du ne schleife über die 1. spalte und vergleichst es mit den einträgen. dann hast du den index gefunden. dann musst du nur noch auf das element [index][1] zugreifen und hast deinen buchstaben. verstanden?
| |
jap darunter kann ich mir was vorstellen....
Hab ich das dann falsch verstanden das mir z.B. mein char [4][2] angibt das ich ein array hab mit 4 Zeilen hab mit je platz für 2 zeichen?
|
|
|
|
|
|
|
| Zitat von [Dicope]
Ach ja - mein Vorschlag nennt sich übrigens Binary Heap.
Man könnte ja mal einen Wettbewerb starten, wer es am schnellsten schafft, X GB Morsedaten in einen String zu konvertieren. Das schreit ja geradezu nach SSE.
| |
ich weiß auch schon welche methode dabei nicht so gut abschneiden wird
/e:
| Zitat von otters
jap darunter kann ich mir was vorstellen....
Hab ich das dann falsch verstanden das mir z.B. mein char [4][2] angibt das ich ein array hab mit 4 Zeilen hab mit je platz für 2 zeichen?
| |
ne stimmt schon, denke ich. ich habs eben nicht gecheckt, dass ein char nur 1 zeichen enthält ich benutze nur c++ und benutze da für zeichen immer strings
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von NRG_Mash am 26.04.2011 20:22]
|
|
|
|
|
|
| Zitat von NRG_Mash
| Zitat von otters
jap darunter kann ich mir was vorstellen....
Hab ich das dann falsch verstanden das mir z.B. mein char [4][2] angibt das ich ein array hab mit 4 Zeilen hab mit je platz für 2 zeichen?
| |
ne stimmt schon, denke ich. ich habs eben nicht gecheckt, dass ein char nur 1 zeichen enthält ich benutze nur c++ und benutze da für zeichen immer strings
| |
okay, danke
ich hoff mal das ich jetzt weiter kommen werd
|
|
|
|
|
|
|
| Zitat von NRG_Mash
ne stimmt schon, denke ich. ich habs eben nicht gecheckt, dass ein char nur 1 zeichen enthält ich benutze nur c++ und benutze da für zeichen immer strings
| |
Speicherschänder!
|
|
|
|
|
|
|
| Zitat von [Dicope]
| Zitat von NRG_Mash
ne stimmt schon, denke ich. ich habs eben nicht gecheckt, dass ein char nur 1 zeichen enthält ich benutze nur c++ und benutze da für zeichen immer strings
| |
Speicherschänder!
| |
er hat es nicht anders verdient :P
|
|
|
|
|
|
|
Dass du so über ihn redest wird dir noch leid tun! Machs wenigstens wo er es nicht hört!
|
|
|
|
|
|
|
| Zitat von [Dicope]
Man könnte ja mal einen Wettbewerb starten, wer es am schnellsten schafft, X GB Morsedaten in einen String zu konvertieren. Das schreit ja geradezu nach SSE.
| |
Mir war langweilig, also dachte ich mir "warum nicht".
Als Test habe ich einfach mal rund 15MB Lorem Ipsum (~45MB Morse) erzeugt und ihn ein bisschen hübscher gemacht um ihn einfacher verarbeitbar zu machen.
Im Archiv finden sich 4 Dateien, text_oneline, text_wrapped, morse_oneline und morse_wrapped. Die _wrapped Varianten haben jeweils ein Wort pro Zeile, _oneline trennen mit Leerpausen.
Morsedaten: Download (~15MB)
Im Text trennen einfache Leerpausen Wörter von Großbuchstaben, es gibt keine Satzzeichen o.ä. Im Morsecode gibt es "-" und "." für lang und kurz, Buchstaben werden getrennt durch einfache Leerzeichen und in der _oneline-Variante sind Worte getrennt durch dreifache Leerzeichen.
Da ich keine Lust hatte irgendwelche Bäume zu baun habe ich einfach eine "Grundlinie" gezogen indem ich ein einfaches Perlscript geschrieben habe das einen Hashtable-Lookup macht. Da mir keine bessere Variante eingefallen ist die Zeit zu messen habe ich zwei Scripte gemacht, eine mit einfachem Print, eine mit integriertem Lookup und die Ergebnisse vergleichen. Ich denke mal das ist nicht sonderlich ideal, wer weiß wie mans besser machen kann bitte sagen.
Jeweils 5 Umwandlungen, daraus den Mittelwert ergibt bei mir 1.1766672 s die auf das Umwandeln der Strings abfallen, geteilt durch 12982420 Umwandlungen gibt das etwa 90ns (3GHz) pro Lookup. Die benutzen Scripts.
Macht's besser!
e/ Im Download sind jetzt noch 2 sample-Dateien mit den jeweils ersten 50 Zeilen der wrapped-Varianten. Damit die nicht jeder selbst machen muss .
Außerdem zur Fehlersuche hier die Liste von Morsecode die ich verwendet habe, ich hoffe ich hab mich nirgends vertan:
|
Code: |
%morse = (
".-" => "A",
"-..." => "B",
"-.-." => "C",
"-.." => "D",
"." => "E",
"..-." => "F",
"--." => "G",
"...." => "H",
".." => "I",
".---" => "J",
"-.-" => "K",
".-.." => "L",
"--" => "M",
"-." => "N",
"---" => "O",
".--." => "P",
"--.-" => "Q",
".-." => "R",
"..." => "S",
"-" => "T",
"..-" => "U",
"...-" => "V",
".--" => "W",
"-..-" => "X",
"-.--" => "Y",
"--.." => "Z",
"-----" => "0",
".----" => "1",
"..---" => "2",
"...--" => "3",
"....-" => "4",
"....." => "5",
"-...." => "6",
"--..." => "7",
"---.." => "8",
"----." => "9",
); |
|
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von B0rG* am 27.04.2011 14:56]
|
|
|
|
|
|
morgen probier ichs auch mal.
|
|
|
|
|
|
|
So, mein Programm: http://pastie.org/1838998
Liest den Code ein, dekodiert und schreibt das Ergebnis, Wörter durch Leerzeilen getrennt, in eine Datei output.txt.
Ein Lookup dauert (ohne viel gemittelt zu haben usw.) 6,4 ns.
Ermittelt hab ich das ähnlich wie Borg.
Algorithmus: Die chars stehen in einem 2-D Array map[a][b]. a ist die Länge des Codes, b die Zahl, die der code bildet, wenn man ihn als Binärzahl auffasst, mit . = 1, - = 0
Also Beispiel:
-... = 0111 = 7 => map[4][7] = B.
Somit brauche ich pro Lookup nur einen Arrayzugriff, lediglich muss ich mir halt die Array Indizes basteln. Man muss dazu sagen, dass ich die Länge des Buchstaben schon kenne, zum Zeitpunkt des Lookups. Auf die 6ns kommt also noch ein strlen() bzw. vergleichbares drauf.
Ich entschuldige mich für unkommentierten und hässlichen Code.
Oli
/e: 2,16 Ghz
|
[Dieser Beitrag wurde 5 mal editiert; zum letzten Mal von OliOli am 27.04.2011 15:30]
|
|
|
|
|
|
Ich hab' da mal ne Frage:
Zur Berechnung des Gewichts eines Planeten habe ich hier irgendwie zwei Formeln:
a³/p²=g*m
und
a³/p²=m
Ich kriege mit beiden merkwürdige Resultate raus - deshalb: Welche von den beiden ist korrekt und wie würde ich damit z.B. das Gewicht unseres Mondes bestimmen?
|
|
|
|
|
|
|
Hat einer nen tollen Link, eine Buchempfehlund oder zuviel Zeit?
Kann mir einer erklären, wie diese tollen Spinsummen funktionierne?
Also ich hab hier Spionoren und dann soll gelten:
bzw
Ich hab mir das jetzt in 3 Büchern durchgelesen aber irgendwie raff ich nicht was die machen, oder die hängen mich vorher schon ab, z.B. im Peskin - Introduction in QFT leiten die das aus der Lösung der Dirac-Gleichung für ein freies Teilchen her. Aber da hängen die mich mit ner komischen Form von Lorentz-Boost ab
|
|
|
|
|
|
|
Ich soll hier in einer Übungsaufgabe ein Programm schreiben, dass für eine eingegebene Zahl z den kleinsten Wert x ermittelt, der z<z+x erfüllt.
Datentyp ist double.
Dazu hab ich eine Schleife, in der ich eben x kleiner werden lasse und mir für jeden Schritt z+x ausgeben lasse. Allerdings ist das ausgegebene z+x schon ziemlich schnell gleich z, wohingegen die Schleife noch wesentlich länger läuft, bis schließlich das kleinste x ausgegeben wird.
Woran liegt das? [dau]Sind die Ausgaben weniger genau, als die tatsächlich zum Rechnen verwendeten Zahlen?[/dau]
|
|
|
|
|
|
|
Dazu müsste man wissen, welche Sprache und wie du ausgibst ...
|
|
|
|
|
|
|
c++.
|
Code: |
main()
{
double x=1;
double z;
cout<<"z eingeben:";
cin>>z;
double c=z+x;
while (z<c)
{
x=x/2;
c=z+x;
cout<<"x ist: "<<x<<", z+x ist: "<<c<<endl;
}
cout<<"x_1 ist: "<<x<<", z+x ist: "<<c<<endl;
} |
|
|
|
|
|
|
|
|
std::cout.precision(30);
std::cout.setf(std::ios::fixed,std::ios::floatfield);
vorher reinhauen, dann siehst du viele nachkommastellen
|
|
|
|
|
|
Thema: pOT-Informatiker, Mathematiker, Physiker V ( Haaahaaaaahaa...LabView...Hahahahaaa...oh wow ) |