---

Hej

Jeg vil høre om der nogle der har et frårslag til hvordan man kunne løse
følgen.
Jeg har 40 værdiger i float hvor jeg skal finde de 5 største og de 5 mindste
og så fjerne dem og lave et gennemsnit af de sidste 30 så jeg ænder op med
en værdig.

Jeg skal lave det i ansi c så jeg har ikke nogle smarte class til af gøre
det grove

MVH

René Nyberg

---

On Thu, 5 Feb 2004 08:24:17 +0100, Rene <rene_r@test.dk> wrote:

> Jeg vil høre om der nogle der har et frårslag til hvordan man kunne løse
> følgen.
> Jeg har 40 værdiger i float hvor jeg skal finde de 5 største og de 5 mindste
> og så fjerne dem og lave et gennemsnit af de sidste 30 så jeg ænder op med
> en værdig.
>
> Jeg skal lave det i ansi c så jeg har ikke nogle smarte class til af gøre
> det grove

Skal det gaa hurtigt? Hvis nej, saa benyt qsort() til at sortere det
hele, pil derefter element 5-34 ud og lav gennemsnit over dem med en
for(;;) loekke. Skal der laves rigtigt mange beregninger, saa kan man
muligvis godt goere det i O(n) tid med en counting sort. Muligvis endnu
hurtigere hvis man holder rede paa hvad man har set og ikke har set.

Men angrib det nu kun med hastighed, hvis det virkeligt er der i dit
program at der aedes klokcykler.


--
Jesper

---

Jesper Louis Andersen wrote:
> On Thu, 5 Feb 2004 08:24:17 +0100, Rene <rene_r@test.dk> wrote:
>
>>Jeg har 40 værdiger i float hvor jeg skal finde de 5 største og de 5 mindste
>>og så fjerne dem og lave et gennemsnit af de sidste 30 så jeg ænder op med
>>en værdig.
>
> Skal der laves rigtigt mange beregninger, saa kan man
> muligvis godt goere det i O(n) tid med en counting sort.

Hvad er counting sort?

> Muligvis endnu
> hurtigere hvis man holder rede paa hvad man har set og ikke har set.

Et gennemsnit af n - 10 tal hurtigere end O(n). Jeg synes det lyder
temmeligt umuligt ...

> Men angrib det nu kun med hastighed, hvis det virkeligt er der i dit
> program at der aedes klokcykler.

Enig. I øvrigt er kunne det nemt være hurtigst bare at sortere først når
der kun er 40 værdier.

---

In article <4022BFE9.9020208@nospam.dk>, Byrial Jensen wrote:

>> Skal der laves rigtigt mange beregninger, saa kan man
>> muligvis godt goere det i O(n) tid med en counting sort.
>
> Hvad er counting sort?

Hvis du ved at dine vaerdier er bounded mellem 0 og k, saa laver du et
array 0..k og taeller hvor mange forekomster af et ciffer i du ser.
Derefter ligger du data paent ud. Kan goeres i O(n)

> Et gennemsnit af n - 10 tal hurtigere end O(n). Jeg synes det lyder
> temmeligt umuligt ...

Jeg skulle have skrevet eksplicit at jeg henviste til konstanten foran
O-notationen, sorry.

> Enig. I øvrigt er kunne det nemt være hurtigst bare at sortere først når
> der kun er 40 værdier.

Specielt naar counting-sort ikke er in-place.

--
j.

---

Jesper Louis Andersen wrote:
> In article <4022BFE9.9020208@nospam.dk>, Byrial Jensen wrote:
>>Hvad er counting sort?
>
> Hvis du ved at dine vaerdier er bounded mellem 0 og k, saa laver du et
> array 0..k og taeller hvor mange forekomster af et ciffer i du ser.
> Derefter ligger du data paent ud. Kan goeres i O(n)

Den går svjv. også under navnet "radix"-sort. Ulempen er, at den bruger
mere hukommelse end f.eks. qsort.


mvh.
\\Mikkel Gjøl

---

"Mikkel Gjøl" <s971661@SPAMMESILLYstudent.dtu.dk> wrote in message
news:O0MUb.85703$jf4.5444995@news000.worldonline.dk...
> Jesper Louis Andersen wrote:
> > In article <4022BFE9.9020208@nospam.dk>, Byrial Jensen wrote:
> >>Hvad er counting sort?
> >
> > Hvis du ved at dine vaerdier er bounded mellem 0 og k, saa laver du et
> > array 0..k og taeller hvor mange forekomster af et ciffer i du ser.
> > Derefter ligger du data paent ud. Kan goeres i O(n)
>
> Den går svjv. også under navnet "radix"-sort. Ulempen er, at den bruger
> mere hukommelse end f.eks. qsort.
>
>
> mvh.
> \\Mikkel Gjøl

http://www.nist.gov/dads/HTML/countingsort.html

mvh
Michael Rasmussen

---

In article <O0MUb.85703$jf4.5444995@news000.worldonline.dk>, Mikkel Gjøl wrote:
> Den går svjv. også under navnet "radix"-sort. Ulempen er, at den bruger
> mere hukommelse end f.eks. qsort.

radixsort er noget helt andet. Du kigger paa radix af dine tal. Det
simple eksempel med radix 10 og d cifre:

RADIX-SORT(A, d)
for i <- 1 to d
do use a stable sort to sort array A on digit i

Den kan man godt presse ned paa Theta(n), hvis man vaelger sine
vaerdier rigtigt. Hvis din stable sort er in-place, ja, saa.

--
j.

---

Jesper Louis Andersen wrote:
> In article <4022BFE9.9020208@nospam.dk>, Byrial Jensen wrote:
>
>>>Skal der laves rigtigt mange beregninger, saa kan man
>>>muligvis godt goere det i O(n) tid med en counting sort.
>>
>>Hvad er counting sort?
>
> Hvis du ved at dine vaerdier er bounded mellem 0 og k, saa laver du et
> array 0..k og taeller hvor mange forekomster af et ciffer i du ser.
> Derefter ligger du data paent ud. Kan goeres i O(n)

O.k., den sortering kender jeg godt. Jeg kunne bare ikke forestille mig
at det var det du tænkte på, når vi har fået vide at der bruges flydende
komma-tal.

Men opgaven kan sagtens løses i O(n) uden sortering overhovedet:
Løb tallene igennem 1 gang idet
1) antal tal tælles,
2) tallene summeres,
3) Der laves en liste over de 5 mindste,
4) Der laves en liste over de 5 største.
Til slut trækkes værdierne af de mindste og største tal fra summen,
og der deles med det resterende antal tal.

Jeg tror bare ikke besværet ved den metode kan betale sig.

---

In article <402430D2.8040201@nospam.dk>, Byrial Jensen wrote:

> O.k., den sortering kender jeg godt. Jeg kunne bare ikke forestille mig
> at det var det du tænkte på, når vi har fået vide at der bruges flydende
> komma-tal.

Doh! Det havde jeg overset. Saa virker det ikke.

> Men opgaven kan sagtens løses i O(n) uden sortering overhovedet:
> Løb tallene igennem 1 gang idet
> 1) antal tal tælles,
> 2) tallene summeres,
> 3) Der laves en liste over de 5 mindste,
> 4) Der laves en liste over de 5 største.
> Til slut trækkes værdierne af de mindste og største tal fra summen,
> og der deles med det resterende antal tal.
>
> Jeg tror bare ikke besværet ved den metode kan betale sig.

Hvis dine lister over de 5 mindste og 5 stoerste er heaps, saa kan du
endda lave det i et gennemloeb af listen. Og uden postwork i form af
at traekke tal fra din sum. Men vi er enige om at det ikke kan betale
sig overhovedet for n = 40.


--
j.