Bitweiser Zugriff

[Peter Thomassen]

Hallo liebes Forum,

ist es via PHP möglich, auf ein bestimmtes Bit einer Variablen zuzugreifen? Ich denke nicht an ($a & pow(2, n)) für das n-te Bit von hinten, da so erst 2^n ausgerechnet wird, doch in meinem Anwendungsfall macht das einen großen Teil der Zeit aus.

Gibt's irgendwas in die Richtung "Gib mir das n-te Bit von hinten"?

Danke!
Peter

[Rouven]

Hallo,

na ja, ich bitte um Nachsicht, wenn mir da jetzt noch irgend eine triviale Operation für Bit-n-auslesen durchgegangen ist, aber zumindest das pow() kannst du noch in eine reine Bit-Operation umsetzen:
1 << Stellen
Bit-Operatoren
Damit besteht deine Berechnung (in der Theorie) aus zwei Bit-Operationen, ich vermute schneller gehts nicht...

MfG
Rouven

[Rouven]

Ach ja, aus den Kommentaren hätte ich hier noch eine passende Funktion:
   function readbit($val, $bit) {
       return ($val&(0+('0x'.dechex(1<<($bit-1)))))?'1':'0';
   }

MfG
Rouven

[dedlfix]

echo $begrüßung;

Ach ja, aus den Kommentaren hätte ich hier noch eine passende Funktion:
   function readbit($val, $bit) {
       return ($val&(0+('0x'.dechex(1<<($bit-1)))))?'1':'0';
   }

Die umständliche Hex-Umwandlung kann man rauslassen. Egal wie man eine Zahl darstellt - Hex oder Dezimal oder sonstwie - das Bitmuster bleibt das gleiche.
Die Klammern können aufgrund der Operator-Rangfolge auch weggelassen werden.

return $val & 1 << $bit - 1 ? '1' : '0';

Anzumerken wäre noch, dass diese Funktion die Bits von rechts nach links - bzw. vom niederwertigsten zum höchstwertigen - mit 1 beginnend zählt.

echo "$verabschiedung $name";

[Peter Thomassen]

Tag,

return $val & 1 << $bit - 1 ? '1' : '0';

Danke, das war's :-) Ich finde, dass für eine binäre Unterschiedung auch

return (bool)($val & 1 << $n);

reicht, oder nicht? Um die Typkonvertierung wegzubekommen, habe ich mir aber

return $val >> $n & 1;

konstruiert. Ist das korrekt oder hab ich einen Denkfehler gemacht?

Danke euch!
Peter

[dedlfix]

echo $begrüßung;

return $val & 1 << $bit - 1 ? '1' : '0';

Danke, das war's :-) Ich finde, dass für eine binäre Unterschiedung auch

return (bool)($val & 1 << $n);

reicht, oder nicht?

Ja, reicht auch.

Um die Typkonvertierung wegzubekommen, habe ich mir aber

return $val >> $n & 1;

konstruiert. Ist das korrekt oder hab ich einen Denkfehler gemacht?

Ja und nein (um die beiden Teilfragen zu beantworten), sieht gut aus.

echo "$verabschiedung $name";

[Peter Thomassen]

Hallo,

Um die Typkonvertierung wegzubekommen, habe ich mir aber

return $val >> $n & 1;

konstruiert. Ist das korrekt oder hab ich einen Denkfehler gemacht?

Ja und nein (um die beiden Teilfragen zu beantworten), sieht gut aus.

Danke!

Peter

[Andreas Görtz]

Hi Peter,

ist es via PHP möglich, auf ein bestimmtes Bit einer Variablen zuzugreifen? Ich denke nicht an ($a & pow(2, n)) für das n-te Bit von hinten, da so erst 2^n ausgerechnet wird, doch in meinem Anwendungsfall macht das einen großen Teil der Zeit aus.

Wenn die Anwendung so zeitkritisch ist, solltest du, falls möglich, nicht PHP nehmen. Beispiel (10 Millionen Bitverschiebungen um 8 Bits nach links):

ag@bart:~$ time php -r 'for ($i = 0; $i < 10000000; $i++) 1<<8;'

real    0m8.571s
user    0m7.633s
sys     0m0.025s

im Gegenzug ein kleines C-Programm (test.c):

  
int main (void)  
{  
  int i;  
  for (i = 0; i < 10000000; i++) 1<<8;  
  
  return 0;  
}  

ag@bart:~$ gcc test.c
ag@bart:~$ time ./a.out

real    0m0.037s
user    0m0.023s
sys     0m0.002s

