Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Zadanie M - Lustra
Idź do strony Poprzedni  1, 2, 3, 4
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Lupus
pijak



Dołączył: 02 Lut 2006
Posty: 105
Przeczytał: 0 tematów

Skąd: Lea/Piastowska

PostWysłany: Pon 3:33, 13 Lis 2006    Temat postu:

Spectro napisał:
No to sobie porównaj: [link widoczny dla zalogowanych] (nawet jeżeli liniowo, to baaaardzo szybko). Z tego co się orientuję, to inicjaizacja tablic jest aktualnie możliwa w czasie logarytmicznym dzięki właściwościom sprzętowym (prawdopodobnie jakieś odznaczanie bloków pamięci, których rozmiary są potęgami dwójki).

Spectro, z ciekawości porównałem sobie memset i pętlę for.

Czasy podane na tej stronce do której link dałeś są jakieś przedpotopowe. U nich czas wypełniania tablicy o 1 000 000 elementach to 4 sekundy, a u mnie (na nie jakimś super komputerze) 0.063s .']

Kazałem programowi wypełnić tablicę 100000000 ( 10^8 ) intów, czyli 400MB. Kompilowałem gcc 3.4.2.
Wypełnianie pętlą for, skompilowane bez optymalizacji trwało 1,375s.
To samo z optymalizacją 1,22s.
Memsetem (zawsze) 0.92s.

Przy tablicy o rząd wielkości mniejszej różnicy w czasie wykonywania nie było _żadnej_.

Wziąwszy jeszcze pod uwagę, jak często przychodzi nam deklarować tablice 400MB, ten memset nie wydaje się jakoś super potrzebny .']

Swoją drogą, inicjalizowanie tablicy wykonuje się w czasie stałym .'] To jest oznaczenie (w pamięci wirtualnej) gdzie się zaczyna i gdzie kończy obszar pamięci którego potrzebujemy. Ewentualnie system operacyjny może potrzebować odrobinki czasu na rozparcelowanie tego obszaru po jakichś wolnych blokach pamięci.


EDIT: well... wpadłem wreszcie na genialny pomysł żeby zamiast raz na dużej tablicy, zapuścić 1000 razy wypełnianie mniejszej (powiedzmy 10^6) .'] Zwracam honor, memest wypadł prawie dwa razy szybszy .'] (memset == 0,6 * pętla_for)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pon 8:13, 13 Lis 2006    Temat postu:

Widzę, że rozpętałem dyskusję o memsecie. Fajnie :) .

@Rogal:
http://www.matinfuj.fora.pl/viewtopic.php?p=20762#20762
http://www.matinfuj.fora.pl/viewtopic.php?p=20768#20768
Zatem piwo należy się mnie :lol: . Swoją drogą nie wiem jak udało Ci się zrobić to zadanie bez zauważenia tego oczywistego faktu :P .

@cct:
Czyli, jak przypuszczałem, wystarczy liniowa ilość luster ;) . Robię zgodnie z metodą, którą opisałeś i udowodniłeś (? - bo nie sprawdzałem) indukcyjnie (teraz rozumiem, o co Ci chodziło z cyklami permutacji). Gdyby np. wypisywać nie całą tablicę, a tylko pozycje na których są lustra, to czas algorytmu byłby liniowy (a i tak po sekundzie miałem OK na Athinie :mrgreen: ).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Pon 15:16, 13 Lis 2006    Temat postu:

Macie jakieś pomysły, czemu mogę mieć RTE :?:
Robię na dwóch wierszach wskazywanych przez wskaźniki, a wypisuję w locie bez żadnej dodatkowej tablicy. Nie mam pojęcia gdzie może się sypnąć :?

EDIT
Już nieważne, standardowo pojebane błędy mnie wkopały :evil:
Chociaż tym razem, dzięki zauważeniu tego błędu zmieniłem na wersję z jednym wierszem i jedną kolumną (wypisywanie znowu na żywca) i przeszło ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Prezioso
pijak



