On Sunday, July 15, 2012 8:37:22 AM UTC+1, Edek Pienkowski wrote:

> Była mowa o sortowaniu. Czy aby na pewno nie da się żyć bez znajomości
> quick sorta? Ile razy w życiu trzeba algorytm sortowania napisać
> samemu? Szczerze mówiąc, mi się jeszcze _nigdy_ nie zdarzyło. To
> samo mogę powiedzieć o wielu innych algorytmach, znam ich właściwości
> i używam, nie muszę nawet wiedzieć jak działają i do głowy by mi
> nie przyszło żeby przepisywać na nowo coś, co zawsze po prostu jest.

Powierzchowna znajomosc narzedzi ktore sie uzywa jest niebezpieczna, bo czlowiek jest
nieswiadomy, kiedy narzedzie przestaje byc efektywne albo nawet staje sie
zagrozeniem.

>
> Ciekawość i chęć poznania świata to zupełnie inny temat, ale
> dlaczego akurat quick sort?

Oklepany przyklad, ale dotyczy mnostwa innych rzeczy. Np. ludzie ktorzy zawsze
uzywaja metody Runge-Kutta 4 rzedu.

RW

do góry

On 2012-07-15, Edek Pienkowski <e...@g...com> wrote:
> W to akurat nie wątpię, że quicksort dobrym przykładem jest, tylko
> jakoś mi umknęło, czego konkretnie miałby być podstawą.

Niestety nie rozumiem tego zdania :/.

> Zazwyczaj jestem świadomy sytuacji, kiedy powinienem się na tym
> pochylić, a jak się pomylę to profiler szybko mnie naprostuje;
> stabilność to osobna cecha, jak o niej nie myślę to zazwyczaj
> nie ma ku temu powodu.

No to masz fart. Ja muszę o sortowaniu myśleć dużo. Taka sytuacja.
Za to inne rzeczy mogę olewać. Np. rzadko piszę jakiekolwiek GUI, więc
roboty mniej :).

Zdarzyło mi się za to kilka razy w życiu stosować sortowanie optymalne.
Większość osób mniej lub bardziej świadomie pisze to dla dwóch liczb,
ale kiedyś miałem potrzebę dla aż 16. Skok wydajności OGROMNY :D.

pozdrawiam,
PK

do góry

PK wrote:

> Rozmowa z "pythoniarzem" zaczyna wyglądać tak:
> "To jak by Pan posortował tę listę?"
> "W Pythonie x.sorted()"
> "A bez tej metody?"
> "Ale jak to? Przecież ona jest zawsze dostępna!"
>
> I 3 minuty później okazuje się, że człowiek nawet bardzo nie wie, na
> czym polega sortowanie i że istnieją różne podejścia.

Tego rodzaju pytania mają pewną interesującą cechę: słabo na nie odpowiadają
ci, którzy akademickie książki czytali dawno. Gdyby oceniać ludzi po
odpowiedziach na tego rodzaju pytania, to dużo lepiej będą wypadać studenci
i świezi absolwenci, niż ludzie z doświadczeniem, którzy dawno się z tymi
tematami nie zetknęli bo nie mieli takiej potrzeby.
Wniosek: nie ma się specjalnie czym emocjonować, że jakiś pythoniarz
niewiele wiedział o algorytmach sortowania. Wcale nie oznacza to, że gdyby
zaszła taka potrzeba, to by się nie douczył (i znów zapomniał po roku).

do góry

On 2012-07-15, Roman W <b...@g...pl> wrote:
> Powierzchowna znajomosc narzedzi ktore sie uzywa jest niebezpieczna,
> bo czlowiek jest nieswiadomy, kiedy narzedzie przestaje byc efektywne
> albo nawet staje sie zagrozeniem.

Bez przesady z tym zagrożeniem - nie każdy modeluje mosty, a tych
modelujących się kontroluje i sprawdza. Trochę gorzej jest w nauce,
gdzie recenzenci potrafią przegapić ewidentne głupoty i można sobie
narobić wiochy :).

Generalnie jeśli wynik jest ważny, to warto wiedzieć co i z jakim błędem
zwracają użyte metody :).

> Oklepany przyklad, ale dotyczy mnostwa innych rzeczy. Np. ludzie
> ktorzy zawsze uzywaja metody Runge-Kutta 4 rzedu.

