STL + kolejka priorytetowa

[Leon]

Czy jest mozliwe, aby w kolejce priorytetowej z STLa, zmieniac wartosci (czyli
przenosic elementy) ktore sa w srodku?

Pozdrawiam

[Witold Kuzminski]

Post by Leon
Czy jest mozliwe, aby w kolejce priorytetowej z STLa, zmieniac wartosci (czyli
przenosic elementy) ktore sa w srodku?

Nie. Prawdopodobnie dlatego, ze nie da sie do nich dobrac :)
Co takiego chcesz zrobic? Pozamnieniac elementy w srodku, zeby
oszukac priority_queue?
Serio: priority_queue mozesz recznie zaimplementowac w jednej linijce,
a operacje w dwu linijkach na operacje. Ciagle nie rozumem po co chcesz
zmieniac cos w srodku...

[k***@et.pl]

Post by Witold Kuzminski
Ciagle nie rozumem po co chcesz
zmieniac cos w srodku...

Dobry przyklad. Zadanie 'samochodziki' z ostatniej olipiady informatycznej :)
Trzeba umozliwic przesuwanie elementow w tablicy, w przeciwnym wypadku zapchamy
kolejke nadmierna iloscia informacji.

Post by Witold Kuzminski
Serio: priority_queue mozesz recznie zaimplementowac w jednej linijce,
a operacje w dwu linijkach na operacje.

A mozesz pokazac jak to zrobic?

Pozdrawiam

[Witold Kuzminski]

Post by k***@et.pl

Post by Witold Kuzminski
Ciagle nie rozumem po co chcesz
zmieniac cos w srodku...

Dobry przyklad. Zadanie 'samochodziki' z ostatniej olipiady informatycznej :)
Trzeba umozliwic przesuwanie elementow w tablicy, w przeciwnym wypadku zapchamy
kolejke nadmierna iloscia informacji.

Hmmm... sam sie nie zalapalem na olimpiade w tym roku. W zeszlym
tez nie :(
Rozumiesz wiec, ze nie calkiem lapie jak te samochodziki mialyby
zapychac kolejke...

Post by k***@et.pl

Post by Witold Kuzminski
Serio: priority_queue mozesz recznie zaimplementowac w jednej linijce,
a operacje w dwu linijkach na operacje.

A mozesz pokazac jak to zrobic?

Yhym:
implementacja: linijka 1: make_heap
pop: linijka 1: pop_heap, linijka 2: pop_back
push: linijka 1: push_back, linijka 2: push_heap

Serio: kolejke mozna implementowac na wiecej niz jeden sposob (tj.
nie koniecznie jako heap).
Moze jak sie czegos chcesz(chcecie) dowiedziec, to pytajcie o sedno
problemu, a nie o to czy w STL priority_queue da sie cos modyfikowac
w srodku...

[Leon]

Post by Witold Kuzminski
Serio: kolejke mozna implementowac na wiecej niz jeden sposob (tj.
nie koniecznie jako heap).
Moze jak sie czegos chcesz(chcecie) dowiedziec, to pytajcie o sedno
problemu, a nie o to czy w STL priority_queue da sie cos modyfikowac
w srodku...

Dobra, wiec spytam prosto :) Jak napisac w C++ (z uzyciem STLa) `cos' co
dzialaniem przypominaloby kolejke priorytetowa, ale z mozliwoscia zmiany
elemenotw w srodku (tj. zmiana wartosci elementu i natychmiastowe jego
przesuniecie). Mam nadzieje, ze zajmie to mniej niz implementacja calkowicie
nowej kolejki (czyli jakies 100 linijek).

P.S. Probowalem zrobic mieszajac queue i heap_sorta, ale po "przesortowaniu" nie
znam indexu elemenetu, wiec nie jestem go w stanie wyciagnac.
Prosze o pomoc :>

Dzieki z gory

[Marek Sieradzki]

Ja zrobiłem samochodziki tak (pewnie tak samo jak wszyscy):
Mam listy, których głowy trzymam w kopcu. Przechodząc drugi raz przez
tablicę samochodzików zwiększam głowy w kopcu (elementy, które zmieniam
mogą mieć tylko większe wartości). Gdy wkładam z półki to dodaję do
kopca wartość z jakiejś listy. Gdy usuwam z półki to usuwam element
kopca. Z tego co wiem nie da się tego zadania zrobić STLowym kopcem bo:
1. trzeba trzymać wystąpienia samochodzików do zwiększania wartości
2. trzeba zwiększać wartości poszczególnych elementów

[Witold Kuzminski]

Post by Leon

Post by Witold Kuzminski
Serio: kolejke mozna implementowac na wiecej niz jeden sposob (tj.
nie koniecznie jako heap).
Moze jak sie czegos chcesz(chcecie) dowiedziec, to pytajcie o sedno
problemu, a nie o to czy w STL priority_queue da sie cos modyfikowac
w srodku...

Dobra, wiec spytam prosto :) Jak napisac w C++ (z uzyciem STLa) `cos' co
dzialaniem przypominaloby kolejke priorytetowa, ale z mozliwoscia zmiany
elemenotw w srodku (tj. zmiana wartosci elementu i natychmiastowe jego
przesuniecie). Mam nadzieje, ze zajmie to mniej niz implementacja calkowicie
nowej kolejki (czyli jakies 100 linijek).
P.S. Probowalem zrobic mieszajac queue i heap_sorta, ale po "przesortowaniu" nie
znam indexu elemenetu, wiec nie jestem go w stanie wyciagnac.
Prosze o pomoc :>

Gdyby nie ta ostatnia uwaga, to chyba bym rozumial o co chodzi...
Poniewaz nie rozumiem, po co ci znac index elementu, ryzykuje, ze
odpowiadam nie na to pytanie co trzeba, tj. zakladam, ze "natychmastowe
przesuniecie" znaczy przesuniecie na wlasiwe miejsce w kolejce.
Poczytaj o strukturze danych heap (sterta). To cos co swietnie sie
nadaje do kolejek priorytetowych. Heap to pelne drzewo binarne, o
dodatkowej wlasnosci takiej, ze kazdy "node" jest wiekszy od swoich
potomkow.
Takie cos pieknie sie da wsadzic do "liniowej" struktury danych jak
np. std::vector, albo dowolnej innej, ktora implementuje iteratory
o dowolnym dostepie (random access iterators) jak np. std::deque.
Operacje na takiej strukturze sa trywialne, bo jak se narysujesz takie
pelne drzewo i wsadzisz je do (np) vector'a to zauwazysz, ze potomkowie
danego node siedza na 2n i 2n+1, jesli n to index danego nodu.
Jest tu maly twist w C/C++, bo to dziala dla indexow liczonych od jeden,
ale jesli to wiesz, to "skompensowanie" jest trywialne.
Czyli, gdy masz "gola" strukture danych, ktora byla heap i nagle zmienisz
w niej priorytet elementu "w srodku" to juz nie masz heap...
Mozesz albo od nowa zawolac make_heap z biblioteki, albo dlubac recznie,
zamieniajac element o nowym priorytecie z potomkami tak dlugo az znowu
bedziesz mial heap. O ile dlubanie reczne nie jest zwykle zalecane, to
w tym wypadku jest trywialne. Ciagle do celow olimpijskich make_heap ma
chyba te zalete, ze napewno dziala i zajmuje 1 linijke.

OK, teraz powiedz czy o to chodzilo, czy o cos innego...

[Witold Kuzminski]

Post by Witold Kuzminski
zamieniajac element o nowym priorytecie z potomkami tak dlugo az znowu
bedziesz mial heap.

