[Alg] Inne spojrzenie na wyszukiwanie binarne

[TRSSpy]

Witam,

no to ja wrzucę swoje 3 grosze.

Problem:
Znaleźć dla danego tekstu (kilka słów) największy rozmiar czcionki, ale taki żeby tekst mieścił się na podanym regionie. Nie będę się tutaj skupiał na żadnym konkretnym API ani środowisku graficznym. Chodzi tylko o to, żeby przekazać główną myśl. Załóżmy zatem, że mamy funkcję, która zwraca nam wartość logiczną, jeśli zadany tekst mieści się na podanym obszarze.

Zastosowanie:
Akurat z tym problemem miałem do czynienia na telefonach komórkowych, gdzie funkcja zwracająca faktyczną wielkość zajmowanego tekstu była STRASZNIE WOLNA. Pewnie na domowych PCtach nie ma to aż takiego znaczenia - chyba jedyny problem, gdzie może wystapić zauważalny spadek wydajności to rozwiązywanie tego w środowisku javascript na stronie WWW.

Rozwiązanie:

Pierwsze jakie się nasuwa.

Kod:

int rozm=1;
while( (checkFit("foobar", rozm, 100, 20)) && (rozm<100) ) rozm++;

Jak widać w powyższym kodzie ilość wywołań kosztownej funkcji checkFit będzie wynosić średnio kilkadziesiąt.
Po skojarzeniu, że wyszukiwanie binarne służy nie tylko do wyszukiwania

Kod:

int rozm=0;
int proba=64;
while(proba){
   if (checkFit("foobar", rozm+proba, 100, 20)) rozm+=proba;
   proba>>=1;
}

Dzięki temu ilość wywołan kosztownej funkcji checkFit spada do kilku.

Podsumowanie:
Sądzę, że w wielu miejscach, gdzie planujecie, że ma się pojawić coś dużego i na środku (np. ukochany napis 'Game Over' ) i jeszcze nie wiadomo ile będzie miało znaków po przetłumaczeniu przez tłumacza itp. to można śmiało stosować.

W sumie to nie wiem jaki poziom zaawansowania ma prezentować ten dział. Być może dla niektórych rozwiązanie nr 2 jest absolutnie oczywiste. Mnie jednak nie przyszło od razu i bardzo się ucieszyłem gdy gra znowu zaczęła chodzić 'płynnie'.

A w ogóle to fajnie, że powstał taki dział na forum, bo do prowadzenia bloga to osobiście nie mam cierpliwości. A tak to zawsze coś na forum można wrzucić.

[deX(ter)]

Heh.. Skoro problem jest sformułowany jak niżej,

Znaleźć dla danego tekstu (kilka słów) największy rozmiar czcionki, ale taki żeby tekst mieścił się na podanym regionie.

to może by tak było cokolwiek na ten temat?

Algorytmy też dobrze - na pewno lepiej niż "estetyka komentarzy" ;].

[RageX]

Kolega w zasadzie dobry problem poruszył i pomysł na przyspieszenie wyszukiwania optymalnego rozmiaru, też w zasadzie dobry - znaczy standardowy, ale i tak przydatny. Ale wykonanie coś nie teges.

Twój algorytm - z tego co rozumiem - to... sprawdza czy napis o danym rozmiarze mieści się w danym zakresie. Iteracja wygląda tak, że 64 dzieli ciągle na pół do 0, Czyli ilość wywołań twojej funkcji sprawdzającej jest stała. Na dodatek ten algorytm nie zwróci nam dokładnego rozmiaru wcale. Będziemy mieli coś takiego...

Kod:

 
0.
rozmiar = 0
proba  = 64
rozmiar do sprawdzenia podany do funkcji = 64
1.
rozmiar = 64
proba = 32
rozmiar do sprawdzenia podany do funkcji = 96
2.
rozmiar = 96
proba = 16
rozmiar do sprawdzenia podany do funkcji = 112

Jak widać, nie ma to nic wspólnego z wyszukiwaniem binarnym. Sprawdzane rozmiary są jakby z kosmosu.

Moim zdaniem popełniłeś "yhym" błąd nazywając wyszukiwaniem binarnym coś co używa operatora binarnego. Przy czym jeden dzieli szukany zakres na pół co iteracje. A drugi po prostu przesuwa bity i sie nazywa operatorem binarnym gdyż działa na bitach.

Wyszukiwanie binarne w tym przykładzie, polegało by na tym że sprawdzamy maksymalny założony rozmiar... może być to jakaś estymacja z narzutem. W kolejnej iteracji, nasz rozmiar dzielimy na pół i znowu sprawdzamy. Jeśli się mieści, to górną połowę (tą między 32, a 64), dzielimy na pół, czyli przeprowadzamy test na 32 + 32/2 czyli 48. Jeśli się nie mieści czyli rozmiar 32 jest za duży to dzielimy dolną część, czyli robimy test na 32 - 32/2.
itd...
Ilość iteracji będzie zależała od pożądanej dokładności.

Powodzenia na przyszłość.
PS. Jeżeli ja po prostu nie rozumiem twojego algorytmu, źle go gdzieś odczytałem to przepraszam - to znak że na przyszłość trzeba go opisywać dokładniej, tak poza tym.

Edit: Oraz... wiem że to tak fajnie jest używać tych operatorów że to sprawia że czujemy się "cool" itd...
Ale funkcja ta zazwyczaj jako parametr rozmiaru przyjmuje wartość float. Konwersja jest stosunkowo droga, lepiej  floaty mnożyć przez połowę. Poza tym jeżeli za pierwszą "próbę" przyjmiemy liczbę która nie jest "power of 2" (przepraszam, nie mogłem sobie przypomnieć jak to po polsku), to pierwszy podział nie będzie na pół.

[albireo]

@RageX: na moje oko algorytm jest dobry, może nie uwzględniłeś, że rozm się zwiększa tylko gdy checkFit() zwróci true.

[RageX]

Ale jeśli zawsze zwraca true to rozmiar rośnie zamiast maleć.

[albireo]

No i dobrze, bo zakres przeszukiwania tej funkcji dla tego przykładu jest od 0 do 127, czyli jeśli zawsze będzie true to wynikowy rozmiar wyjdzie 127.

[RageX]

No rzeczywiście... heh. Źle zrozumiałem  - aczkolwiek sam się sobie nie dziwię. Znaczy działanie algorytmu dobrze odczytałem, ale nie wpadłem (i tu sie nie dziwię), że dobrany rozmiar będzie już jakimś podziałem rozmiaru maksymalnego. Pozostają jeszcze moje argumenty o floatach, oraz o rozmiarach nie będących kolejnymi potęgami dwójki.
Edit:

Kod:

float rozmiar = 0;
float maxRozmiar = 64.0f;

for(maxRozmiar *= .5f; maxRozmiar < .5f; maxRozmiar *= .5f)
    if (checkFit("foobar", rozmiar+maxRozmiar, 100, 20))
        rozmiar+=maxRozmiar;   

no i lepiej... no chyba że zależy nam na ilości testów, to warunek zakończenia testu zamienić na jakieś int i.
Uff.