Sidan 1 av 2 1 2
 
Verktyg Visningsval
2013-02-01, 20:25   #1

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Progblemet #7 - sortering


EDIT: och glömmer alltid skriva detta...
Progblemet är ingen fråga från min sida, det är en helt öppen diskussion kring någon ämne där alla är välkomna att ge sina egna bidrag eller ställa frågor. Tanken är att man ska kunna se hur lösningar på ett problem eller problemområde ser ut i en rad olika programmeringsspråk. Så visa gärna hur man skriver quick sort, shell sort, insert sort eller liknande i Python, C# eller något annat språk du råkar gilla!


Har varit väldigt mycket på jobbet och är fortfarande, så inte riktigt haft tid med något progblemet. Men har tittat in in denna del av forumet till och från och föga oväntat kommer det frågor kring sortering. Så varför inte köra ett progblemet på detta tema.

Det finns väldigt många olika sortering-algoritmer med väldigt olika egenskaper. Noterat att väldigt många frågar om bubble sort, en algoritm som förhoppningsvis aldrig förekommer i produktionskod men den är ändå intressant då implementationen av denna algoritm är typiskt väldigt enkel i språk som är besläktade med C.

Man brukar karakterisera sorteringsalgoritmer enligt följande egenskaper
  • Genomsnittlig tidskomplexitet, d.v.s. om det tar X s att sortera N element, hur lång tid borde det då ta att sortera 10*N element
  • Värsta möjligt tidskomplexitet, samma som ovan om man stoppar in den värsta tänkbara input
  • Utrymmeskomplexitet, hur mycket extra minne behövs för att utföra sorteringen
  • Lite ovanligare, men ibland specificerar man även hur många jämförelser och hur många gånger man måste flytta element som utförs i genomsnitt

Genomsnittlig tidskomplexitet är något man visar med "big-O notation". O(N^2) betyder då att tiden det tar att sortera växer kvadratiskt med storleken på indata medan O(N*log(N)) betyder att tiden växer lite snabbare än storleken på indata (lite förenklat).

Låt oss använda [4,3,1,2] som indata

Bubble-sort är en algoritm som garanterat sorterar in minst ett element på rätt plats varje gång man går igenom data. Det gör det till en O(N^2) algoritm, vilket i sin tur gör den olämplig att sortera något annat än väldigt små data-mängder. Processen är att jämföra två element, om det första elementet ska ligga längre bak så byter man plats på elementen. Om elementen är i rätt ordning jämför man nästföljande par o.s.v. till man når slutet. I det läget vet man att sista elementet ligger på rätt plats och man kan börja om från början.

[4,3,1,2] -> 4 > 3 så byt plats på elementen -> [3,4,1,2] -> [3,1,4,2] -> [3,1,2,4] nummer 4 är nu garanterat på rätt plats
[3,1,2,4] -> [1,3,2,4] -> [1,2,3,4] de två sista elementen är nu garanterat rätt
[1,2,3,4] -> elementen redan på rätt plats, så gå vidare men i detta fall är vi klara


En lite mer praktisk användbar algoritm är quick sort. Det är en algoritm som är O(N*log(N) i genomsnitt, men tyvärr O(N^2) om det vill sig illa. I praktiken går det nästan alltid att undvika det dåliga fallet om man tänker till lite. Denna fungerar så att man väljer ett avgränsnings element, sedan delar man upp indata i två delar
* mindre eller lika med avgränsningselementet
* större än avgränsningselementet
sedan sorterar man varje del för sig. Processen avbryts när indata är ett eller noll element, för i det läget är ju indata redan sorterat

[4,3,1,2] -> i detta fall väljs sista elementet som avskiljare -> [1] [4,3]
[1] är redan sorterad
[4,3] -> [] [4]

Vi har nu [1] 2 [] 3 [4] där de fristående avskiljarna nu ligger i variabler, detta slås ihop till [1,2,3,4]


Ett sista exempel här är merge sort som har den trevliga egenskapen att alltid vara O(N*log(N)). Så varför skulle man då någonsin välja quick sort? Problemet med merge sort är att den fungerar jättebra till länkade listor, men om man vill sortera arrayer så kräver merge sort extra utrymma motsvarande storleken på input, något quick sort inte kräver (bubble sort kräver inte heller det). Processen är att dela indata i två lika stora delar, något som repeteras till dess att indata är ett eller noll element stort

[4,3,1,2] -> [4,3] [1,2] -> [4] [3]  [1] [2]

i detta läge kommer det som gett denna algoritm sitt namn, man måste nu sätta ihop alla delar (merge) i rätt ordning.

[] [4] [3] -> [3] [4] [] -> [3,4] [] []
[] [1] [2] -> [1] [] [2] -> [1,2] [] []
[] [3,4] [1,2] -> [1] [3,4] [2] -> [1,2] [3,4] [] -> [1,2,3] [4] [] -> [1,2,3,4] [] []


Om någon vill visa upp någon annan algoritm kan de ju skriva en kort förklaring om hur den fungerar!

Senast redigerad av virtual void 2013-02-01 klockan 20:44.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-01, 20:28   #2

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Quicksort i Go


Här kommer en variant av quick sort skrivet i Go. Den använder första elementet som avgränsare

func partition(arr []int) ([]int, []int) {
    pivot := arr[0]
    front := 1
    back  := len(arr) - 1

    for front <= back {
        if arr[front] < pivot {
            front++
        } else if (arr[back] >= pivot) {
            back--
        } else {
            arr[front], arr[back] = arr[back], arr[front]
        }
    }

    front--
    arr[0], arr[front] = arr[front], pivot
    return arr[:front], arr[back+1:]
}

func qsort(arr []int) {
    if len(arr) > 1 {
        lo, hi := partition(arr)
        qsort(lo)
        qsort(hi)
    }
}

func main() {
   arr := []int{3,4,1,2}
   qsort(arr)
   fmt.Println(arr)
}
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-01, 20:30   #3

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Merge sort i Go


Och en variant av merge sort i Go. Gjort det väldigt enkelt för mig och allokerar en temporär area som jag sätter ihop resultatet i sedan kopierar jag tillbaka det sorterade resultatet i ursprungs-arrayen.

func merge(result []int, a []int, b []int) {
    scratch := make([]int, len(result))
    ai := 0
    bi := 0
    for i := 0; i < len(result); i++ {
        if ai == len(a) {
            copy(scratch[i:], b[bi:])
            break
        } else if bi == len(b) {
            copy(scratch[i:], a[ai:])
            break
        } else {
            if a[ai] < b[bi] {
                scratch[i] = a[ai]
                ai++
            } else {
                scratch[i] = b[bi]
                bi++
            }
        }
    }
    copy(result, scratch)
}

func msort(arr []int) []int {
    if len(arr) > 1 {
        middle := len(arr) / 2
        merge(arr, msort(arr[:middle]), msort(arr[middle:]))
    }
    return arr
}

func main() {
    arr := []int{4,3,1,2}
    msort(arr)
    fmt.Println(arr)
}
Båda dessa är in-place sorting som är betydligt "snällare" mot CPU-cachen jämfört med om man skapat en ny array där (del)-svaret sparats. Vi kommer säkert få se varianter skrivna i funktionella språk som är betydligt enklare rent kod-mässigt än dessa, men dessa har tyvärr betydligt mycket sämre prestanda än in-place sorting.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-01, 20:45   #4

Mr_no_one

Medlem

Mr_no_ones avatar

Plats: Uppsala

Registrerad: okt 2010

__________________
■║ ASUS P6T Deluxe V2 ║ Intel i7 950 ║ GTX780Ti ║ 24gb DDR3 1600MHz ║ 256GB 840PRO-OS, ~20TB-Data
■║ 3x Hazro HZ27WC-noneGlass
■║ Ultrasone PRO 900 ║ AKG K-701 ║ Matrix M-Stage AMP ║ C421 [OPA2227]
Mr_no_one är inte uppkopplad
2013-02-02, 00:29   #5

nesohc

Medlem

Plats: Västerås

Registrerad: jun 2011

Min favorit sort i Java
    public static void main(String[] args) {
        long[] array = new long[]{10, 4, 2, 3, 7, 5,1};
        for (final long num : array) {
            new Thread(new Runnable() {
                public void run() {
                    try {
                        Thread.sleep(num);
                        System.out.println(num);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }).start();
        }
    }
nesohc är inte uppkopplad
2013-02-02, 12:00   #6

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av nesohc Visa inlägg
Min favorit sort i Java


Faktum är att din algoritm har O(N) som tidskomplexitet och på universitet får man ju lära sig att man ska bara titta på komplexitet och ignorera den konstanta termen, så detta måste ju vara en super-sorterare

Just konstanten gör att det faktiskt finns lägen när till och med bubble-sort kan vara vettig. Gjorde en Amiga-demo för länge, länge sedan och att implementera saker som quick-sort eller liknande i assembler är betydligt mycket mer komplicerat än bubble-sort. Bubble sort behöver bara 3 register, en för yttre loopen, en för inre loopen och en som pekar på det man sorterar. Så ska man sortera <=50-100 element så blir det svårt att slå bubble-sort.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-02, 12:10   #7

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Bubble sort i Go, Quick sort i Haskell och Clojure


Bubble-sort i Go, denna algoritm blir väldigt enkel i princip alla språk som tillåter "mutable" data.
func bubble_sort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
                                arr[j], arr[j+1] = arr[j+1], arr[j]
                        }
                }
        }
}

