VI. Mischen

Mischen
- siehe:
  - 4. Zerlegungsstrategie
- wir haben schon: O(log n) Zeit, aber O(n) Work
- optimal: also Work ist schon ok
- Q aber: nicht schnell genug, wenn man in logarithmischer Zeit sortieren will
- Zeit geht schneller!
Ranken einer kurzen Folge in einer anderen Folge
- Ausgangspunkt ist eine Folge X = (x₁, x₂, ..., x_n)
  - sortiert
- Rang(x:X) = Zahl der Elemente Î X die ≤ x sind
- Y=(y₁, y₂, ..., y_m)
  - sortiert
- Rang (Y:X) = (r₁, r₂, ..., r_m) mit r_μ = Rang(y_μ:X), μ= 1,..., m
- Ziel: Optimalität O(1) Zeit
  O(n) WORK
- Definition: Y ist kurz bezüglich X ↔ m=O(n^s) mit 0<s<1
  - i typisch: s= 1
    
    2
- Lemma: ist Y^m kurz bezüglich Xⁿ, dann kann Y in O(1) Zeit mit O(n) Work gerankt werden
  - CREW-PRAM
    - concurrent read exclusive write parallel random access machine
  - nach Kruskal
- Beweis:
  - für jedes Element aus Y einen Suchprozess
  - Ranken mit p = \floor{n/m} für jedes Element Î Y
  - p = \floor{ n
    
    } ≈ \floor{ n } Î Ω(n^1-s) ist die Anzahl der Prozessoren pro Element aus Y
    
    n^s
    
    m
  - → log (n+1) Zeit
    
    log (p+1)
    - Beweis für die Laufzeit: siehe
      - V. Suchen
    - →Zeit = O( log (n+1)
      
      ) = O( log(n+1)
      
      ) = O( 1
      
      · log(n+1) ) = O(1) Zeit
      
      log n
      
      1-s
      
      log(n^1-s)
      
      log (p+1)
  - O(n/m) Work pro Element
  - → m·O( n ) = O(n) Work insgesamt
    
    m
  - Für O(1) TIME haben wir n Prozessoren zur Verfügung und nutzen diese auch
Mischen
- Neu:
  - Teilen in Stücke der Größe √n
  - → √n Abschnitte der Länge √n
  - Annahme: A, B seien disjunkt (der Einfachheit halber)
  - → Pfeile zeigen zwischen Elemente
  - Ranken jetzt nicht mit binärer Suche, sondern mit Kruskal
  - rekursiv
- Algorithmus Ranking einer sortierten Folge in einer anderen
  - INPUT: Zwei sortierte Folgen der Längen m und n
  - OUTPUT: Array mit Rang (B:A)
  - begin
  - if m<4
    - Ranke die Elemente von B mit Kruskal
      mit p=n Prozessoren
      - // geht in O(1) Zeit, sichert uns O(n) Work
  - pardo
    - Ranke die roten Elemente (b_√m, b_2√m ...) von B in A mit Kruskal
      mit p=√n Prozessoren
      - // Sei j(i) = Rang(b_i√m:A)
      - // 1 ≤ i ≤ √m
      - // j(0) = 0
  - berechne rekursiv den Rang (B_i : A_i)
    - // B_i = (b_i√m+1, ... , b_(i+1)√m-1)
    - // A_i = (a_j(i)+1, ... , a_j(i+1))
    - // Herausnehmen der roten Elemente
  - sei 1 ≤ k ≤ m ein Index, der nicht einem rot markierten Element entspricht (kein Vielfaches von √m)
    
    Sei Rang(b_k : A) = j(i)+Rang(B_i:A_j) (i=\floor{ k })
    
    √m
  - end
- Lemma: Der Algorithmus arbeitet korrekt in O(log log m) Time
  mit O((m+n)log log m) Work
  - Definition: T(n,m) sei die entsprechende Zeit für den Algorithmus
  - Schritt 1 geht in O(1) mit O(n) Work
  - Problem: Nachweis der Zeit für Schritt 2
  - wir haben
    - √m Aufrufe von Schritt 2
    - O(1) Zeit für einen Rank-Aufruf nach Kruskal (Ranken einer kurzen Folge)
    - WORK: √m Pfeile
      √n Prozessoren
      O(√m·√n) Prozessoren Î O(n+m) WORK
      - Beweis:
        
        2√m · √n = √m√n+√m√n
        
        1. Fall: m ≤ n → ≤2√n√n = n + n = O(2n) = O(n) = O(n+m)
        
        2. Fall: n ≤ m: analog
    - Sei |A_i| = n_i
      - 0 ≤ i ≤ √m-1
    - |B_i| = √m
  - T(n_i,√m) sei die Zeit für das Paar (B_i, A_i), dass im Schritt 3 verarbeitet wird
    (durch rekursiven Aufruf)
  - →T(n,m) ≤ max_i T(n_i,√m) + O(1)
  - mit T(n,3) = O(1) ergibt sich:
  - T(n,m) = O(log log m)
  - → Work = O((n+m) log log m)
  - Folgerung: Sei n=m → Mischen geht in O(log log n) Zeit mit O(n log log n) Work