Oczywiscie mialo byc:
zamieniajac element o nowym priorytecie z potomkami/rodzicem(ami)
az znowu bedziesz mial heap.

[k***@et.pl]

Ogolnie, chodzi mi to ze..w niektorych zadaniach (jak np samochodziki z OI)
sytuacja wygladala nastepujaco (wbrew pozorom ta sytuacja w zadaniach zdarza sie
dosc czesto).
Mam sobie kolejke priorytetowa ktora trzyma struktury :>
zalozmy
struct x_t { int a,b; };

Na kolejce wszystko jest sortowane w/g zmiennej `a'. I teraz, chce wrzucic
kolejna strukture, ale takie, ze dane "b" juz wystepuje. Wiec pamietam index do
miejsca w kolejce gdzie wystepuje dane 'b', a nastepnie podmieniam tam 'a' i
przesuwam sobie zgodnie z wytycznymi kolejki :) Jesli bym dorzucil do kolejki to
po krotkim czasie zawalilaby sie ona niepotrzebnymi smieciami...i w koncu
doprowadzila do SEGFAUTA.

Rozumiem co chciales mi przekazac, mam tylko jeden problem. Gdy wrzuce juz do
kontenera (wektora, kolejki, listy etc). i posortuje to make_heap'em to ZGUBIE
index mojej strukturki, i przez to nie bede wiedzial gdzie wystepuje moja
zmienna `b'.

Mam nadzieje ze zrozumiales o co chodzi :)
Pozdrawiam

[Witold Kuzminski]

Post by k***@et.pl
Ogolnie, chodzi mi to ze..w niektorych zadaniach (jak np samochodziki z OI)

OK, nie wytrzymalem: to te samochodziki?
http://www.oi.edu.pl/php/show.php?ac=p100000&module=show&file=zadania/oi12/sam

Post by k***@et.pl
sytuacja wygladala nastepujaco (wbrew pozorom ta sytuacja w
zadaniach zdarza sie dosc czesto).
Mam sobie kolejke priorytetowa ktora trzyma struktury :>
zalozmy
struct x_t { int a,b; };

[...]

Post by k***@et.pl
Mam nadzieje ze zrozumiales o co chodzi :)