Quick-sort i Haskell, denna kommer skapa massa kortlivade arrayer under sorteringen vilket gör den långsammare än Go versionen. Att dela upp elementen kommer i detta fall resultera i att man går igenom arrayen två gånger (två anrop till filter).

Men å andra sidan är denna väldigt enkel i kod!
qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (pivot:xs) = (quicksort lo) ++ [pivot] ++ (quicksort hi)
    where
        lo  = filter (<= pivot) xs
        hi = filter (> pivot) xs

Quick-sort i Clojure, även den skapar massa kortlivade arrayer (vektorer) men tack vare group-by så kan man i alla fall dela upp elementen med en enda passering av arrayen.
(defn qsort[lst]
  (if (empty? lst)
    lst
    (let [pivot (first lst)
          parted (group-by (partial >= pivot) (rest lst))]
      (concat (qsort (parted true)) [pivot] (qsort (parted false))))))
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-02, 12:30   #8

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Lite benchmarking


Alltid kul att jämföra saker. Testar att variera två parametrar
  1. storleken på arrayen som ska sorteras
  2. maximala värdet på det slumptal som genereras

För Clojure använder jag detta, tiden som mäts är bara själva sorteringen
Spoiler:
defn qsort[lst]
  (if (empty? lst)
    lst
    (let [pivot (first lst)
          parted (group-by (partial >= pivot) (rest lst))]
      (concat (qsort (parted true)) [pivot] (qsort (parted false))))))

(defn rand-seq[limit]
  (lazy-seq (cons (rand-int limit) (rand-seq limit))))

(doseq [sz [100000 1000000 10000000 2000000]
        limit [10000 1000000000]]
  (println "sz" sz " limit" limit)
  (let [arr (take sz (rand-seq limit))]
       (time (qsort arr))))


För Go kör jag detta, tar inte med Bubble sort mer än i fallet med 100k element då den skalar som O(N^2) så det skulle ta väldigt lång tid med 1M element,
Spoiler:
package main

import (
        "fmt"
        "math/rand"
	"time"
)

func merge(result []int, a []int, b []int) {
        scratch := make([]int, len(result))
	ai := 0
	bi := 0
	for i := 0; i < len(result); i++ {
                if ai == len(a) {
                        copy(scratch[i:], b[bi:])
                        break
	        } else if bi == len(b) {
			copy(scratch[i:], a[ai:])
                        break
		} else {
                        if a[ai] < b[bi] {
	                        scratch[i] = a[ai]
                                ai++
        	        } else {
                                scratch[i] = b[bi]
                                bi++
                        }
        	}
        }
        copy(result, scratch)
}

func msort(arr []int) []int {
        if len(arr) > 1 {
	        middle := len(arr) / 2
                merge(arr, msort(arr[:middle]), msort(arr[middle:]))
        }
	return arr
}

func partition(arr []int) ([]int, []int) {
        pivot := arr[0]
        front := 1
	back  := len(arr) - 1

        for front <= back {
		if arr[front] <= pivot {
                        front++
	        } else if (arr[back] >= pivot) {
                        back--
        	} else {
                        arr[front], arr[back] = arr[back], arr[front]
                }
        }

        front--
        arr[0], arr[front] = arr[front], pivot
        return arr[:front], arr[back+1:]
}

func qsort(arr []int) {
	if len(arr) > 1 {
                lo, hi := partition(arr)
                qsort(lo)
	        qsort(hi)
        }
}

func bubble_sort(arr []int) {
        for i := 0; i < len(arr); i++ {
	        for j := 0; j < i; j++ {
	                if arr[j] > arr[j+1] {
	                        arr[j], arr[j+1] = arr[j+1], arr[j]
			}
	        }
	}
}

func rand_arr(cnt int, limit int) []int {
        arr := make([]int, cnt)
        for i := 0; i < cnt; i++ {
                arr[i] = rand.Intn(limit)
        }
        return arr
}

func do_timed(action func()) float64 {
        start := time.Now()
        action()
        end := time.Now()
        return end.Sub(start).Seconds()
}

func main() {
        k := 1000
        M := k * 1000
        szs := []int{ 100*k, 1*M, 10*M, 20*M }
        limits := []int{ 10*k, 1000*M }

        for _, sz := range(szs) {
                for _, limit := range(limits) {
                        fmt.Println("sz", sz, "limit", limit)
                        arr := rand_arr(sz, limit)

                        fmt.Print("Merge sort:\t")
                        a := make([]int, len(arr))
                        copy(a, arr)
                        fmt.Printf("%.2fs\n", do_timed(func() { msort(a) }))

                        fmt.Print("Quick sort:\t")
                        b := make([]int, len(arr))
                        copy(b, arr)
                        fmt.Printf("%.2fs\n", do_timed(func() { qsort(b) }))

                        if sz <= 100000 {
                                fmt.Print("Bubble sort:\t")
                                c := make([]int, len(arr))
                                copy(c, arr)
                                fmt.Printf("%.2fs\n", do_timed(func() { bubble_sort(b) }))
                        }
                }
                fmt.Println()
        }
}


Clojure:
Quick sort
100k element, 10k gräns -> 0.86s
100k element, 1000M gräns -> 0.51s
1M element, 10k gräns -> 12.5s
1M element, 1000M gräns -> 5.94s
10M element, 10k gräns -> orkar inte vänta så länge
10M element, 1000M gräns -> kraschar med GC overhead limit exceed

