eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingKiedy qsort zaczyna źle działać?
Ilość wypowiedzi w tym wątku: 12

  • 1. Data: 2015-07-15 21:44:34
    Temat: Kiedy qsort zaczyna źle działać?
    Od: Borneq <b...@a...hidden.pl>

    QSort w najgorszym przypadku jak słyszałem, ma złożoność kwadratową.
    Kiedy występuje ten najgorszy przypadek? Kiedy dane są już posortowane?
    czy też jest to jeden specyficzny porządek, na którego natrafienie jest
    trudniejsze niż wygranie w toto lotka?


  • 2. Data: 2015-07-15 22:55:00
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: Pit <n...@s...lonestar.org>

    Dnia 15.07.2015 Borneq <b...@a...hidden.pl> napisał/a:
    > QSort w najgorszym przypadku jak słyszałem, ma złożoność kwadratową.
    > Kiedy występuje ten najgorszy przypadek? Kiedy dane są już posortowane?
    > czy też jest to jeden specyficzny porządek, na którego natrafienie jest
    > trudniejsze niż wygranie w toto lotka?

    Zależy nie tyle od samego posortowania, co od wyboru elementu wg którego
    "dzielisz" zbiór. Jeśli "pechowo" zawsze trafisz w element największy
    (lub najmniejszy) to dostajesz podział na zbiór jednoelementowy i "resztę"
    (czyli nie dość że takie "pechowe typowania" sortują tak na prawdę tylko
    jeden element a reszta pozostaje jak było, to jeszcze rośnie
    zapotrzebowanie na pamięć stosu, bo rekurencja idzie bardzo głęboko).


  • 3. Data: 2015-07-15 23:06:18
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2015-07-15 o 22:55, Pit pisze:
    > Zależy nie tyle od samego posortowania, co od wyboru elementu wg którego
    > "dzielisz" zbiór. Jeśli "pechowo" zawsze trafisz w element największy
    > (lub najmniejszy) to dostajesz podział na zbiór jednoelementowy i "resztę"
    > (czyli nie dość że takie "pechowe typowania" sortują tak na prawdę tylko
    > jeden element a reszta pozostaje jak było, to jeszcze rośnie
    > zapotrzebowanie na pamięć stosu, bo rekurencja idzie bardzo głęboko).

    Czy procedury się przed tym zabezpieczają? czy to jest naprawdę rzadki
    przypadek, że łatwiej trafić w totolotka?



  • 4. Data: 2015-07-15 23:08:09
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2015-07-15 o 23:06, Borneq pisze:
    > Czy procedury się przed tym zabezpieczają? czy to jest naprawdę rzadki
    > przypadek, że łatwiej trafić w totolotka?

    Ale nawet rzadki, to może trafić się gdy sortujemy indeks bazy danych
    wiele razy na sekundę a system wykrzacza się raz na parę miesięcy z
    powodu przepełnienia stosu przez qsort.



  • 5. Data: 2015-07-15 23:10:50
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: bartekltg <b...@g...com>

    On 15.07.2015 21:44, Borneq wrote:
    > QSort w najgorszym przypadku jak słyszałem, ma złożoność kwadratową.
    > Kiedy występuje ten najgorszy przypadek? Kiedy dane są już posortowane?
    > czy też jest to jeden specyficzny porządek, na którego natrafienie jest
    > trudniejsze niż wygranie w toto lotka?


    Zależy od tego, jako to qsort. Ten szkolny nie działą dla danych
    monotonicznych (posortowanych lub odwrotnie posortowanych).
    Dlaczego? Dlatego, że jeśli za element dzielący weźmiemy pierwszy
    element podtablicy, to wyląduje on albo na początku, albo na końcu.
    Rekurencja podzieliła nam podtablicę długośći na tablice dlugosci 1
    i n-2.
    Sposobów raczenia sobie z tym jest masa, pierwszym, jest losowy
    wybór elementu dzialącego. Wtedy musisz mieć ogromengo pecha ;-)

    Częściej stosowanym jest wzięcie za element dzielący mediany
    z trzech elementów, pierwszego, ostatniego i środkowego.
    Posortowane dane dzialą się idealnie (rekurencja dzlei na pół),
    dodatkową zaletą jest to, że element dzielący na pewno nie jest
    najmniejszym ani największym elementem tablicy, dzięki czemu
    można obyć się bez pewnych sprawdzeń w pętli.

    Niestety, nadal można tak spreparować dane, aby podział był
    bardzo zły (wymaga już to trochę wysiłku ;-) Weź kartkę i sobie
    rozrysuj. pewnie jakiś grzebień wyjdzie.
    Dlatego sporo implementacji (w tym chyba wszystkie standardowe w c++)
    używają algorytmu introsort, który jest to quicksorttem,
    który w wywołaniach rekurencyjnych sprawdza głębokość rekurencji.
    Jeśli jest ona zbyt duża (tzn z jakiś powodów, jak bardzo złośliwe
    dane, ciagle źle trafiamy) podtablica traktowana jest heapsortem.

    I ostatecznie biblioteczny "qsort" nie wpada w tryb kwadratowy nigdy.

    pzdr
    bartekltg







  • 6. Data: 2015-07-15 23:11:41
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: bartekltg <b...@g...com>

    On 15.07.2015 23:08, Borneq wrote:
    > W dniu 2015-07-15 o 23:06, Borneq pisze:
    >> Czy procedury się przed tym zabezpieczają? czy to jest naprawdę rzadki
    >> przypadek, że łatwiej trafić w totolotka?
    >
    > Ale nawet rzadki, to może trafić się gdy sortujemy indeks bazy danych
    > wiele razy na sekundę a system wykrzacza się raz na parę miesięcy z
    > powodu przepełnienia stosu przez qsort.

    Ktoś go chujowo napisał;-)

    pzdr
    bartekltg



  • 7. Data: 2015-07-15 23:18:00
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2015-07-15 o 23:10, bartekltg pisze:
    > Dlatego sporo implementacji (w tym chyba wszystkie standardowe w c++)
    > używają algorytmu introsort, który jest to quicksorttem,
    > który w wywołaniach rekurencyjnych sprawdza głębokość rekurencji.
    > Jeśli jest ona zbyt duża (tzn z jakiś powodów, jak bardzo złośliwe
    > dane, ciagle źle trafiamy) podtablica traktowana jest heapsortem.

    Spotkałem się z przypadkiem zamiany quicksorta na metodę iteracyjną,
    zamiast stosu używając lokalnej tablicy. Działał szybciej.
    Jeśli chodzi o sprawdzanie tej tablicy, to występuje to tak rzadko, że
    zamiast sprawdzać za pomocą if, lepiej, zwłaszcza w Javie czekać na wyjątek.


  • 8. Data: 2015-07-15 23:37:07
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: bartekltg <b...@g...com>

    On 15.07.2015 23:18, Borneq wrote:
    > W dniu 2015-07-15 o 23:10, bartekltg pisze:
    >> Dlatego sporo implementacji (w tym chyba wszystkie standardowe w c++)
    >> używają algorytmu introsort, który jest to quicksorttem,
    >> który w wywołaniach rekurencyjnych sprawdza głębokość rekurencji.
    >> Jeśli jest ona zbyt duża (tzn z jakiś powodów, jak bardzo złośliwe
    >> dane, ciagle źle trafiamy) podtablica traktowana jest heapsortem.
    >
    > Spotkałem się z przypadkiem zamiany quicksorta na metodę iteracyjną,
    > zamiast stosu używając lokalnej tablicy. Działał szybciej.

    W pewnym przypadkach i mnimalnie. Potrzebujesz dodatkowej pamięci.
    Chyba nawet w Cormenia było;-) Tworzy sie stos z wrzucanymi na niego
    elementami podziału.

    W ząden sposób nie zapobiega to przypadkowi złego działąnia qsorta.
    Wiec tablica musi mieć w praktyce długość rzędu długości danych.


    > Jeśli chodzi o sprawdzanie tej tablicy, to występuje to tak rzadko, że
    > zamiast sprawdzać za pomocą if, lepiej, zwłaszcza w Javie czekać na
    > wyjątek.


    Pomojając, że nie mam pojęćia, jak odnieść to co mówisz do
    quicksota bez stosu:

    Raczej tylko w javie. W niektórych jezykach 'skryptowych'
    sterowanie programem za pomocą wyjątków jest pobłogosławioną
    metodą, i twory nazwane tam wyjatkami są do tego przestosowane.
    Czy java jest jednym z nich, nie wiem, bardzo prawdopodobne.
    W innych językach jest to idiotyzm od strony logicnzej
    i wydajnościowej.

    A od siebie dodam:
    I czekać na cotygodniowe wywalanie się bazy danych;-)

    pzdr
    bartekltg





  • 9. Data: 2015-07-16 01:39:45
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: Pit <n...@s...lonestar.org>

    Dnia 15.07.2015 Borneq <b...@a...hidden.pl> napisał/a:
    > Jeśli chodzi o sprawdzanie tej tablicy, to występuje to tak rzadko, że
    > zamiast sprawdzać za pomocą if, lepiej, zwłaszcza w Javie czekać na wyjątek.

    W Javie żadna kolekcja (ze standardowej biblioteki) nie zwraca dla 'sort'
    wyjątków postaci "nietypowy przypadek, zabrakło stosu" tylko radzi sobie z
    takimi problemami wewnętrznie. Jedyne wyjątki jakie można dostać, to
    nieprawidłowy zakres czy nieprawidłowy komparator (ewentualnie
    NullPointerException jeśli masz tablicę referencji do obiektów i któraś
    referencja jest pusta). Zresztą nie można mieć żadnej gwarancji co do tego
    jaki konkretnie algorytm kryje się pod metodą 'sort' (może być inny dla
    listy, inny dla wektora a jeszcze inny dla na przykład SortedSet czy
    kolejki priorytetowej), bo po pierwsze implementacja może się różnić w
    zależności od wersji Javy a po drugie implementacja może się różnić od
    ilości danych (czy od tego co się będzie działo w trakcie sortowania).

    Zresztą wyjątki w Javie służą raczej do sytuacji w których twórca
    klasy/metody musi coś zasygnalizować użytkownikowi klasy/metody z czym
    klasa/metoda sama w sobie nie jest w stanie sobie poradzić w rozsądny
    sposób (na przykład użytkownik klasy zgłasza chęć utworzenia pliku, którego
    nazwa w danym systemie operacyjnym zawiera niedopuszczalne znaki). Problemy
    typu "niebezpiecznie duże użycie stosu" należy rozwiązywać wewnętrznie a
    nie poprzez zgłaszanie wyjątków typu "pomieszaj trochę dane, bo się
    trafił nieoptymalny/brzegowy przypadek" D


  • 10. Data: 2015-07-16 08:31:56
    Temat: Re: Kiedy qsort zaczyna źle działać?
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2015-07-15 o 23:37, bartekltg pisze:
    > W pewnym przypadkach i mnimalnie. Potrzebujesz dodatkowej pamięci.
    > Chyba nawet w Cormenia było;-) Tworzy sie stos z wrzucanymi na niego
    > elementami podziału.

    Widziałem implementacje w Pascalu zwykłego Qsorta i iteracyjnego.
    Iteracyjny był znacząco szybszy. Nie bez powodu stosuje się w programach
    funkcje inline aby nie mieć narzutu na wołanie procedury. W
    rekurencyjnej metodzie nie można zrobić inline natomiast mamy tam masę
    wywołań. Poza tym łatwiej jest zaimplementować pasek postępu dla
    długiego sortowania.

    > W ząden sposób nie zapobiega to przypadkowi złego działąnia qsorta.
    > Wiec tablica musi mieć w praktyce długość rzędu długości danych.

    W procedurze pascalowej była tablica rzędu 40-tu par i nigdy się do tej
    granicy nie zbliżało, był pewien zapas. Dla kilu milionów 20 w
    zupełności wystarczało, trzeba było mniej tablicy niż log2(N).
    Zostaje przypadek złośliwy, ale wtedy lepiej przełączyć się na heapsort
    zamiast zwiększać tablicę.

strony : [ 1 ] . 2


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: