Ich hatte heute ein Interview, in dem sie mich gebeten haben, zwei "C" -Funktionen zu schreiben, eine, um ein einzelnes Bit zu extrahieren, und eine, um eine Reihe von Bits aus einem Zeichen zu extrahieren. Ich brauchte eine Weile und kam mit diesen Methoden auf.
%Vor%Aber der Interviewer fragte mich immer wieder, ob ich den Code (in Bezug auf die CPU-Zyklen) beschleunigen könnte und ob es einen Optimierungsbereich gäbe, den ich tun könnte, um dies zu erreichen. Ich war eindeutig unzufrieden und ich bin neugierig zu wissen, wie du das machen würdest.
Wenn Sie in extractBit zuerst verschieben, können Sie mit 1 anstelle von (1<<pos) maskieren.
Wenn man bedenkt, dass pos ein Argument der Funktion ist, wird eine Berechnung gespeichert.
return (byte >> pos) & 1;
In der zweiten Funktion würde ich behaupten, dass startingPos und offset beide positiv sind, anstatt zu behaupten, dass ihre Summe positiv ist, es ergibt mehr Sinn.
Eine andere, die Sie in einem Bereich von Bits tun:
%Vor% Da << 1 nicht mehr als *2 ist, können Sie diese Operation auf Ihrer Konstante durchführen (was, wenn Sie mit Signle-Bytes arbeiten, nur LSB loswerden).
Sie können die erste Funktion beschleunigen, indem Sie zuerst nach rechts verschieben und dann das Bit maskieren:
%Vor%Dies erspart Ihnen einen Vorgang.
Für die zweite Frage nehme ich an, dass startingPos das erste Bit des Chunks ist, das Sie extrahieren möchten, und offset ist, wie viele Bits in dem Chunk Sie benötigen.
Dann könnten Sie das verwenden:
Natürlich müssen Sie bei den Bereichen genauso vorsichtig sein wie in Ihrem Code.
BEARBEITEN: Wenn extractBitRange(b,i,0) sich wie extractBit(b,i) verhalten soll und ein einzelnes Bit an Position i extrahiert werden soll, macht diese Variante folgendes:
Wenn Sie wirklich schnell werden wollen, können Sie eine Nachschlagetabelle verwenden. Ich vermute, dass das der Interviewer war (als endgültige Antwort auf "wie kann ich das schneller machen").
Das bedeutet im Grunde, dass Sie im Voraus eine riesige Tabelle erstellen und jede mögliche Kombination von Parametern auf das richtige Ergebnis abbilden. Zum Beispiel hättest du:
%Vor%Offensichtlich müsste dies in gültige c-Datenstrukturen (Arrays, indexiert durch das Byte und die Position) gesetzt werden. Dies würde es Ihnen erlauben, in Ihrer Funktion einfach einen Platz in einem Array zurückzugeben, basierend auf dem von Ihnen gewählten Indexschema.
Für die erste Funktion würde dies nicht zu viel Speicher beanspruchen. Wir sprechen über die Werte eines Bytes (ein Byte kann 256 verschiedene Werte haben) mal 8 mögliche Werte für den Anfangspunkt, was ein Array von 2048 ergibt.
Für die zweite Funktion würde viel mehr Platz benötigen. Sie müssten 256 Mal alle möglichen Werte für Anfangs- und Endpunkte multiplizieren (wobei zu beachten ist, dass es ungültige Kombinationen von Start- und Endposition gibt).
Ich nehme an, der Interviewer wollte nur, dass Sie antworten, dass dies ein Weg wäre, um es zu beschleunigen, und dann das obige Denken in den Versuch zu setzen, abzuschätzen, wie viel Platz im Vergleich zur Zeit eingespart werden würde.
Tags und Links optimization c