Go:
Quick sort
100k element, 10k gräns -> 0.01s
100k element, 1000M gräns -> 0.01s
1M element, 10k gräns -> 0.12s
1M element, 1000M gräns -> 0.10s
10M element, 10k gräns -> 5.06s
10M element, 1000M gräns -> 1.10s
20M element, 10k gräns -> 18.8s
20M element, 1000M gräns -> 2.28s

Merge sort
100k element, 10k gräns -> 0.02s
100k element, 1000M gräns -> 0.02s
1M element, 10k gräns -> 0.23s
1M element, 1000M gräns -> 0.23s
10M element, 10k gräns -> 2.48s
10M element, 1000M gräns -> 2.48s
20M element, 10k gräns -> 4.87s
20M element, 1000M gräns -> 5.34s

Bubble sort
100k element, 10k gräns -> 5.78s
100k element, 1000M gräns -> 5.77s


Notera att quick-sort är känslig för "dålig" input. När man genererar en array med som innehåller relativt många duplicerade värden så kommer quick-sort att bli O(log(N^2)) i de lägena att man har väldigt långa del-arrayer som innehåller samma eller några enstaka värden. Merge sort påverkar i princip inte alls av detta, men är å andra sidan långsammare när indata är "snällt"

Edit: systemet jag kört på är 64-bitars Ubuntu körandes på en Core i7 2760QM (2.4Ghz men när man bara använder en kärna brukar den hålla sig på 3.1GHz).

Senast redigerad av virtual void 2013-02-02 klockan 15:26.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-02, 13:19   #9

tufflax

Medlem

tufflaxs avatar

Plats: Stockholm

Registrerad: jan 2010

Citat:
Ursprungligen inskrivet av virtual void Visa inlägg
Och en variant av merge sort i Go. Gjort det väldigt enkelt för mig och allokerar en temporär area som jag sätter ihop resultatet i sedan kopierar jag tillbaka det sorterade resultatet i ursprungs-arrayen.

...

Båda dessa är in-place sorting som är betydligt "snällare" mot CPU-cachen jämfört med om man skapat en ny array där (del)-svaret sparats. Vi kommer säkert få se varianter skrivna i funktionella språk som är betydligt enklare rent kod-mässigt än dessa, men dessa har tyvärr betydligt mycket sämre prestanda än in-place sorting.
Du sa ju ovan att den inte var in-place. Dessutom kan man i Clojure använda arrayer, precis som i Java om man verkligen vill att det ska gå snabbt. Smutskasta inte funktionella språk!

Senast redigerad av tufflax 2013-02-02 klockan 13:28.
tufflax är inte uppkopplad
2013-02-02, 16:02   #10

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av tufflax Visa inlägg
Du sa ju ovan att den inte var in-place. Dessutom kan man i Clojure använda arrayer, precis som i Java om man verkligen vill att det ska gå snabbt. Smutskasta inte funktionella språk!
Well, beror lite på hur mycket man sträcker på sanningen. Bubble-sort och quick-sort är in-place helt och hållet, det enda jag jämfört mellan språk är quicksort.

Min Go merge-sort kan ses som in-place fast den kräver O(N) extra utrymme, i alla fall för någon som bara är användare av merge() funktionen då in-data och ut-data ockuperar samma minnesarea. Hade den inte varit in-place så hade merge skapat en ny array, vilket är klart enklare att resonera kring men blir långsammare på de CPUer vi har idag. Det går att göra en in-place merge av arrayer på O(1) extra utrymme, men i praktiken är det så pass komplicerat att det ofta blir billigare att allokera minne och sedan göra en kopiering på slutet.

Slutligen kring merge-sort: hade jag i stället sorterat listor så är merge-sort ofta ett väldigt bra val då det är trivialt att göra en in-place merge på O(1) utrymme om input är två listor.