Przykro mi ale ni konia... :(
Ni w zab nie rozumiem o czym mowi Marek S. ani o jakich kolejkach
priorytetowych mowisz ty...:(

Pewnie czegos w tych samochodzikach nie kumam, ale wedlug mnie
zadanie to sprowadza sie do tego, ktory samochod ma usunac z
podlogi mama.
Jesli to jest problem, to pomyslalem, ze mama powinna odstawiac
na polke ten samochodzik, ktorym maly Zdzisio bedzie sie bawil
najpozniej...
Jesliby przypadkiem to bylo poprawne rozwiazanie zadania
samochodziki, to ni kota nie widze tu kopcy list Marka (albo jakos
podobnie: moglem cos pokrecic) ani twojej kolejki priorytetowej.
Gdyby to bylo rozwiazanie, to da sie ono prawie doslownie z opisu
wyzej przelozyc na C++. To pare wywolan algorytmow z biblioteki...
Moze np. cos takiego:

#include <vector>
#include <iterator>
#include <iostream>
using namespace std;
//-----------------------------------------------------------------------------
struct sam {
explicit sam(int n, int p=0): n_(n), p_(p) {}
bool operator<(sam const & rhs) const { return p_ < rhs.p_; }
bool operator==(sam const& rhs) const {
return rhs.n_ == 0 ? p_ == rhs.p_ : n_ == rhs.n_ ; }
int n_, p_;
};
struct sam_generator {
sam_generator(): last_n_(0) {}
sam operator()() { return sam(++last_n_); }
int last_n_;
};
//-----------------------------------------------------------------------------
typedef vector<int> s_seq;
typedef vector<int>::const_iterator s_seq_iter;
typedef vector<sam> pool;
struct played_in {
played_in(s_seq_iter s, s_seq_iter e): st_i_(s), en_i_(e) {}
void operator()(sam& s) {
s.p_ = distance(st_i_, find(st_i_+1, en_i_, s.n_)); }
s_seq_iter st_i_, en_i_;
};
//-----------------------------------------------------------------------------
int main() {
int n, k, p;
cin >> n >> k >> p;
pool sams;
s_seq seq;

generate_n(back_inserter<pool>(sams), n, sam_generator());
copy(istream_iterator<int>(cin), istream_iterator<int>(),
back_inserter<s_seq>(seq));
s_seq_iter bi = seq.begin(), be = seq.end();
int cnt = 0;
for(; bi != be; ++bi) {
if(find(sams.begin(), sams.end(), sam(*bi))->p_ == 0) {
if(count(sams.begin(), sams.end(), sam(0)) <= n - k) {
partition(sams.begin(), sams.end(),
not1(bind2nd(equal_to<sam>(), sam(0))));
for_each(sams.begin(), sams.begin() + k, played_in(bi, be));
max_element(sams.begin(), sams.end())->p_ = 0;
}
find(sams.begin(), sams.end(), sam(*bi))->p_ = k;
++cnt;
}
}
cout << cnt << endl;
}

[Marek Sieradzki]

Zaraz spróbuję skompilować twoje i przetestować nieco, a to jest moje
rozwiązanie:

#include <cstdio>
#include <list>

using namespace std;

const int MIN = 1 << 31;
const int MAXN = 100000;
const int MAXK = 100000;
const int MAXP = 500000;
const int MAX = 1000000;

inline int parent(int i) { return i / 2; }
inline int left(int i) { return 2 * i; }
inline int right(int i) { return 2 * i + 1; }

struct Para
{
int s;
int o;
Para(int a, int b) : s(a), o(b){}
Para(){ Para(0,0); }
};

struct Kopiec //wiekszosc z wprowadzenia do algorytmow
{
int length;
int size;
int *wystapienia;
Para *t;
Kopiec(int rozmiar) : length(rozmiar), size(0){t = new
Para[rozmiar+1]; wystapienia = new int[MAXN+1];}
Kopiec() : length(MAXK), size(0){t = new Para[MAXK+1]; wystapienia
= new int[MAXN+1]; }
~Kopiec(){ delete[] t; delete[] wystapienia; }
inline void swap(int a, int b)
{
wystapienia[t[a].s] = b;
wystapienia[t[b].s] = a;
Para temp = t[a]; t[a] = t[b]; t[b] = temp;
}
void maxHeapify(int i)
{
int largest;
int l = left(i);
int r = right(i);
if(l <= size && t[l].o > t[i].o)
largest = l;
else
largest = i;
if(r <= size && t[r].o > t[largest].o)
largest = r;
if(largest != i)
{
swap(i,largest);
maxHeapify(largest);
}
}
Para maximum()
{
return t[1];
}
Para extractMax()
{
if(size < 1)
{
printf("PUSTY KOPIEC\n");
return Para(0,0);
}
wystapienia[t[1].s] = 0;
Para max = t[1];
t[1] = t[size];
size--;
maxHeapify(1);
return max;
}
void increaseKey(int i, int key)
{
if(key < t[i].o)
printf("MNIEJSZY KLUCZ\n");//bzdura
t[i].o = key;
while(i > 1 && t[parent(i)].o < t[i].o)
{
swap(i,parent(i));
i = parent(i);
}
}
void insert(Para key)
{
size++;
wystapienia[key.s] = size;
t[size].o = MIN;
t[size].s = key.s;
increaseKey(size,key.o);
}
};

struct Polka
{
int ilosc;
int *s;
Polka(int p) : ilosc(1){ s = new int[p+1]; }
~Polka(){ delete[] s; }
inline void dodaj(int samochodzik)
{
s[ilosc++] = samochodzik;
}
};

struct Podloga
{
private:
int ilosc;
int max;
bool *pod;
list<int> *lista;
inline void pop()
{
Para a = kolejka.extractMax();
#ifdef DEBUG
printf("Zabieram %d ",a.s);
#endif
pod[a.s] = false;
}
public:
Kopiec kolejka;
int zdjete;
Podloga(int n, int k) : ilosc(0), max(k), zdjete(0)
{
pod = new bool[n+1];
lista = new list<int>[n+1];
}
~Podloga(){ delete[] pod; delete[] lista;}
inline void push(int s)
{
lista[s].pop_front();
if(pod[s] == false)
{
if(ilosc < max)
{
if(lista[s].empty())
kolejka.insert(Para(s,MAX));
else
kolejka.insert(Para(s,lista[s].front()));
#ifdef DEBUG
printf("Klade %d\n",s);
#endif
pod[s] = true;
ilosc++;
zdjete++;
}
else
{
pop();
#ifdef DEBUG
printf("i klade %d\n",s);
#endif
if(lista[s].empty())
kolejka.insert(Para(s,MAX));
else
kolejka.insert(Para(s,lista[s].front()));
pod[s] = true;
zdjete++;
}
}
else
{
if(!lista[s].empty())

kolejka.increaseKey(kolejka.wystapienia[s],lista[s].front());
else
kolejka.increaseKey(kolejka.wystapienia[s],MAX);
#ifdef DEBUG
printf("Samochod %d jest juz na podlodze\n",s);
#endif
}
}
inline void dodaj(int samochodzik, int i)
{
lista[samochodzik].push_back(i);
}
};

int n,k,p;
int a;
Polka *polka;
Podloga *podloga;
// n laczna liczba samochodzikow
// k ile na podlodze
// p dlugosc ciagu

int main()
{
scanf("%d %d %d",&n,&k,&p);
polka = new Polka(p);
podloga = new Podloga(n,k);
for(int i = 1; i <= p; i++)
{
scanf("%d",&a);
polka->dodaj(a);
podloga->dodaj(a,i);
}
for(int i = 1; i <= p; i++)
podloga->push(polka->s[i]);
printf("%d\n",podloga->zdjete);
return 0;
}

[Witold Kuzminski]

Post by Marek Sieradzki
Zaraz spróbuję skompilować twoje i przetestować nieco, a to jest moje

[...]

Jak tam testy?
Ja przetestowalem twoje rowiazanie...
Wygeneruj dane tym:
#include <iostream>

int main(int argc, char *argv[]) {
if(argc != 4) {
std::cerr << "n k p ?\n";
return 1;
}
int n = atoi(argv[1]);
int k = atoi(argv[2]);
int p = atoi(argv[3]);
std::cout << n << ' ' << k << ' ' << p << '\n';

srand(100);
for(int i = 0; i < p; ++i) {
int s = (rand() % n) + 1;
std::cout << s << '\n';
if(s < 1 || s > n) abort(); // :)
}
}

tak, ze n,k,p sa 1000 500 50000 (odpowiednio),
czyli np: generuj 1000 500 50000
Potem pusc swoj program, ciekawe co dostaniesz...

BTW: stale w rand mozesz miec inne niz ja; ja to
puscilem pod gcc 3.3.2

[Marek Sieradzki]

Nie patrzyłem dokładnie co robisz, ale domyślam się, że usuwasz
najdalszy samochodzik (ten którego wystąpienie jest najdalej). Bez kopca
się nie da wydajnie rozwiązać tego zadania, bo złożoność będzie O(n^2).
Z kopcem będzie dokładnie O(p*log(k)). Twoje rozwiązanie praktycznie
zacina się przy piątym teście z maksymalnymi danymi.

[Witold Kuzminski]

Post by Marek Sieradzki
Nie patrzyłem dokładnie co robisz, ale domyślam się, że usuwasz
najdalszy samochodzik (ten którego wystąpienie jest najdalej). Bez kopca
się nie da wydajnie rozwiązać tego zadania, bo złożoność będzie O(n^2).
Z kopcem będzie dokładnie O(p*log(k)). Twoje rozwiązanie praktycznie
zacina się przy piątym teście z maksymalnymi danymi.

Moglbys to troche rozwinac?
Co to znaczy zacina sie?

[Marek Sieradzki]

Przy maksymalnym teście 500000 samochodzików działa co najmniej
kilkanaście razy wolniej od mojego programu. Co najmniej bo nie chciało
mi się tyle czasu czekać.

[Witold Kuzminski]

Post by Marek Sieradzki
Przy maksymalnym teście 500000 samochodzików działa co najmniej
kilkanaście razy wolniej od mojego programu. Co najmniej bo nie chciało
mi się tyle czasu czekać.

Nie calkiem rozumiem jak twoja ochota do czekania ma sie tu do rzeczy?
Czy w tresci zadania widziesz wymaganie co do tego jak szybko trzeba
sie doczekac na wynik? Cos o zlozonosci algorytmu albo takie tam jakies?
Ja nie widze.
Przetestuj swoj program z danymi z innego postu tutaj.
Gdyby twoj program chodzil 100 milionow razy szybciej od mojego,
to i tak nie ma to znaczenia w wypadku kiedy jego chodzenie to
strata energii elektrycznej.
Przyznaje, ze na temat poswiecilem godzine i teraz 10 minut na testy.
Moze cos tam przoczylem, albo jakies tam.
Na pewno te dwa programy daja rozne wyniki i twoj zamiast tego co
trzeba pisac na wyjscie pisze cos o mniejszym kluczu.

Wyglada, ze puszczanie twojego programu to degradacja srodowiska
naturalnego. Wydaje sie, ze twoj program jest niepoprawny wiec
dywagacje o tym ile razy jest szybszy od programu poprawnego (poki
co wydaje sie, ze moj jest poprawny) to strata czasu.

[Marek Sieradzki]

Jesteś bardzo pewny siebie. Napisałeś kod, który korzysta z niewydajnego
w takich przypadkach cout/cin. Złożoność masz pewnie O(n^2). Podaj mi
test na którym mój program mówi o mniejszym kluczu.

[Witold Kuzminski]

Post by Marek Sieradzki
Jesteś bardzo pewny siebie.

Eee tam. Zauwaz, ze wszystko o wlasnym rozwiazaniu pisze w trybie
warunkowym: jesli..., narazie wyglada... i.t.p.

Post by Marek Sieradzki
Napisałeś kod, który korzysta z niewydajnego
w takich przypadkach cout/cin.

O cie felek. Moj kod korzysta z niewydajnego cin/cout?
Niewydajnego w porownaniu z asemblerem? Moze i niewydajnego,
ale zczytuje dane w dwu linijkach. Do tego spie spokojnie,
bo sam tego (copy i innych istream_iteratorow) nie pisalem,
wiec raczej to dziala.
BTW: widziales gdzies w zadaniu jakies wymogi co do wydajnosci?

Post by Marek Sieradzki
Złożoność masz pewnie O(n^2).

Znowu... Co cie ugryzlo z ta wydajnoscia. Poszukaj w google
moich innych postow na temat wydajnych programistow. Ostatnio
chyba pomsowalem w watku "cos szybszego niz vector" :)

Post by Marek Sieradzki
Podaj mi
test na którym mój program mówi o mniejszym kluczu.

Juz ci podalem. W odpowiedzi na twoj post, gdzie podales
wlasny kod.
Twoj program nie tylko pisze o kluczu, ale daje inne wyniki
i albo pisze albo nie o kluczu w zaleznosci od tego czy go
skompilowac z, czy bez -O3 (gcc 3.3.2). Oczywiscie zawsze istnieje
szansa, ze mam zepsuty kompilator, ale moj program przynajmniej
zawsze daje ten sam wynik.

[Marek Sieradzki]

Post by Witold Kuzminski
O cie felek. Moj kod korzysta z niewydajnego cin/cout?
Niewydajnego w porownaniu z asemblerem? Moze i niewydajnego,
ale zczytuje dane w dwu linijkach. Do tego spie spokojnie,
bo sam tego (copy i innych istream_iteratorow) nie pisalem,
wiec raczej to dziala.
BTW: widziales gdzies w zadaniu jakies wymogi co do wydajnosci?

Wymóg: zdążyć przetworzyć maksymalne dane w kilka sekund. Góra 10.

Post by Witold Kuzminski

Post by Marek Sieradzki
Złożoność masz pewnie O(n^2).

Znowu... Co cie ugryzlo z ta wydajnoscia. Poszukaj w google
moich innych postow na temat wydajnych programistow. Ostatnio
chyba pomsowalem w watku "cos szybszego niz vector" :)