Akurat ze standardowym Runge-Kutta są większe problemy.
Nie jest symplektyczny i odwracalny w czasie, więc w praktyce nadaje się
chyba tylko do gier i edukacji :).

Lepsze wersje są już na tyle bardziej skomplikowane, że raczej trudno
ich używać nieświadomie :).

pozdrawiam,
PK

do góry

On 2012-07-15, Wojciech Jaczewski <w...@o...pl> wrote:
> Tego rodzaju pytania mają pewną interesującą cechę: słabo na nie odpowiadają
> ci, którzy akademickie książki czytali dawno. Gdyby oceniać ludzi po
> odpowiedziach na tego rodzaju pytania, to dużo lepiej będą wypadać studenci
> i świezi absolwenci, niż ludzie z doświadczeniem, którzy dawno się z tymi
> tematami nie zetknęli bo nie mieli takiej potrzeby.

Jeśli zadaje się takie pytania, to pewnie są one istotne w danym
projekcie / na danym stanowisku. Ludzie do klepania interfejsów nie
muszą tego wiedzieć, więc pewnie tego się od nich nie wymaga.

Jeśli ktoś zajmuje się algorytmiką regularnie, to pewnie i 20 lat
po studiach będzie sobie radził z takimi pytaniami. Tym bardziej, że
cały czas pojawia się coś nowego i najlepszych dostępnych algorytmów
generalnie szuka się w publikacjach z ostatnich ~10 lat.

> Wniosek: nie ma się specjalnie czym emocjonować, że jakiś pythoniarz
> niewiele wiedział o algorytmach sortowania. Wcale nie oznacza to, że gdyby
> zaszła taka potrzeba, to by się nie douczył (i znów zapomniał po roku).

Idąc tym tropem można w ogóle stwierdzić, że wszystko jest do
"douczenia", więc programista niczego nie musi umieć :).
Ale czasem trzeba wybrać osobę z grupy na jakiejś podstawie.
Doświadczenie ("programuję od 20 lat!") tak naprawdę nie mówi niczego.
Doświadczenie i brak rozwoju ("programuję od 20 lat tak samo!") mówią
już dużo, ale raczej nie na korzyść :).

pozdrawiam,
PK

do góry

Dnia Sun, 15 Jul 2012 11:45:22 +0000, PK napisal:

> On 2012-07-15, Wojciech Jaczewski <w...@o...pl> wrote:
>> Tego rodzaju pytania mają pewną interesującą cechę: słabo na nie odpowiadają
>> ci, którzy akademickie książki czytali dawno. Gdyby oceniać ludzi po
>> odpowiedziach na tego rodzaju pytania, to dużo lepiej będą wypadać studenci
>> i świezi absolwenci, niż ludzie z doświadczeniem, którzy dawno się z tymi
>> tematami nie zetknęli bo nie mieli takiej potrzeby.
>
> Jeśli zadaje się takie pytania, to pewnie są one istotne w danym
> projekcie / na danym stanowisku. Ludzie do klepania interfejsów nie
> muszą tego wiedzieć, więc pewnie tego się od nich nie wymaga.

Jeżeli takie pytania są istotne, to miałbym żal o to, że nie było
dopisku "studenci ostatnich lat mile widziani". Bo to strata czasu.

> Jeśli ktoś zajmuje się algorytmiką regularnie, to pewnie i 20 lat
> po studiach będzie sobie radził z takimi pytaniami. Tym bardziej, że
> cały czas pojawia się coś nowego i najlepszych dostępnych algorytmów
> generalnie szuka się w publikacjach z ostatnich ~10 lat.

Sortowanie nie jest z ostatnich 10 lat. Nie wiem, co masz na myśli
mówiąc "algorytmika". Jeżeli tworzenie nowego algorytmu sortowania to ok,
ale przy zwykłym stosowaniu i to "często i gęsto" sortowania nie ma
żadnego znaczenia, jakiego sorta używa biblioteka, o ile a) nie jest
w ciasnej pętli, albo b) nie ma zauważalnie dużo elementów. Ostatecznie
i tak z profilerem się nie dyskutuje.