Sedan försöker jag inte smutskasta funktionella språk, min avatar är ju loggan för Clojure som många anser var ett funktionellt språk (själv håller jag inte med, Lisp är inte funktionellt språk, man kan programmera funktionellt, men det kan man i språk som C,Go&C# också). Men den bistra sanningen är att dagens CPUer är byggda på ett sätt som gör att "mutable" strukturer och användning av variabler i stället för värden resulterar i betydligt mycket snabbare kod. För 6-7 år sedan trodda de flesta att funktionella språk skulle lösa problematiken kring hur man programmerar multi-core system (det är brutalt komplicerat om man använder sig av OOP och språk som C++, Java och C#). Och visst är det mycket enklare att programmera multi-core system i funktionella språk, men problemet är att resultatet blir långsamt och i många fall skalar det inte lika bra som vad är möjligt i C/C++.

Visst kan man använda sig av "mutable" i Clojure (det är inte ett funktionellt språk), men vad är poängen med att programmera Clojure då språkets stora styrka är att allt data ska vara ett värde (immutable) och gäller även vektorer/listor som är implementerade som persistent data structure (anses av många att vara den bästa implementationen av "persistent data structure" just nu)?

Det man insett är att problemet med att programmera multi-core system är inte "mutable"-state i sig, det är "mutable"-tillstånd som potentiellt kan refereras från mer än en CPU-kärna. Go är inte på något funktionellt, de som skapat språket ser det tvärt-om som ett modernt C. Men det Go har lagt till är möjligheten att väldigt enkelt kunna dela tillstånd mellan samtida trådar utan att för den delen direkt dela data (som är orsaken till race-buggar i multitrådade C, C++, Java och C# program). Inom en tråd är det inte mer komplicerat att hantera "mutable"-data än det var på 90-talet då vi bara hade en CPU-kärna.

Go, precis som Erlang, bygger på en grundfilosofi som kallas Communicating sequential processes (CSP), vilket betyder att saker delas endast genom att meddelade skickas mellan trådar/processer, inte genom att dela data och skydda data med lås.

Funktionella språk löste samma problem som Erlang/Go löser med meddelanden genom att garantera att data är ett värde (immutable), då behövs inga lås. Problemet är som sagt att sättet man skapar listor och andra former av strukturer blir relativt dyrt givet designen av dagens CPUer.

Tycker inte heller jag smutskastar funktionella språk genom att visa upp hur mycket enklare det är att skriva quicksort i t.ex. Haskell jämfört med Go. Men faktum kvarstår att ingen som skriver program med någon form av prestandakrav (i bemärkelsen lösa CPU-bundna problem) skulle komma på tanken att använda ett funktionellt språk. I vissa lägen är ändå funktionella språk en väldigt bra lösning, även om man har bråttom, kan ju finnas betydligt större flaskhalsar i systemet (*host* databaser, vilket då gör problemet I/O-bundet).
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-02, 18:14   #11

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Java quick-sort och merge sort


Körde motsvarande test på Java-koden nedan. Java var i begynnelsen ökänt för att vara långsamt, något som definitivt inte längre är sant. Sedan Java5 har ett typiskt Java-program kört snabbare än motsvarande C# program, i Java6/7 så har man gjort re-JIT och andra optimeringar än mer aggressiva. Resultatet är att Java ofta ligger på helt samma nivå som motsvarande C++, i vissa lägen kan det faktiskt vara snabbare.

Nackdelen med Java är programmen tenderar vara väldigt minneshungriga, se t.ex. detta där Java typiskt drar 2-20 gånger mer minne jämfört med Go som också är ett språk som använder sig av GC. Men då Java idag främst används på olika former av servers så är det kanske inte ett speciellt stort problem.

Spoiler:
import java.util.Random;

class Sort {
    static void merge(int[] arr, int start, int middle, int end) {
        int len = end - start;
        int alen = middle - start;
        int blen = end - middle;
        int[] scratch = new int[len];
        int ai = 0;
        int bi = 0;
        for (int i = 0; i < len; i++) {
            if (ai == alen) {
                System.arraycopy(arr, middle + bi,
                                 scratch, i,
                                 len - ai - bi);
                break;
            } else if (bi == blen) {
                System.arraycopy(arr, start + ai,
                                 scratch, i,
                                 len - ai - bi);
                break;
            }
            if (arr[ai + start] < arr[bi + middle])
                scratch[i] = arr[start + ai++];
            else
                scratch[i] = arr[middle + bi++];
        }
        System.arraycopy(scratch, 0, arr, start, len);
    }

    static void msort(int[] arr, int start, int end)  {
        if (end - start > 1) {
            int middle = (end - start) / 2 + start;
            msort(arr, start, middle);
            msort(arr, middle, end);
            merge(arr, start, middle, end);
        }
    }

    static void mergeSort(int[] arr) {
        msort(arr, 0, arr.length);
    }

    static int partition(int[] arr, int left, int right) {
        int l = left + 1;
        int r = right;
        int pivot = arr[left];
        int tmp;

        while (l <= r) {
            if (arr[l] < pivot)
                l++;
            else {
                tmp = arr[l];
                arr[l] = arr[r];
        	arr[r] = tmp;
                r--;
            }
        }

        arr[left] = arr[r];
        arr[r] = pivot;

        return r;
    }

    static void qsort(int[] arr, int left, int right) {
        if (right - left > 1) {
            int pivotIdx = partition(arr, left, right);
            qsort(arr, left, pivotIdx - 1);
            qsort(arr, pivotIdx + 1, right);
        }
    }

    static void quickSort(int[] arr) {
	qsort(arr, 0, arr.length - 1);
    }

    static int[] randArr(int cnt, int limit) {
        Random r = new Random();
        int[] arr = new int[cnt];
        for (int i = 0; i < cnt; i++)
            arr[i] = r.nextInt(limit);
        return arr;
    }

    static double doTimed(Runnable action) {
        long start = System.nanoTime();
        action.run();
        long end = System.nanoTime();
        return (end - start) / 1_000_000_000.0;
    }

    public static void main(String []args) {
        int[] szs = new int[]{ 100_000, 1_000_000, 10_000_000, 20_000_000 };
        int[] limits = new int[]{ 10_000, 1_000_000_000 };

        for (int sz: szs)
            for (int limit: limits)
            {
                System.out.printf("sz %d  limit %d\n", sz, limit);
                int[] arr = randArr(sz, limit);

                System.out.print("Merge sort:\t");
                final int[] a = new int[arr.length];
                System.arraycopy(arr, 0, a, 0, arr.length);
                System.out.printf("%.2fs\n", doTimed(new Runnable() {
                        public void run() {
                            mergeSort(a);
                        } }));

                System.out.print("Quick sort:\t");
                final int[] b = new int[arr.length];
                System.arraycopy(arr, 0, b, 0, arr.length);
                System.out.printf("%.2fs\n", doTimed(new Runnable() {
                        public void run() {
                            quickSort(b);
                        } }));

            }
    }
}

Tyvärr kanske det kritiken att Java är ett "pratigt" språk stämmer, fast jämfört med Go (som har ett kortare program) så är det främst avsaknaden av array-slicing som komplicerar merge och partition. Array-siicing finns i språk som Python, Ruby och många andra skript-språk, men det saknas i populära språk som C, C#, Java och C++ (inte helt sant för C++, boost har slices).

Samma maskin som ovan. Java är i genomsnitt något snabbare än Go på merge-sort, men något långsammare på quck-sort. Go i sin tur ligger väldigt nära C/C++, så för sortering av heltal så kan man nog hävda att alla dessa språk leder till program som är ungefär lika snabba.

Java:
Quick sort
100k element, 10k gräns -> 0.02s
100k element, 1000M gräns -> 0.01s
1M element, 10k gräns -> 0.17s
1M element, 1000M gräns -> 0.11s
10M element, 10k gräns -> 9.48s
10M element, 1000M gräns -> 1.27s
20M element, 10k gräns -> 36.28s
20M element, 1000M gräns -> 2.64s

Merge sort
100k element, 10k gräns -> 0.04s
100k element, 1000M gräns -> 0.02s
1M element, 10k gräns -> 0.17s
1M element, 1000M gräns -> 0.16s
10M element, 10k gräns -> 1.72s
10M element, 1000M gräns -> 1.92s
20M element, 10k gräns -> 3.29s
20M element, 1000M gräns -> 3.86s
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-03, 19:15   #12

EuQ

Medlem

Plats: Dalby

Registrerad: jun 2008

Har skrivit några sorteringsalgoritmer i c++ mest för skojs skull, är inte vidare kunnig i c++ så resultaten är antagligen inte så bra som de kan vara.

Insertionsort
Spoiler:
template<typename T>
void Insertionsort(T arr[], int n)
{
	T item;
	int j;
	for(int i = 1; i < n; i++){
		if(arr[i] < arr[i-1])
		{
			item = arr[i];
			j = i;
			while(j > 0 && item < arr[j-1])
			{
				arr[j] = arr[j-1];
				j--;
			}
			arr[j] = item;
		}
	}
}


Selectionsort
Spoiler:
template<typename T>
void Selectionsort(T arr[], int n)
{
	int i, j, min;

	for(i = 0; i < n-1; i++)
	{	
		min = i;
		for(j = i+1; j < n; j++){
			if(arr[j] < arr[min])
				min = j;
		}
		swap(arr[i], arr[min]);
	}
}


Mergesort
Spoiler:
template<typename T>
void Mergesort(T *arr, int left, int right)
{
 	int mid = (left + right)/2;

	if(left<right)
	{
		Mergesort(arr, left, mid);
		Mergesort(arr, mid+1, right);
		Merge(arr, left, mid, right);
	}
}

template<typename T>
void Merge(T *arr, int left, int mid, int right)
{
	T *temp = new T[right-left+1];
	
	int pos = 0, lpos = left, rpos = mid+1;
	
	while(lpos <= mid && rpos <= right)
	{
		if(arr[lpos] < arr[rpos])
			temp[pos++] = arr[lpos++];
		else
			temp[pos++] = arr[rpos++];
	}
	while (lpos <= mid)
		temp[pos++] = arr[lpos++];
	while (rpos <= right)
		temp[pos++] = arr[rpos++];

	for(int i = 0; i < pos; i++)
	{
		arr[i+left] = temp[i];
	}
}


Quicksort
Spoiler:
template<typename T>
void Quicksort(T arr[], int n)
{
	if(n <= 1)
		return;
	int pivot = arr[rand() % n];
	int l = 0;
	int r = n - 1;

	while(l < r)
	{
		while(arr[l] < pivot){
			l++;
		}
		while(arr[r] > pivot){
			r--;
		}
		swap(arr[r], arr[l]);
	}
	Quicksort(arr, l);
	Quicksort(&(arr[l+1]), n - l - 1);
}


Tog tid på upp till 100k element och fick då dessa resultat:

Insertionsort: 1,194s
Selectionsort: 17,03s
Mergesort: 0,117s
Quicksort: 0,0039
EuQ är inte uppkopplad
2013-02-03, 21:02   #13

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av EuQ Visa inlägg
Har skrivit några sorteringsalgoritmer i c++ mest för skojs skull, är inte vidare kunnig i c++ så resultaten är antagligen inte så bra som de kan vara.
Tycker det så bra ut, mer eller mindre skolboksexempel. Finns dock en bugg i Quicksort som gör att den inte hanterar fall där man har duplikat av värden (blir evighetsloop).

Fixade den på detta sätt

Spoiler:
template<typename T>
void Quicksort(T arr[], int n)
{
    if(n <= 1)
        return;
    int pivot_idx = rand() % n;
    int pivot = arr[pivot_idx];
    int l = 0;
    int r = n - 2;

    swap(arr[pivot_idx], arr[n-1]);
    while (l <= r)
    {
        if (arr[l] <= pivot)
     	    l++;
        else if (arr[r] > pivot)
            r--;
	else
            swap(arr[r], arr[l]);
    }
    swap(arr[l], arr[n-1]);

    Quicksort(arr, l);
    Quicksort(&(arr[l+1]), n - l - 1);
}


Noterade att du använder ett slumpmässigt pivot-tal. Det gör att man undviker O(N²) på saker som är sorterade baklänges, men det fixar ändå inte fallet där man har väldigt många tal som har samma värde.

Får följande värden på den dator jag kört alla andra tester på

Spoiler:
sz 100000 limit 10000
Merge sort: 0.02
Quick sort: 0.01
sz 100000 limit 1000000000
Merge sort: 0.01
Quick sort: 0.01
sz 1000000 limit 10000
Merge sort: 0.13
Quick sort: 0.13
sz 1000000 limit 1000000000
Merge sort: 0.14
Quick sort: 0.11
sz 10000000 limit 10000
Merge sort: 1.37
Quick sort: 5.36
sz 10000000 limit 1000000000
Merge sort: 1.65
Quick sort: 1.29
sz 20000000 limit 10000
Merge sort: 2.85
Quick sort: 20.49
sz 20000000 limit 1000000000
Merge sort: 3.41
Quick sort: 2.51

Hela programmet är här
Spoiler:
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <functional>
#include <vector>
#include <time.h>

using namespace std;

template<typename T>
void Insertionsort(T arr[], int n)
{
    T item;
    int j;
    for(int i = 1; i < n; i++){
	if(arr[i] < arr[i-1])
	{
            item = arr[i];
            j = i;
            while(j > 0 && item < arr[j-1])
            {
             	arr[j] = arr[j-1];
		j--;
            }
            arr[j] = item;
	}
    }
}


template<typename T>
void Selectionsort(T arr[], int n)
{
    int i, j, min;

    for(i = 0; i < n-1; i++)
    {
     	min = i;
	for(j = i+1; j < n; j++){
            if(arr[j] < arr[min])
		min = j;
	}
        swap(arr[i], arr[min]);
    }
}

template<typename T>
void Merge(T *arr, int left, int mid, int right)
{
    T *temp = new T[right-left+1];

    int pos = 0, lpos = left, rpos = mid+1;

    while(lpos <= mid && rpos <= right)
    {
        if(arr[lpos] < arr[rpos])
            temp[pos++] = arr[lpos++];
        else
            temp[pos++] = arr[rpos++];
    }
    while (lpos <= mid)
        temp[pos++] = arr[lpos++];
    while (rpos <= right)
        temp[pos++] = arr[rpos++];

    for(int i = 0; i < pos; i++)
    {
        arr[i+left] = temp[i];
    }
}

template<typename T>
void Mergesort(T arr[], int left, int right)
{
    int mid = (left + right)/2;

    if(left<right)
    {
        Mergesort(arr, left, mid);
        Mergesort(arr, mid+1, right);
        Merge(arr, left, mid, right);
    }
}

template<typename T>
void Quicksort(T arr[], int n)
{
    if(n <= 1)
        return;
    int pivot_idx = rand() % n;
    int pivot = arr[pivot_idx];
    int l = 0;
    int r = n - 2;

    swap(arr[pivot_idx], arr[n-1]);
    while (l <= r)
    {
        if (arr[l] <= pivot)
            l++;
        else if (arr[r] > pivot)
            r--;
        else
            swap(arr[r], arr[l]);
    }
    swap(arr[l], arr[n-1]);

    Quicksort(arr, l);
    Quicksort(&(arr[l+1]), n - l - 1);
}

vector<int> randArr(int cnt, int limit)
{
    vector<int> v(cnt);
    generate(begin(v), end(v), [=]() { return rand() % limit; });
    return v;
}

double doTimed(function<void()> action)
{
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    action();
    clock_gettime(CLOCK_MONOTONIC, &end);
    if (end.tv_nsec < start.tv_nsec)
    {
        end.tv_sec  -= 1;
        end.tv_nsec += 1000000000;
    }

    return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1000000000.0;
}

int main(int argc, char *argv[])
{
    auto szs = vector<int>{ 100000, 1000000, 10000000, 20000000 };                                    
    auto limits = vector<int>{ 10000, 1000000000 };                                                   

    cout << fixed << setprecision(2);
    for (auto sz: szs)
        for (auto limit: limits)
        {
            cout << "sz " << sz << " limit " << limit << endl;
            auto arr = randArr(sz, limit);

            cout << "Merge sort:\t";
            vector<int> a;
            copy(begin(arr), end(arr), back_inserter(a));
            cout << doTimed([&](){ Mergesort(a.data(), 0, a.size()); }) << endl;

            cout << "Quick sort:\t";
            vector<int> b;
            copy(begin(arr), end(arr), back_inserter(b));
            cout << doTimed([&](){ Quicksort(b.data(), b.size()); }) << endl;
       }

    return 0;
}


Använt lite C++11, som lambda och array-initializers. Dessa saker är helt klart ett lyft för C++

Ska sammanställa alla tider i ett Excel-ark och posta en länk till grafen, kanske inte händer i dag bara. Rent generellt verkar C++ ligga ungefär på samma nivå som Go och Java, vilket är precis vad man kan förvänta sig.

Edit: Merge sort tiderna var lite lustiga för C++, inser nu att Merge funktionen läcker minne, så det kan förklara varför programmet beter sig lite skumt. Saknas ett delete temp. Har uppdaterat tiderna.

Senast redigerad av virtual void 2013-02-03 klockan 22:11.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-03, 21:29   #14

Doodle

Medlem

Doodles avatar

Plats: Norrbotten

Registrerad: aug 2003

Vad rolig tråd. Jag besitter lite testdata från bubble sort, selection sort och quick sort. Selection och bubble sort är lite småtrista men den här implementationen (c++) av Quicksort använde jag:

Spoiler:
void quickSort(double *arr, int left, int right) {

      int i = left, j = right;
      double tmp;
      double pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j)
	  {
            while (arr[i] < pivot)
		  i++;

            while (arr[j] > pivot)
                  j--;

            if (i <= j)
	    {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}
Fråga mig inte vad jag tänkte med doubles.. Jag tror det blev kvar efter lite felsökning

Testresultat:
Spoiler:
Citat:
n = 1 000 000

RANDOM numbers
Antal element tid (ms)
1n 7
2n 14
3n 21
4n 29
5n 35
6n 42
7n 49
8n 55
9n 62
10n 70

DESCENDING numbers (99 98 97 96 ....)
Antal element tid (ms)
1n 16
2n 30
3n 48
4n 64
5n 84
6n 105
7n 122
8n 137
9n 154
10n 176

INCREASING numbers (1 2 3 4 5 ....)
Antal element tid (ms)
1n 16
2n 31
3n 49
4n 64
5n 83
6n 104
7n 119
8n 134
9n 154
10n 172

EQUAL numbers ( 1 1 1 1 .... )
Antal element tid (ms)
1n 17
2n 37
3n 59
4n 79
5n 104
6n 127
7n 150
8n 167
9n 203
10n 220
Om det mot förmodan skulle finnas intresse för bubble sort och slection sort kan lägga upp det också

Jag har även grafer för alltihopa, om det skulle vara kul.

Senast redigerad av Doodle 2013-02-03 klockan 21:38.
Doodle är inte uppkopplad
2013-02-03, 22:44   #15

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Jämförelse mellan lite olika språk. Har normalisera värdena så att högre stapel är bättre. Den snabbaste har alltid värdet 1.0 och om det tog dubbel så lång tid får man värdet 0.5 o.s.v. Tider för 100k element kan man ignorera, det var så korta tider att mätningen inte blir vettig.

Spoiler:



C# koden är en direkt översättning från Java-koden. Testa också att göra en QuickSort som använde LINQ för uppdelningen, likt hur jag gjorde i Clojure. Det fungerar men blev tokslött, mycket långsammare än Clojure (typ 10-100 gånger långsammare). Här är LINQ varianten om någon vill testa
Spoiler:
static IEnumerable<int> linqQsort(IEnumerable<int> arr)
    {
    if (arr.Count() <= 1)
        return arr;
    var pivot = arr.First();
    var rest = arr.Skip(1);
    return linqQsort(rest.Where(n => n <= pivot)).Concat(new int[]{pivot}.Concat(linqQsort(rest.Where(n => n > pivot))));
}


Här är hela C#-programmet
Spoiler:
using System.Text;
using System.Threading.Tasks;

namespace progblemet7_sorting
{
    class Program
    {
        static void merge(int[] arr, int start, int middle, int end)
        {
            var len = end - start;
            var alen = middle - start;
            var blen = end - middle;
            var scratch = new int[len];
            var ai = 0;
            var bi = 0;
            for (var i = 0; i < len; i++)
            {
                if (ai == alen)
                {
                    Array.Copy(arr, middle + bi,
                               scratch, i,
                               len - ai - bi);
                    break;
                }
                else if (bi == blen)
                {
                    Array.Copy(arr, start + ai,
                               scratch, i,
                               len - ai - bi);
                    break;
                }
                if (arr[ai + start] < arr[bi + middle])
                    scratch[i] = arr[start + ai++];
                else
                    scratch[i] = arr[middle + bi++];
            }
            Array.Copy(scratch, 0, arr, start, len);
        }

        static void msort(int[] arr, int start, int end)
        {
            if (end - start > 1)
            {
                var middle = (end - start) / 2 + start;
                msort(arr, start, middle);
                msort(arr, middle, end);
        	merge(arr, start, middle, end);
            }
	}

        static void mergeSort(int[] arr)
        {
            msort(arr, 0, arr.Length);
        }


        static int partition(int[] arr, int left, int right)
        {
            var l = left + 1;
            var r = right;
            var pivot = arr[left];
            int tmp;

            while (l <= r)
            {
                if (arr[l] < pivot)
                    l++;
                else
                {
                    tmp = arr[l];
                    arr[l] = arr[r];
                    arr[r] = tmp;
                    r--;
                }
            }

            arr[left] = arr[r];
            arr[r] = pivot;

            return r;
        }

        static void qsort(int[] arr, int left, int right)
        {
            if (right - left > 1)
            {
                int pivotIdx = partition(arr, left, right);
                qsort(arr, left, pivotIdx - 1);
                qsort(arr, pivotIdx + 1, right);
            }
        }

        static void quickSort(int[] arr)
        {
            qsort(arr, 0, arr.Length - 1);
        }

        static int[] randArr(int cnt, int limit)
        {
            var r = new Random();
            var arr = new int[cnt];
            for (var i = 0; i < cnt; i++)
                arr[i] = r.Next(limit);
            return arr;
        }

        delegate void TimedAction();

        static double doTimed(TimedAction action) {
        var start = DateTime.Now;
        action();
        var elapsed = DateTime.Now - start;

        return elapsed.Seconds + elapsed.Milliseconds / 1000.0;
    }

        static void Main(string[] args)
        {
            var szs = new int[]{ 1000, 10000, 100000, 200000 };
            var limits = new int[]{ 10000, 1000000000 };

            foreach (var sz in szs)
                foreach (var limit in limits)
                {
                    Console.Out.WriteLine("sz {0}  limit {1}", sz, limit);
                    int[] arr = randArr(sz, limit);

                    Console.Out.Write("Merge sort:\t");
                    var a = new int[arr.Length];
                    Array.Copy(arr, 0, a, 0, arr.Length);
                    Console.Out.WriteLine("{0:F2}s", doTimed(() => mergeSort(a)));

                    Console.Out.Write("Quick sort:\t");
                    var b = new int[arr.Length];
                    Array.Copy(arr, 0, b, 0, arr.Length);
                    Console.Out.WriteLine("{0:F2}s", doTimed(() => quickSort(b)));
                }
        }
    }
}


Jag körde C# med Visual Studio 2012 på 64-bitars Win8 Pro. Testade även att köra Java-koden och den var väldigt nära samma program körandes på 64-bitars Linux, skilde typ 10% till Linux fördel. Så Java7 är faktiskt nära nog dubbelt så snabbt som .Net 5 just i detta fall. Säger inte att skillnaden är så stor alltid, men min erfarenhet är att Java6/7 har blivit rejält snabbt och är typiskt alltid lika snabbt eller snabbare än motsvarande C#/.Net program.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-04, 00:11   #16

Teknocide

Medlem

Plats: i din garderob

Registrerad: sep 2007

Citat:
Ursprungligen inskrivet av virtual void Visa inlägg
Jämförelse mellan lite olika språk. Har normalisera värdena så att högre stapel är bättre. Den snabbaste har alltid värdet 1.0 och om det tog dubbel så lång tid får man värdet 0.5 o.s.v. Tider för 100k element kan man ignorera, det var så korta tider att mätningen inte blir vettig.

C# koden är en direkt översättning från Java-koden. Testa också att göra en QuickSort som använde LINQ för uppdelningen, likt hur jag gjorde i Clojure. Det fungerar men blev tokslött, mycket långsammare än Clojure (typ 10-100 gånger långsammare).
IEnumerable har inte någon uppfattning om sin storlek. Ett anrop till .Count() innebär att varje element itereras över. Då detta görs i en tight loop blir resultatet som du så passande uttrycker det "tokslött" :-)

Edit: samma sak med partitioneringen; det blir dubbelt jobb för att hämta ut större och mindre tal.

Jag kan fixa en version i Scala som du kan benchmarka om det verkar intressant :-)
Skickades från m.sweclockers.com

Senast redigerad av Teknocide 2013-02-04 klockan 00:19.
__________________
Bilanaloger är som Volvo — varenda svenne kör med dem
Teknocide är uppkopplad nu
2013-02-04, 16:33   #17

Flostyle

Medlem

Registrerad: sep 2010

ExchangeSort i C#


public static void ExchangeSort(int[] vektor)
{
       for (int i = 0; i < vektor.Length -1; i++)
       {
             int minst = i;
             for (int j = i + 1; j < vektor.Length; i++)
             {
                   if (vektor[minst] > vektor[j])
                      minst = j;
             }

              if (i < minst)
                 Swap(vektor, minst, i);
        }
}

public static void Swap(int[] vektor, int a, int b )
{
     int r = vektor[a];
     vektor[a] = vektor[b];
     vektor[b] = r;
}
Flostyle är inte uppkopplad
2013-02-04, 20:13   #18

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av Teknocide Visa inlägg
IEnumerable har inte någon uppfattning om sin storlek. Ett anrop till .Count() innebär att varje element itereras över. Då detta görs i en tight loop blir resultatet som du så passande uttrycker det "tokslött" :-)

Edit: samma sak med partitioneringen; det blir dubbelt jobb för att hämta ut större och mindre tal.

Jag kan fixa en version i Scala som du kan benchmarka om det verkar intressant :-)
Skickades från m.sweclockers.com
När jag såg din kommentar om IEnumerable så tänkte jag först: ah, du har rätt. Men sen började jag fundera, om det vore så visar det att MS totalt missförstått konceptet att frikoppla interface från konkret implementation. För varför skulle en array som implementerar IEnumerable inte ha ett Count() anrop som är O(1)???

Rent generellt kan man inte anta att Count() är O(1), i många fall kanske den faktiskt är O(N), men det finns ingen rimligt anledning varför den skulle vara det i mitt fall.

Skrev lite testkod där mäter kostnaden av att anropa Count() på en underliggande int[] och precis som jag misstänkte så är inte MS idioter. Det är en konstant-tid operation (och en extrem snabb sådan) i just detta fall.

Du har helt rätt i att man måste gå igenom arrayen två gånger när man använder Where(), min första implementation använde faktiskt GroupBy() just för att undvika detta men det var ännu långsammare.
Hur långsamt är det då? Att sortera 10k element tar ganska exakt 20s och äter ungefär 20M RAM....

Problemet verkar vara att LINQ skapar tusen och åter tusen små temporära objekt så GCn får slita ihjäl sig. LINQ är helt enkelt inte rätt verktyg här och det är nog just när folk testat att göra saker likt detta de har klagat på LINQ att leda till långsamma program. Och helt fel är inte kritiken, jag använder faktiskt samma angreppssätt i Clojure som ändå fixade 100k element på ungefär en halv sekund (så Clojure är närmare 1000 gånger snabbare än de 10-100 jag höftade till med ovan).
Personligen gillar jag dock LINQ skarpt, det är trots allt en riktigt trevlig Lisp feature i C#-smak!

Skulle vara väldigt intressant att se vad Scala presterar här och då med en implementation som är "bra" Scala och inte bara Java-implementation med Scala-syntax
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-04, 21:43   #19

MugiMugi

Medlem

MugiMugis avatar

Plats: Borås

Registrerad: jul 2004

Har ont om tid denna vecka annars hade jag implementerat en unsafe C# variant, lite sugen på vilken prestanda man kan få med pekare istället, om du har tid kan du fixa din variant med det? http://msdn.microsoft.com/en-us/libr...(v=vs.71).aspx Samt denna är av intresse också http://msdn.microsoft.com/en-us/libr...s.marshal.aspx

Vist detta bryter lite mot C# traditionen men vet man att sina klasser passerar testerna så bygg in det i en dll och inkludera in i ett safe projekt Klart. är dock lite nyfiken på vad C# klarar att prestera med det dock.

Sedan när det gäller C# använd inte DateTime för att mäta tid, använd StopWatch du får otroligt bättre precision, DateTime är lite mandom precision på.

--

Samt jo LINQ är mer praktiskt för att arbeta med större data sets, inte precis göra beräkningar som sortering, man kan få ner antal kod rader något enormt med LINQ med en kostnad av liten CPU förlust, åt andra sidan mindre kod gör det lättare att underhålla och i sin tur mindre chanser för buggar, det sagt så lämpar sig inte linq till allt.

Senast redigerad av MugiMugi 2013-02-04 klockan 21:55.
__________________
Speldator: SB i7-2600k @ 4,5Ghz P8Z68-V Pro, 8GB DDR3, Plextor M3 Pro 128GB. AMD Radeon R9 280X
Arbetsdator: IB i7-3770k Z77A-GD65, 16GB DDR3, 2x Corsair Force GT 120GB.
Server 1: SB 2500k, MZI -P67GD55, 32GB DDR3, Corsair MX 240GB SSD
Tablet: Surface Pro, Konsoler: PS4, PS3, Xbox 360, Wii U, PS Vita, 3DSXL, PS2, Xbox, +++
MugiMugi är uppkopplad nu
2013-02-04, 22:28   #20

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av MugiMugi Visa inlägg
text
Kan bli lite tid över någon kväll senare i veckan, ska titta på det då.

Men kom ihåg att jag inte är en C# expert. Håller mig mest uppdaterad kring .Net/C# för jag anser att det är en för stor/viktigt plattform att ignorera, men vare sig språk eller plattform är någon större favorit, hade därför totalt missat Stopwatch. Sedan står det att om man inte har en HPET i sin dator så använder Stopwatch DateTime internt, men jag har en HPET i denna dator med en upplösning på 1ns (är den som används för att mäta tiden i C++ versionen via clock_gettime()). Ska ändra till den, men då tiderna det handlar om här är 100-tals millisekunder upp till 10-tals sekunder så är jag rätt säker på att eventuellt mätfel i DateTime kan ignoreras

Visst är LINQ otroligt smidigt i vissa fall, men det är lite oroväckande när det är runt 1000 gånger långsammare än i princip samma logik skrivet i Clojure vars implementation i sin tur är runt 50 gånger långsammare än"mutable" varianterna i C++/C#/Java/Go. Skulle vara intressant att se hur Scala står sig om man kör med exakt samma logik där. Normalt sett är Scala-program snabbare än motsvarande Clojure, men Clojures implementation av "persistent data structures" är som sagt nog den bästa som går att hitta, vilket gör att hantering av containers som värden är relativt sett väldigt effektivt i Clojure.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-04, 22:35   #21

vmattsson

Medlem

Registrerad: okt 2012

Liten shellsort i Java skriven direkt från psuedokod!
public int[] shellSort(int[] n){
	int i, j;
	int temp;
	int inc = n.length >>> 1;
	while(inc > 0){
		for(i = 0; i < n.length; i++){
			temp = n[i];
			j = i;
			while(j >= inc && n[j-inc] > temp){
				n[j] = n[j-inc];
				j = j-inc;
			}
			n[j] = temp;
		}
		inc = (int)Math.round(inc/2.2);
	}
	return n;
}
Shellsort må kanske inte vara speciellt bra men jag gillar den. Simpel som insertionsort men bättre i många fall.
vmattsson är inte uppkopplad
2013-02-04, 23:28   #22

Teknocide

Medlem

Plats: i din garderob

Registrerad: sep 2007

Citat:
Ursprungligen inskrivet av virtual void Visa inlägg
När jag såg din kommentar om IEnumerable så tänkte jag först: ah, du har rätt. Men sen började jag fundera, om det vore så visar det att MS totalt missförstått konceptet att frikoppla interface från konkret implementation. För varför skulle en array som implementerar IEnumerable inte ha ett Count() anrop som är O(1)???

Rent generellt kan man inte anta att Count() är O(1), i många fall kanske den faktiskt är O(N), men det finns ingen rimligt anledning varför den skulle vara det i mitt fall.

Skrev lite testkod där mäter kostnaden av att anropa Count() på en underliggande int[] och precis som jag misstänkte så är inte MS idioter. Det är en konstant-tid operation (och en extrem snabb sådan) i just detta fall.
Jag är inte så säker på det där.

IEnumerable har ingen egen Count(); den får metoden genom extensions i Enumerable. Dvs, oavsett vilken typ av IEnumerable du skickar in är det Enumerable.Count() som tar hand om jobbet. Enumerable.Count() kan göra en massa instanceof-checkar (fult) för att försöka lista ut vilken den egentliga typen är, men i första rekursionen går typen förlorad i och med anropet till .Where() som returnerar en ny IEnumerable<int>. Det borde iofs gå att undvika med en .ToArray() på slutet.

Citat:
Ursprungligen inskrivet av virtual void Visa inlägg
Skulle vara väldigt intressant att se vad Scala presterar här och då med en implementation som är "bra" Scala och inte bara Java-implementation med Scala-syntax
Då sätter jag ihop något inom kort
__________________
Bilanaloger är som Volvo — varenda svenne kör med dem
Teknocide är uppkopplad nu
2013-02-05, 07:34   #23

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av Teknocide Visa inlägg
Jag är inte så säker på det där.

IEnumerable har ingen egen Count(); den får metoden genom extensions i Enumerable. Dvs, oavsett vilken typ av IEnumerable du skickar in är det Enumerable.Count() som tar hand om jobbet. Enumerable.Count() kan göra en massa instanceof-checkar (fult) för att försöka lista ut vilken den egentliga typen är, men i första rekursionen går typen förlorad i och med anropet till .Where() som returnerar en ny IEnumerable<int>. Det borde iofs gå att undvika med en .ToArray() på slutet.
Det är sant att metoderna för IEnumerable implementeras via "extensions methods" (i System.Linq.Enumerable), men polymorfism är möjligt även på "extensions methods" så det finns ingen anledning att förstöra information om typen då det dels skulle paja möjligheten till O(1) Count på t.ex. arrayer. Enligt både min black-box mätning (mätte tiden att en rad gånger köra Count() på arrayer med längden 10M, 100M, 1000M och 10000M) och enligt detta svar på stack-overflow så är Count() konstant tid om underliggande typ tillåter.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-05, 08:50   #24

Ernesto

Medlem

Plats: Stockholm

Registrerad: aug 2005

Jag kan vara ute och cykla nu, men är det inte så att så länge man använder typade collections går det bra som fisken att köra .Count() (Implementerar .Count eftersom det går - Att kolla om det går tar ju bara nån ms om ens det), typ Dictionary<> och List<>. Kör man en .Count() på en var från nån select eller liknande, tyggar det lite långsammare?
__________________
Intel 2500K @ 4.6Ghz | Asus Matrix 7970 Crossfire | Asus P8P67-Pro | Antec P183 |
Eyefinity 3x Dell u2312hm | Corsair HX 750w | 2x Intel 320 240GB SSD | 3 x Mekanisk HDD
Ernesto är inte uppkopplad
2013-02-05, 09:13   #25

Teknocide

Medlem

Plats: i din garderob

Registrerad: sep 2007

Citat:
Ursprungligen inskrivet av virtual void Visa inlägg
Det är sant att metoderna för IEnumerable implementeras via "extensions methods" (i System.Linq.Enumerable), men polymorfism är möjligt även på "extensions methods" så det finns ingen anledning att förstöra information om typen då det dels skulle paja möjligheten till O(1) Count på t.ex. arrayer. Enligt både min black-box mätning (mätte tiden att en rad gånger köra Count() på arrayer med längden 10M, 100M, 1000M och 10000M) och enligt detta svar på stack-overflow så är Count() konstant tid om underliggande typ tillåter.
Som du ser försöker .Count() downcasta till rätt typ. Polymorfism i den vanliga betydelsen är inte möjligt på extensionmetoder eftersom dessa är statiska och därför inte overrideable.

När du kör Where() på en array får du tillbaka en WhereArrayIterator<Int32> som även den saknar definierad längd. Det är denna du sedan skickar in i qsort igen. För att få ut längden av en WhereArrayIterator behöver man itererera, se http://stackoverflow.com/questions/7...answer-7269655
__________________
Bilanaloger är som Volvo — varenda svenne kör med dem
Teknocide är uppkopplad nu
2013-02-05, 09:29   #26

Ernesto

Medlem

Plats: Stockholm

Registrerad: aug 2005

Men varför kör ni med Arrayer och inte List (eller Dictionary) istället?
__________________
Intel 2500K @ 4.6Ghz | Asus Matrix 7970 Crossfire | Asus P8P67-Pro | Antec P183 |
Eyefinity 3x Dell u2312hm | Corsair HX 750w | 2x Intel 320 240GB SSD | 3 x Mekanisk HDD
Ernesto är inte uppkopplad
2013-02-05, 11:47   #27

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av Ernesto Visa inlägg
Men varför kör ni med Arrayer och inte List (eller Dictionary) istället?
Mest för att avgränsa det lite. Men du har naturligtvis en poäng, kör man med listor så skulle t.ex. MergeSort blir både enklare och effektivare medan QuickSort skulle bli väldigt ineffektivt. Samma sak med InsertSort, blir ju en massa kopierande om man har en array medan det blir väldigt naturligt om man har listor (som att sortera in kort från vänster hand till ett sorterat set i höger hand).

Men med "rätt" algoritm så är det i princip alltid betydligt snabbare att sortera en array än att sortera en lista. Listor orsakar långt mycket fler minnesaccesser som nödvändigtvis inte ligger bredvid varandra i minne, vilket inte gillas av CPU-cache -> långsammare.

Hur man skulle använda Dictionary begriper jag inte riktigt. En sådan använder man för att mappa en nyckel till ett värde, vill man även att saker ska vara sorterade väljer man något form av självbalanserat träd.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-05, 12:21   #28

Ernesto

Medlem

Plats: Stockholm

Registrerad: aug 2005

Aha! Tack för den lektionen!

Ända sen jag bytte från php till C# försöker jag använda så mycket typat som möjligt, är så otroligt trevligt om man jämför med hur det var att arbeta med alla förbenade arrayer i php hehe.
__________________
Intel 2500K @ 4.6Ghz | Asus Matrix 7970 Crossfire | Asus P8P67-Pro | Antec P183 |
Eyefinity 3x Dell u2312hm | Corsair HX 750w | 2x Intel 320 240GB SSD | 3 x Mekanisk HDD
Ernesto är inte uppkopplad
2013-02-05, 13:05   #29

Teknocide

Medlem

Plats: i din garderob

Registrerad: sep 2007

Citat:
Ursprungligen inskrivet av Ernesto Visa inlägg
Aha! Tack för den lektionen!

Ända sen jag bytte från php till C# försöker jag använda så mycket typat som möjligt, är så otroligt trevligt om man jämför med hur det var att arbeta med alla förbenade arrayer i php hehe.
Ordvrängerivarning här, men allting i C# är typat. Samma grej med PHP, fast man brukar kalla typmodellen "loosely typed" när man till exempel kan jämföra objekt över typgränser.
__________________
Bilanaloger är som Volvo — varenda svenne kör med dem
Teknocide är uppkopplad nu
2013-02-05, 20:52   #30

Tiaitchsi

Medlem

Tiaitchsis avatar

Registrerad: sep 2011

En variant av quicksort i Ruby:

def quicksort(list)
	if list.size <= 1
		return list
	end
	pivot = list.sample
	left, right = list.partition { |e| e < pivot }
	quicksort(left) + quicksort(right)
end
Simpelt språk!
Tiaitchsi är inte uppkopplad
Senaste nyheterna

Redaktionens senaste nyhetsrubriker

Sök jobb