[delphi] Szybkie sortowanie ListView

[Max1414]

Jak zrobić szybkie sortowanie na komponencie typu ListView. Bo mam coś takiego, że jak klikne na nagłówek to się sortuje i to bardzo szybko, ale niestety względem długości ciągu, a ja potrzebuje względem liczb (od najmniejszej do największej) i zrobiłem to przy pomocy quick sorta, ale przy np. 3000 itemów to trwa jakieś 4sekundy... Ma ktoś jakiś pomysł?

[Gifanonim]

Jest udowodnione ze żaden algorytm sortowania opierający sie na porównywaniu nie posortuje szybciej tablicy niż w 1.43*n.

wiec możesz to zrobić na 2 sposoby:

 

1) pokażesz algorytm i spróbujemy go zoptymalizować (może robisz cos niepotrzebnie)

2) Jeśli liczby jakie masz posortować nie są duże to możesz spróbować pokusić się o sortowanie przez zliczanie.

[Max1414]

"1.43*n" to jest 143ms*n ?

No ale czemu standardowo sortuje bardzo szybko po kliknięciu na nagłówek. Jest to komponent TAdvListView

 

1) nie mam już tego kodu... był to zwykły quicksort tylko porównywał wartości z listview

2) liczby mogą być 1-99999

 

Ogolnie to mi się wydaje, że to przez visuala tak zwalnia... probówalem robić to sortowanie z BeginUpdate i EndUdpdate oraz z sortowaniu w tablicy "array of TListItems" i potem przypisanie tego wszystkiego do ListView.Items, ale tak samo wolno.

[Blind]

A nie lepiej przy dodawaniu nowych itemow zadbac o to zeby lista byla posortowana?

[Max1414]

A nie lepiej przy dodawaniu nowych itemow zadbac o to zeby lista byla posortowana?

 

no ba... tylko ze jest możliwość zmiany sortowania poprzez klikanie w nagłówki...

[Gifanonim]

"1.43*n" to jest 143ms*n ?

 

tu nie chodzi o czas tylko ilość operacji (chyba to było kopiowań) na tablicy o długości n. Poczytaj sobie o obliczaniu złożoności algorytmów a zrozumiesz o czym mowie.

 

wiesz trudno cokolwiek doradzać jak sie nie zna implementacji, bo możesz np. rzutować cos niepotrzebnie lub za dużo razy. Chodzi o to ze QUCK-SORT można napisać na tyle sposobów ilu jest programistów tak jak każdy algorytm zresztą. Swoja droga można by sortowanie zrobić wielowątkowe co mogło by dać ci jakiegoś kopa

[xevil21]

Swoja droga można by sortowanie zrobić wielowątkowe co mogło by dać ci jakiegoś kopa

 

jestem za..., a raczej przeciw

[sazian]

ale wam sie spodobała ta wielowątkowość tylko nie zapominajcie że to nie jest złoty środek i nie wpychajcie jej wszędzie na siłę

 

w tym przypadku najważniejszy jest dobry algorytm

[Toster]

nie problem w algorytmach moi Panstwo tylko w magicznych metodach Begin/EndUpdate.

 

zrob tak

 

listView.BeginUpdate

>>

listView.EndUpdate;

 

zobaczysz wielokrotne przyspieszenie.

[xevil21]

Wspominałem Max1414 o tym,

 

lecz on twierdził, że to nie to.

 

P.S. ująłem to w troszkę prostsze słowa

[Force]

Ja to robie tak: trzymam elementy w TList i na nich sortuje, a potem mam własną metodę na OnDrawItem, wiec jak dodaje to tylko do TList, a do TListView wstawiam byle jaki wiersz bo i tak potem wyświetlę co trzeba, jak usuwam to kasuje wiersz i tyle, jak sortuje to nei roibę Clear i Add tylko sortuje w TList a potem wystarczy odmalować widoczne wiersze

[Max1414]

CYTAT(Toster @ nie, 04 maj 2008 - 02:25)

nie problem w algorytmach moi Panstwo tylko w magicznych metodach Begin/EndUpdate.

 

zrob tak

 

listView.BeginUpdate

>>

listView.EndUpdate;

 

zobaczysz wielokrotne przyspieszenie.

 

Pisałem o tym kilka postów wyżej :

Ogolnie to mi się wydaje, że to przez visuala tak zwalnia... probówalem robić to sortowanie z BeginUpdate i EndUdpdate oraz z sortowaniu w tablicy "array of TListItems" i potem przypisanie tego wszystkiego do ListView.Items, ale tak samo wolno.

[Toster]

Jak zawsze mi to umyka Musze pocwiczyc czytanie ze zrozumieniem

tak czy siak 3000 elementow sortujac bubblem trwa mi mniej niz 4s, wiec cos masz dziwnego.

podaj koda co i jak ty sortujesz

[Force]

Dlatego uważam, że mój sposób jest najlepszy bo TList ma sortowania logarytmiczne Mam coś takiego:

type
 TCompare = function(item1,item2 : TIUIdObject):integer;
var
 SortF1,SortF2,SortF3 : TCompare;
 BackF1,BackF2,BackF3 : integer;
(..)

function CompareFunction(item1,item2 : Pointer):integer;
begin
 Result := SortF1(TIUIdObject(item1),TIUIdObject(item2))*BackF1;
 if (Result = 0) and (Addr(SortF2) <> nil) then
 begin
       Result := SortF2(TIUIdObject(item1),TIUIdObject(item2))*BackF2;
       if (Result = 0) and (Addr(SortF3) <> nil) then
         Result := SortF3(TIUIdObject(item1),TIUIdObject(item2))*BackF3;
 end;
end;

Wystarczy podpiąć funkcje sortujące i ustawić Back-i na 1 lub -1 (-1 gdy ma byc sortowanie odwrotne) i do TList wysłać metodę CompareFunction jako sortującą. Można (a raczej powinno się) zrobić te zmienne jako tablicę. Gdy klika się na jakąs kolumnę to przerzucasz dane z Sort2 do Sort3 a z Sort1 do Sort2 i do Sort jeden podpinasz nową funkcję w zależności jaka kolumna (tak samo z Back). Jak się klika kolumnę to najpierw sprawdzasz czy nie jest to ta sama co w Sort1 jeśli tak to mnożysz Back1 * -1 (bez przerzucania danych) to odwracasz sortowanie . Na koniec robisz repaint na ListView. Jak chcesz wielowątkowo to zamiast var zrób threadvar. Wg mnie to jest o wiele lepsze bo jest n log n i dodatkowo masz możliwość sortowania elementów gdy w pierwszym sortowaniu wyszło ze są równe. Oczywiście dla każdej kolumny trzeba napisać metodę porównującą

 

Edit: tagi z Delphi nie działają (nie da się dodać postu)