Sidan 2 av 2 1 2
 
Verktyg Visningsval
2013-02-05, 21:02   #31

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av Teknocide Visa inlägg
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
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++
Spoiler:
  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
Spoiler:
sz 100000 limit 10000
Quick sort: 0.03
sz 100000 limit 1000000000
Quick sort: 0.03
sz 1000000 limit 10000
Quick sort: 0.53
sz 1000000 limit 1000000000
Quick sort: 0.35
sz 10000000 limit 10000
Quick sort: 21.42
sz 10000000 limit 1000000000
Quick sort: 3.96
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-05, 21:07   #32

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Citat:
Ursprungligen inskrivet av Tiaitchsi Visa inlägg
En variant av quicksort i Ruby:

Simpelt språk!
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.
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-05, 21:31   #33

Yoshman

Datavetare

Yoshmans avatar

Plats: Stockholm

Registrerad: jun 2011

Erlang


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
Spoiler:
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
Spoiler:
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
Spoiler:
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
Spoiler:
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)).
__________________
Those who don't understand UNIX are condemned to reinvent it, poorly. – Henry Spencer

Yoshman är inte uppkopplad
2013-02-05, 22:02   #34

perost

Medlem

perosts avatar

Plats: Linköping

Registrerad: jun 2007

På tal om att vara lätt att förstå, här är bogosort implementerad i C++11 (is_sorted är ny):
template<class T>
vector<T>& bogosort(vector<T> &data) {
  while(!is_sorted(data.begin(), data.end())) {
    random_shuffle(data.begin(), data.end());
  }
  return data;
}
Att sortera 12 element tog ungefär 5 sekunder för mig, fler element än så rekommenderas inte
perost är uppkopplad nu
Senaste nyheterna

Redaktionens senaste nyhetsrubriker