Żyla, żyletka, śmierć.Aniele usłysz moje myśli,które uciszyleś ...
2. to może być trochę mało, żeby zobaczyć pożądany wizualnie efekt. Z drugiej strony nie ma
gwarantującego żądaną bliskość
ale jest prawo iterowanego logarytmu
http://en.wikipedia.org/w...rated_logarithm
ktore mowi w jakich granicach mieszcza sie wartosci odchylen od 0
Nie no, po tak miłej zachęcie nie mogę przecież nie podzielić się z Wami informacją, iż:
"W minionym semestrze zajmowałam się miarami konforemnymi i niezmienniczymi w zespolonych układach dynamicznych oraz ich zastosowaniem do badania takich własności tych układów, jak Centralne Twierdzenie Graniczne i Prawo Iterowanego Logarytmu. Poznałam techniki konstrukcji miar konforemnych i niezmienniczych dla odwzorowań wymiernych sfery Riemanna T:C-->C stopnia co najmniej dwa oraz dla rodziny eksponencjalnej fλ = λexp(z), λεC{0} /pozowoliłam sobie posłużyć się znakiem ε z braku symbolu 'należy'/ w przypadku hiperbolicznym, tzn. gdy fλ posiada cykl przyciągający. Następnie uczyłam się jak przy pomocy skonstruowanych miar wyprowadzić Centralne Twierdzenie Graniczne w obu wymienionych wyżej przypadkach. Moim celem jest wyprowadzenie Prawa Iterowanego Logarytmu dla rodziny fλ w przypadku hiperbolicznym i dla pewnej klasy potencjałów zwanych oswojonymi ("tame"). (...)"
Dla ścisłości dodam, że jest to wersja lajtowa tego, czym się zajmowałam, gdyż przeznaczona jest dla sekreteariatu studiów doktoranckich, który niekoniecznie zna się na dynamice holomorficznej
PS. Jakby komu było mało, mogę jeszcze opowiedzieć w dwóch słowach o krokach dowodu PIL
Dobra, to a propos złożoności, memseta i paru innych spraw.
Traktować jako luźne dywagacje, a nie pretekst do jakiegoś flame'a, na którego i tak nikt nie ma czasu! ;)
1. Złożoność
Mamy policzyć w*h elementów, i tego nie obejdziemy. Można by jedynie oszacować czego będzie mniej (luster czy pustych pól) i stworzyć jedynie zbiór tych punktów. Jedyne rozwiązanie które mi przychodzi później do głowy na stały czas sprawdzenia to hashowanie (pamiętajmy, tablice odpadają bo wtedy trzeba by je zerować!) - jeśli mamy hita, to należy, jeśli missa, to nienależy. Ale hashowanie z obsługą kolizji (inne nas nie interesuje tutaj) pesymistycznie i tak ma zawsze czas liniowy wyszukiwania... (liniowy względem liczby wyników, bo tyle maksymalnie rzeczy będzie w tabeli).
(Dla uproszczenia - K = liczba wyników).
Inna sprawa to trzymanie wyników w formie posortowanej. Możemy założyć strukturkę podobną do countinga. Tj. wyniki trzymamy w tablicy wyniki[] o długości K, a w tablicy count[] o długości h ( przy założeniu h > w, inaczej transponujemy) szereg ilości elementów w kolejnych wierszach (czyli count[ i ] = ile jest łącznie luster we wszystkich wierszach do i-tego włącznie; inaczej: pozycja ostatniego lustra na i-tym poziomie w tablicy wyniki[]). Wtedy sprawdzenie czy dana pozycja pudełka zawiera lustro czy nie jest binserchem po wynikach odpowiedniego poziomu ( binsearch( left = count[ i-1 ], right = count[ i ], szukany ) ), czyli de facto w wersji z dwoma porównaniami O( log( min{ w, K } ) ).
Opłacalne tylko dla liniowej ilości pól które sprawdzamy.
To tak z nudów napisane, tak czy siak - każda reprezentacja się kwadraci już przy liczeniu dla liczby luster rzędu kwadratowego ;))
Za to ciekawy problem - jaka jest maksymalna minimalna ilość luster niezbędnych do wstawienia? Dla zestawu (n,n) dla którego dobrą odpowiedzią byłyby lustra na każdej pozycji istnieje przykładowo rozwiązanie liniowe ( lustra na przekątnej ). Dla nieco zaburzonych danych, np. 4 x 10, wychodzi 10.
Ciekawe, czy liczba jest zawsze liniowa, np. od dłuższego boku czy sumy?
2. Czyszczenie tablicy
a) tak naprawdę, to jeśli to co raku napisał przetransponować na wiersze (zamiana indeksów) to przy założeniu, że najpierw idą dane dla wszystkich promieni z jednej ściany nie trzeba pamięci niczego trzymać poza jedną ścianą - WPP trzeba trzymać obie, i tyle: wszystko to, co byśmy liczyli dla tablicy lub jej wiersza można puszczać od razu na wyjście (i po zrobieniu kolejnego wiersza wczytywać następny promień z drugiej ściany). Czyli pamięciowo Th( 1*min{ w, h } + 1 ). Oczywiście - wtedy nie ma czego czyścić.
b) memset logarytmicznie nie zadziała. Może bardzo szybko, ale logarytmicznie nie nawet jeśli znakowałby całe bloki jako wyczyszczone, to przy pierwszym odwołaniu do niego i nadpisaniu już spójność "czystości" by się poszła kochać i trzeba by zapamiętywać informacje o zmianach - więc byłby już zbiór informacji, które przy każdym odwoływaniu trzeba by przeszukiwać. (Pewnie binsearchem, ale kogo to obchodzi - byłoby to szalenie długie nawet gdyby sprowadzało się do logarytmu iterowanego).
Mapy
Mapa to taka tablica, w której można indeksować obiektami dowolnego typu. W przypadku, gdy element o danym indeksie nie istnieje, jest on automatycznie tworzony (za pomocą konstruktora domyślnego) i wstawiany do mapy. Implementacja zwykle bazuje na drzewach zrównoważonych, tak więc złożoność operacji wstawiania i pobierania elementu wynosi O(log n). Ze względu na tę implementację (i ograniczenie na złożoność operacji) wymagane jest, aby na indeksach był zdefiniowany liniowy porządek (operator '<').
Mapa jest zdefiniowana w nagłówku <map>. Przykład użycia:
Code: map<int, node*> M; // tworzy (pustą) mapę wskaźników na 'node' indeksowanych liczbami typu 'int'
M[1001] = ptr1; // wstawia wskaźnik 'ptr1' pod indeksem 1001
M[-79] = ptr2; // wstawia wskaźnik 'ptr2' pod indeksem -79
M[1001] = M[-79]; // pobiera wskaźnik z indeksu -79 i zastępuje nim element pod indeksem 1001
Czasem zachodzi potrzeba sprawdzenia, czy w mapie istnieje element o zadanym indeksie. Można to zrobić za pomocą wyrażenia:
Code: (M.find(index) != M.end())
Metoda 'find' zwraca iterator to elementu mapy pod danym indeksem. Jeżeli taki element nie istnieje, zwraca 'M.end()'. Wyłuskanie iteratora do elementu mapy zwraca parę - obiekt typu 'pair<const index_type, content_type>' (w naszym przypadku 'pair<const int, node*>'). W ten sposób poprzez iterator dostępne są zarówno indeks (jako składowa 'first'), jak i wartość pod tym indeksem (składowa 'second'). Oto elegancki sposób operowania na elemencie mapy:
Code: map<int, node*>::iterator i = M.find(index);
if (i != M.end()) {
// zrób coś z 'i->second'
}
Oczywiście można też tak:
Code: if (M.find(index)) {
// zrób coś z 'M[index]'
}
Ale sposób ten ma tę wadę, że wyszukuje elementu o indeksie 'index' dwukrotnie: raz sprawdzając, czy w ogóle istnieje, a drugi raz przy wywołaniu 'M[index]'.
Przeglądanie mapy wygląda tak samo jak w przypadku innych kontenerów. Trzeba tylko pamiętać o tym, że wyłuskanie iteratora zwraca referencję na obiekt-parę:
Code: for (map<int, node*>::iterator i = M.begin(); i != M.end(); ++i) {
// odczytaj indeks z 'i->first' (ale nie można zmienić indeksu!)
// zrób coś z wartością 'i->second' (tutaj modyfikacja jest możliwa)
}
Usuwanie z mapy odbywa się za pomocą instrukcji 'erase', przy czym może ona przyjąć argument, który jest iteratorem albo samym indeksem:
Code: M.erase(M.begin());
M.erase(1001);
Jest drobna różnica pomiędzy usuwaniem z listy i z mapy. Operacja 'erase' na liście zwraca iterator na następny element. W przypadku mapy 'erase' nic nie zwraca. Dlatego na przykład nie można wyczyścić mapy, iterując przez 'erase' (ale też nie trzeba - w końcu jest 'clear').
Aby wstawić nowy obiekt do mapy, możemy też użyć metody 'insert':
Code: M.insert(make_pair(1001, ptr1));
Ma ona tę zaletę nad przypisaniem do 'M[1001]', że nie jest tworzony obiekt konstruktorem domyślnym tylko po to, aby potem go zastąpić innym. Ale w przypadku intów to raczej nie ma znaczenia. 'make_pair' tworzy obiekt typu 'pair<int, node*>' (ten jest potem rzutowany na 'pair<const int, node*>'). Można by napisać 'pair<int, node*>(1001, ptr1)', ale wtedy trzeba jawnie wpisać typy-argumenty szablonu. Natomiast 'make_pair' jako funkcja może automatycznie rozpoznać typy argumentów - ot taka sztuczka syntaktyczna w C++
W mapie też można wyszukiwać binarnie - w końcu mamy porządek liniowy na indeksach. Oto przykład:
Code: map<int, node*>::iterator i1 = M.lower_bound(index1);
map<int, node*>::iterator i2 = M.upper_bound(index2);
Semantyka operacji 'lower_bound' i 'upper_bound' jest taka jak przy zwykłym wyszukiwaniu binarnym.
Pewnym wariantem mapy jest multimapa - obiekt typu szablonowego 'multimap'. Tym się różni od zwykłej mapy, że może przechowywać wiele obiektów pod tym samym indeksem. Odwołanie 'M[index]' traci wówczas sens, więc nie ma go w multimapie. Ale wyszukiwanie binarne oczywiście nadal działa.