IPB
> Opss - Optymalizator  
Reply to this topicStart new topic
cezar_1
wyślij 4-04-2006, 21:43
Wpis #1


Fantom


Grupa: AI
Sex: Male


Podajcie sredni czas dzialania dla pojedynczego testu (nie zestawu danych) dla tej paczki: http://radnet.one.pl/~dzwiedziu/download/OPSS/
Go to the top of the page
 
+Quote Post
Corpse Fiend
wyślij 4-04-2006, 22:51
Wpis #2


Odyseusz
*****

Grupa: AI
Sex: Male


Jeszcze nie mam, ale zastanawiam się co będzie lepiej działało - poprawka O(n^3) na O(n^2 logn), czy może zrobienie tego podobnie, co problemu plecakowego (zakresy liczbowe dość małe).
W drugim przypadku trzeba tylko trochę uważać na ujemne liczby, ale to nie jest problem żaden tak naprawdę.

Jak napiszę program, to wrzucę czasy działania tutaj. Noc na szczęście długa jeszcze.
___
Jesu - Tired Of Me

Olać to co pisałem o logarytmicznym czasie, coś mi się powaliło (treść).
___
How Like A Winter - Laying Together Again

Losowo wybrany test:

cfiend@Abomination ~/src/opss/2006kwiecien/a3/debug/src/Testy- OPT $ g++ -o a3 a3.cpp
cfiend@Abomination ~/src/opss/2006kwiecien/a3/debug/src/Testy- OPT $ time ./a3 < opt43.in
NIE
TAK
NIE
NIE
TAK
NIE
NIE
NIE
NIE
NIE

real    0m0.144s
user    0m0.130s
sys     0m0.001s


Z optymalizacjami:

cfiend@Abomination ~/src/opss/2006kwiecien/a3/debug/src/Testy- OPT $ g++ -O2 -static -o a3 a3.cpp
cfiend@Abomination ~/src/opss/2006kwiecien/a3/debug/src/Testy- OPT $ time ./a3 < opt43.in
NIE
TAK
NIE
NIE
TAK
NIE
NIE
NIE
NIE
NIE

real    0m0.068s
user    0m0.053s
sys     0m0.003s


cfiend@Abomination ~/src/opss/2006kwiecien/a3/debug/src/Testy- OPT $ g++ -v

gcc version 3.4.6 (Gentoo 3.4.6, ssp-3.4.5-1.0, pie-8.7.9)


CPU Pentium 4 Prescott 2.8 GHz, więc wynik może nie być miarodajny. No i na sprawdzarce mają gcc-4.0.2.
___
How Like A Winter - The Night, Then Him

Dodatek specjalny:

time ./a3 < opt11.in > /dev/null

real    0m0.233s
user    0m0.198s
sys     0m0.001s

time ./a3 < opt13.in > /dev/null

real    0m0.257s
user    0m0.189s
sys     0m0.005s

time ./a3 < opt16.in > /dev/null

real    0m0.283s
user    0m0.250s
sys     0m0.003s

time ./a3 < opt24.in > /dev/null

real    0m0.287s
user    0m0.263s
sys     0m0.005s

time ./a3 < opt25.in > /dev/null

real    0m0.410s
user    0m0.316s
sys     0m0.025s


Dalej mi się nie chce sprawdzać. Zaraz sobie jakieś swoje testy pogeneruję.
___
How Like A Winter - So Death Would Be Just A Bad Dream
The Sins of Thy Beloved - My Love

Ten wpis był edytowany przez Corpse Fiend: 4-04-2006, 22:52
Go to the top of the page
 
+Quote Post
cezar_1
wyślij 4-04-2006, 23:08
Wpis #3


Fantom


Grupa: AI
Sex: Male


opt11.in - 0.11 s
opt13.in - 0.11 s
opt16.in - 0.16 s
opt24.in - 0.16 s
opt25.in - 0.22 s
Go to the top of the page
 
+Quote Post
Corpse Fiend
wyślij 4-04-2006, 23:09
Wpis #4


Odyseusz
*****

Grupa: AI
Sex: Male


Generator
#include <cstdio>

using namespace std;

const int MAX=500;

int main(void)
{
        int i,j;
        printf("10\n");
        for (i=0;i<10;i++)
        {
                printf("500 -125250\n");
                for (j=1;j<=MAX;j++) printf("-%d ",j); printf("\n");
        }
        return 0;
}


Czasy i odpowiedzi

