Hallo liebes Forum, ich möchte das Array vorher nicht initialisieren
sondern diese kleine Tabelle soll nur einmal dort stehen wo sie auch
verwendet wird.
Falk B. schrieb:> Und was hast du jetzt gewonnen?>> Speicherplatz gespart? Nein.> Schnelleres Programm? Nein.> Übersichtlicheres Programm? Nein.>> Hmm, eine etwas magere Bilanz.
Er hat was dazu gelernt. Unbezahlbar.
Markus F. schrieb:> Falk B. schrieb:>> Und was hast du jetzt gewonnen?>>>> Speicherplatz gespart? Nein.>> Schnelleres Programm? Nein.>> Übersichtlicheres Programm? Nein.>>>> Hmm, eine etwas magere Bilanz.>> Er hat was dazu gelernt. Unbezahlbar.
Um was in Zukunft zu erreichen? Ein Array in den Kopf einer For-Schleife
zu pressen und NOCH mehr kryptische C-Syntax zu nutzen? Tolle Leistung!
Falk B. schrieb:> Um was in Zukunft zu erreichen? Ein Array in den Kopf einer For-Schleife> zu pressen und NOCH mehr kryptische C-Syntax zu nutzen? Tolle Leistung!
Da wir das Programm nicht kennen ist es schwer das zu beurteilen, nech?
Falk B. schrieb:> Um was in Zukunft zu erreichen? Ein Array in den Kopf einer For-Schleife> zu pressen und NOCH mehr kryptische C-Syntax zu nutzen? Tolle Leistung!
... um künftig für das passende Problem die passende Lösung parat zu
haben?
Compound literals kann man durchaus lesbar und auf den Punkt (sinnvoll)
benutzen:
Dennsi W. schrieb:> H = "0123456789ABCDE"[n%16];> Klassiker, bei dem das Array nur einmal verwendet wird und es super Sinn> ergibt das alles an einem Ort stehen zu haben.
Super, mit eingebautem Buffer Overflow, glücklicherweise aber nur in
Leserichtung. :-/
Andreas S. schrieb:> Dennsi W. schrieb:>> H = "0123456789ABCDE"[n%16];>> Klassiker, bei dem das Array nur einmal verwendet wird und es super Sinn>> ergibt das alles an einem Ort stehen zu haben.>> Super, mit eingebautem Buffer Overflow
Wie kann hier bei einem unsigned n ein Buffer-Overflow entstehen. Selbst
wenn n (jeder Logik widersprechend) signed wäre, wäre die Gefahr eines
Buffer-Overflows nicht größer als bei jedem anderen Array-Zugriff.
Möchtest du deswegen Arrays komplett verbieten?
Anmerkung: Ja, das fehlende 'F' habe ich schon bemerkt ;-)
Markus F. schrieb:> Ein Buffer-Overflow ist das nicht.
Es ist aber ein Lesezugriff auf einen nicht gültigen Bereich. Je nachdem
wo der liegt passieren halt mehr oder weniger schlimme Dinge.
Markus F. schrieb:> Er hat was dazu gelernt. Unbezahlbar.Andreas S. schrieb:>> Übersichtlicheres Programm? Nein.>> Doch.
Nein.
Das ist weder übersichtlich noch hat er dazugelernt, wie man das sauber
und leserlich schreibt. Er hat lediglich dazugelernt, wie man sich
maximal unleserlich und schlecht wartbar ausdrücken kann.
Jaja, in C kann man eine Menge an abenteuerlichen Konstrukten schreiben,
die rein formal durchaus gültiger Code sind. Aber MUSS MAN DAS dann auch
noch tatsächlich tun? Nein, natürlich nicht.
Man kann so ein Array auch ganz bieder und außerhalb irgendwelcher
Schleifen hinschreiben und es auf übliche Weise benutzen.
Das geht!
Warum also derartige Verrenkungen? Um dem Rest der Welt zu zeigen, wie
toll man ist? Männliches Imponiergehabe anstelle rationaler Vernunft?
W.S.
M.K. B. schrieb:> Markus F. schrieb:>> Ein Buffer-Overflow ist das nicht.>> Es ist aber ein Lesezugriff auf einen nicht gültigen Bereich. Je nachdem> wo der liegt passieren halt mehr oder weniger schlimme Dinge.
Da es ein Stringliteral ist, kommt noch die '\0' dazu.
Daher gibt es keinen ungültigen Zugriff.
Peter D. schrieb:> Dennsi W. schrieb:>> H = "0123456789ABCDE"[n%16];>> Ist aber nicht sonderlich effizient.
Was sollte daran nicht effizient sein? Gut, es braucht ein paar Bytes
Speicher mehr, dafür vermutlich ein paar Taktzyklen weniger. Am Ende
dürfte das aber sehr selten eine Rolle spielen.
Rolf M. schrieb:> DPA schrieb:>> Ist doch beides O(1), sowohl Laufzeit, als auch Speicher, oder?>> Bezogen worauf? Die O-Notation macht hier doch überhautp keinen Sinn.
Warum nicht? Der Speicherverbrauch und die Laufzeit ist doch hier immer
Konstant, egal welche zahl/welches Zeichen, etc. O(1) ist doch quasi
Konstante Laufzeit/Speicherverbrauch, und da das hier immer der Fall
ist, brauch ich doch keinen Bezugspunkt oder sonstige Einschränkungen,
oder?
Peter D. schrieb:> Dennsi W. schrieb:>> H = "0123456789ABCDE"[n%16];>> Ist aber nicht sonderlich effizient. Besser:n &= 0x0F;> n += n < 10 ? '0' : 'A' - 10;
Das hängt stark von der Zielplattform und dem verwendeten Compiler ab.
DPA schrieb:> Ist doch beides O(1), sowohl Laufzeit, als auch Speicher, oder?
Zwei O(1)-Algorithmen können sich in der tatsächlichen Laufzeit um einen
beliebig großen Faktor unterscheiden.
Yalu X. schrieb:> Zwei O(1)-Algorithmen können sich in der tatsächlichen Laufzeit um einen> beliebig großen Faktor unterscheiden.
Was bedeutet denn diese 0(1) Geschichte?
Peter D. schrieb:> Dennsi W. schrieb:>> H = "0123456789ABCDE"[n%16];>> Ist aber nicht sonderlich effizient.
Doch, ist es, da branch-free, und außerdem ohne zusätzliche Addition.
Das ineffiziente %16 wird der Compiler automatisch durch &0x0F ersetzen.
Dein Vorschlag ist weniger effizienz in Bezug auf Geschwindigkeit.
Nop schrieb:> Peter D. schrieb:>> Dennsi W. schrieb:>>> H = "0123456789ABCDE"[n%16];>>>> Ist aber nicht sonderlich effizient.>> Doch, ist es, da branch-free, und außerdem ohne zusätzliche Addition.> Das ineffiziente %16 wird der Compiler automatisch durch &0x0F ersetzen.> Dein Vorschlag ist weniger effizienz in Bezug auf Geschwindigkeit.
Weder Peters noch deine Aussage ist allgemein richtig. Wie ich oben
schon geschrieben habe, hängt das stark von der Zielplattform und dem
verwendeten Compiler ab.
Peter hat recht für die AVR-CPUs (für die er wohl hauptsächlich
programmmiert), da diese relativ schnell springen, aber Array-Zugriffe
nur mäßige gut unterstützen. Der Unterschied ist aber nicht sehr groß: 6
Zyklen für Peteres Variante, 7 Zyklen für die Array-Methode.
Du hast teilweise recht für die meisten dickeren CPUs (x86, ARM usw.),
die eine gute Array-Unterstützung bieten, aber auf Grund ihrer langen
Pipeline u.U. nur langsam springen. Dennoch ist der Vorsprung der
Array-Methode gering (oder evtl. gar nicht vorhanden), weil ein schlauer
Compiler den Sprung als größten Zeitfresser wegoptimiert.
Die Länge des Compilats ist (für mich im ersten Augenblick überraschend)
stark davon abhängig, ob n signed oder unsigned ist.
Läßt sich übrigens hier:
https://godbolt.org/
flott und bequem für verschiedene Compiler und Plattformen durchspielen.
DPA schrieb:> Rolf M. schrieb:>> DPA schrieb:>>> Ist doch beides O(1), sowohl Laufzeit, als auch Speicher, oder?>>>> Bezogen worauf? Die O-Notation macht hier doch überhautp keinen Sinn.>> Warum nicht? Der Speicherverbrauch und die Laufzeit ist doch hier immer> Konstant, egal welche zahl/welches Zeichen, etc. O(1) ist doch quasi> Konstante Laufzeit/Speicherverbrauch,
Die O-Notation gibt nicht die Laufzeit eines Algorithmus an, sondern wie
er skaliert. Also wenn man beispielsweise einen Sortieralgorithmus hat,
wie stark die Laufzeit von der Anzahl der zu sortierenden Elemente
abhängt. Hier gibt's nur ein Element - eine Zahl. Und Algorithmen werden
schrittweise ausgeführt. Hier gibt's nur einen Schritt.
> und da das hier immer der Fall ist, brauch ich doch keinen Bezugspunkt> oder sonstige Einschränkungen, oder?
Meine Frage war, auf welche Anzahl du dich beziehst. Es gibt hier keine
Anzahl.
Rolf M. schrieb:> DPA schrieb:>> Rolf M. schrieb:>>> DPA schrieb:>>>> Ist doch beides O(1), sowohl Laufzeit, als auch Speicher, oder?>>>>>> Bezogen worauf? Die O-Notation macht hier doch überhautp keinen Sinn.>>>> Warum nicht? Der Speicherverbrauch und die Laufzeit ist doch hier immer>> Konstant, egal welche zahl/welches Zeichen, etc. O(1) ist doch quasi>> Konstante Laufzeit/Speicherverbrauch,>> Die O-Notation gibt nicht die Laufzeit eines Algorithmus an, sondern wie> er skaliert.
"Konstante Laufzeit" ist eine Angabe der Skalierung der Laufzeit. Ich
sage nirgends etwas zur effektiven Laufzeit des Algorithmus.
> Also wenn man beispielsweise einen Sortieralgorithmus hat,> wie stark die Laufzeit von der Anzahl der zu sortierenden Elemente> abhängt. Hier gibt's nur ein Element - eine Zahl. Und Algorithmen werden> schrittweise ausgeführt. Hier gibt's nur einen Schritt.
Und das ist ein weiterer Grund, warum die Laufzeit Konstant, und damit
O(1) ist.
>> und da das hier immer der Fall ist, brauch ich doch keinen Bezugspunkt>> oder sonstige Einschränkungen, oder?>> Meine Frage war, auf welche Anzahl du dich beziehst. Es gibt hier keine> Anzahl.
Und das zeigt lediglich, dass die Frage hier keinen Sinn macht. Die
O-Notation setzt keine Anzahl voraus. Hätte ich eine sleep(n) funktion,
wäre dessen Laufzeit O(n), also die Laufzeit skaliert linear zum Wert
von n der sleep funktion. Bei sleep(60*60*24*365) wäre die Laufzeit
wieder O(1). Ich kann auch mehr als einen Parameter haben, und ein
Parameter kann auch eine Anzahl sein, etc.
Um dir noch mal anders die Absurdität der Frage aufzuzeigen: Du darfst 1
Kugel nehmen. Relativ zu wie vielen Kugeln ist das 1 Kugel? Meine frage
war auf welche Anzahl kugeln du dich Beziehst!
Siehst du? Das macht keinen Sinn.
Man könnte jetzt natürlich noch fragen, welchen Sinn es macht zu sagen,
dass die Laufzeiten beider Funktionen Konstant sind. Die O-Notation ist
unter anderem nützlich eine Idee zu bekommen, wo es Sinvoll sein könnte,
zu optimieren. Wir wissen hier, dass die Laufzeit beider Funktionen um
die es ursprünglich ging, konstant ist. Es ist aber nicht möglich eine
Allgemeine Aussage zu machen, welche schneller ist, da dies von der
Architektur usw. abhängt. Man kann aber ziemlich sicher sagen, dass
Optimierungen vermutlich an anderen Orten sinnvoller sind. Das ist,
worauf ich mit dem Kommentar eigentlich hinwies. Aber das war wohl
einigen leider etwas zu hoch...
DPA schrieb:>> Die O-Notation gibt nicht die Laufzeit eines Algorithmus an, sondern wie>> er skaliert.>> "Konstante Laufzeit" ist eine Angabe der Skalierung der Laufzeit.
Ja, aber hier gibt es keine Skalierung. Es geht ein Wert rein und einer
raus. Es gibt keine Schleife und nichts anders, das irgendwie
irgendwomit skaliert werden könnte.
> Ich sage nirgends etwas zur effektiven Laufzeit des Algorithmus.
Aber genau um die geht es!
> Und das zeigt lediglich, dass die Frage hier keinen Sinn macht.
Welche Frage?
> Die O-Notation setzt keine Anzahl voraus.
Doch, klar tut sie das. Ich zitiere mal den oben verlinkten
Wikipedia-Eintrag, der's gut erklärt:
"Landau-Symbole werden in der Mathematik und in der Informatik
verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu
beschreiben. In der Informatik werden sie bei der Analyse von
Algorithmen verwendet und geben ein Maß für die Anzahl der
Elementarschritte oder der Speichereinheiten in Abhängigkeit von der
Größe der Eingangsvariablen an."
> Um dir noch mal anders die Absurdität der Frage aufzuzeigen: Du darfst 1> Kugel nehmen. Relativ zu wie vielen Kugeln ist das 1 Kugel? Meine frage> war auf welche Anzahl kugeln du dich Beziehst!
Es ist eher so, als ob jemand das Gewicht der Kugel wissen will. Statt
sowas zu sagen wie: "sie wiegt 100g", sagst du: "das Gewicht der einen
Kugel skaliert linear [mit ihrer Anzahl]". Die Aussage ist zwar nicht
falsch, aber auch nicht wirklich sinnvoll.
> Man kann aber ziemlich sicher sagen, dass Optimierungen vermutlich an> anderen Orten sinnvoller sind.
Daher schrieb ich ja:
Rolf M. schrieb:> Am Ende dürfte das aber sehr selten eine Rolle spielen.DPA schrieb:> Das ist, worauf ich mit dem Kommentar eigentlich hinwies. Aber das war> wohl einigen leider etwas zu hoch...
Oder vielleicht einfach von dir ungeschickt gewählt. Ich war wohl nicht
der einzige, dem nicht klar war, was du hier plötzlich mit deinem O(1)
willst.
Das O(1) ist formal vollkommen korrekt, denn beide Algorithmen skalieren
mit konstanter Laufzeit. Die relevante Information war aber die
Konstante selbst, welche bei Skalierbarkeitsanalysen immer
vernachlässigt wird.
Der Algorithmus selbst hat einen Eingabewert n, nämlich die zu
konvertierende Ziffer (0..15). Beide Implementationen skalieren aber
unabhängig davon - ein naiver "suche in der Tabelle"-Ansatz würde O(n),
abhängig von der Ziffer, skalieren.
Das ist möglicherweise effizienter. Aber im allgemeinen nicht korrekt
(außer du hast zusätzliches Wissen darüber, wie im Locale die Buchstaben
'A' bis 'F' kodiert sind).
Peter D. schrieb:> Ist aber nicht sonderlich effizient. Besser:
Wie oben schon geschrieben. Hier mal das Programm eingeben:
https://godbolt.org/
Interessant, was bei unterschiedlichen Plattformen (mal x86 vs. ARM
probieren) dabei herauskommt (-O2 nicht vergessen)
Eine generelle Aussage, was effizienter ist, läßt sich m.E. nicht
treffen.