Opowieść o małym n ;-)

Wielu się może nie zgodzić, ale powszechna prawda w programowaniu mówi "proste algorytmy działają dobrze dla małych n, a zwykle mamy do czynienia z małymi n". Wniosek jest taki, że w 80 czy nawet 90% (a nawet 99%) przypadków najbardziej prosty i banalny algorytm działa całkowicie znośnie.Problemy zaczynają się gdy wchodzimy w ten obszar, w którym n bywa już większe.Szczęście w nieszczęściu jest takie, że większość programistów nigdy dużych n nie widzi. Co czasem może boleć ;-)Można się o tym przekonać bawiąc się w rozwiązywanie zadań z Google Code Jam ;-)Mają po 2 zestawy danych, mały i duży. Na małym zestawie danych naiwne algorytmy działają praktycznie zawsze, na dużym do czasu ;-)W TopCoder zwykle naiwny algorytm wystarcza.Dlatego czasem przydałoby się kilka prostych tricków w języku ;-)Np. mamy taki kod:

 static long factorial(long l) {  return (l>1)?l*factorial(l-1):1; }

Czyż nie byłoby miło gdyby dało się powiedzieć Java'ie "jeżeli ta funkcja wołana była już z danym parametrem to po prostu zwróć jej obliczoną wcześniej wartość".Np. definicja takiej funkcji mogłaby wyglądać tak:

 static cached long factorial(long l) {  return (l>1)?l*factorial(l-1):1; }

albo jakoś podobnie ;-)Wtedy powyższy kod mógłby zostać zamieniony w coś takiego:

 static Map factorial = new HashMap();  static long factorial(long l) {    Long result = factorial.get(l);  if (result==null) {   result=(l>1)?l*factorial(l-1):1;   factorial.put(l, result);  }  return result; }

Zawsze by to choć trochę prościej było ;-)Chociaż z drugiej strony takie coś miałoby też swoje wady. Java ma tą miłą właściwość, że język nie próbuje być mądrzejszy od developera w tym sensie, że nie generuje sobie na boku żadnego ogólnie dostępnego kodu [OK, generuje np. metody do trzymania związku między klasą wewnętrzną, a zewnętrzną, ale to co innego]. Nie ma np. właściwości więc developer pisząc obiekt.pole=10 wie, że po prostu pisze do jakiegoś pola [i popełnia grzech śmiertelny, ale to akurat szczegół ;-)], ale nie woła żadnego kodu w Java'ie.To powoduje, że mniej jest magicznych zależności, a to też ułatwia ;-)Ale mimo wszystko, przydałyby się czasem takie czary ;-)O! albo dodatkowy konstruktor dla wszystkich typów implementujących Map, dla takiej HashMap'y mógłby wyglądać tak new HashMap("toster"), który inicializowałby nową HashMap'ę, która dla get(key) w momencie gdy dany klucz nie miałby wartości zwracałaby tą domyślną wartość przekazaną w konstruktorze :-)Albo chociaż dodatkową metodę get(key,defaultValue) :-)Chociaż tu by mieli problem podobny do tego co się dzieje z JDBC w Java 6. Zmienili interface i nie wystarczy przekompilować starego kodu przy pomocy nowej Java'y :-(To może nowy interface MapWithDefaultValue z jedną metodą get(key,defaultValue), którą implementowałyby wszystkie domyślne mapy? ;-)Dodanie takich cosiów [tak naprawdę głównie tego pierwszego] pewnie by o trochę problem dużych n troszkę odsuwało ;-)

Podobne posty^beta
Algorytmy Genetyczne szukają Symbolu Newtona ;-)
Prawdziwy narodowo-katolicki patriota i prawdziwy żydokomunista - opis wzorców
Jak z metody size() w List w Java'ie dostać ujemną liczbę? ;-)
Modale nie takie dobre dla Androida ;-)
Refleksje i serializacja w Java'ie - podstawy i obalanie mitów ;-)