Ziel: Optimalität O(log n) TIME
O(n) WORK
neuer Ansatz (accelerated cascading)
- Idee:
  - gleichzeitiges Zerlegen beider Fogen
  - Rot: erste Elemente der Teilfolgen
  - Folgen paarweise verschieden
  - Pfeile: Ranken
    - können sich nicht kreuzen
  - es kann passieren, dass zwischen zwei Elementen in der einen Folge
    viele Elemente in der anderen Folge liegen
- Voraussetzung:
  - sei (der Einfachheit halber) m=n
  - Alle Blöcke B_i, A_i haben log log n Elemente
  - die ersten Elemente der Blöcke seien Bezeichnet mit q₁, q₂, ... bzw. p₁, p₂, ...
- seien
  - 1.) A₁, A₂, .... die Blöcke von A
  - 2.) p₁, p₂, ... die ersten Elemente von A₁, A₂, ....
  - 3.) B₁, B₂, .... die Blöcke von B
  - 4.) q₁, q₂, ... die ersten Elemente von B₁, B₂, ....
  - 5.) A' = {p₁, p₂, p₃, ...}
    - n sortierte Elemente
      
      log log n
    - |A'| = Θ( n )
      
      log log n
  - 5.) B' = {q₁, q₂, q₃, ...}
    - n sortierte Elemente
      
      log log n
    - |B'| = Θ( n )
      
      log log n
- Vorgehen
  - (I): Mische (A', B')
    - → Time O(log log n)
    - → Work O(log log n n ) = O(n)
      
      log log n
  - (II): Dann: Bestimme die Arrays
    - Rang (A' : B)
    - Rang (B' : A)
    - jetzt genaues "Nachschauen" wo die Pfeile hingehen
    - dazu: suche parallel für alle Roten Elemente
      (in Abschnitten der Länge log log n) die Zielpunkte
    - geht in O(log log n ) = O(log og n) Time
      
      log log n
    - jeweils nur n Elemente zu durchsuchen (da nicht überlappend)
    - → Work O(n)
  - Definition:
    - Rang (p_i : B') = r_i
      - bedeutet: p_i kommt in den Block B_{r_i}
      - d.h. q_{r_i} < p_i < q_{r_i+1}
  - (III) Dann:
    - "i: Bestimme die Ränge der Elemente in A_i \ {p_i} in B
    - "k: Bestimme die Ränge der Elemente in B_k \ {q_k} in A
    - Skizze
      - Rang (p_i : B) :=: j(i)
      - Rang (q_k : A) :=: j*(k)
      - sind bekannt nach (II)
    - Sei j(i+1) > j(i) →Alle Elemente b_j(i)+1...b_j(i+1) kommen zwischen p_i und p_i+1
    - Wenn |b_j(i)+1 ... b_j(i+1)| < log log n Þ Mischen von A_i und B mit sequentiellem Ansatz
      ( |A_i| = log log n)
    - Wenn nicht: Þ Es existieren Elemente in B': q_k ... q_k+s ,
      die zwischen b_j(i) ... b_j(i+1) liegen und Abstand 1 haben
      - Die Ränge j*(k), j*(k+1) ... j*(k+s) sind nach (II) bekannt
      - Jedes Paar (schraffiert) hat < log log n Elemente (oben und unten)
      - Þ unabhängig sequentiell Mischen
  - Þ optimales Mischen in O(log log n) Zeit möglich!
- Voraussetzung:
  - CREW-PRAM
    - concurrent read exclusive write parallel random access machine

i typisch: s=	1
	2

→	log (n+1)	Zeit
	log (p+1)

→ m·O(	n	) = O(n) Work insgesamt
	m

Sei Rang(b_k : A) = j(i)+Rang(B_i:A_j) (i=\floor{	k	})
	√m