JavaKod hjälp

http://sv.wikipedia.org/wiki/Pseudokod

Sortera listan med java.util.Arrays och ta de två sista.

En sortering är mer generisk och fungerar även för att ta ut de n största (eller minsta) talen, den har minimal felmarginal och den är relativt enkel att förstå. Det tar en aning längre tid men är värt det såvida hastigheten på operationen är den avgörande faktorn.... och vi vet båda två att förebyggande optimering är en dålig ide.

Nu är jag rätt säker på att uppgiften går ut på att faktiskt lösa det hela med "egen" kod. Ska man ge sig på en mer generell lösning är fortfarande sortering av hela indata en dålig lösning då det i bästa fall är O(N*log(N)) vilket är helt onödigt. En precis lika enkelt lösning som kan ta ut de M första talen ur en serie på N element i valfri ordning är att ordna indata som en binärheap O(N) och sedan plocka ur de M första elementen.

I.e. detta har samma tidskomplexitet som att manuellt gå igenom indata och hela tiden spara de två högsta man sett, vilket är den lösning som föreslagits i denna tråd och nog är det TS bör lägga tid på att fullt förstå. Eller för att vara helt korrekt, det är samma tidskomplexitet så länge som M är väsenligt mycket mindre än N. Om man läser ut majoriteten av elementen så konvergerar tidskomplexiteten på denna lösning mot att sortera alla element m.h.a. heap-sort vilket då ger O(N*log(N)).

Via Javas standardbibliotek kan man väldigt enkelt gör en lösning som bygger på en binär-heap via java.util.PriorityQueue.

Exemplet som vajjan länkar till är precis lösningen att sortera hela indata. LINQ är definitivt en totalt cool finess, men det har ett rykte om sig att vara långsamt. LINQ är inte speciellt långsamt, men folk tendera att använda det på sätt som gör långt mer beräkningar än vad som strikt är nödvändigt vilket i många fall spelar liten roll men totalt sänker prestanda när datamängden inte längre är trivialt liten. Har man en serie av LINQ kommandon kommer man även generera en hel del temporära objekt som kommer gör att GCn för en hel del att jobba med, vilket då också sänker skalbarhet över många CPU-kärnor...

Jo du har rätt, uppgiften var att skriva en loop — vilket skulle kunna leda till en helt annan intressant diskussion om rekursion. Själv hade jag aldrig skrivit en loop för en sådan uppgift då det innebär för mycket kladd till ingen nytta.

Att skapa ett binärträd tar väl också O(n log n) om jag inte missminner mig så skillnaden mellan att sortera en befintlig array och skapa en heap borde vara minimal. Fördelen med sorteringen av en array är att man enkelt kan läsa den från bägge håll för att få ut både det största och det minsta värdet.

Om du tar en osorterad serie av något med N element så tar det O(N) att skapa en giltig heap-struktur av detta. Så tidskomplexiteten är bättre än att sortera.

Från C++ make_heap()

Testa gärna själv, här är ett exempel

import java.util.*;

class NHigh {
    static List<Integer> getNums(int cnt) {
        List<Integer> lst = new ArrayList<Integer>();
        Random rnd = new Random(42);
        for (int i = 0; i < cnt; i++)
            lst.add(rnd.nextInt(100));
        return lst;
    }

    static void binaryHeap(int cnt) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(cnt, Collections.reverseOrder());
        pq.addAll(getNums(cnt));
        System.out.println(pq.poll());
        System.out.println(pq.poll());
    }

    static void list(int cnt) {
        List<Integer> sorted = getNums(cnt);
        Collections.sort(sorted, Collections.reverseOrder());
        System.out.println(sorted.get(0));
        System.out.println(sorted.get(1));
    }

    static void measure(String desc, Runnable r) {
        long start = System.nanoTime();
        r.run();
        long end = System.nanoTime();
        System.out.printf("%s: took %dms\n", desc, (end - start) / 1_000_000);
    }

    public static void main(String[] args) {
        final int cnt = 10_000_000;
        for (int _ = 0; _ < 3; _++) {
            measure("Binary Heap", new Runnable() { public void run() { binaryHeap(cnt); } });
            measure("Sort", new Runnable() { public void run() { list(cnt); } });
        }
    }
}

Ändra 10_000_000 till 10000000 om du använder pre Java7 (att kunna använda '_' som separator är extremt trevligt).

Får detta resultat på min gamla MBP körandes Linux under Virtual Box (ja, orkar inte programmera under OSX...). Kör flera gånger då det tar en kort stund för JIT-optimeringen att ställa in sig.

