Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #27057 > unrolled thread
| Started by | Pit <nospam@sdf.lonestar.org> |
|---|---|
| First post | 2015-07-15 20:55 +0000 |
| Last post | 2015-07-15 23:11 +0200 |
| Articles | 4 — 3 participants |
Back to article view | Back to pl.comp.programming
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
Re: Kiedy qsort zaczyna źle działać? Pit <nospam@sdf.lonestar.org> - 2015-07-15 20:55 +0000
Re: Kiedy qsort zaczyna źle działać? Borneq <borneq@antyspam.hidden.pl> - 2015-07-15 23:06 +0200
Re: Kiedy qsort zaczyna źle działać? Borneq <borneq@antyspam.hidden.pl> - 2015-07-15 23:08 +0200
Re: Kiedy qsort zaczyna źle działać? bartekltg <bartekltg@gmail.com> - 2015-07-15 23:11 +0200
| From | Pit <nospam@sdf.lonestar.org> |
|---|---|
| Date | 2015-07-15 20:55 +0000 |
| Subject | Re: Kiedy qsort zaczyna źle działać? |
| Message-ID | <slrnmqdi53.3uo.nospam@nc10.lan> |
Dnia 15.07.2015 Borneq <borneq@antyspam.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).
[toc] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2015-07-15 23:06 +0200 |
| Message-ID | <mo6i0a$c32$1@node2.news.atman.pl> |
| In reply to | #27057 |
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?
[toc] | [prev] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2015-07-15 23:08 +0200 |
| Message-ID | <mo6i3p$c32$2@node2.news.atman.pl> |
| In reply to | #27058 |
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.
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Date | 2015-07-15 23:11 +0200 |
| Message-ID | <mo6iac$sld$2@node1.news.atman.pl> |
| In reply to | #27059 |
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
[toc] | [prev] | [standalone]
Back to top | Article view | pl.comp.programming
csiph-web