Hilf mir zu verstehen diese „Programmieren Perlen“ Bitsort Programm

StackOverflow https://stackoverflow.com/questions/1050253

  •  20-08-2019
  •  | 
  •  

Frage

Jon Bentley in Spalte 1 seine Buch Programmierung Perlen stellt eine Technik für eine Folge von Nicht-Null positiven ganzen Zahlen Sortierung mit Bit-Vektoren.

Ich habe das Programm bitsort.c von hier genommen und klebte es unter: 

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* bitsort.c -- bitmap sort from Column 1
 *   Sort distinct integers in the range [0..N-1]
 */

#include <stdio.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1 + N/BITSPERWORD];

void set(int i) 
{
    int sh = i>>SHIFT;
    a[i>>SHIFT] |=  (1<<(i & MASK)); 
}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

int main()
{   int i;
for (i = 0; i < N; i++)
    clr(i);

    /*Replace above 2 lines with below 3 for word-parallel init
    int top = 1 + N/BITSPERWORD;
    for (i = 0; i < top; i++)
    a[i] = 0;
    */

while (scanf("%d", &i) != EOF)
    set(i);
for (i = 0; i < N; i++)
        if (test(i))
    printf("%d\n", i);
return 0;
}

Ich verstehe, was die Funktionen clr, gesetzt und Test tun und erklären sie unter: (bitte korrigieren Sie mich, wenn ich hier falsch bin)

.
  • clr löscht das i-te Bit
  • Satz setzt das i-te Bit
  • Test gibt den Wert an der i-te Bit

Nun, ich verstehe nicht, wie die Funktionen tun, was sie tun. Ich bin nicht in der Lage alle Bit Manipulation in diesen drei Funktionen geschieht, um herauszufinden.

Bitte helfen.

War es hilfreich?

Lösung

Die ersten drei Konstanten sind miteinander verbunden. BITSPERWORD ist 32. Diese Sie auf der Grundlage Ihrer Compiler + Architektur einstellen wollen würde. SHIFT 5 ist, weil 2 ^ 5 = 32. Schließlich MASK 0x1F ist, die 11111 in binär ist (das heißt: die unteren 5 Bits sind alle gesetzt). Gleichwertig, MASK = BITSPERWORD -. 1

Die bitset ist vom Konzept her nur ein Array von Bits. Diese Implementierung verwendet tatsächlich eine Anordnung von ints und nimmt 32 Bit pro Int. Also, wenn wir setzen wollen, klar oder Test (Lesen) ein bisschen müssen wir zwei Dinge herauszufinden:

  • welche int (der Anordnung) ist es in
  • , die jener int die Bits reden wir

Weil wir 32 Bits pro int vorausgesetzt, können wir nur durch 32 teilen (und gestutzt), um den Array-Index wollen wir zu erhalten. Dividieren durch 32 (BITSPERWORD) ist die gleiche wie von 5 (SHIFT) nach rechts zu verschieben. Also das ist, was die a [i >> SHIFT] Bit geht. Man könnte dies auch als schreiben [i / BITSPERWORD] (und in der Tat, werden Sie wahrscheinlich den gleichen oder sehr ähnlichen Code vorausgesetzt, Ihren Compiler bekommen hat einen vernünftigen Optimierer).

Jetzt, da wir wissen, welches Element ein wir wollen, müssen wir die etwas herauszufinden. Wirklich wollen wir den Rest. Wir konnten dies mit i% BITSPERWORD, aber es stellt sich heraus, dass i & MASK entspricht. Dies liegt daran, BITSPERWORD eine Potenz von 2 (2 ^ 5 in diesem Fall) ist und die Maske wird der Boden 5 Bits alle gesetzt.

Andere Tipps

Im Grunde ist ein Bucketsort optimiert:

  • ein Bitfeld der Länge n reservieren    Bits.
  • Bitarray löschen (zuerst in main).
  • Lesen Sie die Artikel, eins nach dem anderen (sie alle sein verschieden sein).
    • die i-te Bit in den Bit-Array gesetzt, wenn die gelesene Anzahl i ist.
  • iterieren die Bit-Array.
    • , wenn das Bit gesetzt ist, dann die Position drucken.

oder mit anderen Worten (für n <10 und sortieren, 3-Nummern 4, 6, 2) 0

mit einem leeren 10-Bit-Array starten (auch bekannt als eine ganze Zahl in der Regel) 

0000000000

lesen 4 und das Bit im Array .. 

0000100000

lesen 6 und das Bit in dem Array 

0000101000

2 gelesen und das Bit in dem Array 

