-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Potyczki
Date: Sat, 24 Nov 2012 16:43:30 +0100
Organization: ATMAN - ATM S.A.
Lines: 94
Message-ID: <k8qpv4$euu$1@node2.news.atman.pl>
References: <k8frhm$5pg$1@node1.news.atman.pl>
<50abbc9e$0$1214$65785112@news.neostrada.pl>
<k8p9ei$h43$1@mx1.internetia.pl> <s...@n...notb-home>
<50b0bf80$0$1213$65785112@news.neostrada.pl>
<s...@n...notb-home>
<50b0cf1f$0$1211$65785112@news.neostrada.pl>
<s...@n...notb-home>
<50b0d9e3$0$1214$65785112@news.neostrada.pl>
<s...@n...notb-home>
<k8qo81$2n6$1@node1.news.atman.pl>
<s...@n...notb-home>
NNTP-Posting-Host: 144-mi3-6.acn.waw.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1353771812 15326 85.222.69.144 (24 Nov 2012 15:43:32
GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Sat, 24 Nov 2012 15:43:32 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121026
Thunderbird/16.0.2
In-Reply-To: <s...@n...notb-home>
Xref: news-archive.icm.edu.pl pl.comp.programming:201213
[ ukryj nagłówki ]W dniu 2012-11-24 16:25, PK pisze:
> On 2012-11-24, bartekltg <b...@g...com> wrote:
>> Niedawno był to całkiem niezły watek o sortowaniu.
>> Sortowania pozycyjne tez były omówione;)
>
> Wiem. W nim również zwróciłem slawkowi uwagę, że nie rozumie sortowania,
> a potem przestałem się udzielać, bo po prostu żal mi było czasu. Nie
> mniej widzę, że Wasza dyskusja (trwająca chyba kilka tygodni) była
> dla niego zupełnie bezowocna.
Hmm, dyskusja była chyba głownie w około fira.
Zresztą, nie pamiętam dokładnie.
>> Ale posortować beż użycia > na elementach sortowanych się da;)
>> Pewnych specyficznych elementów, jak liczby naturalne.
>
> Można zastąpić relację ">" obliczeniem pewnych f(a,b) i g(a,b), ale
> wyniki tych funkcji trzeba przyrównać do zera.
> Poza tym operacja "=" jest zazwyczaj wolniejsza niż ">".
Ale czasem złożonością jednak przebija. Posortowanie
miliarda bajtów będzie szybsze 'sortowaniem przez zliczanie'
niz qsortem. Tylko jak często mamy taką potrzebę;-)
Odkopałem test, który robiłem w tamtej dyskusji.
Wygląda, że i inty lecą szybciej. Pod warunkiem,
że tablica jest dostatecznie duża.
A, to nizej to kod chyba niepoprawiony, sortowanie
nie jest stabilne. Trzeba gdzieś zamienić kierunek pętli.
pzdr
bartekltg
***
Przetestowane, porównane z std::sort
Na przedziale n 10^5 - 10^7 przewaga 2 do 3.5 raza
szybsze. Co ciekawe, przewaga pozycyjnego od pewnego
momentu maleje.
void pozycyjne(unsigned int * tab, int n)
{
const int shift = 16;
const int K = 1<<shift;
int * h = new int [K];
unsigned int * temp = new unsigned int [n];
for (int j=0;j<K;j++) //zerowanie
h[j]=0;
for (int j=0;j<n;j++)//zliczanie wystąpień
h[(unsigned short)(tab[j])]++;
for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
h[j]+=h[j-1]; //na indeksy
for (int j=0;j<n;j++)//kopiowanie
{
temp[--h[(unsigned short)tab[j]]]=tab[j];
}
///////////faza druga
for (int j=0;j<K;j++) //zerowanie
h[j]=0;
for (int j=0;j<n;j++)//zliczanie wystąpień
h[(unsigned short)(temp[j]>>shift)]++;
for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
h[j]+=h[j-1]; //na indeksy
for (int j=n-1;j>=0;j--)//kopiowanie
{
tab[--h[(unsigned short)temp[j]>>shift]]=temp[j];
}
delete[]temp;
delete[]h;
}
*****
pzdr
bartekltg
Następne wpisy z tego wątku
- 24.11.12 16:51 e...@g...com
- 24.11.12 20:38 Stachu 'Dozzie' K.
- 24.11.12 21:18 PK
- 24.11.12 21:19 Stachu 'Dozzie' K.
- 24.11.12 21:35 PK
- 24.11.12 21:44 Stachu 'Dozzie' K.
- 25.11.12 13:15 Roman W
- 25.11.12 13:35 bartekltg
- 25.11.12 14:57 Jacek
- 25.11.12 18:08 PK
- 25.11.12 18:10 PK
- 25.11.12 20:27 Roman W
- 25.11.12 21:07 bartekltg
- 26.11.12 07:23 Jacek
- 26.11.12 10:36 Roman W
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=
- 2024-05-18 Łódź => Handlowiec - Systemy CRM <=
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=