time ./a3 < gen.in
TAK
TAK
TAK
TAK
TAK
TAK
TAK
TAK
TAK
TAK

real    0m0.911s
user    0m0.820s
sys     0m0.002s


___
The Sins of Thy Beloved - The Kiss


[EDIT]
U mnie wszystkie czasy można teraz liczyć tak 0.10 - 0.15 mniej, bo KDE się skończyło kompilować już i nie zamula. <-:

Ten wpis był edytowany przez Corpse Fiend: 4-04-2006, 23:10
Go to the top of the page
 
+Quote Post
cezar_1
wyślij 4-04-2006, 23:17
Wpis #5


Fantom


Grupa: AI
Sex: Male


mam dla tego testu 0.66 s ;]
Go to the top of the page
 
+Quote Post
qfel
wyślij 5-04-2006, 12:24
Wpis #6


Fantom


Grupa: AI
Sex: Male


(Corpse Fiend @ 04-5-2006, 00:51) *

Jeszcze nie mam, ale zastanawiam się co będzie lepiej działało - poprawka O(n^3) na O(n^2 logn), czy może zrobienie tego podobnie, co problemu plecakowego (zakresy liczbowe dość małe).
W drugim przypadku trzeba tylko trochę uważać na ujemne liczby, ale to nie jest problem żaden tak naprawdę.


n^2 log n? A moglbys mnie poinformowac jak:P?
Ja za rozwiazanie plecakowe dostalem maxa, ale to "lepsze" rozwiazanie mialo w testach z forum czasy 10 x mniejsze.

BTW jakie mieliscie czasy na sprawdzarce? Moje

0 Program zaakceptowany 0.01 / 0.50 2700 / 16384
1 Program zaakceptowany 0.01 / 0.50 2700 / 16384
2 Program zaakceptowany 0.01 / 0.50 2696 / 16384
3 Program zaakceptowany 0.01 / 0.50 2700 / 16384
4 Program zaakceptowany 0.01 / 0.50 2700 / 16384
5 Program zaakceptowany 0.01 / 0.50 2696 / 16384
6 Program zaakceptowany 0.04 / 0.50 2696 / 16384
7 Program zaakceptowany 0.18 / 1.00 2696 / 16384
8 Program zaakceptowany 0.24 / 2.00 2700 / 16384
9 Program zaakceptowany 0.34 / 2.00 2696 / 16384
10 Program zaakceptowany 0.55 / 2.00 2696 / 16384
Go to the top of the page
 
+Quote Post
Corpse Fiend
wyślij 5-04-2006, 22:29
Wpis #7


Odyseusz
*****

Grupa: AI
Sex: Male


0     Program zaakceptowany     0.01 / 0.50     2700 / 16384
1     Program zaakceptowany     0.01 / 0.50     2700 / 16384
2     Błędna odpowiedź     0.01 / 0.50     2696 / 16384
3     Program zaakceptowany     0.01 / 0.50     2696 / 16384
4     Program zaakceptowany     0.01 / 0.50     2700 / 16384
5     Program zaakceptowany     0.01 / 0.50     2696 / 16384
6     Program zaakceptowany     0.06 / 0.50     2696 / 16384
7     Program zaakceptowany     0.24 / 1.00     2696 / 16384
8     Program zaakceptowany     0.33 / 2.00     2696 / 16384
9     Program zaakceptowany     0.30 / 2.00     2696 / 16384
10     Program zaakceptowany     0.62 / 2.00     2696 / 16384


Tak się zastanawiam gdzie błąd miałem. Jakieś sugestie?
___
Jesu - Tired Of Me
Go to the top of the page
 
+Quote Post
qfel
wyślij 6-04-2006, 14:49
Wpis #8


Fantom


Grupa: AI
Sex: Male


(Corpse Fiend @ 04-6-2006, 00:29) *

Tak się zastanawiam gdzie błąd miałem. Jakieś sugestie?


Skad mam wiedziec, jak nawet nie wiem jakim algorytmem..
Sprawdz na testach z forum (http://opss.safo.biz/?menu=forum&sub=forum&subject=4866&comp=6), jesli tego jeszcze nie zrobiles.
Go to the top of the page
 
+Quote Post
Reply to this topicStart new topic
2 Użyszkodników czyta ten temat [2 Gości i 0 anonimowych Użyszkodników]
0 Zarejestrowanych:

 

Wersja Lo-Fi Obecna data i czas: 21-02-2017, 14:32
Skin created by No1 1000 / Sublime Development