0010101000

das Array iterieren und jede Position gedruckt werden, in der die Bits auf eins gesetzt sind.

2, 4, 6

sortiert.

Beginnend mit set ():
Eine Verschiebung nach rechts von 5 ist die gleiche wie durch 32 dividiert Es findet, an dem die Bit-int ist in.
MASK ist 0x1f oder 31 ANDing mit der Adresse gibt die Bit-Index innerhalb des int. Es ist der gleiche wie der Rest der Division der Adresse von 32
Shifting 1 durch den Bitindex links ( "1 << (i & MASK)") führt zu einer ganzen Zahl, die nur 1-Bit in der vorgegebenen Position gesetzt hat.
ORing setzt das Bit.
Die Zeile "int sh = i >> SHIFT;" ist eine vergeudete Linie, weil sie sh nicht wieder darunter, und stattdessen nur wiederholt „i >> SHIFT“

verwendet haben

clr () ist grundsätzlich die gleiche wie Satz, außer statt ORing mit 1 << (i & MASK), um das Bit zu setzen, es ANDs mit dem inversen dem Bit zu löschen. (Test) ANDs mit 1 << (i & MASK), um das Bit zu testen.

Der Bitsort wird auch Duplikate aus der Liste entfernen, weil sie nur auf 1 pro ganzer Zahl zählen werden. Eine Art, die ganzen Zahlen anstelle von Bits verwendet mehr als 1 von jedem zu zählen ist eine Radixsort genannt.

Die Bit-Magie wird als Sonderadressierungsschema verwendet, die gut mit Zeilengrößen arbeiten, die Zweierpotenzen sind.

Wenn Sie das versuchen, verstehen (Anmerkung: ich eher Bits pro Zeile verwenden als Bits pro Wort, denn wir reden ein bisschen-Matrix hier): 

// supposing an int of 1 bit would exist...
int1 bits[BITSPERROW * N]; // an array of N x BITSPERROW elements

// set bit at x,y:
int linear_address = y*BITSPERWORD + x;
bits + linear_address = 1; // or 0
// 0 1 2 3 4 5 6 7 8 9 10 11 ... 31
// . . . . . . . . . .  .  .       .  
// . . . . X . . . . .  .  .       .  -> x = 4, y = 1 => i = (1*32 + 4)

Die Aussage linear_address = y*BITSPERWORD + x bedeutet auch, dass x = linear_address % BITSPERWORD und y = linear_address / BITSPERWORD.

Wenn Sie diese im Speicher zu optimieren, indem unter Verwendung von 1 Wort von 32 Bits pro Zeile, können Sie die Tatsache erhalten, dass ein Bit in Spalte x kann mit eingestellt werden 

int bitrow = 0;
bitrow |= 1 << (x);

Nun, wenn wir über die Bits laufen, we Haben die lineare Adresse, sondern müssen das entsprechende Wort finden. 

int column = linear_address % BITSPERROW;
int bit_mask =  1 << column; // meaning for the xth column, 
                             // you take 1 and shift that bit x times
int row    = linear_address / BITSPERROW;

So das i-te Bit zu setzen, können Sie dies tun: 

bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );

Eine zusätzliche gotcha ist, dass der Modulo-Operator durch eine logischen ersetzt werden kann, und, und der / Operator kann durch eine Verschiebung auch ersetzt werden, wenn der zweite Operand eine Zweierpotenz ist. 

a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT

Dies läuft darauf hinaus letztlich auf das sehr dicht, aber schwer zu versteh-for-the-bitfucker unabhängige Schreibweise 

a[ i >> SHIFT ] |= ( 1 << (i&MASK) );

Aber ich sehe nicht, der Algorithmus arbeitet für z.B. 40 Bits pro Wort.

die Auszüge aus Bentleys' Original-Artikel in DDJ Zitiert, das ist, was der Code tut auf hohem Niveau: 

/* phase 1: initialize set to empty */

for (i = 0; i < n; i++)

    bit[i] = 0

/* phase 2: insert present elements */

for each i in the input file

    bit[i] = 1

/* phase 3: write sorted output */

for (i = 0; i < n; i++)

    if bit[i] == 1

        write i on the output file

Einige Zweifel: 1. Warum ist es ein Bedürfnis nach einem 32-Bit? 2. Können wir tun dies in Java durch eine HashMap mit Keys 0.000.000-9.999.999 Schaffung    und die Werte 0 oder 1 auf der Grundlage der Anwesenheit / Abwesenheit des Bits? Was sind die Auswirkungen    für ein solches Programm?

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top