Nie wiem co tam pisałeś, ale wydaje się jakbyś nie znał pojęcia
złożoności obliczeniowej.

Post by Witold Kuzminski
Juz ci podalem. W odpowiedzi na twoj post, gdzie podales
wlasny kod.
Twoj program nie tylko pisze o kluczu, ale daje inne wyniki
i albo pisze albo nie o kluczu w zaleznosci od tego czy go
skompilowac z, czy bez -O3 (gcc 3.3.2). Oczywiscie zawsze istnieje
szansa, ze mam zepsuty kompilator, ale moj program przynajmniej
zawsze daje ten sam wynik.

Mi działa idealnie na twoim generatorze.

[Witold Kuzminski]

Post by Marek Sieradzki

Post by Witold Kuzminski
O cie felek. Moj kod korzysta z niewydajnego cin/cout?
Niewydajnego w porownaniu z asemblerem? Moze i niewydajnego,
ale zczytuje dane w dwu linijkach. Do tego spie spokojnie,
bo sam tego (copy i innych istream_iteratorow) nie pisalem,
wiec raczej to dziala.
BTW: widziales gdzies w zadaniu jakies wymogi co do wydajnosci?

Wymóg: zdążyć przetworzyć maksymalne dane w kilka sekund. Góra 10.

Przeczytalem zadanie z tego linku, ktory zamiescilem wczesniej
i nic takiego nie znalazlem.
Takie cos samo w sobie nic nie znaczy (jest smieszne).

Post by Marek Sieradzki

Post by Witold Kuzminski

Post by Marek Sieradzki
Złożoność masz pewnie O(n^2).

Znowu... Co cie ugryzlo z ta wydajnoscia. Poszukaj w google
moich innych postow na temat wydajnych programistow. Ostatnio
chyba pomsowalem w watku "cos szybszego niz vector" :)

Nie wiem co tam pisałeś, ale wydaje się jakbyś nie znał pojęcia
złożoności obliczeniowej.

Po czym to poznales?

Post by Marek Sieradzki

Post by Witold Kuzminski
Juz ci podalem. W odpowiedzi na twoj post, gdzie podales
wlasny kod.
Twoj program nie tylko pisze o kluczu, ale daje inne wyniki
i albo pisze albo nie o kluczu w zaleznosci od tego czy go
skompilowac z, czy bez -O3 (gcc 3.3.2). Oczywiscie zawsze istnieje
szansa, ze mam zepsuty kompilator, ale moj program przynajmniej
zawsze daje ten sam wynik.

Mi działa idealnie na twoim generatorze.

Zobacz jak mi dziala:odin:/home/dmg/wkuzmins/work/tmp/sam>uname -a
HP-UX odin B.11.00 U 9000/899 1669432301 unlimited-user license

odin:/home/dmg/wkuzmins/work/tmp/sam>mkdat 100 50 5000 > idat5000
odin:/home/dmg/wkuzmins/work/tmp/sam>g++ ms.cpp -o ms
odin:/home/dmg/wkuzmins/work/tmp/sam>ms < idat5000
1079
odin:/home/dmg/wkuzmins/work/tmp/sam>g++ -O3 ms.cpp -o ms
odin:/home/dmg/wkuzmins/work/tmp/sam>ms < idat5000
MNIEJSZY KLUCZ

[ ze sto razy to samo]

MNIEJSZY KLUCZ
MNIEJSZY KLUCZ
983
odin:/home/dmg/wkuzmins/work/tmp/sam>g++ -v
Reading specs from /usr/local/lib/gcc-lib/hppa2.0n-hp-hpux11.00/3.3.2/specs
Configured with: ./configure [blah, blah, blah]
gcc version 3.3.2


Moze mam zepsuty kompilator (niewykluczone, gcc na HPUX nie ma dobrej opinii).
Pisze tylko to, co widze...

Inny kompilator (HP aCC) daje te same wyniki bez wzgledu na opcje, ale zobacz
co mowi purify:

odin:/home/dmg/wkuzmins/work/tmp/sam>aCC -V
aCC: HP ANSI C++ B3910B A.03.31
odin:/home/dmg/wkuzmins/work/tmp/sam>purify aCC msa.cpp -o msa
Purify 2003a.06.13 FixPack 0155 040723 HP-UX (32-bit) (c) Copyright IBM Corp.
1992, 2004 All rights reserved.
Instrumenting: msa.o Linking
odin:/home/dmg/wkuzmins/work/tmp/sam>msa < idat5000
1079

Tu masz rozwiniete komentarze od purify:


