Clasele 11-12 lecția 25 - 1 apr 2015

Premierea concursului de teme

Vezi Clasamentul temelor.

• Premiul 1: Alexandru Văleanu
• Premiul 2:
• Premiul 3:
• Mențiune:

(suspans până în ultima clipă)

Geometrie computațională: Sweep line

Nu vrem să ne îndopăm cu algoritmi până în ultima clipă. De aceea, predăm doar puțină geometrie computațională, care este de fapt o aplicație a structurilor de date echilibrate.

Pornim de la o problemă. Se dau n segmente în plan; există două care se intersectează? Algoritmul naiv, care compară fiecare pereche de segmente, funcționează în $O(n^{2})$.

Ca idee de îmbunătățire, sortăm cele 2n puncte după coordonata x. Nu are sens să testăm un segment care deja s-a terminat cu altul care încă nu a început. Parcurgem planul de la stânga la dreapta cu o linie de baleiere (sweep line) și facem opriri în 2n puncte de interes (capetele segmentelor). Pe parcurs, întreținem lista de segmente intersectate de linia de baleiere, ordonate de sus în jos. Două segmente se intersectează dacă își interschimbă poziția în listă.

// TODO: imagine

Avem nevoie de o structură de valori sortate care să permită următoarele operații în O(log n):

• inserare
• ștergere
• predecesor
• succesor

Putem folosi skip lists, treaps etc. Structura trebuie particularizată un pic: pentru a afla poziția corectă de inserare vom folosi, în loc de comparații de numere, produse vectoriale. De ce? Deoarece coordonatele la care segmentele intersectează linia de baleiere se modifică pe măsură ce linia avansează.

Pentru fiecare din cele 2n puncte,

• dacă punctul este începutul unui segment s, inserează s în structura ordonată. Fie r predecesorul. Dacă există, verifică dacă r și s se intersectează. Idem pentru succesor.
• dacă punctul este sfârșitul unui segment s, șterge s din structura ordonată. Fie r și t predecesorul și succesorul. Dacă ambii există, verifică dacă r și t se intersectează.

Complexitatea totală este $O(n\log n)$. Subliniem că algoritmul nu găsește decât un punct de intersecție, nu pe toate (care pot fi $O(n^{2})$).

Cazuri particulare:

• mai multe capete de segment pe aceeași verticală
• segmente verticale;
• intersecții de trei segmente în același punct

Găsirea tuturor intersecțiilor a n segmente

• algoritmul anterior nu poate fi aplicat pentru găsirea tuturor intersecțiilor
  • exemplu când algoritmul pierde intersecții
• Bentley-Ottmann au inventat o generalizare
• pornim cu cele 2n puncte într-o coadă de priorități ordonată după coordonata x
• cu timpul, coada de priorități va ține și intersecții viitoare ale segmentelor baleiate până acum
• pentru fiecare punct din coadă,
  • dacă este începutul unui segment s:
    • inserează-l în lista ordonată, fie r predecesorul și t succesorul
    • șterge r x t din coadă dacă există
    • inserează r x s și s x t în coadă dacă este cazul
  • dacă este sfârșitul unui segment s:
    • șterge-l din lista ordonată, fie r predecesorul și t succesorul
    • inserează r x t în coadă dacă este cazul
  • dacă este intersecția a două segmente s și t:
    • schimbă ordinea lui s și t în lista ordonată
    • șterge r x s și t x u din coadă dacă existau
    • inserează r x t și s x u din coadă dacă este cazul
• motivul pentru care ștergem intersecții din coadă este ca memoria necesară să rămână O(n)
• la fiecare moment, în coadă avem maxim 3n puncte: 2n capete de segmente și n intersecții de segmente consecutive în lista ordonată
• complexitate: O((n + k) log n), unde k este numărul de intersecții
• îmbunătățit de Balaban O(n log n + k), dar considerabil mai greu

Retușuri pentru ONI

Pentru că „retuș” sună mai bine decât „îngrășăm porcul în Ajun”. :-)

Parsarea ieșirii

Am testat dacă merită parsată ieșirea. Merită, dar câștigul este mai mic decât în cazul intrării. Am comparat trei programe care generează 1.000.000 de numere aleatoare între 1.000.000 și le afișează. Fișierul de ieșire are 6,9 MB.

• Varianta naivă face afișarea cu %d.
• Varianta parsată separă cifrele numărului cu împărțire și modulo, apoi le afișează în ordine inversă.
• Varianta optimizată evită operația modulo, calculând x % 10 ca x - (x / 10) * 10.

Concluzii: Pe calculatorul Varena, parsarea câștigă cam 250-300 ms. Varianta optimizată nu mai aduce câștiguri. Pe un calculator ceva mai bun, diferența se reduce la 80 ms.

Nu uitați că, înainte de a închide fișierul de ieșire, trebuie să scrieți în el tot ce v-a mai rămas în bufferul din memorie (flush the buffer).

Anexez media:parsare-iesire-naiv.cpp și media:parsare-iesire.cpp.

Un pic de Bash scripting

... sau măcar cum să scriem un while într-o linie de comandă.

Scenariu ipotetic: pentru o problemă, aveți o soluție rapidă, dar de care nu sunteți prea sigur. O soluție naivă (lentă) și un generator de teste se pot implementa rapid. Atunci, iată un script de o linie în Bash care generează teste mici, rulează ambele soluții și se oprește când răspunsurile diferă.

  while true; do ./gen parametri > p.in; rm -f p.out; ./v1; mv p.out /tmp; ./v2; diff /tmp/p.out p.out || break; sleep 1; done

Pe bucăți, scriptul funcționează așa:

• Ciclează la infinit. Ar fi frumos să putem încheia elegant cu o sintaxă de genul repeat ... until fișierele_diferă, dar Bash nu are conceptul de buclă cu testare la sfârșit.
• ./gen parametri > p.in rulează generatorul de teste. Presupune că generatorul acceptă parametri din linia de comandă și tipărește pe ecran, de aceea ieșirea generatorului este redirectată în fișier. Evident, puteți să faceți scriptul să nu accepte parametri, să tipărească singur direct în p.in etc.
• Fișierele de intrare ieșire se numesc p.in și p.out.
• v1 și v2 sunt cele două versiuni de program, probabil compilate din v1.cpp și v2.cpp
• Fișierul produs de prima versiune este mutat în /tmp pentru a nu fi suprascris de a doua versiune.
• Dacă diff returnează un cod de eroare (ceea ce se întâmplă când fișierele diferă), atunci se execută a doua parte a disjuncției, break, și scriptul se termină.
• Executăm sleep 1 pentru că, probabil, oricum inițializați generatorul de numere aleatoare cu srand(time(NULL)) și deci va genera date identice până când trece o secundă.
• Dacă cumva apare o diferență, fișierul de intrare rămas în p.in este cel care cauzează diferența între versiuni.

Desigur, ca să ajungeți să faceți aceste lucruri trebuie să știți unde stau pe disc binarele generate. Dacă folosiți un IDE (CodeBlocks etc.), familiarizați-vă cu directoarele unde salvează sursele.