Wenn ich bei dem C-Programm keinen Bock geschossen habe, würde ich sagen, es lohnt sich ;-)

Gruß,
Andreas.

[Der Martin]

Hallo Andreas,

int main (void)
{
  int i;
  for (i = 0; i < 10000000; i++) 1<<8;

return 0;
}

  

> Wenn ich bei dem C-Programm keinen Bock geschossen habe, würde ich sagen, es lohnt sich ;-)  
  
Doch, ich würde sagen, du hast. ;-)  
Denn ich kenne genug Beispiele für Compiler, die schon beim Übersetzen erkennen, dass der Ausdruck 1<<8 nur aus Konstanten besteht, das Ergebnis also auch eine Konstante ist, und daher gleich den konstanten Wert in den Code einsetzen.  
Da der Ausdruck als Anweisung außerdem keine Auswirkungen hat, könnte ich mir sogar vorstellen, dass ein "schlauer" Compiler die Anweisung komplett wegoptimiert, so dass nur noch  
  

>  for (i=0; i<10000000; i++);  
  
übrigbleibt. Dann misst du eigentlich nur den Overhead der for-Schleife.  
  
So long,  
  
 Martin  

-- 
Wenn zwei dasselbe tun, sind sie vielleicht bald zu dritt.  
  

[Andreas Görtz]

Hi,

Wenn ich bei dem C-Programm keinen Bock geschossen habe, würde ich sagen, es lohnt sich ;-)

Doch, ich würde sagen, du hast. ;-)
[...]
Da der Ausdruck als Anweisung außerdem keine Auswirkungen hat, könnte ich mir sogar vorstellen, dass ein "schlauer" Compiler die Anweisung komplett wegoptimiert

Danke Martin. Genau sowas hatte ich befürchtet ;-) Wie könnte man denn für dieses Problem einen Vergleich zwischen PHP und C aufbauen?

Gruß,
Andreas.

[Peter Thomassen]

Hallo

Da der Ausdruck als Anweisung außerdem keine Auswirkungen hat, könnte ich mir sogar vorstellen, dass ein "schlauer" Compiler die Anweisung komplett wegoptimiert

Danke Martin. Genau sowas hatte ich befürchtet ;-) Wie könnte man denn für dieses Problem einen Vergleich zwischen PHP und C aufbauen?

Du musst was tun, könntest also beispielsweise jedes Mal eine 1-Bit-Variable invertieren oder so.

Bye,
Peter

[dedlfix]

echo $begrüßung;

Danke Martin. Genau sowas hatte ich befürchtet ;-) Wie könnte man denn für dieses Problem einen Vergleich zwischen PHP und C aufbauen?

Das wäre dann Äpfel mit Birnen verglichen, aber warum nicht.
Ich würde an der Stelle gar nichts zusätzliches einbauen. Wenn der C-Compiler so schlau ist das wegzuoptimieren, dann gehört das zu den Vorteilen von C (bzw. dieses Compilers) dazu, finde ich.

echo "$verabschiedung $name";

[Andreas Görtz]

Hi dedlfix,

Das wäre dann Äpfel mit Birnen verglichen, aber warum nicht.

ja - das ist mir schon klar. Es ginge dabei nur darum, wie hier, zu zeigen, dass es für einige Probleme Schwachsinn wäre, z.B. PHP zu bemühen[1]. In diesem Thread natürlich unnötig, da sich Peter dessen bewusst war, was ich aber vorher nicht wissen konnte ;-)

Ich würde an der Stelle gar nichts zusätzliches einbauen. Wenn der C-Compiler so schlau ist das wegzuoptimieren, dann gehört das zu den Vorteilen von C (bzw. dieses Compilers) dazu, finde ich.

Ja, so gesehen hast du natürlich Recht.

[1] Ich habe mal in einer Firma gearbeitet, in der wurden komplexe Berechnungen (über mehrere Millionen Datensätze) mittels VBScript in Excel (sic!) gelöst. Mit C (in dem Fall wohl auch mit PHP) wäre die Berechnung vermutlich eine Sache von Sekunden gewesen - das Script in Excel ackerte Stunden ;-)

Gruß,
Andreas.

[Peter Thomassen]

Hallo,

Wenn die Anwendung so zeitkritisch ist, solltest du, falls möglich, nicht PHP nehmen. Beispiel (10 Millionen Bitverschiebungen um 8 Bits nach links):

Es soll die relative Geschwindigkeit zweier Algorithmen gezeigt werden, weswegen ich ein paar Optimierungen vornehmen möchte. Zeit habe ich also schon, mich interessieren lediglich die Verhältnisse.