>> Wniosek: nie ma się specjalnie czym emocjonować, że jakiś pythoniarz
>> niewiele wiedział o algorytmach sortowania. Wcale nie oznacza to, że gdyby
>> zaszła taka potrzeba, to by się nie douczył (i znów zapomniał po roku).
>
> Idąc tym tropem można w ogóle stwierdzić, że wszystko jest do
> "douczenia", więc programista niczego nie musi umieć :).
> Ale czasem trzeba wybrać osobę z grupy na jakiejś podstawie.
> Doświadczenie ("programuję od 20 lat!") tak naprawdę nie mówi niczego.
> Doświadczenie i brak rozwoju ("programuję od 20 lat tak samo!") mówią
> już dużo, ale raczej nie na korzyść :).

Twoje podejście też nie przemawia na korzyść. W tym wątku pojawił
się parę razy temat "podstaw", albo inaczej, na jakich podstawowych
umiejętnościach student może zbudować przyszłą karierę. Różne uczelnie
mają różne podejście m.in. do wyboru programu nauczania, ocenia się je
po owocach a nie po swoim własnym podejściu do tematu. Więc w mojej
opinii, nie trzeba wszystkiego wiedzieć, co nie znaczy, że nie warto.

Edek

do góry

On 2012-07-15, Edek Pienkowski <e...@g...com> wrote:
> Sortowanie nie jest z ostatnich 10 lat. Nie wiem, co masz na myśli

Wspomniany wcześniej Timsoft jest z 2002 roku. Nie jest to algorytm
znany, ale jest bardzo często używany (przez popularność Pythona, więc
w pewnym sensie ważny :)). Z tego samego roku pochodzi bardzo ciekawy
spreadsort (polecam poczytać).

Z bardziej znanych... tu nie mam pewności, ale chyba bucket sort
(jako uogólnienie kilku innych) jest dosyć świeży. Z całą pewnością
w ostatnich latach ten algorytm był mocno rozwijany.

> mówiąc "algorytmika". Jeżeli tworzenie nowego algorytmu sortowania to ok,
> ale przy zwykłym stosowaniu i to "często i gęsto" sortowania nie ma
> żadnego znaczenia, jakiego sorta używa biblioteka, o ile a) nie jest
> w ciasnej pętli, albo b) nie ma zauważalnie dużo elementów. Ostatecznie
> i tak z profilerem się nie dyskutuje.

Może w Twoim doświadczeniu nie ma, ale ludzie mają różne sytuacje.
Np. dla mnie zazwyczaj wariant pesymistyczny jest znacznie bardziej
istotny niż średni - dlatego m.in. nie używam quicksorta. Poza tym
często cierpię na deficyt RAMu i staram się dobierać algorytmy in situ.

Niektóre algorytmy dobrze radzą sobie z ciągami zupełnie losowymi,
a inne z już częściowo posortowanymi.

I to nie jest tak, że chcę być fajny i optymalizuję sortowanie
200 numerów telefonów w książce adresowej :). Te problemy są dla mnie
naprawdę istotne :).

Wiem, że jestem w tym wypadku marginesem, ale to nie zmienia faktu, że
każda osoba używająca jakiejś funkcji "sort()" powinna przynajmniej
wiedzieć, co ta funkcja zwraca, czyli czy algorytm jest stabilny.
Widywałem już programy sypiące się, bo autor o tym zapomniał.

pozdrawiam,
PK

do góry

PK wrote:

> [...]
> I to nie jest tak, że chcę być fajny i optymalizuję sortowanie
> 200 numerów telefonów w książce adresowej :). Te problemy są dla mnie
> naprawdę istotne :).

I czy zajmujesz się tym dlatego, że ktoś zamówił produkt, w którym jest to
niezbędne, czy może robisz pracę naukową?

do góry

Dnia Sun, 15 Jul 2012 16:41:06 +0000, PK napisal:

> On 2012-07-15, Edek Pienkowski <e...@g...com> wrote:
>> Sortowanie nie jest z ostatnich 10 lat. Nie wiem, co masz na myśli
>
> Wspomniany wcześniej Timsoft jest z 2002 roku. Nie jest to algorytm
> znany, ale jest bardzo często używany (przez popularność Pythona, więc
> w pewnym sensie ważny :)). Z tego samego roku pochodzi bardzo ciekawy
> spreadsort (polecam poczytać).

Z kwietnia czy października? To już prawie 10 ;)

