Binärer Auswahlprozess

Question

Ich habe an einer scheinbar einfachen Aufgabe gearbeitet, die mich verrückt macht. Also, wenn Sie Lust auf eine Programmieraufgabe haben ... lesen Sie weiter.

Ich möchte in der Lage sein, einen Nummernbereich z. [1:20] und drucken Sie die Werte mit einem Mechanismus ähnlich einem binären Suchalgorithmus. Drucken Sie zuerst den niedrigsten Wert (in diesem Fall 1) und dann den mittleren Wert (z. B. in diesem Fall 10) und teilen Sie dann den Bereich in Viertel und drucken Sie die Werte bei 1/4 und 3/4 (in diesem Fall 5) und 15) und dann in Achten aufteilen, bis alle Werte im Bereich gedruckt sind.

Die Anwendung von diesem (das nicht wirklich notwendig ist, um hier zu verstehen) ist für einen Speicherseitenzugriffsmechanismus, der sich effizienter verhält, wenn auf Seiten zuerst in den mittleren Bereichen zugegriffen wird.

Für dieses Problem wäre es ausreichend, einen beliebigen Zahlenbereich zu nehmen und die Werte in der oben beschriebenen Weise zu drucken.

Irgendwelche Gedanken dazu? Eine Pseudo-Code-Lösung wäre in Ordnung. Ich würde versuchen, dies zu versuchen, aber alles, was ich bisher versucht habe, schneidet es nicht ab. Vielen Dank.

Update: Wie gewünscht, würde die gewünschte Ausgabe für das Beispiel [1:20] etwa so aussehen: 1, 10, 5, 15, 3, 7, 12, 17, 2, 4, 6, 8, 11, 13, 16, 18, 9, 19, 20

Dieser Ausgang könnte auf viele ähnliche Arten dargestellt werden, abhängig vom verwendeten Algorithmus. Aber, die Idee ist, zuerst die halben Werte, dann die Viertel, dann die Achten, dann die Sechzehntel usw. anzuzeigen, wobei vorher präsentierte Werte weggelassen werden.

Answer 1

Hier einige Python-Code ähnlich Ausgabe an Ihrem Beispiel Herstellung:

def f(low, high): 
    ranges = collections.deque([(low, high)]) 
    while ranges: 
     low, high = ranges.popleft() 
     mid = (low + high) // 2 
     yield mid 
     if low < mid: 
      ranges.append((low, mid)) 
     if mid + 1 < high: 
      ranges.append((mid + 1, high)) 

Beispiel:

>>> list(f(0, 20)) 
[10, 5, 15, 2, 8, 13, 18, 1, 4, 7, 9, 12, 14, 17, 19, 0, 3, 6, 11, 16] 

Der low, high Bereich schließt den Endpunkt, als Konvention in Python ist, so das Ergebnis enthält die Zahlen von 0 bis 19.

Der Code verwendet einen FIFO, um die Teilbereiche zu speichern, die noch verarbeitet werden müssen. Der FIFO wird mit dem vollen Bereich initialisiert. In jeder Iteration wird der nächste Bereich aufgeklappt und der Mittelpunkt zurückgegeben. Dann werden der untere und der obere Teilbereich des aktuellen Bereichs an den FIFO angehängt, wenn sie nicht leer sind.

bearbeitet: Hier ist eine ganz andere Implementierung in C99:

#include <stdio.h> 

int main() 
{ 
    const unsigned n = 20; 
    for (unsigned i = 1; n >> (i - 1); ++i) { 
     unsigned last = n; // guaranteed to be different from all x values 
     unsigned count = 1; 
     for (unsigned j = 1; j < (1 << i); ++j) { 
      const unsigned x = (n * j) >> i; 
      if (last == x) { 
       ++count; 
      } else { 
       if (count == 1 && !(j & 1)) { 
        printf("%u\n", last); 
       } 
       count = 1; 
       last = x; 
      } 
     } 
     if (count == 1) 
      printf("%u\n", last); 
    } 
    return 0; 
} 

Dies vermeidet die Notwendigkeit eines FIFO durch einige Tricks, um zu bestimmen, ob eine ganze Zahl bereits in einer früheren Iteration aufgetreten ist.

Sie könnten auch die ursprüngliche Lösung in C einfach implementieren. Da Sie die maximale Größe des FIFO kennen (ich denke, es ist so etwas wie (n + 1)/2, aber Sie müssten dies überprüfen), können Sie Verwenden Sie einen Ringpuffer, um die eingereihten Bereiche zu halten.

Bearbeiten 2: Hier ist noch eine andere Lösung in C99. Es ist optimiert, nur die Hälfte der Schleifeniterationen auszuführen und nur Bitoperationen und Additionen, keine Multiplikation oder Divisionen zu verwenden. Es ist auch prägnanter, und es enthält 0 nicht in den Ergebnissen, so können Sie dies am Anfang wie ursprünglich geplant haben.

for (int i = 1; n >> (i - 1); ++i) { 
    const int m = 1 << i; 
    for (int x = n; x < (n << i); x += n << 1) { 
     const int k = x & (m - 1); 
     if (m - n <= k && k < n) 
      printf("%u\n", x >> i); 
    } 
} 

(Dies ist der Code, den ich von Anfang an schreiben wollte, aber es hat mich einige Zeit meinen Kopf zu wickeln um ihn herum.)

Answer 2

Binary Heap als Array bereits diese Struktur hat. Vielleicht möchten Sie Ihr Array in diesem Formular speichern und es sequentiell drucken. Für Knoten i sind Kinder 2i + 1, 2i + 2.

Answer 3

Hmmm ... Sie suchen im Grunde nach einer Art raumfüllender Kurve. Ich bin mir fast sicher, dass du das mit cleverem Bit-Twiddling machen kannst. Vielleicht möchten Sie einen Blick darauf werfen, wie Indizes für die Morton-Z-Order- oder Ahnentafel-Indexierung berechnet werden, die in einigen Cache-lastigen Stencil-Algorithmen verwendet wird. Ich habe mir das vor einigen Jahren angeschaut, und die Indizierung war ähnlich dem, was Sie beschreiben und mit Bit-Twiddling machen.

Answer 4

Es ist einfach für 1/2, oder?

Warum also nicht rekursiv, so dass 1/4 1/2 von 1/2 und 1/8 1/2 von 1/4 ist?