Finished msa ( 100 errors, 0 leaked bytes)
Purify instrumented msa (pid 8531 at Wed Dec 1 15:32:48 2004)
UMR: Uninitialized memory read (100 times)
This is occurring while in:
Podloga::push(int) [msa.cpp:141]
if(ilosc < max)
{
if(lista[s].empty())
=> kolejka.insert(Para(s,MAX));
else
kolejka.insert(Para(s,lista[s].front()));
#ifdef DEBUG
main [msa.cpp:204]
podloga->dodaj(a,i);
}
for(i = 1; i <= p; i++)
=> podloga->push(polka->s[i]);
printf("%d\n",podloga->zdjete);
return 0;
}
_start [libc.2]
$START$ [crt0.o]
$START$ [crt0.o]
Reading 1 byte from 0x4015355f in the heap.
Address 0x4015355f is 63 bytes into a malloc'd block at 0x40153520 of 101
bytes.
This block was allocated from:
malloc [rtlib.o]
__nWa__FuL [libCsup.2]
operator new[](unsigned long) [rtlib.o]
Podloga::Podloga(int,int)%2 [msa.cpp:131]
{
pod = new bool[n+1];
lista = new list<int>[n+1];
=> }
~Podloga(){ delete[] pod; delete[] lista;}
inline void push(int s)
{
main [msa.cpp:195]
{
scanf("%d %d %d",&n,&k,&p);
polka = new Polka(p);
=> podloga = new Podloga(n,k);
int i;
for(i = 1; i <= p; i++)
{
_start [libc.2]
Current file descriptors in use: 5
Memory leaked: 0 bytes (0%); potentially leaked: 804468 bytes (51.9%)
Program exited with status code 0.


O ile aCC jest raczej archaiczny, to napewno bardziej "stabilny" niz gcc
na HP-UX; ciagle purify nie myli sie zbyt czesto...

[Marek Sieradzki]

Ja swój kod dosyć intensywnie testowałem na x86. g++ 3.3.5. Możliwe, że
gdzieś mam niezainicjalizowaną pamięć (ten nieszczęsny wskaźnik na
listy). Na moim K6-2 działa dobrze, na Systemie Internetowym Olimpiady
też, na komputerze kolegi tak samo. Oczywiście komunikat MNIEJSZY KLUCZ
oznacza, że mój program chce zrobić coś idiotycznego co nie powinno się
zdarzyć. Może wiesz co to złożoność obliczeniowa, ale zupełnie
ignorujesz jej znaczenie. To że w zadaniu nie ma konkretnie podanego
limitu czasowego nie znaczy, że go nie ma. Na www.oi.edu.pl jest to
dokładnie wyjaśnione. Próbowałeś ten test, który podałem ci do
ściągnięcia? Wiele osób ma ten wynik. Co do poprawności ich rozwiązań:
jestem pewien, że tyle osób musi mieć to dobrze.

[Witold Kuzminski]

Post by Marek Sieradzki
Ja swój kod dosyć intensywnie testowałem na x86. g++ 3.3.5. Możliwe, że
gdzieś mam niezainicjalizowaną pamięć (ten nieszczęsny wskaźnik na
listy). Na moim K6-2 działa dobrze, na Systemie Internetowym Olimpiady
też, na komputerze kolegi tak samo.

Nic dziwnego. To chyba wszystko takie same komputery. Zatem mimo tego,
ze wyraznie dziala przypadkiem, to gdy dziala na jednym, to pewnie
bedzie dzialal na drugim i trzecim takim samym.

Post by Marek Sieradzki
Oczywiście komunikat MNIEJSZY KLUCZ
oznacza, że mój program chce zrobić coś idiotycznego co nie powinno się
zdarzyć.

A jednak...

Post by Marek Sieradzki
Może wiesz co to złożoność obliczeniowa, ale zupełnie

Moze wiem, a moze nie. Jak do tej pory jest o tym malo danych, a ty
juz zdazyles zajac obie pozycje :)

Post by Marek Sieradzki
ignorujesz jej znaczenie.

Gdy mam do rozwiazania zadanie, ktore nie naklada wymagan na zlozonosc
obliczeniowa, to faktycznie nie zawracam nia sobie glowy.

Post by Marek Sieradzki
To że w zadaniu nie ma konkretnie podanego
limitu czasowego nie znaczy, że go nie ma. Na www.oi.edu.pl jest to
dokładnie wyjaśnione.

Tu nie jest olimpiada. Wzialem tresc zadania jak jest, nie wertujac
stron olimpiady. Chodzilo w sumie o to jak oszukac priority_queue,
pamietasz? (oczywiscie zartuje)
Kod, ktory podalem to rozwiazanie samochodzikow w dziesieciu linijkach,
ktore dodatkowo sa prawie doslownym tlumaczceniem rozwiazania w jezyku
naturalnym na C++. To jest piekno tego rozwiazania. Wyglada ono tak:
gdy nastepny samochodzik Jasia jest na polce (p_==0) i gdy nie ma
miejsca (count) to posprzatac na podlodze (partition), wybrac jeden
z podlogi do odstawienia na polke (for_each) i go odstawic (p_=0),
a ten z polki na podloge(p_=k); else nic. Piekno tego kodu to nie
tylko to, ze jest doslownym tlumaczeniem, ale dodatkowo to, ze z
moich wlasnych konstrukcji wystepuje tam petla for oraz instrukcja if.
Wiecej chyba nic, wiec malo co sie moze popsuc.
Ty prawdopodobnie dostrzezesz piekno takich rozwiazan gdy i jesli
bedziesz robil rzeczy troche wieksze niz samochodziki Jasia :)
Rozumiesz wiec, ze twoj wyskok z tym szkaradztwem nie specjalnie
mi zaimponowal :) Uwierz mi, goscie ktorzy zrobia samochodziki Jasia
szybciej od ciebie, sa po dziesiec centow za tuzin. Siebie nie licze :)
Ludzi, ktorzy potrafia pisac kod, ktory __dziala__ jest znacznie mniej.
Pozwole sobie zasugerowac, ze koncentracja na tej "cesze" kodu
moze byc bardziej owocna. Na poczatek warto pisac jak najmniej wlasnego
kodu. Wtedy ma sie mnuiejsze szanse na "nieszczesny wskaznik" :)

Post by Marek Sieradzki
Próbowałeś ten test, który podałem ci do
jestem pewien, że tyle osób musi mieć to dobrze.

Nie probowalem. Olimpiada chyba sie juz skonczyla...

W sumie gdyby OP chcial, to moze korzystac z "kopca STL" i dlubac
w nim recznie. W bibliotece (jak juz wspomnialem) sa make_heap, pop_heap
i push_heap. Jak cos sie knuje w srodku recznie to mozna trywialnie samemu
move'nac up albo down (jak zgrabnie nazwal to Sedgewick). W koncu te
algorytmy chodza na "golym" kontenerze.

[Marek Sieradzki]

Post by Witold Kuzminski

Post by Marek Sieradzki
Ja swój kod dosyć intensywnie testowałem na x86. g++ 3.3.5. Możliwe, że
gdzieś mam niezainicjalizowaną pamięć (ten nieszczęsny wskaźnik na
listy). Na moim K6-2 działa dobrze, na Systemie Internetowym Olimpiady
też, na komputerze kolegi tak samo.

Nic dziwnego. To chyba wszystko takie same komputery. Zatem mimo tego,
ze wyraznie dziala przypadkiem, to gdy dziala na jednym, to pewnie
bedzie dzialal na drugim i trzecim takim samym.

Wiem

Post by Witold Kuzminski

Post by Marek Sieradzki
Oczywiście komunikat MNIEJSZY KLUCZ
oznacza, że mój program chce zrobić coś idiotycznego co nie powinno się
zdarzyć.

A jednak...

Nie da się wszystkiego przewidzieć. :)

Post by Witold Kuzminski

Post by Marek Sieradzki
Może wiesz co to złożoność obliczeniowa, ale zupełnie

Moze wiem, a moze nie. Jak do tej pory jest o tym malo danych, a ty
juz zdazyles zajac obie pozycje :)

Post by Marek Sieradzki
ignorujesz jej znaczenie.

Gdy mam do rozwiazania zadanie, ktore nie naklada wymagan na zlozonosc
obliczeniowa, to faktycznie nie zawracam nia sobie glowy.

Mi się wydawało, że te zadania wymaga określonej złożoności tzn.
mniejszej niż O(n^2).

Post by Witold Kuzminski

Post by Marek Sieradzki
To że w zadaniu nie ma konkretnie podanego
limitu czasowego nie znaczy, że go nie ma. Na www.oi.edu.pl jest to
dokładnie wyjaśnione.