Bye,
Peter

[Vinzenz Mai]

Hallo Peter,

Es soll die relative Geschwindigkeit zweier Algorithmen gezeigt werden, weswegen ich ein paar Optimierungen vornehmen möchte. Zeit habe ich also schon, mich interessieren lediglich die Verhältnisse.

nur aus Interesse: Sind beide Algorithmen von <http://de.wikipedia.org/wiki/Komplexit%C3%A4t_%28Informatik%29title=@gleicher Komplexität>? Was hast Du genau vor? Willst Du z.B. das Verhalten empirisch ermitteln und demonstrieren?

Freundliche Grüße

Vinzenz

[Peter Thomassen]

Tag,

Es soll die relative Geschwindigkeit zweier Algorithmen gezeigt werden, weswegen ich ein paar Optimierungen vornehmen möchte. Zeit habe ich also schon, mich interessieren lediglich die Verhältnisse.

nur aus Interesse: Sind beide Algorithmen von <http://de.wikipedia.org/wiki/Komplexit%C3%A4t_%28Informatik%29title=@gleicher Komplexität>? Was hast Du genau vor? Willst Du z.B. das Verhalten empirisch ermitteln und demonstrieren?

Teilweise, es geht um Sortieralgorithmen. Die getesteten sind Bubblesort, Insertion sort und Selection sort mit O(n^2), Quicksort mit O(n log n) und mein Bitsort mit O(n). Daher auch hier die Bitfrage. Ein Test gerade hat ergeben (der jeweils zweite Wert bezieht sich auf die Sortierung der bereits sortierten Liste, d.h. den best case):

3000 Zufallszahlen: 0.0158278942108 Sekunden.

Bubblesort:     12.5058748722 Sekunden.
Bubblesort:     7.46138906479 Sekunden.
Insertion sort: 13.6109161377 Sekunden.
Insertion sort: 9.9717400074 Sekunden.
Selection sort: 10.0230801105 Sekunden.
Selection sort: 7.15000391006 Sekunden.
Quicksort:      0.545024871826 Sekunden.
Quicksort:      0.522994041443 Sekunden.
Bitsort:        0.0652689933777 Sekunden.
Bitsort:        0.0693278312683 Sekunden.

Die Zufallszahlen waren jeweils dieselben. PHP ist hier sicher nicht die optimale Wahl, reicht aber, um die Komplexitätsunterschiede zu zeigen.

Bye,
Peter

[Peter Thomassen]

Hallo,

Teilweise, es geht um Sortieralgorithmen. Die getesteten sind Bubblesort, Insertion sort und Selection sort mit O(n^2), Quicksort mit O(n log n) und mein Bitsort mit O(n). Daher auch hier die Bitfrage. Ein Test gerade hat ergeben (der jeweils zweite Wert bezieht sich auf die Sortierung der bereits sortierten Liste, d.h. den best case):

Falls es noch jemanden interessiert:

50000 Zufallszahlen: 0.299767971039 Sekunden.

Quicksort:      203.10271883 Sekunden.
Quicksort:      219.95638895 Sekunden.
Bitsort:        1.5677728653 Sekunden.
Bitsort:        2.0780570507 Sekunden.

So, es reicht, morgen ist Schule.

Ciao,
Peter

[Vinzenz Mai]

Hallo Peter,

ein paar ergänzende Bemerkungen (auch für das Archiv). Wahrscheinlich weißt Du das eh' schon, da Du Dich offensichtlich intensiv mit Sortierverfahren beschäftigst.

Teilweise, es geht um Sortieralgorithmen. Die getesteten sind Bubblesort, Insertion sort und Selection sort mit O(n^2), Quicksort mit O(n log n)

für Quicksort im Durchschnitt. Worst Case für Quicksort ist O(n^2).

und mein Bitsort mit O(n). Daher auch hier die Bitfrage. Ein Test gerade hat ergeben (der jeweils zweite Wert bezieht sich auf die Sortierung der bereits sortierten Liste, d.h. den best case):

mit einer "naiven" Implementation ist die bereits sortierte Liste der worst case für Quicksort, siehe z.B. Wikipedia, Quicksort.

3000 Zufallszahlen: 0.0158278942108 Sekunden.
Insertion sort: 13.6109161377 Sekunden.
Insertion sort: 9.9717400074 Sekunden.

