Informatyka UJ forum

Rogal

Źle to zrozumiałaś. Za 'a' podstawiasz wynik działania funkcji Select dla tablicy M. Wtedy 'a' jest znalezioną medianą tablicy M zawierającej mediany zbioru S, czyli a jest medianą median wejściowego zbioru S.

Później to a podstawiasz do algorytmu Hoara opisanego w wykładzie punkt wyżej. W zasadzie to kroki 2-5, czyli to całe liczenie mediany median, jest tylko po to, żeby zapewnić liniowy czas działania Hoara nawet w pesymistcznym przypadku.

Krisowski

Spectro

Heh, też miałem TLE. Wprowadziłem jednak pewne poprawki:
- zrandomizowałem wczytywanie danych,
- dla przedziałów <=1000 wstrzelam się piwotem w środek, dla większych bawię się w medianę median,
- dodałem uses Buffering (wreszcie się przydał :P ).

Athina program o dziwo zaakceptowała O_o .

trywialna

Takie pytanie. W algorytmie Hoare zapuszczamy rekurencje wiec czy starczy nam pamięci? Jak ciągle generujemy nowe tablice S1 S2 S3 no to nie wydaje mi sie:/

jagm

Ale tablicę przekazujesz przez vara i tylko podajesz l,r jako zakres, na którym operujesz.

trywialna

No tak.. :roll: ja już nie moge z tym zadaniem:/

Pawel Str.

@Trywialna - po dokonaniu podziału na trzy części nie musimy robić wywołania rekurencyjnego, bo interesuje nas tylko jedna z części - lew lub prawa. W takim razie rekurencje można zastąpić pętlą.

Natomiast jeżeli chodzi o tablice median piątek, to można tworzyć nowe tablice bez problemu. Każda nowa tablica jest okolo 5 razy mniejsza od poprzedniej, więc w sumie zużyjemy nie więcej niż 5/4 rozmiaru tablicy wejściowej.

hansu

No ale jak to zrobic w pascalu? Tu rozmiar tablicy musi byc znany w chwili kompilacji wiec za kazdym razem w rekurencji musimy powolywac do zycia tablice o rozmiarze n/5. Tak mi sie przynajmniej wydaje :)

kap00ch

hmm no ale po co w ogole generowac/tworzyc jakiekolwiek nowe tablice? przeciez wszystko moznaladnie iszybko zrobic in-place, wystarczy mediany przerzucac na sam poczatek tablicy i wywoywac rekurencje zawsze dla tego kawalka :] szybko , latwo iprzyjemnie

Spectro

kap00ch

no ba! iteracyjna podstawa sukcesu :]

Pawel Str.

Nie no, da się przecież zrobić tablicę dynamiczną. Może niepotrzebne kombinowanie, ale da się. Mnie tak było łatwiej niż przerzucać na początek tablicy.

Skrobocik

No dobra, tylko powiedzcie mi, jak się inicjuje tablice dynamiczne we Free Pascalu, bo to chyba nie chodzi o "new" :?: Nie mam pojęcia :cry:

oinopion

exeman

Bo Pascal na szczescie nie jest Java i tutaj tak proste typy jak tablica bajtow nie jest obiektem. W Javie Integer jako obiekt to juz jest szczyt szczytow, przerost formy nad trescia.

Java powinna byc zakazana w srodowisku akademickim, o tak!

hansu

Popieram!!! TAK!!! Swiete slowa!!! Brawo Exeman!!!! Java won!!!! Jest beznadziejna, wolna, mulasta nieintuicyjna, obiektowa na sile i w ogole do dupy. :)

Btw. dzisiaj z jagmem na so wymyslilismy joke: dlaczego java zostala stworzona prze zespol programistow? Bo jeden nie bylby w stanie sam takich glupot nawymyslac :P

Spectro

Jak pazabo zobaczy wasze teksty o javie, to pewnie aż się wysili coś napisać na forum :twisted: .

chlebek

Czy ktos z robiacych to zadanie z Cormena tez mial problem z TLE i jakos sobie poradzil ? Moze caly problem tkwi w Partiotion Hoare'a ?

Skrobocik

Przeszło mi właśnie. W końcu nie bawiłem się w dynamiczną tablicę, tylko zrobiłem typ Sequence(ciąg), który składa się z 6mln, a nie 5mln elementów i po prostu medianki wrzucałem na koniec, czyli od miejsca 5000001 :D

chlebek

tez tak mialem i dalej TLE, cos musi byc nie tak skoro na 3 ostatnich testach na gronostaju ma TLE, a reszta wszystko OK, rowniez na Virgo same OK.
Tylko nie wiem czemu jak zmienilem z 2 tablicy { 5 mln i 1mln } na jedna tablice 6 mln to czasy sa gorsze na gronostaju { dla 3 ostatnich wciaz TLE }

hansu

@chlebek: jesli uzywasz partition hoare'a i nie masz go uodpornionego w zaden sposob na ciagi stale lub prawie stale, to nic dziwnego ze dostajesz TLE. Ja tak robilem quicksorta na poczatku (tzn. lomuto, ale na 2 a nie na 3) i dla maksymalnego ciagu stalego mieszal nim i mieszal podan 20 (!!!) sekund. Podejrzewam ze tu jest podobnie. Dlatego goraco polecam przepisanie tego na lomuto na 3, tan algorytm jest naprawde prosty (IMHO duzo prostszy od hoare'a) a i juz tutaj na forum byl kilkakrotnie opisywany. I powinno byc git :)

chlebek

Dzieki, w wolnej chwili pomiedzy ASD i ASD sprobuje poprawic to :lol:

trywialna

Może niektórzy z was pisali to zadanie bardzo krótko i ich zdaniem jest to zadanie proste, ale powiem wam że żadne zadanie mnie tak nie wykończylo psychicznie jak ta mediana:/ już nawet magiczną siódemke pisało mi sie lepiej. błąd na błędzie, poprostu zwiariować można:[. Na szczęście koniec tego koszmaru..

I bardzo dziekuje Mateuszowi za testerke na virgo, bez niej bym sobie napewno nie poradziła:)

hansu

No trudno mi sie z Toba nie zgodzic... Chociaz moze tyle czasu co A to mi to zadanie nie zajelo.... Ale jak sobie przypomne analizowanie 1.5 megowych "logow" z dzialania mojego programu - po kazdym najmniejszym kroku wypisywalem cala tablice i wszystkie zmienne... A zeby jeszcze wylapac bledy to tesy musialy byc dosc duze bo jakis taki upierdliwy blad mialem... W kazdym razie cos kilkaset elementow te moje tablice mialy... No HORROR to byl po prostu... Ale nauczylem sie na tym zadaniu baaaardzo duzo o debugowaniu - moze nie tyle nauczylem ile nabralem wprawy... Natomiast juz drze na mysl o debugowaniu K :/