UnionFind

13.11.2009
Trudność

Na zajęciach poznaliśmy też inną struktruę danych, która posiada "explicit layout", jaką jest union-find, zaimplementowany jako pojedyncza tablica.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int u[N];
int find(int x);
bool unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y)return false;
  if(u[x]<u[y]){
    u[y]=x;
  }else if(u[y]<u[x]){
    u[x]=y;
  }else{
    u[x]=y;
    --u[y];
  }
  return true;
}
memset(u,-1,sizeof(u));

Tu dygresja jest taka, że memset jako drugi argument bierze pojedynczy bajt, więc to, że ten kod działa wynika tylko z tego, że czterobajtowy zapis liczby -1, wygląda tak samo jak 4 zapisy jednobajtowej liczby -1 pod rząd.

Jako ćwiczenie można sobie zaimplementować funkcję find.

Snippet icon

Napisz funkcję

1
int find(int x);
która znajdzie korzeń danej klasy abstrakcji, korzystając z tablicy globalnej u.

Oto jedno z moich ulubionych zadanek pochodzące z 10 Olimpiady Informatycznej Małpki. Zadanko jest dostępne na MAINie SIO.

Powiedzieliśmy sobie też, z grubsza co to jest logartym iterowany, oraz, że analiza złożoności dla problemu Union-Find do najłatwiejszych nie należy. Kluczowe jednak są pewne prawdy objawione:

  • Jeśli zapomnimy o optymalizacji z kompresją ścieżek w funkcji find, to program nadal będzie działał poprawnie, tyle, że zamiast logarytmu iterowanego zagości zwykły logarytm
  • Jeśli zapomnimy o optymalizacji z rangami i będziemy zawsze podpinać lewy do prawego w funkcji unite, to program nadal będzie działał poprawnie, ale złożoność pogorszy się i szczerze mówiąc nie umiem na oko powiedzieć czy istotnie...Wikipedia też nie wie, a także w google mi nie wyszło. Zachęcam do pobawienia się myślami nad tym.
  • Jeśli zapomnimy o obu optymalizacjach to może być kiepsko czyli np. $ O(n^2) $, chociaż program nadal będzie działał

Prawda jest taka, że Union-Find działa bardzo szybko i że nie chodzi nawet o logarytm iterowany, tylko o odwrotność funkcji Ackermana. Prawda jest też taka, że żeby móc coś sensownie mówić o złożoności, to wypada powiedzieć ile operacji union, a ile operacji find, chcemy zrobić. Nie mniej, do naszych ziemskich celów, wystarczy wiedzieć, że to jest po prostu mniej niż 4.

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com