Du musst einen Fehler in Deinem Insertion Sort haben. Insertion Sort ist im besten Fall (vorsortierte Liste) linear. Folgende Funktion (nach Algorithmen, Robert Sedgewick, Addison-Wesley) tut dies zumindest:

  
function insertion_sort (&$array, $anzahl) {  
    $i = $j = $v = 0;  
    for ($i = 1; $i < $anzahl; $i++) {  
        $v = $array[$i];  
        $j = $i;  
        while ($j > 0 && $array[$j-1] > $v) {  
            $array[$j] = $array[$j-1];  
            $j--;  
        }  
        $array[$j] = $v;  
    }  
}  

Bitsort:        0.0652689933777 Sekunden.
Bitsort:        0.0693278312683 Sekunden.

Eine Implementierung einer Radix-Sort-Variante?

Die Zufallszahlen waren jeweils dieselben. PHP ist hier sicher nicht die optimale Wahl, reicht aber, um die Komplexitätsunterschiede zu zeigen.

Für die Komplexität der Verfahren wäre dies ein einziger Messpunkt. Ich weiß ja, dass Du mehrfach gemessen hast. Wäre es nicht eine nette Idee, per GD-Lib eine hübsche Grafik automatisiert erstellen zu lassen?

Freundliche Grüße

Vinzenz

[Peter Thomassen]

Tag,

3000 Zufallszahlen: 0.0158278942108 Sekunden.
Insertion sort: 13.6109161377 Sekunden.
Insertion sort: 9.9717400074 Sekunden.

Du musst einen Fehler in Deinem Insertion Sort haben. Insertion Sort ist im besten Fall (vorsortierte Liste) linear. Folgende Funktion (nach Algorithmen, Robert Sedgewick, Addison-Wesley) tut dies zumindest:

function insertion_sort (&$array, $anzahl) {
    $i = $j = $v = 0;
    for ($i = 1; $i < $anzahl; $i++) {
        $v = $array[$i];
        $j = $i;
        while ($j > 0 && $array[$j-1] > $v) {
            $array[$j] = $array[$j-1];
            $j--;
        }
        $array[$j] = $v;
    }
}

  
Das hat mich auch gewundert, aber ich habe:  
~~~php
  
function insertionSort(&$a) {  
 for($i = 1; $i < count($a); $i++) {  
  $focus = $a[$i];  
  for($j = $i; $j > 0 && $a[$j - 1] > $focus; $j--) {  
   $a[$j] = $a[$j - 1];  
  }  
  $a[$j] = $focus;  
 }  
}  

Ich wüsste nicht, was daran falsch sein soll. So weit ich sehe, unterscheiden sich die Implementierungen nur in der (überflüssigen) Variablendeklaration und im Schleifentyp. Hab ich bei der for-Schleife einen Denkfehler gemacht? Ich hab Insertion sort noch nie mit for-Schleife gesehen, war aber der Meinung, dass es funktionieren müsste.

Bitsort:        0.0652689933777 Sekunden.
Bitsort:        0.0693278312683 Sekunden.

Eine Implementierung einer Radix-Sort-Variante?

Ja, allerdings etwas verallgemeint, sodass man es auch für lexikografische Sortierung etc. verwenden kann. Ich wüsste daher nicht, was noch für die "traditionellen allgemeinen" Sortieralgorithmen spricht, meins ist dann ja auch ein solches.

Für die Komplexität der Verfahren wäre dies ein einziger Messpunkt. Ich weiß ja, dass Du mehrfach gemessen hast. Wäre es nicht eine nette Idee, per GD-Lib eine hübsche Grafik automatisiert erstellen zu lassen?

Wenn ich jetzt GDlib könnte. Ich hab mir gedacht, dass ich einfach ein paar Messreihen mache und das dann mit GnuPlot irgendwie hinbastle, wobei ich damit auch keine Erfahrung habe. Meinst du, GDlib wäre praktischer?

Danke,
Peter

[Peter Thomassen]

Hallo

Du musst einen Fehler in Deinem Insertion Sort haben. Insertion Sort ist im besten Fall (vorsortierte Liste) linear. Folgende Funktion (nach Algorithmen, Robert Sedgewick, Addison-Wesley) tut dies zumindest:

Das hat mich auch gewundert, aber ich habe:

function insertionSort(&$a) {
for($i = 1; $i < count($a); $i++) {
  $focus = $a[$i];
  for($j = $i; $j > 0 && $a[$j - 1] > $focus; $j--) {
   $a[$j] = $a[$j - 1];
  }
  $a[$j] = $focus;
}
}

  
\*grr\* Erst denken, dann reden. count($a) wird bei jedem Schleifendurchlauf ausgeführt und macht's so quadratisch. Hab's mal in eine Varialbe ausgelagert.  
  
Bye,  
Peter