> Z bardziej znanych... tu nie mam pewności, ale chyba bucket sort
> (jako uogólnienie kilku innych) jest dosyć świeży. Z całą pewnością
> w ostatnich latach ten algorytm był mocno rozwijany.
>
>> mówiąc "algorytmika". Jeżeli tworzenie nowego algorytmu sortowania to ok,
>> ale przy zwykłym stosowaniu i to "często i gęsto" sortowania nie ma
>> żadnego znaczenia, jakiego sorta używa biblioteka, o ile a) nie jest
>> w ciasnej pętli, albo b) nie ma zauważalnie dużo elementów. Ostatecznie
>> i tak z profilerem się nie dyskutuje.
>
> Może w Twoim doświadczeniu nie ma, ale ludzie mają różne sytuacje.
> Np. dla mnie zazwyczaj wariant pesymistyczny jest znacznie bardziej
> istotny niż średni - dlatego m.in. nie używam quicksorta. Poza tym
> często cierpię na deficyt RAMu i staram się dobierać algorytmy in situ.

Ja faktycznie mam takie podejście do sortowania jak do nowego modelu
uchwytu śrubokręta. Zwracam na nie uwagę tylko wtedy gdy jest mi
potrzebny akurat taki a nie inny. Domyślam się, że mamy tu swoistą
symetrię.

> Niektóre algorytmy dobrze radzą sobie z ciągami zupełnie losowymi,
> a inne z już częściowo posortowanymi.

To jest odwieczny problem, dane o określonej skrukturze mogą trafić
w wariant pesymistyczny albo nawet trafiać bardzo często. Brak
struktury to też pewna cecha z gatunku cech strukturalnych,
nie ma jak tego skompresować chociażby.

Z ciekawości, który algorytm najlepiej odwróci sortowanie?
(Poza reverse(), nie wiemy, że są posortowane odwrotnie).

> I to nie jest tak, że chcę być fajny i optymalizuję sortowanie
> 200 numerów telefonów w książce adresowej :). Te problemy są dla mnie
> naprawdę istotne :).

Rozumiem. O większości powyższych słyszałem, w dokumentacji bibliotek
Pythona też pamiętam, że chyba faktycznie był to timsort, ale mój
mózg nisko spriorytetyzował tę informację i się zagubiła.

Zaskoczyło mnie, że te algorytmy są stosunkowo nowe. Doczytam kiedyś
w wolnej chwili, kiedyś ta wiedza się może przydać. Kolejna dziedzina,
gdzie wydawałoby się że nic już nowego nie powstanie, a jednak.

> Wiem, że jestem w tym wypadku marginesem, ale to nie zmienia faktu, że
> każda osoba używająca jakiejś funkcji "sort()" powinna przynajmniej
> wiedzieć, co ta funkcja zwraca, czyli czy algorytm jest stabilny.
> Widywałem już programy sypiące się, bo autor o tym zapomniał.

Prawda, ja też widzę często bardziej podstawowe błędu typu a < b < c
i c < a. Nie różnię się tutaj od innych programistów, robię błędy
które muszę poprawiać, takie też z podobną częstotliwością jak
if (a) zamiast if (!a).

Edek

do góry

On 2012-07-15, Wojciech Jaczewski <w...@o...pl> wrote:
> I czy zajmujesz się tym dlatego, że ktoś zamówił produkt, w którym jest to
> niezbędne, czy może robisz pracę naukową?

Różnie.

Dużymi zbiorami danych zajmuję się hobbystycznie i w pracy.

W aktualnej pracy naukowej akurat żadnego sortowania explicite nie
uprawiam, ale bardzo interesuje mnie wydajne wprowadzanie elementów
do pewnej dość skomplikowanej struktury (z kilkoma porządkami).

W solidną optymalizację algorytmów bawię się zupełnie prywatnie (akurat
chodzi o analizę szeregów czasowych). W skrócie: klepię krótkie
programy wykonujące sporo operacji na relatywnie małych danych, ale
bardzo zależy mi na zmieszczeniu się w pewnym limicie czasu (tu pojawiło
się optymalne sortowanie 16 elementów, o którym pisałem wcześniej :)).

Mam nadzieję, że to wystarczająco szczegółowa odpowiedź, bo więcej
powiem tylko szałowej blondynce, a Twoje imię nie wskazuje... :]

pozdrawiam,
PK

do góry