Tu nie jest olimpiada. Wzialem tresc zadania jak jest, nie wertujac
stron olimpiady. Chodzilo w sumie o to jak oszukac priority_queue,
pamietasz? (oczywiscie zartuje)
Kod, ktory podalem to rozwiazanie samochodzikow w dziesieciu linijkach,
ktore dodatkowo sa prawie doslownym tlumaczceniem rozwiazania w jezyku
gdy nastepny samochodzik Jasia jest na polce (p_==0) i gdy nie ma
miejsca (count) to posprzatac na podlodze (partition), wybrac jeden
z podlogi do odstawienia na polke (for_each) i go odstawic (p_=0),
a ten z polki na podloge(p_=k); else nic. Piekno tego kodu to nie
tylko to, ze jest doslownym tlumaczeniem, ale dodatkowo to, ze z
moich wlasnych konstrukcji wystepuje tam petla for oraz instrukcja if.
Wiecej chyba nic, wiec malo co sie moze popsuc.
Ty prawdopodobnie dostrzezesz piekno takich rozwiazan gdy i jesli
bedziesz robil rzeczy troche wieksze niz samochodziki Jasia :)
Rozumiesz wiec, ze twoj wyskok z tym szkaradztwem nie specjalnie
mi zaimponowal :) Uwierz mi, goscie ktorzy zrobia samochodziki Jasia
szybciej od ciebie, sa po dziesiec centow za tuzin. Siebie nie licze :)
Ludzi, ktorzy potrafia pisac kod, ktory __dziala__ jest znacznie mniej.
Pozwole sobie zasugerowac, ze koncentracja na tej "cesze" kodu
moze byc bardziej owocna. Na poczatek warto pisac jak najmniej wlasnego
kodu. Wtedy ma sie mnuiejsze szanse na "nieszczesny wskaznik" :)

Ten mój kod był pisany na dzień przed terminem wysłania zadań. Teraz nie
chce mi się go poprawiać ani szukać w nim błędów. :) Oczywiście bardzo
łatwo zapisać te zadanie w "naturalny" sposób, z tym, że taka złożoność
dyskwalifikuje takie rozwiązanie.
Co do pisania tak, żeby najmniej było w tym własnego niepewnego kodu. OI
uczy, że warto wiedzieć jak działa lista w STLu. Jest zadanie, w którym
lista STLowa zajmie za dużo pamięci, a napisana samemu (ew. ext/slist)
zmieści się w limicie. Najciekawsze jest to, że ta lista jest i tak
niepotrzebna, bo jest jeszcze lepsze rozwiązanie.
Co do błedu w moim kodzie. Dosyć starannie go przeglądałem i nie
znalazłem żadnych błędów. Z tego co pamiętam to dobrze przetestowałem
kopiec. Z resztą jedynie popróbowałem całość programu na dużych testach.
Wyniki były dobre. Przy okazji, wyraźnie widać w moim kodzie, że na siłę
chciałem za dużo podzielić na klasy. Skutek jest widoczny od razu.

Post by Witold Kuzminski

Post by Marek Sieradzki
Próbowałeś ten test, który podałem ci do
jestem pewien, że tyle osób musi mieć to dobrze.

Nie probowalem. Olimpiada chyba sie juz skonczyla...

Czyżby twój program działał za wolno? :D;)

Post by Witold Kuzminski
W sumie gdyby OP chcial, to moze korzystac z "kopca STL" i dlubac
w nim recznie. W bibliotece (jak juz wspomnialem) sa make_heap, pop_heap
i push_heap. Jak cos sie knuje w srodku recznie to mozna trywialnie samemu
move'nac up albo down (jak zgrabnie nazwal to Sedgewick). W koncu te
algorytmy chodza na "golym" kontenerze.

Niby tak, ale muszę wiedzieć co mam zamieniać do góry. Kopiec sam sobie
pozmienia elementy, a ja tylko wiem, że mam zmienić element samochodzika
n. Może on być wszędzie. Żeby dostać tę informacje muszę sam napisać
kopiec. (tablica z wystąpieniami wykorzystywana przy funkcji swap).
Chyba że w STL mogę zrobić priority_queue, który wykorzystywałby moją
funkcję swap.

[Witold Kuzminski]

[...]

Post by Marek Sieradzki

Post by Witold Kuzminski

Post by Marek Sieradzki
Oczywiście komunikat MNIEJSZY KLUCZ
oznacza, że mój program chce zrobić coś idiotycznego co nie powinno się
zdarzyć.

A jednak...

Nie da się wszystkiego przewidzieć. :)

Trzeba pisac tak, zeby jak najmniej zostawic na przewidywania.

Post by Marek Sieradzki

Post by Witold Kuzminski

Post by Marek Sieradzki
Może wiesz co to złożoność obliczeniowa, ale zupełnie

Moze wiem, a moze nie. Jak do tej pory jest o tym malo danych, a ty
juz zdazyles zajac obie pozycje :)

Post by Marek Sieradzki
ignorujesz jej znaczenie.

Gdy mam do rozwiazania zadanie, ktore nie naklada wymagan na zlozonosc
obliczeniowa, to faktycznie nie zawracam nia sobie glowy.

Mi się wydawało, że te zadania wymaga określonej złożoności tzn.
mniejszej niż O(n^2).

Na olimpiadzie prawdopodobnie.

[...]

Post by Marek Sieradzki

Post by Witold Kuzminski

Post by Marek Sieradzki
Próbowałeś ten test, który podałem ci do
jestem pewien, że tyle osób musi mieć to dobrze.

Nie probowalem. Olimpiada chyba sie juz skonczyla...

Czyżby twój program działał za wolno? :D;)

Ach ta dzisiejsza mlodziez... (patrz nizej).

Post by Marek Sieradzki

Post by Witold Kuzminski
W sumie gdyby OP chcial, to moze korzystac z "kopca STL" i dlubac
w nim recznie. W bibliotece (jak juz wspomnialem) sa make_heap, pop_heap
i push_heap. Jak cos sie knuje w srodku recznie to mozna trywialnie samemu
move'nac up albo down (jak zgrabnie nazwal to Sedgewick). W koncu te
algorytmy chodza na "golym" kontenerze.

Niby tak, ale muszę wiedzieć co mam zamieniać do góry. Kopiec sam sobie
pozmienia elementy, a ja tylko wiem, że mam zmienić element samochodzika
n. Może on być wszędzie. Żeby dostać tę informacje muszę sam napisać
kopiec.

Moze trzeba szukac rozwiazan prostych?

[...]

Post by Marek Sieradzki
Chyba że w STL mogę zrobić priority_queue, który wykorzystywałby moją
funkcję swap.

Nie musisz nic pisac.
Moze by tak podkrasc sugestie Tomasza z tego watku? Zamiast kopcowac
i zamieniac moze by tak dac bibliotece odrobic za nas zadanie?
Patrz co ja w przerwie obiadowej zrobilem z podpowiedzi Tomasza:

#include <vector>
#include <set>
#include <iostream>
using namespace std;

typedef vector<vector<int> > sam_seq;
typedef vector<vector<int>::const_iterator> zabawa;
sam_seq sev;
zabawa baw;
struct
ord_cmp { bool operator()(int i, int v) { return *(baw[i]) < *(baw[v]); } };
typedef set<int, ord_cmp> podloga;
podloga pod;
int seq[500001];
//-----------------------------------------------------------------------------
int main() {
int n, k, p;
scanf("%d %d %d", &n, &k, &p);
sev.resize(n+1);
baw.resize(n+1);
int sam;
for(int s = 1; s <= p; ++s) { // przeczytaj sekwencje i uporzadkuj
scanf("%d", &sam); seq[s] = sam; sev[sam].push_back(s); }
for(int zz=1; zz <= n; ++zz) { // tak sie bedzie Jasio bawil
sev[zz].push_back(p+zz); baw[zz] = sev[zz].begin(); }

podloga::iterator na_polce = pod.end();
int mvs = 0;
for(int si = 1; si <= p; ++si) {
sam = seq[si];
int flsz = mvs < k ? mvs : k;
podloga::iterator is_there = pod.find(sam);
if(is_there == na_polce && ++mvs) {
if(flsz >= k) pod.erase(--pod.end());
}
else pod.erase(is_there);
++baw[sam];
pod.insert(sam);
}
cout << mvs << endl;
}


Nie dosyc, ze jest to szybsze od twojej dlubaniny, to jeszcze
rozwiazuje problem samochodzikow w __szesciu__ linijkach.
Dzieki temu nie ma sie raczej co popsuc.
Jedyna wada, to to, ze nie jest to doslowne tlumaczenie z
polskiego na C++ :(

[Marek Sieradzki]

Post by Witold Kuzminski
Nie musisz nic pisac.
Moze by tak podkrasc sugestie Tomasza z tego watku? Zamiast kopcowac
i zamieniac moze by tak dac bibliotece odrobic za nas zadanie?
#include <vector>
#include <set>
#include <iostream>
using namespace std;
typedef vector<vector<int> > sam_seq;
typedef vector<vector<int>::const_iterator> zabawa;
sam_seq sev;
zabawa baw;
struct
ord_cmp { bool operator()(int i, int v) { return *(baw[i]) < *(baw[v]); } };
typedef set<int, ord_cmp> podloga;
podloga pod;
int seq[500001];
//-----------------------------------------------------------------------------
int main() {
int n, k, p;
scanf("%d %d %d", &n, &k, &p);
sev.resize(n+1);
baw.resize(n+1);
int sam;
for(int s = 1; s <= p; ++s) { // przeczytaj sekwencje i uporzadkuj
scanf("%d", &sam); seq[s] = sam; sev[sam].push_back(s); }
for(int zz=1; zz <= n; ++zz) { // tak sie bedzie Jasio bawil
sev[zz].push_back(p+zz); baw[zz] = sev[zz].begin(); }
podloga::iterator na_polce = pod.end();
int mvs = 0;
for(int si = 1; si <= p; ++si) {
sam = seq[si];
int flsz = mvs < k ? mvs : k;
podloga::iterator is_there = pod.find(sam);
if(is_there == na_polce && ++mvs) {
if(flsz >= k) pod.erase(--pod.end());
}
else pod.erase(is_there);
++baw[sam];
pod.insert(sam);
}
cout << mvs << endl;
}
Nie dosyc, ze jest to szybsze od twojej dlubaniny, to jeszcze
rozwiazuje problem samochodzikow w __szesciu__ linijkach.
Dzieki temu nie ma sie raczej co popsuc.
Jedyna wada, to to, ze nie jest to doslowne tlumaczenie z
polskiego na C++ :(

Nigdzie nie twierdziłem, że znam C++ wystarczająco dobrze, żeby pisąc
tak ładne programy jak tamten twój poprzedni. Z tym, że taki program do
niczego się nie przyda tak samo jak mój jeśli nie będzie działał. Mój
np. niedziała, bo coś zwaliłem, a twój ma nieakceptowalną złożoność
czasową. Twój obecny wydaje się być już dobry choć kilka razy wolniejszy
od mojego(stała). Ja wolę korzystać z własnego kodu, co do którego mam
pewność, że nie zawiera tego co mi niepotrzebne i będzie przez to
wystarczająco szybki. Z tego co w tym kodzie widzę set.find() używa find
z drzewa RB. Po co komu taka reprezentacja? STL nie jest idealny do
wszystkiego i moim zdaniem lepiej nie używać na siłę STL gdy można coś
zrobić prościej. W tym przypadku (mój pogmatwany kod) nie miałem czasu
dokładnie poznać na tyle STL, żeby napisać coś czysto C++owo. Jakie
sześć linijek masz na myśli?

[Witold Kuzminski]

Post by Marek Sieradzki
Twój obecny wydaje się być już dobry choć kilka razy wolniejszy
od mojego(stała).

Juz dobry? Ciesze sie ze tym razem cie zadowala.
Hmmm...ms to twoj kod jak jest, msa z modyfikacjami tak, zeby stary aCC
go przyjal:
odin:/home/dmg/wkuzmins/work/tmp/sam>g++ -O3 ms.cpp -o ms
odin:/home/dmg/wkuzmins/work/tmp/sam>aCC +O2 msa.cpp -o msa
odin:/home/dmg/wkuzmins/work/tmp/sam>mkdat 100000 500 500000 > id500
odin:/home/dmg/wkuzmins/work/tmp/sam>timex ms < id500
MNIEJSZY KLUCZ
[duzo razy to samo]
MNIEJSZY KLUCZ
417027

real 5.16
user 4.94
sys 0.22

odin:/home/dmg/wkuzmins/work/tmp/sam>timex msa < id500
MNIEJSZY KLUCZ
[inna ilosc tego samego]
MNIEJSZY KLUCZ
417051

real 8.05
user 6.22
sys 1.79

Teraz moj: modyfikacje takie same (no namespace, i.t.p.) sam to kod
jak zamieszczony wczesniej, sama to ten sam kod dla aCC:

odin:/home/dmg/wkuzmins/work/tmp/sam>timex sam < id500
417102

real 5.50
user 5.29
sys 0.17

odin:/home/dmg/wkuzmins/work/tmp/sam>timex sama < id500
417102

real 7.83
user 6.06
sys 1.75


Patrz! Oba wyniki takie same :)
Wczesniej bawilem sie aCC, bo gcc za kazdym razem wypisywal
te interesujace komunikaty o kluczu. aCC wyraznie stracil
cierpliwosc (do kluczy) dopiero dla max danych :)
Dlatego wczesniej napisalem szybszy: jak widac aCC generuje
kod szybszy (ma chyba szybsza implementacje std::set).

Post by Marek Sieradzki
Ja wolę korzystać z własnego kodu, co do którego mam
pewność, że nie zawiera tego co mi niepotrzebne i będzie przez to
wystarczająco szybki.

Moze masz pewnosc, ze nie zawiera tego co niepotrzebne. Jak na razie
powinienes tez miec pewnosc, ze nie zawiera tego co potrzebne...
Nie chce sie znecac nad twoim kodem, ale gdy go skopmilowac bez
optymalizacji to daje jeszcze inne (rozne) wyniki.

Post by Marek Sieradzki
Z tego co w tym kodzie widzę set.find() używa find
z drzewa RB. Po co komu taka reprezentacja?

Eeee... niech pomysle. Moze po to, zeby cos szybko znalezc?

Post by Marek Sieradzki
STL nie jest idealny do
wszystkiego i moim zdaniem lepiej nie używać na siłę STL gdy można coś
zrobić prościej.

Tylko wtedy gdy sie to potrafi zrobic. Ty jak na razie nie potrafisz.
Czy koniecznie trzeba ci to mowic wprost?
Prosciej? Te twoje 200 linii to prosciej niz uzycie bilioteki?

Post by Marek Sieradzki
W tym przypadku (mój pogmatwany kod) nie miałem czasu
dokładnie poznać na tyle STL, żeby napisać coś czysto C++owo. Jakie
sześć linijek masz na myśli?

Jakie? Chyba do rozwiazania nie ma co liczyc int k,n,p; i podobnych.
Rozwiazanie to szesc linijek zaczynajac od find z pominieciem tej,
w ktorej jest sam nawias }.

[Marek Sieradzki]

Post by Witold Kuzminski

Post by Marek Sieradzki
Twój obecny wydaje się być już dobry choć kilka razy wolniejszy
od mojego(stała).

Juz dobry? Ciesze sie ze tym razem cie zadowala.
Hmmm...ms to twoj kod jak jest, msa z modyfikacjami tak, zeby stary aCC

To, że mój kod powiedzmy do niczego się nie nadaje, nie znaczy, że twój
jest lepszy. :D Przy okazji właśnie są wyniki wstępne I etapu OI. Za to
zadanie mam 100/100 punktów.

Post by Witold Kuzminski
odin:/home/dmg/wkuzmins/work/tmp/sam>g++ -O3 ms.cpp -o ms
odin:/home/dmg/wkuzmins/work/tmp/sam>aCC +O2 msa.cpp -o msa

Masz pewność, że O3 napewno zadziała? Ja nie mam i kompiluje najwyżej z -O2.

Post by Witold Kuzminski
odin:/home/dmg/wkuzmins/work/tmp/sam>mkdat 100000 500 500000 > id500
odin:/home/dmg/wkuzmins/work/tmp/sam>timex ms < id500
MNIEJSZY KLUCZ
[duzo razy to samo]
MNIEJSZY KLUCZ
417027
real 5.16
user 4.94
sys 0.22
odin:/home/dmg/wkuzmins/work/tmp/sam>timex msa < id500
MNIEJSZY KLUCZ
[inna ilosc tego samego]
MNIEJSZY KLUCZ
417051
real 8.05
user 6.22
sys 1.79
Teraz moj: modyfikacje takie same (no namespace, i.t.p.) sam to kod
odin:/home/dmg/wkuzmins/work/tmp/sam>timex sam < id500
417102
real 5.50
user 5.29
sys 0.17
odin:/home/dmg/wkuzmins/work/tmp/sam>timex sama < id500
417102
real 7.83
user 6.06
sys 1.75
Patrz! Oba wyniki takie same :)
Wczesniej bawilem sie aCC, bo gcc za kazdym razem wypisywal
te interesujace komunikaty o kluczu. aCC wyraznie stracil
cierpliwosc (do kluczy) dopiero dla max danych :)
Dlatego wczesniej napisalem szybszy: jak widac aCC generuje
kod szybszy (ma chyba szybsza implementacje std::set).

Mozliwe

Post by Witold Kuzminski

Post by Marek Sieradzki
Ja wolę korzystać z własnego kodu, co do którego mam
pewność, że nie zawiera tego co mi niepotrzebne i będzie przez to
wystarczająco szybki.

Moze masz pewnosc, ze nie zawiera tego co niepotrzebne. Jak na razie
powinienes tez miec pewnosc, ze nie zawiera tego co potrzebne...

Zawiera.

Post by Witold Kuzminski
Nie chce sie znecac nad twoim kodem, ale gdy go skopmilowac bez
optymalizacji to daje jeszcze inne (rozne) wyniki.

Rozne tzn?

Post by Witold Kuzminski

Post by Marek Sieradzki
Z tego co w tym kodzie widzę set.find() używa find
z drzewa RB. Po co komu taka reprezentacja?

Eeee... niech pomysle. Moze po to, zeby cos szybko znalezc?

Chyba jesteś w stanie się domyślić o co mi chodziło? Po co tutaj drzewo
czerwono-czarne jak wystarczy kopiec.

Post by Witold Kuzminski

Post by Marek Sieradzki
STL nie jest idealny do
wszystkiego i moim zdaniem lepiej nie używać na siłę STL gdy można coś
zrobić prościej.

Tylko wtedy gdy sie to potrafi zrobic. Ty jak na razie nie potrafisz.

Jak mówiłem te samochodziki to wypadek przy pracy. Za dużo czasu zajmie
debugowanie żeby doprowadzić to do ładu. (tzn żeby na twoim lipnym
kompilatorze+środowisku przeszło)

Post by Witold Kuzminski
Czy koniecznie trzeba ci to mowic wprost?
Prosciej? Te twoje 200 linii to prosciej niz uzycie bilioteki?

Gdy się nie zna dobrze biblioteki...

Post by Witold Kuzminski

Post by Marek Sieradzki
W tym przypadku (mój pogmatwany kod) nie miałem czasu
dokładnie poznać na tyle STL, żeby napisać coś czysto C++owo. Jakie
sześć linijek masz na myśli?

Jakie? Chyba do rozwiazania nie ma co liczyc int k,n,p; i podobnych.
Rozwiazanie to szesc linijek zaczynajac od find z pominieciem tej,
w ktorej jest sam nawias }.

Z reguły liczy się cały kod, a nie to mi nie pasuje, tamto też nie itd.
Jeśli traktujesz ten kod samochodzików jako coś więcej niż wypadek przy
pracy to trudno. Pisałem na szybko, mogłem czegoś nie zauważyć.

[Witold Kuzminski]

Post by Marek Sieradzki
Przy okazji właśnie są wyniki wstępne I etapu OI. Za to
zadanie mam 100/100 punktów.

Gratuluje.
Przy okazji: wiesz jaki scanf jest wolny? W twoim programie
zajmuje pewnie wiecej niz polowe czasu. Mysle, ze w drugim
etapie powinienes czytac wszystko za jedym razem do bufora
znakowego uzywajac read i recznie robic odpowiednik atoi.
To bedzie z 50 razy szybciej niz scanf.

[Marek Sieradzki]

Post by Witold Kuzminski

Post by Marek Sieradzki
Przy okazji właśnie są wyniki wstępne I etapu OI. Za to
zadanie mam 100/100 punktów.

Gratuluje.
Przy okazji: wiesz jaki scanf jest wolny? W twoim programie
zajmuje pewnie wiecej niz polowe czasu. Mysle, ze w drugim
etapie powinienes czytac wszystko za jedym razem do bufora
znakowego uzywajac read i recznie robic odpowiednik atoi.
To bedzie z 50 razy szybciej niz scanf.

Mógłbyś sobie darować tę ironię.
Można czytać readem większe kawałki, a potem parsować. Rzeczywiście
czasem (całkiem często) wyjdzie to szybciej. Tylko po co?
Jeśli by założyć, że to aluzja do STLa: używałbym scanfa gdybym go
dobrze znał. Jak jestem w stanie jedynie napisać za pomocą atoi i reada
to tego używam.

[Witold Kuzminski]

Post by Witold Kuzminski

Post by Marek Sieradzki
Przy okazji właśnie są wyniki wstępne I etapu OI. Za to
zadanie mam 100/100 punktów.

Gratuluje.
Przy okazji: wiesz jaki scanf jest wolny?

Alez skad.
Zycze ci co najmniej tyle samo szczescia w dalszych etapach OI.

[Marek Sieradzki]

http://www.lo3.wroc.pl/~mrukowi/gis_sam_1.in~
Duzy test, odpowiedź: 216653
U mnie mój kod działa idealnie z tym.
Korzystasz czasem z IRCa(ircnet) lub z GG? Możnaby szybciej znaleźć kto
ma błąd.

[Tomasz Zielonka]

Post by Leon
Dobra, wiec spytam prosto :) Jak napisac w C++ (z uzyciem STLa) `cos' co
dzialaniem przypominaloby kolejke priorytetowa, ale z mozliwoscia zmiany
elemenotw w srodku (tj. zmiana wartosci elementu i natychmiastowe jego
przesuniecie). Mam nadzieje, ze zajmie to mniej niz implementacja calkowicie
nowej kolejki (czyli jakies 100 linijek).

Dlaczego nie uzyjesz std::set lub std::map? Dosyc latwo mozna przy ich
pomocy zaimplementowac kolejke priorytetowa z mozliwoscia usuwania czy
tez modyfikacji dowolnych jej elementow, z kosztami operacji O(log N).
Wyszukanie minimalnego/maxymalnego elementu robisz przez begin() lub
end().

Jesli chcesz sie sensownie czepic STL'a, zapytaj jak mozna
zaimplementowac wzbogacone drzewo AVL/RB bez potrzeby implementowania
drzew od zera. Moim zdaniem tu STL jest kiepski - zawiera implementacje
zrownowazonych drzew binarnych, ktorej nie mozna wykorzystac do
czegokolwiek bardziej skomplikowanego.

Pozdrawiam,
Tomek