Ich habe 3 Basisdarstellungen für positive ganze Zahlen:
Ich möchte in der Lage sein, zwischen Zahlen in allen 3 Darstellungen auf die effizienteste Weise zu konvertieren. I.e. um die folgenden 6 Funktionen zu implementieren:
%Vor%Was ist der effizienteste Ansatz für jeden von ihnen? Ich kann C und C ++ verwenden, aber nicht boosten.
Edit: Mit "Effizienz" meine ich Zeiteffizienz: Kürzeste Ausführungszeit.
Wie bereits erwähnt, würde ich mit sscanf() beginnen, printf() und / oder strtoul() . Sie sind für die meisten Anwendungen schnell genug und sie haben weniger Fehler. Ich werde jedoch sagen, dass diese Funktionen generischer sind, als Sie vielleicht erwarten würden, da sie mit Nicht-ASCII-Zeichensätzen umgehen müssen, mit Zahlen, die in irgendeiner Basis dargestellt sind, und so weiter. Für einige Domains ist es möglich, die Bibliotheksfunktionen zu überlisten.
Also, zuerst messen, und wenn die Leistung dieser Konvertierung wirklich ein Problem ist, dann:
1) In manchen Anwendungen / Domains tauchen bestimmte Zahlen sehr häufig auf, zB Null, 100, 200, 19.95, so häufig, dass es sinnvoll ist, Ihre Funktionen zu optimieren, um solche Zahlen mit einer Menge if () -Anweisungen zu konvertieren und dann auf die allgemeinen Bibliotheksfunktionen zurückgreifen. 2) Verwenden Sie eine Tabellensuche für die gebräuchlichsten 100 Zahlen und greifen Sie dann auf eine Bibliotheksfunktion zurück. Denken Sie daran, dass große Tabellen möglicherweise nicht in Ihren Cache passen und möglicherweise mehrere Umleitungen für gemeinsam genutzte Bibliotheken erfordern. Messen Sie diese Punkte sorgfältig, um sicherzustellen, dass Sie die Leistung nicht verringern.
Sie können auch lexical_cast-Funktionen von boost ausprobieren, obwohl diese nach meiner Erfahrung relativ gut mit den guten alten C-Funktionen verglichen werden.
Viele haben es gesagt, es lohnt sich, es immer wieder zu wiederholen: Optimieren Sie diese Conversions erst, wenn Sie Anzeichen dafür haben, dass es sich um ein Problem handelt. Wenn Sie optimieren, messen Sie Ihre neue Implementierung, um sicherzustellen, dass sie schneller ist. und stellen Sie sicher, dass Sie eine Menge Unit-Tests für Ihre eigene Version haben, weil Sie Fehler einführen werden: - (
Warum müssen diese Routinen so zeiteffizient sein? Diese Art von Anspruch lässt mich immer wieder fragen. Sind Sie sicher, dass die offensichtlichen Konvertierungsmethoden wie strtol () zu langsam sind oder dass Sie es besser machen können? Systemfunktionen sind normalerweise ziemlich effizient. Sie sind manchmal langsamer, um die Generalität und Fehlerprüfung zu unterstützen, aber Sie müssen überlegen, was mit Fehlern geschehen soll. Wenn ein bin Argument andere Zeichen als '0' und '1' hat, was dann? Abbrechen? Riesige Fehler weitergeben?
Warum verwenden Sie "Dec", um die interne Darstellung darzustellen? Dez, Hex und Bin sollten verwendet werden, um auf die Zeichenfolgendarstellungen zu verweisen. Es gibt keine Dezimalstelle in unsigned long . Haben Sie es mit Strings zu tun, die die Zahl in Dezimalzahlen anzeigen? Wenn nicht, verwirren Sie die Leute hier und werden viele mehr verwirren.
Die Transformation zwischen binären und hexadezimalen Textformaten kann schnell und effizient mit Nachschlagetabellen durchgeführt werden, aber alles, was das dezimale Textformat betrifft, wird komplizierter.
Das hängt davon ab, wofür Sie optimieren, was meinen Sie mit "effizient"? Ist es wichtig, dass die Konvertierungen schnell sind, wenig Speicher, wenig Programmierzeit, weniger WTFs von anderen Programmierern, die den Code lesen, oder was? p>
Zur besseren Lesbarkeit und einfachen Implementierung sollten Sie zumindest Dec2Hex() und Dec2Binary() implementieren, indem Sie einfach strotul() aufrufen. Das macht sie zu One-Linern, was für einige der obigen Interpretationen des Wortes sehr effizient ist.
Klingt sehr nach Hausaufgaben, aber was soll's ...
Die kurze Antwort bezieht sich auf das Konvertieren von long int in Ihre Strings mit zwei Lookup-Tabellen. Jede Tabelle sollte 256 Einträge haben. Man ordnet ein Byte einer hexadezimalen Zeichenfolge zu: 0 - & gt; "00", 1 - & gt; "01" usw. Der andere bildet ein Byte auf eine Bitfolge ab: 0 - & gt; "00000000", 1 - & gt; "00000001".
Dann müssen Sie für jedes Byte in Ihrem long int nur die richtige Zeichenfolge suchen und verketten.
Um von Strings zurück in long zu konvertieren, können Sie einfach die hexadezimale Zeichenfolge und die Bitzeichenfolge in eine Dezimalzahl umwandeln, indem Sie den numerischen Wert jedes Zeichens mit der entsprechenden Potenz von 16 oder 2 multiplizieren und die Ergebnisse summieren / p>
EDIT: Sie können die gleichen Nachschlagetabellen auch für die Rückwärtskonvertierung verwenden, indem Sie die binäre Suche ausführen, um die richtige Zeichenfolge zu finden. Dies würde Log (256) = 8 Vergleiche Ihrer Strings erfordern. Leider habe ich keine Zeit für die Analyse, ob der Vergleich von Strings viel schneller ist als Multiplikation und Addition von ganzen Zahlen.
Lassen Sie uns einen Moment über die Hälfte der Aufgabe nachdenken - Umwandlung von einer string-isierten Basis n in unsigned long, wobei n eine Potenz von 2 ist (Basis 2 für binär und Basis 16 für hex).
Wenn Ihre Eingabe gesund ist, dann ist diese Arbeit nichts anderes als ein Vergleich, ein Subtrahieren, eine Verschiebung und eine oder pro Ziffer. Wenn deine Eingabe nicht vernünftig ist, dann wird das hässlich, oder? Die Konvertierung superschnell ist nicht schwer. Es ist die Herausforderung, es unter allen Umständen gut zu machen.
Nehmen wir also an, dass Ihre Eingabe vernünftig ist, dann lautet das Herz Ihrer Konvertierung:
%Vor%Sehen Sie, wie einfach das ist? Und es wird bei nicht vernünftigen Eingaben scheitern. Der Großteil Ihrer Arbeit wird darin bestehen, Ihren Input vernünftig zu machen, nicht Leistung.
Nun, dieser Code nutzt die Vorteile der zweifachen Verschiebung. Es ist einfach, auf Basis 4, Basis 8, Basis 32 usw. zu erweitern. Es funktioniert nicht auf Nicht-Leistung von zwei Basen. Für diese muss sich Ihre Mathematik ändern. Du bekommst
%Vor%was konzeptionell für diese Menge von Operationen gleich ist. Die Multiplikation mit der Basis entspricht der Verschiebung. Daher würde ich eher eine vollständig allgemeine Routine verwenden. Säubern Sie den Code und sanieren Sie die Eingaben. Und zu diesem Zeitpunkt ist strtoul wahrscheinlich die beste Wahl. Hier ist ein Link zu einer Version von strtoul. Fast die ganze Arbeit behandelt Randbedingungen - das sollte dich darauf hinweisen, wo deine Energien konzentriert sein sollten: korrekter, widerstandsfähiger Code. Die Einsparungen bei der Verwendung von Bit-Shifts werden minimal sein im Vergleich zu den Einsparungen von, sagen wir mal, bei schlechtem Input nicht abstürzen.