Dołączył: 18 Lis 2005
Posty: 100
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Pią 1:29, 17 Lis 2006    Temat postu:

Nio ładnie... Athina daje OK, a Avast wywala wirka:

[link widoczny dla zalogowanych]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Pią 1:45, 17 Lis 2006    Temat postu:

hehe. czyli nie tylko ja mam ten problem ;] avast jest chyba z dupy ;] jak dasz include <iostream> to już nie będzie krzyczał ;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kafex
zielony żul



Dołączył: 28 Mar 2006
Posty: 1458
Przeczytał: 0 tematów

Skąd: Zawiercie

PostWysłany: Pią 1:49, 17 Lis 2006    Temat postu:

U mnie w Zawierciu ponoc szalał w katalogu ASD pare dni temu ;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Sob 12:59, 18 Lis 2006    Temat postu:

Jak robiliscie wczytywanie, bo mi zawsze pomija cos, jak cos zakodze to idzie to z tresci zadania, ale jak wkleje z forum to sie sypie, no wrrrr. da sie to jakos normalnie scanfami zrobic, czy trza kodzic wszystko na getc?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Sob 13:03, 18 Lis 2006    Temat postu:

ja mialem normalnie scanfami ;]

ilość zestawów:
Kod:
scanf("%d\n",&nr);


wysokość i szerokość:
Kod:
scanf("%d %d\n",&w,&h);


pojedynczy opis:
Kod:
scanf("%c %hd %c %hd\n",&a,&x,&b,&y);
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Sob 13:14, 18 Lis 2006    Temat postu:

Ja też zawsze scanf robię, ziom ;)
Nawet bez wczytywania końców linii, bo skoro to są liczby, to i tak sobie z tym poradzi.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kafex
zielony żul



Dołączył: 28 Mar 2006
Posty: 1458
Przeczytał: 0 tematów

Skąd: Zawiercie

PostWysłany: Sob 13:15, 18 Lis 2006    Temat postu:

exe te przykłady z forum mają spacje na końcu więc nic dziwnego, że Ci sie pitoli ; )
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Sob 13:20, 18 Lis 2006    Temat postu:

nic nie działa nic nie działa nic nie działa!!!!!!
Fidel: Twoj pseudokod nie dziala :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Sob 13:24, 18 Lis 2006    Temat postu:

Skrobocik napisał:
Ja też zawsze scanf robię, ziom ;)
Nawet bez wczytywania końców linii, bo skoro to są liczby, to i tak sobie z tym poradzi.

w tym zadaniu akurat bez wczytywania końca lini mi się sypało. to pewnie przez czytanie chara później ;]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fidel
żul



Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Sob 13:54, 18 Lis 2006    Temat postu:

exeman napisał:
nic nie działa nic nie działa nic nie działa!!!!!!
Fidel: Twoj pseudokod nie dziala :P
nie mozliwe :D
chcoiaz w pseudokodzie brakowalo continue i break i jak tego nie dodales to masz powod :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Sob 14:06, 18 Lis 2006    Temat postu:

jagm napisał:
Skrobocik napisał:
Ja też zawsze scanf robię, ziom ;)
Nawet bez wczytywania końców linii, bo skoro to są liczby, to i tak sobie z tym poradzi.

w tym zadaniu akurat bez wczytywania końca lini mi się sypało. to pewnie przez czytanie chara później ;]

Aaaaaa, no rzeczywiście: jeśli potem zczytuje się chara, to trzeba wczytać ten koniec linii. Zapomniałem jakie było tu wczytywanie, że była literka symbolizująca ścianę ;) Racja, racja...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Sob 14:10, 18 Lis 2006    Temat postu:

Przeszło, dzięki za support :)
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Idź do strony Poprzedni  1, 2, 3, 4
Strona 4 z 4

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin