Progblemet #7 - sortering

Inser exakt vad du säger och har nu justerat black-box-mätningen så den skapar en WhereArrayIterator(). Det är faktiskt värre än man kunde ana, visar sig att tiden det tar att anropa Count() är O(N) men N referera inte till storleken på resultatet från Where() utan från indata. WTF! Det betyder att man inte kan komma runt prestandaproblemen genom att se till att lägga de filter som tar bort många element tidigt i pipeline:en.

Skulle hävda att dessa saker gör LINQ broken-by-implementation för alla former av icke-trivial manipulation av även rätt små data-set (qsort havererar redan vid 10k element). Att anropa Count() en enda gång på en WhereArrayIterator() med 1M element tar 10ms på min laptop (Sandy Bridge på 3.1GHz). 10ms är eoner av tid, man hinner t.ex. sortera 100k element på den tiden med QuickSort/MergeSort om man skippar LINQ...

Visst kan man hävda att jag använder LINQ på ett felaktigt sätt, men faktum kvarstår att jag kan skriva exakt samma logik i Clojure, Erlang (ska lägga till exempel i detta språk) och även i C++ via biblioteket CppLinq och få något som är minst 1000 gånger snabbare. Så kritiken mot att LINQ är slött är definitivt inte obefogad, man kan inte heller hävda att idéerna bakom LINQ är broken-by-design då de bevisligen fungerar och är effektiva i andra implementationer.

Med CppLinq kan man implementera QuickSort t.ex. så här i C++

  vector<int> quick_sort(const vector<int>& v)
  {
      // detta är naturligtvis onödigt, kan ju köra .size() på 'v', men vill var så nära C#/LINQ varianten som möjligt
      auto c = from(v);
      if (c >> count() <= 1)
          return v;

      auto pivot = c >> first_or_default();
      auto rest = c >> skip(1);
      auto lo = quick_sort(rest >> where([pivot](int e) { return e <= pivot; }) >> to_vector());
      lo.push_back(pivot);
      auto hi = quick_sort(rest >> where([pivot](int e) { return e > pivot; }) >> to_vector());
      copy(begin(hi), end(hi), back_inserter(lo));
      return lo;
  }

och hastigheten är ungefär 3-4 gånger långsammare än att jobbar direkt med råa arrayer

Ruby är verkligen ett språk som borde få mer uppmärksamhet, det lever lite i skuggan av Python. Var själv en som länge tyckte Python var det enda skript-språk man behöver, så ingen poäng att lära sig Ruby. Men har tittat en del på Ruby under detta år och måste säga att jag personligen tycker Ruby är ett mer genomtänkt språk än Python och kommer använda Ruby i framtiden i det lägen skriptspråk är det bästa valet.

Tror att av alla varianter som postas så är det nog ingen som är så lätt att förstå som Erlang, eller Haskell är på samma nivå.

QuickSort

quick_sort([]) -> [];
quick_sort([Pivot|Rest]) ->
    {L,H} = lists:partition(fun(E) -> E < Pivot end, Rest),
    quick_sort(L) ++ [Pivot] ++ quick_sort(H).

Man ser precis delar, dela upp input i det om som är mindre resp. större än avgränsningselementet, sortera delarna och sätt ihop. Tog 1.29s att sortera 1M element [0..1G].

MergeSort

merge(L, []) ->
    L;
merge([], R) ->
    R;
merge([H|Lrest], R) when H < hd(R) ->
    [H | merge(Lrest, R)];
merge(L, [H|Rrest]) ->
    [H | merge(L, Rrest)].

merge_sort([]) ->
    [];
merge_sort([E]) ->
    [E];
merge_sort(L) ->
    Middle = trunc(length(L) / 2),
    {F,B} = lists:split(Middle, L),
    merge(merge_sort(F), merge_sort(B)).

Även här ser man enkelt logiken, tom lista eller lista med ett element är redan sorterad, annars delar man listan på mitten, sorterar delarna och merge:ar ihop dem. Tog 0.86s för 1M element [0..1G] (fast distribution av element är irrelevant för MergeSort).

InsertSort

isort(Sorted,[]) -> 
    Sorted;
isort(Sorted,[Elem|Unsorted]) ->
    {L,H} = lists:partition(fun(E) -> E < Elem end, Sorted),
    isort(L ++ [Elem] ++ H, Unsorted).

insert_sort(L) -> 
    isort([],L).

Börja med en tom sorterad lista och en lista med osorterad element. När det inte finns några osorterade element kvar är man klar. I varje steg letar man på var i den sorterade listan första element i den osorterade listan ska läggas in. Tar 1.78s att sortera 10k element (är ju en O(N^2) så 1M element tar lång tid att sortera).

SelectSort

min([Head|[]]) -> 
    Head;
min([Head|Rest]) when Head > hd(Rest) -> 
    min(Rest);
min([Head|Rest]) when Head =< hd(Rest) -> 
    min([Head] ++ tl(Rest)).

ssort(Sorted, []) ->
    Sorted;
ssort(Sorted, Unsorted) ->
    Min = min(Unsorted),
    ssort(Sorted ++ [Min], Unsorted -- [Min]).

select_sort(L) -> 
    ssort([],L).

Även här startar man med en osorterad lista och en sorterad lista (Erlang stödjer inte in-place uppdateringar överhuvudtaget). I varje steg letar man på det minsta elementet i den osorterade listan och lägger det sist i den sorterade listan. Tar 1.94s att sortera 10k element (också O(N^2)).