$ java -server NHigh 
99
99
Binary Heap: took 991ms
99
99
Sort: took 2309ms
99
99
Binary Heap: took 669ms
99
99
Sort: took 2237ms
99
99
Binary Heap: took 731ms
99
99
Sort: took 2067ms

Edit: och till TS, denna lösning är inte lämplig att lämna in. Tvivlar på att den blir godkänd givet problembeskrivningen...

En sak jag från egen erfarenhet av system i drift kan säga om rekursion är: använd det inte om du inte är 100% säker på maxdjup (och det är mycket litet) alt. om du bara använder svansrekursion och är säker på att alla kompilator som kan komma ifråga skriver om det till en loop (vilket du i praktiken bara har i språk som kräver sådan typ av optimeringar i sin specifikation, i.e. inte C/C++/Java/C# men Erlang och många Lisp-dialekter garanterar detta).

Jag gillar starkt att använda rekursion då väldigt många problem blir väldigt mycket enklare att lösa så. Men man måste veta exakt vad man håller på med om det handlar om produktionskod och är man minsta osäker så måste man skriva om sin logik så den använder loopar.

Ett språk där rekursion faktiskt skulle gå att använda till väldigt mycket är Go då Go (likt Erlang) allokerar sin stack från heap:en (till skillnad från t.ex. C/C++/Java/C# som har en stack med fix storlek på typiskt någon MB) så du kan ha extremt djupa anropsstackar bara du har mycket RAM tillgängligt. Anledningen till denna design är att man vill kunna starta varje "Go-routine" med 200-300 byte stack (vilket gör det möjligt att i produktionssystem har extremt många "go-rutiner", vilket förenklar "concurrent programming" något enormt) men stacken växer/krymper vid behov (något som måste byggas in i språkets ABI för att det ska vara möjligt).

Borde väl vara bättre med nästlade If, för att undvika en onödig If :).

Skickades från m.sweclockers.com

Ah, sorry då missförstod jag dig!

Och visst är den "manuella" metoden klart snabbast, lade till den till min Java lösning och ändrade antal element till 100000, då får man

Manual: took 0.18ms
BinaryHeap: took 3.19ms
Sort: took 17.61ms

Är ju ~18x snabbare med en ren loop, vilket inte är så konstigt när de andra är långt mer generella än vad som är nödvändigt. Nu vet jag inte vilken maskin du kör på, men är fortfarande förvånad över hur mycket snabbare Java (OpenJDK7 i mitt fall) har blivit än .Net. Jobbade en del i .Net i version 1 och 2 och på den tiden var Java klart långsammare. Mina siffror kommer från en 2.4GHz laptop (2011 år MBP) som kör en virtualiserad (Virtual Box) 64-bitars Linux under OSX och ändå är det mer än dubbelt så snabbt som C#. På en "riktigt" Linux på en i7-2600 så får man

Manual: took 0.10ms
BinaryHeap: took 1.90ms
Sort: took 9.46ms

vilket i.o.f.s visar att det inte verkar vara någon direkt kostnad att köra detta virtualiserat då skillnaden är ungefär den man kan förvänta sig av Nehalem -> Sandy Bridge + högre frekvens.

Se på tusan, jag räknade kallt med att den var n log n då n element ska in i heapen på ett arbiträrt djup. Hur kommer det sig att det bara blir O(n), eller väsentligare frågat kanske, vad är det då som skiljer byggandet av en heap från en heap-sort (som, om jag inte missförstått även detta, ska vara just n log n)

Tar du indata [1,2,3,4,5,6,7] och skapar en heap där du vill ha det största talet först får du t.ex. (finns flera giltiga sätt att göra detta till en heap)

[7,6,3,5,4,1,2] eller ritat som ett träd

    7
 6     3
5 4   1 2

I.e. det enda du garanterar är att det högsta elementet hamnar överst och att övriga element uppfyller "heap-property", d.v.s att föräldern alltid "har högre prioritet" (högre numerisk värde i detta fall) än båda sina barn. Att bygga en sådan struktur tar O(N).

För heapsort måste du sedan plocka hur N element och varje sådan operation tar log(N). Så sortering blir O(N + N*log(N)), den linjära komponenten har ingen relevans då den har lägre komplexitet än den andra, så sortering blir O(N*log(N)). Normal sett är heap-sort långsammare än både mergesort och quicksort i praktiken, men alla har samma tidskomplexitet för det genomsnittliga fallet.

Edit: fördelen med heapsort är att den kan sortera på O(N*log(N)) tid med konstant mängd "auxiliary space" (temporärt minne på stacken eller liknande), både mergesort och quicksort behöver "auxiliary space" som är proportionellt mot log(N). Sedan har heapsort och mergesort fördelen att båda har O(N*log(N)) även som "worst case" medan quicksort har O(N^2)).