TList
GAD Zombie
Przy okazji wielkiego watku na temat kontenerow wyszla sprawa
implementacji TList w Delphi5. Troche sie zdziwilem, bo bylem pewny, ze
lista to lista i w Delphi powinna byc "w srodku" zbudowana na
wskaznikach. Okazuje sie, ze to prawda i faktycznie TList "opakowuje"
tylko zwykla tablice. Co gorsza, nie tylko problemem jest wstawianie
elementow (przy obowiazkowym kopiowaniu pamieci), ale rowniez
ograniczenie ilosciowe w rozmiarze tej tablicy, do bodaj ilosci maxint /
4 czy jakos tak. Smuci mnie to, bo od dawna uzywam takiej listy z
nadzieja, ze jest zwykla lista, czyli moge sobie wstawiac, usuwac co
chce, jedynym klopotem moze byc szukanie elementu przez [], ale to
wydawalo mi sie przyzwoicie szybkie (teraz wiem dlaczego:)).
I tu powstawlo moje pytanie. Poniewaz jestem leniwy i nie chce mi sie
pisac takiej klasy recznie - czy skads mozna do starego D5 czy D6
dociagnac porzadna i sprawna implementacje klasy jak TList, ale
dzialajacej jako prawdziwa lista jedno/dwukierunkowa na wskaznikach?
Moze ktos znalazl i sprawdzil, ze jest dobra i sie podzieli? Najlepiej
by bylo, gdyby w uzyciu przypominala TList, ale w srodku dzialala jako
normalna lista. A jeszcze lepiej gdyby bylo to analogiczne do TObjectList.
--
GAD Zombie
http://gad.art.pl/ http://sadist.art.pl/
http://gry-samochodowe.gad.art.pl/
darekm
Możesz powiedzieć po co Ci to. Ograniczenie wynika z ograniczeń pamięci
dla 32 bitów, przejdziesz na 64 i po kłopocie, choć wątpię abyś się
kiedykolwiek zbliżył do 0.5 mld elementów. Faktycznie prawdziwa lista
umożliwia bardzo szybkie wstawianie (nie mylić z dodawaniem na końcu) i
usuwanie elementów w porównaniu do innych struktur ale ta własność
rzadko bywa bardzo istotna. Bardzo ładnie zachowują się listy przy
multithreadingu, jeżeli są zaimplementowane jako lockfree, ale wtedy
zapomnij od liście dwukierunkowej. A w ogóle to użycie listy raczej nie
będzie przypominać TList. Lista składa się z dwóch elementów: głowy i
ogona i to wszystko, wszystkie operacje trywialne. Poszukaj przykładów a
nie komponentów.
--
Darek
GAD Zombie
> Możesz powiedzieć po co Ci to. Ograniczenie wynika z ograniczeń pamięci
Niewazne po co, wazne, ze chcialbym uzyc. Nie rozumiem takich pytan.
> dla 32 bitów, przejdziesz na 64 i po kłopocie, choć wątpię abyś się
> kiedykolwiek zbliżył do 0.5 mld elementów. Faktycznie prawdziwa lista
> umożliwia bardzo szybkie wstawianie (nie mylić z dodawaniem na końcu) i
> usuwanie elementów w porównaniu do innych struktur ale ta własność
> rzadko bywa bardzo istotna. Bardzo ładnie zachowują się listy przy
Zalezy co sie robi. Ja akurat mam wiele zastosowan i wazniejsze jest dla
mnie szybkie usuwanie ze srodka elementow niz wyszukiwanie, bo zwykle i
tak przegladam wszystkie po kolei, wiec tu zastosowanie typowej listy
jest idealne.
> multithreadingu, jeżeli są zaimplementowane jako lockfree, ale wtedy
> zapomnij od liście dwukierunkowej. A w ogóle to użycie listy raczej nie
> będzie przypominać TList. Lista składa się z dwóch elementów: głowy i
> ogona i to wszystko, wszystkie operacje trywialne. Poszukaj przykładów a
> nie komponentów.
Nie potrzebuje przykladow, bo wiem jak to dziala i umiem to robic, ale -
po co wywazac otwarte drzwi, jesli ktos juz to zrobil. Dlatego pytalem.
Krzysztof Szyszka
Zanim zaczniesz optymalizować coś, co zapewne optymalizacji nie wymaga,
(a na pewno nie w taki sposób, jak chcesz to zrobić), to sprawdź sobie czas
wstawiania/usuwania jednego elementu do TList dla największego rozmiaru
danych, jaki dziś używasz, bo odczytu szybszego niż przez indeks na pewno
nie uzyskasz. Operacje przesuwania wykonywane na tablicy wskaźników są
stosunkowo proste i szybkie dla nawet dość dużej liczby elementów.
Przy naprawdę dużej liczbie elementów hash table może być szybsza, ale kolega,
który namieszał Ci w głowie w tym dużym wątku zapomniał, że wyliczanie hasha
też trochę trwa i to nie jest operacja trywialna, szczególnie jeśli funkcja hashująca
ma być dobra (dająca bardzo mało kolizji). Źle dobrana funkcja hashująca potrafi
zniweczyć najlepiej napisany kontener hash table.
P.S.
TObjectList też jest zbudowana na TList.
--
pozdrowienia
Krzysztof Szyszka, X-Files Software
Developer of X-Files Components
Borland/CodeGear/Embarcadero Technology Partner
_________________________________________
Website: http://www.x-files.pl/ E-mail: ne...@x-files.pl
Arivald
A instalacja FastMove z FastProject jeszcze ją przyśpiesza.
> Przy naprawdę dużej liczbie elementów hash table może być szybsza, ale
> kolega,
> który namieszał Ci w głowie w tym dużym wątku zapomniał, że wyliczanie
> hasha
> też trochę trwa i to nie jest operacja trywialna, szczególnie jeśli
> funkcja hashująca
> ma być dobra (dająca bardzo mało kolizji). Źle dobrana funkcja hashująca
> potrafi
> zniweczyć najlepiej napisany kontener hash table.
Hash najbardziej się opłaca jak masz szybki procek, lub powolne medium
ale z dowolnym dostępem (random access, czyli że możesz zażądać dostępu
do każdego offsetu bez straty wydajności) (np 40 GB pliku, czy dostęp
przez sieć)
> P.S.
> TObjectList też jest zbudowana na TList.
Jaki i duża część kontenerów w Delphi (TCollection, TStack, TQueue, etc) ;-)
--
Arivald
Arivald
> W dniu 2010-10-29 14:06, darekm pisze:
>> Możesz powiedzieć po co Ci to. Ograniczenie wynika z ograniczeń pamięci
>
> Niewazne po co, wazne, ze chcialbym uzyc. Nie rozumiem takich pytan.
Kompilator nie pozwoli ci zadeklarować typu który potencjalnie zajmuje
więcej niż 4 gb pamięci. Chodzi o to ze jak przekroczysz tą granicę to
nastąpi przepełnienie w operacjach na wskaźnikach.
MaxListSize istnieje tylko i wyłącznie w tym celu, żeby można było
zadeklarować tablicę o maksymalnym możliwym rozmiarze, pomimo tego że i
tak nie da się jej zaalokować.
>
>> dla 32 bitów, przejdziesz na 64 i po kłopocie, choć wątpię abyś się
>> kiedykolwiek zbliżył do 0.5 mld elementów. Faktycznie prawdziwa lista
>> umożliwia bardzo szybkie wstawianie (nie mylić z dodawaniem na końcu) i
>> usuwanie elementów w porównaniu do innych struktur ale ta własność
>> rzadko bywa bardzo istotna. Bardzo ładnie zachowują się listy przy
>
> Zalezy co sie robi. Ja akurat mam wiele zastosowan i wazniejsze jest dla
> mnie szybkie usuwanie ze srodka elementow niz wyszukiwanie, bo zwykle i
> tak przegladam wszystkie po kolei, wiec tu zastosowanie typowej listy
> jest idealne.
jeśli jesteś w stanie tak przerobić procedury żeby pomijały elementy
listy = nil, to zamiast usuwać po prostu niluj te elementy.
Jest też TList.Pack(), które kompaktuje listę osuwając wszystkie nil-e
(chociaż nie używa toto najwydajniejszej metody kompaktowania).
Pack przydaje się przy usuwaniu w pętli for. Domyślnie jak dasz
for i := 0 to list.Count - 1 do
to kompilator optymalizuje i zapamiętuje wartość "list.Count - 1", i jak
usuniesz w takiej pętli element, to po dojściu do końca wyjdziesz poza
zakres (wyjątek).
Dlatego robi się to tak:
for i := 0 to list.Count - 1 do
if something then
list[i] := nil;
list.Pack();
>> multithreadingu, jeżeli są zaimplementowane jako lockfree, ale wtedy
>> zapomnij od liście dwukierunkowej. A w ogóle to użycie listy raczej nie
>> będzie przypominać TList. Lista składa się z dwóch elementów: głowy i
>> ogona i to wszystko, wszystkie operacje trywialne. Poszukaj przykładów a
>> nie komponentów.
>
> Nie potrzebuje przykladow, bo wiem jak to dziala i umiem to robic, ale -
> po co wywazac otwarte drzwi, jesli ktos juz to zrobil. Dlatego pytalem.
>
http://www.boyet.com/FixedArticles/EZDSL.html
w paczce najróżniejsze struktury, miedzy innymi listy.
--
Arivlad
GAD Zombie
> (a na pewno nie w taki sposób, jak chcesz to zrobić), to sprawdź sobie czas
> wstawiania/usuwania jednego elementu do TList dla największego rozmiaru
> danych, jaki dziś używasz, bo odczytu szybszego niż przez indeks na pewno
> nie uzyskasz. Operacje przesuwania wykonywane na tablicy wskaźników są
> stosunkowo proste i szybkie dla nawet dość dużej liczby elementów.
Mam wrazenie, ze nie zrozumiales moich intencji. Nie chce optymalizowac
TList, tylko chce uzyc kontenera, ktory podczas usuwania elementu ze
srodka, nie musi kopiowac w pamieci calej reszty listy. Jesli takich
usuwan zrobie wiele naraz, okazuje sie, ze takich kopiowan w pamieci
wykona sie tez duzo, a w przypadku zwyklej listy na wskaznikach,
ogranicza sie to tylko do przepiecia wskaznikow w noewe miejsce.
> Przy naprawdę dużej liczbie elementów hash table może być szybsza, ale
> kolega,
> który namieszał Ci w głowie w tym dużym wątku zapomniał, że wyliczanie
> hasha
Nikt mi nie namieszal w glowie, bo zupelnie o co innego zapytalem. W
ogole nie potrzebuje hashow, pisalem tez, ze nie zalezy mi na szybkim
dostepie do dowolnych elementow listy, bo zwykle i tak przegladam cala
liste pokolei, wiec wystarczy jakis prosty iterator, ktory bedzie
przeskakiwal na kolejny element listy.
> też trochę trwa i to nie jest operacja trywialna, szczególnie jeśli
> funkcja hashująca
> ma być dobra (dająca bardzo mało kolizji). Źle dobrana funkcja hashująca
> potrafi
> zniweczyć najlepiej napisany kontener hash table.
>
> P.S.
> TObjectList też jest zbudowana na TList.
Wiem, ze jest i stad dopisalem, ze jeszcze lepiej by bylo, gdyby znalezc
odpowiednik TObjectlist zbudowany na zwyklej liscie, tak jak obecnie
TObjectlist jest zbudowany na TList.
GAD Zombie
> W dniu 2010-10-29 14:22, GAD Zombie pisze:
>> W dniu 2010-10-29 14:06, darekm pisze:
>>> Możesz powiedzieć po co Ci to. Ograniczenie wynika z ograniczeń pamięci
>>
>> Niewazne po co, wazne, ze chcialbym uzyc. Nie rozumiem takich pytan.
>
> Kompilator nie pozwoli ci zadeklarować typu który potencjalnie zajmuje
> więcej niż 4 gb pamięci. Chodzi o to ze jak przekroczysz tą granicę to
> nastąpi przepełnienie w operacjach na wskaźnikach.
To oczywiste. Mnie nie chodzilo o duza liczbe elementow w liscie, a o
sposob dzialania samej listy.
>> Zalezy co sie robi. Ja akurat mam wiele zastosowan i wazniejsze jest dla
>> mnie szybkie usuwanie ze srodka elementow niz wyszukiwanie, bo zwykle i
>> tak przegladam wszystkie po kolei, wiec tu zastosowanie typowej listy
>> jest idealne.
>
> jeśli jesteś w stanie tak przerobić procedury żeby pomijały elementy
> listy = nil, to zamiast usuwać po prostu niluj te elementy.
>
> Jest też TList.Pack(), które kompaktuje listę osuwając wszystkie nil-e
> (chociaż nie używa toto najwydajniejszej metody kompaktowania).
O, o tym nie wiedzialem. Przejrze to, moze taka metoda nieco przyspieszy
dzialanie TList.
> http://www.boyet.com/FixedArticles/EZDSL.html
Dzieki, obejrze to.
Sebastian Biały
> który namieszał Ci w głowie w tym dużym wątku zapomniał, że wyliczanie
> hasha
> też trochę trwa i to nie jest operacja trywialna
Za to przemieszczanie miliona elementów oczko niżej jest bez wątpienia
bardzo szybkie ;)
Nie nie zapomnialem. U mnie hash jest niezły i szybki. Bo taka specyfika
danych. Sugerowalbym nie uogolniać.
> Źle dobrana funkcja hashująca
> potrafi
> zniweczyć najlepiej napisany kontener hash table.
Więc najlepiej uzyć np. płaskiego wektora z nilami i kompaktacją robiącą
perdyliard przemieszczeń pamieci gdyby ktoś zapomniał że operacja
wstawiania i kompaktacji nie jest taka trywialna. OK.
Sorry ze znowu się pojawilem, ale skoro już mnie ktoś wola prawie po
imieniu...
Widzę że wektor jest dobry na wszystko. Nawet jak nie jest dobry.
Arivald
> W dniu 2010-10-29 14:39, Krzysztof Szyszka pisze:
>> Zanim zaczniesz optymalizować coś, co zapewne optymalizacji nie wymaga,
>> (a na pewno nie w taki sposób, jak chcesz to zrobić), to sprawdź sobie
>> czas
>> wstawiania/usuwania jednego elementu do TList dla największego rozmiaru
>> danych, jaki dziś używasz, bo odczytu szybszego niż przez indeks na pewno
>> nie uzyskasz. Operacje przesuwania wykonywane na tablicy wskaźników są
>> stosunkowo proste i szybkie dla nawet dość dużej liczby elementów.
>
> Mam wrazenie, ze nie zrozumiales moich intencji. Nie chce optymalizowac
> TList, tylko chce uzyc kontenera, ktory podczas usuwania elementu ze
> srodka, nie musi kopiowac w pamieci calej reszty listy. Jesli takich
> usuwan zrobie wiele naraz, okazuje sie, ze takich kopiowan w pamieci
> wykona sie tez duzo, a w przypadku zwyklej listy na wskaznikach,
> ogranicza sie to tylko do przepiecia wskaznikow w noewe miejsce.
Tak mi przyszło do głowy, że jesli uzywasz wystarczającio nowej wersji
Delphi (z for x in list), to mozesz sobie odziedziczyć po TList (czy
innej liscie) , i zrobić własny enumerator, tak ze "for x in list"
będzie pomijać nil-e.
Wtedy zamiast usuwanie nilowanie będzie ok.
Dodatkowo możesz zoptymalizować metodę pack (poniżej piszę jak), plus
zareagować przy usuwaniu elementu żeby odpalać Pack() w jakichś
rozsądnych odstepach czasu (no po 100 usunieciach, dla listy z Count =
1000), i będzie działać całkiem miło...
Oprymalizacja Pack() polegała by na tym, że zamiast wołać Delete(), co
kopiuje CAŁY blok od aktualnego nil-a do końca, kopiować tylko bloki
wypełnione danymi.
np:
numerki - zajęte
o - nil
* - wolna przestraszeń (Tlist zawsze alokuje więcej niż aktualnie
potrzeba, tak że dodawanie elementów na koniec jest dość tanie)
masz
0123456ooo7890oo1234ooo5678901234*****
* szukasz pierwszego nila (index 7) , potem drugiego (index 14).
* kopiujesz od indeksu 8 do indeksu 13, w przestrzeń na indeks 7,
01234567890890oo1234ooo5678901234*****
^^^
Zauważ że teraz te trzy elementy są podwójnie! dlatego nastepny krok to
* nil-ujesz przestrzeń po przesunięciu, od indeksu 10 do 13
01234567890ooooo1234ooo5678901234*****
Zresztą możesz jej nie nilować, a jedynie pamiętać gdzie się zaczyna
pusta przestrzeń. I tak ją potem nadpiszesz w kolejnej iteracji.
przypisujesz index drugiego nila do pierwszego, szukasz następnego i
powtarzasz petlę.
kolejne kroki (od pierwszego)
0123456ooo7890oo1234ooo5678901234*****
01234567890ooooo1234ooo5678901234*****
012345678901234oooooooo5678901234*****
0123456789012345678901234oooooooo*****
teraz wystarczy zmniejszyć Count do 25...
0123456789012345678901234*************
> Nikt mi nie namieszal w glowie, bo zupelnie o co innego zapytalem. W ogole nie potrzebuje hashow, pisalem tez, ze nie zalezy mi na szybkim dostepie do dowolnych elementow listy, bo zwykle i tak przegladam cala liste pokolei, wiec wystarczy jakis prosty iterator, ktory bedzie przeskakiwal na kolejny element listy.
Dodawanie elementów na koniec listy jest stosunkowo tanie 9jedno jedno
porównanie (Fcoun < FCapacity), kopiowanie wskaxnika, jeden inc(FCount),
i opcjonalnie jeśli nie ma wolnej pojemności to realokacja.
Realokację można odsunąć w czasie od razu ustawiając duże Capacity.
--
Arivald
niusy.pl
Użytkownik "GAD Zombie" <g...@USUN.gad.USUN.art.pl>
> Mam wrazenie, ze nie zrozumiales moich intencji. Nie chce optymalizowac
> TList, tylko chce uzyc kontenera, ktory podczas usuwania elementu ze
> srodka, nie musi kopiowac w pamieci calej reszty listy. Jesli takich
> usuwan zrobie wiele naraz, okazuje sie, ze takich kopiowan w pamieci
> wykona sie tez duzo, a w przypadku zwyklej listy na wskaznikach, ogranicza
> sie to tylko do przepiecia wskaznikow w noewe miejsce.
No to napisz taki kontener. To proste jest przecież.
Krzysztof Szyszka
Przestałbyś się już ośmieszać, bo zamiast zrobić proste testy, to bijesz pianę
na tej grupie już przez kilka dni. Po pierwsze, żeby przechowac milion zwykłych
wskaźników w jednej strukturze potrzebujesz 4 GB ramu. Może C++ sobie
z tym poradzi, ale Delphi jest na to za cienkie ;-) Po drugie, żeby sprawdzić
ile czasu zajmie przesuwanie tablicy wskażników do pół miliona elementów
wystarczy prosty test. Musiałem go puścić 1000 razy w pętli, żeby zobaczyć
niezerowy wynik na moim leciwym laptopie.
var
A: array[0..500000] of Pointer;
procedure TForm1.Button1Click(Sender: TObject);
var
Start, Stop: TDateTime;
I: Integer;
begin
Start := Now;
for I := 1 to 1000 do
Move(A[0], A[1], SizeOf(A)-SizeOf(Pointer));
Stop := Now;
ShowMessage('Time is ' + FormatDateTime('hh:nn:ss.zzz', Stop-Start));
end;
Może puść sobie ten test i przestań w końcu mędrkować na temat języka,
o którym nie masz zielonego pojęcia.
Krzysztof Szyszka
> żeby przechowac milion zwykłych wskaźników w jednej strukturze potrzebujesz 4 GB ramu.
Oczywiście 4 MB ramu i 1 milion też się zmieści :-)
Wpisałem w deklaracji za dużo zer i kompilator mi się buntował ;-)
Przykładowy test jest OK.
Sebastian Biały
> Przestałbyś się już ośmieszać
> [...]
> Po pierwsze, żeby przechowac milion
> zwykłych
> wskaźników w jednej strukturze potrzebujesz 4 GB ramu.
Nie.
> ile czasu zajmie przesuwanie tablicy wskażników do pół miliona elementów
> wystarczy prosty test. Musiałem go puścić 1000 razy w pętli, żeby zobaczyć
> niezerowy wynik na moim leciwym laptopie.
Teraz zrób doświadczenie. Niech rozmiar tablic będzie parametrem.
Zmieniaj go w pętli i mierz czas. Suprise. Czas będzie liniowo się
zmieniał. Dla *prawdziwej* listy bedzie stały bez względu na ilość
elementów. To jest *katastrofalna* różnica i przekreśla wektor jako
narzedzie do insertowania na początek. Pewnie myslisz że te pare
(mili)sekund to nic. Widocznie nie mialeś potrzeby ich oszczędzenia. Ja
miałem wiele razy. Końcowe efekty liczone sa np. w tygodniach pracy vs
godziny pracy (przypadek z życia wzięty). W zasadzie żadna różnica ...
> Może puść sobie ten test i przestań w końcu mędrkować na temat języka,
> o którym nie masz zielonego pojęcia.
Tobie się *wydaje* że ten benchmark w innym języku będzie inny? W Delphi
obowiazuje inna matematyka?
Krzysztof Szyszka
> czas. Suprise. Czas będzie liniowo się zmieniał. Dla *prawdziwej* listy bedzie stały bez względu
> na ilość elementów. To jest *katastrofalna* różnica i przekreśla wektor jako narzedzie do
> insertowania na początek. Pewnie myslisz że te pare (mili)sekund to nic. Widocznie nie mialeś
> potrzeby ich oszczędzenia. Ja miałem wiele razy. Końcowe efekty liczone sa np. w tygodniach pracy
> vs godziny pracy (przypadek z życia wzięty). W zasadzie żadna różnica ...
Nie muszę robić testów, żeby wiedzieć, że wraz ze wzrostem ilości danych
czas wstawiania elementu na początek TList będzie coraz dłuższy, ale też
wiem (lub sprawdzam doświadczalnie) do jakiego rozmiaru danych mogę
jej spokojnie używać, a kiedy trzeba pomyśleć o optymalizacji lub zmianie
struktury danych. Poza tym, nikt mi nie każe wstawiać kolejnych elementów
na początek listy. Mogę też wstawiać na koniec i potem posortować całość.
Mogę zaznaczać elementy do usunięcia i potem usunąc wszystkie na raz.
TList nie zostało stworzone do przechowywania olbrzymiej liczby elementów.
To podstawowa struktura VCLa używana do składowania elementów w liczbie
nadającej się do typowych zastosowań. Nikt nie ładuje miliona elementów,
żeby je pokazać użytkownikowi, jako prostą listę wyboru. Na TList bazuje dużo
innych klas, bo jest prosta i szybka w działaniu przy rozsądnej ilości elementów.
Do specjalistycznych zadań od zawsze można znaleźć specjalizowane biblioteki.
Coraz więcej z nich jest włączane/implementowane w standardowych modułach
kolejnych wersji Delphi (np. Generics.Collection), ale ty używasz Delphi sprzed
ponad 10 lat i oceniasz język, przez pryzmat tego, co dla nas już dawno jest nie
aktualne. Równie dobrze mógłyś napisać, że Delphi nie wspiera Windows Themes,
tylko, że w czasach Delphi 5 nie było jeszcze Windows XP !!! Zacznij używać
najnowszych wersji, skoro chcesz wydawać miarodajne opinie.
Sebastian Biały
> Poza tym, nikt mi nie każe wstawiać kolejnych elementów
> na początek listy. Mogę też wstawiać na koniec i potem posortować całość.
Pi razy drzwi N log N. Dla dużych N o kant dupy potłuc. Myślę że 500000
to duże N.
> Mogę zaznaczać elementy do usunięcia i potem usunąc wszystkie na raz.
Zaznaczać? W stylu robienia nil i przeskakiwania / kompaktacji ?
> TList nie zostało stworzone do przechowywania olbrzymiej liczby elementów.
To widać. Nazwa jest jednak sprytnie myląca.
> kolejnych wersji Delphi (np. Generics.Collection), ale ty używasz Delphi
> sprzed
> ponad 10 lat i oceniasz język, przez pryzmat tego, co dla nas już dawno
> jest nie
Nie oceniam teraz Delphi. Oceniam zaskakującą metodę benchamrkowania
czegoś na zasadzie "hej, dla 500000 elementów działa w czasie całkiem
spoko! Nic więcej nie trzeba!".
> Zacznij używać
> najnowszych wersji, skoro chcesz wydawać miarodajne opinie.
W niczym nie pomogą jesli "musisz" przesortować 500000 elementów.
J-23
> On 2010-10-29 22:55, Krzysztof Szyszka wrote:
>> Poza tym, nikt mi nie każe wstawiać kolejnych elementów
>> na początek listy. Mogę też wstawiać na koniec i potem posortować całość.
>
> Pi razy drzwi N log N. Dla dużych N o kant dupy potłuc. Myślę że 500000
> to duże N.
1. Uparłeś się na tą TList jak byłaby jedynym typem podstawowym listy, a
nie jest. Są też inne wystarczy pogrzebać na google i nawet na D% jakieś
biblioteki znajdziesz :)
>
>> Mogę zaznaczać elementy do usunięcia i potem usunąc wszystkie na raz.
>
> Zaznaczać? W stylu robienia nil i przeskakiwania / kompaktacji ?
2. Dostałeś pomysł to... pokombinuj, przetestuj, a nie zachowuj się jak
byś wszystko wiedział najlepiej. (Z obecnym nastawieniem nawet szkoda ci
podawać jakieś pomysły)
>
>> TList nie zostało stworzone do przechowywania olbrzymiej liczby
>> elementów.
>
> To widać. Nazwa jest jednak sprytnie myląca.
>
3. patrz punkt 1. Ponadto od kiedy to ten objekt służy jako baza danych
:) Po za tym skoro ci za wolno a chcesz koniecznie TList to moze porcjuj
dane i tyle (choć nie znam założeń projektu)
>> kolejnych wersji Delphi (np. Generics.Collection), ale ty używasz Delphi
>> sprzed
>> ponad 10 lat i oceniasz język, przez pryzmat tego, co dla nas już dawno
>> jest nie
>
> Nie oceniam teraz Delphi. Oceniam zaskakującą metodę benchamrkowania
> czegoś na zasadzie "hej, dla 500000 elementów działa w czasie całkiem
> spoko! Nic więcej nie trzeba!".
>
4. Zależy od wymagań projektowych w jednych przedział czasowy pasuje w
innych nie. Jeśli nie pasuje ci czas operacji na TList patrz punkt 1.
>> Zacznij używać
>> najnowszych wersji, skoro chcesz wydawać miarodajne opinie.
>
> W niczym nie pomogą jesli "musisz" przesortować 500000 elementów.
5.Z takim podejściem jak twoje, bylibyśmy nadal w czasach "gdzie do
palenia ognia używano kamienia. Jeżeli tak podchodzisz do programowania
(komputera) to kalkulator powinien ci wystarczyć :) (to nie jest
złośliwa uwaga, tylko stwierdzenie faktów)
Pozdrawiam
Krzysztof Szyszka
>> kolejnych wersji Delphi (np. Generics.Collection), ale ty u�ywasz Delphi sprzed
>> ponad 10 lat i oceniasz j�zyk, przez pryzmat tego, co dla nas ju� dawno jest nie
>
> Nie oceniam teraz Delphi. Oceniam zaskakuj�c� metod� benchamrkowania czego� na zasadzie "hej, dla
> 500000 element�w dzia�a w czasie ca�kiem spoko! Nic wi�cej nie trzeba!".
Tak. Masz racj�. Korzystaj�c z jakiego� narz�dzia trzeba najpierw wiedzi�, do czego
mo�na go u�y�. Wielu uzna, �e TList jest "wystarczaj�co dobre" do kilkuset tysi�cy
element�w, inni zakupi� dodatkow� bibliotek� do Delphi 5, albo now� wersj� Delphi,
albo sami sobie napisz� lepszy kontener, a Ty tu siedzisz i p�aczesz od tygodnia,
bo klient kaza� Ci je�dzi� starym Polonezem i zabroni� go tunigowa�, a przecie�
innym autem (lub z innym silnikiem) mo�na by je�dzi� szybciej. Tak to wygl�da.
>> Zacznij u�ywa� najnowszych wersji, skoro chcesz wydawa� miarodajne opinie.
>
> W niczym nie pomog� jesli "musisz" przesortowa� 500000 element�w.
I znowu zaczynasz dyskutowa� bez sensu, wi�c szkoda czasu, �eby Ci odpisywa�.
Napisa�em ju� wcze�niej, �e od Delphi 2009 masz do dyspozycji klasyczne hash table,
czyli TDictionary<TKey,TValue>, a ty mi wyje�d�asz z sortowaniem. EOT.
Sebastian Biały
> 1. Uparłeś się na tą TList jak byłaby jedynym typem podstawowym listy, a
> nie jest.
*JA* się uparłem? Przecież to nie ja podaje metody które wymagają
przesortowania lub przekopiowania pamięci.
>> Zaznaczać? W stylu robienia nil i przeskakiwania / kompaktacji ?
> 2. Dostałeś pomysł to... pokombinuj, przetestuj
Alez ja juz nie jedą strukturę danych testowalem. Taką też (konkretnie
mam na tym zrobiony kompaktujący allokator z gc dla JVM). Istnieja
przypadki kiedy taka naiwna metoda robienia dziur ma sens. W ogólnym
jednak sens jest nikły poza uzywaniem *na siłę* koncepcji wektora. Juz
lepsze będzie coś w kształcie std::deque.
Sebastian Biały
> a Ty tu siedzisz i płaczesz
O wypraszam sobie. Ja tu ciężko trolluje. Proszę chociaz to docenić. I
uwzględnić że przynajmniej jest jakiś pozytywny efekt: ktoś
zainteresował się że TList to nie List.
wloochacz
/ciach/
> czyli TDictionary<TKey,TValue>, a ty mi wyjeżdżasz z sortowaniem. EOT.
Które ma błędy, jest dziurawe i nie powinno wejść do biblioteki
standardowej w takiej postaci.
Poprawili to w Delphi XE?
Może jeszcze poprawili Internal Error URW 1111?
--
wloochacz
darekm
> pianę
Proste testy bardzo często o niczym istotnym nie mówią. Ten poniższy
należy do tej grupy.
> na tej grupie już przez kilka dni. Po pierwsze, żeby przechowac milion
> zwykłych
> wskaźników w jednej strukturze potrzebujesz 4 GB ramu. Może C++ sobie
> z tym poradzi, ale Delphi jest na to za cienkie ;-) Po drugie, żeby
> sprawdzić
> ile czasu zajmie przesuwanie tablicy wskażników do pół miliona elementów
> wystarczy prosty test. Musiałem go puścić 1000 razy w pętli, żeby zobaczyć
> niezerowy wynik na moim leciwym laptopie.
Zastanów się co mierzysz. Skąd wziąłeś liczbę 1000. Jak opiszesz
przypadek że potrzebujesz jednorazowo tyle, a co z resztą. Jeżeli
wstawiasz to zakładasz utrzymywanie posortowanej struktury, czyli musisz
najpierw znaleźć miejsce wstawiania. A po drugie wstawiany zostanie
każdy z 500000 elementów, może w kilku etapach ale jednak.
Pomiar też jest średnio dokładny, krótkie czasy należy mierzyć
GetTickCount, a po drugie w testach należy zniwelować wpływ cache. Czas
wykonania funkcji move wcale nie jest liniowy względem wielkości
obszaru pamięci.
Poza tym masz rację. TList może być szybszy od HashTable w pewnych
zastosowaniach, złożoność to nie to samo co czas wykonania.
>
> var
> A: array[0..500000] of Pointer;
>
> procedure TForm1.Button1Click(Sender: TObject);
> var
> Start, Stop: TDateTime;
> I: Integer;
> begin
> Start := Now;
> for I := 1 to 1000 do
> Move(A[0], A[1], SizeOf(A)-SizeOf(Pointer));
> Stop := Now;
> ShowMessage('Time is ' + FormatDateTime('hh:nn:ss.zzz', Stop-Start));
> end;
>
> Może puść sobie ten test i przestań w końcu mędrkować na temat języka,
> o którym nie masz zielonego pojęcia.
>
--
Darek
J-23
> On 2010-10-30 04:00, J-23 wrote:
>> 1. Uparłeś się na tą TList jak byłaby jedynym typem podstawowym listy, a
>> nie jest.
>
> *JA* się uparłem? Przecież to nie ja podaje metody które wymagają
> przesortowania lub przekopiowania pamięci.
Po pierwsze jest to odwracanie kota ogonem.
Po drugie jeżeli liczysz że ktoś da ci gotowe rozwiązanie to nie jesteś
wart ani jednej minuty, która ci poświecił każdy kto starał ci się coś
podpowiedzieć.
>
>>> Zaznaczać? W stylu robienia nil i przeskakiwania / kompaktacji ?
>> 2. Dostałeś pomysł to... pokombinuj, przetestuj
>
> Alez ja juz nie jedą strukturę danych testowalem. Taką też (konkretnie
> mam na tym zrobiony kompaktujący allokator z gc dla JVM). Istnieja
> przypadki kiedy taka naiwna metoda robienia dziur ma sens. W ogólnym
> jednak sens jest nikły poza uzywaniem *na siłę* koncepcji wektora. Juz
> lepsze będzie coś w kształcie std::deque.
>
Widocznie albo cienko testowałeś albo założenia projektowe są do d... :)
Pozdrawiam
Sebastian Biały
>> *JA* się uparłem? Przecież to nie ja podaje metody które wymagają
>> przesortowania lub przekopiowania pamięci.
> Po pierwsze jest to odwracanie kota ogonem.
<Ziew>.
> Po drugie jeżeli liczysz że ktoś da ci gotowe rozwiązanie
Kto liczy? Ja tu tylko narzekam, że vector *nie* jest najlepszy do
wszystkiego wbrew opini dyskutantów. On jest dobry dla waskiej grupy
problemów.
> Widocznie albo cienko testowałeś albo założenia projektowe są do d... :)
Bo wektor, panie, musi byc lepszy i juz. A jak fakty przeczą to nalezy
zmienić matematykę!
J-23
Bełkot - eksperta od wszystkiego :)
Ja już znikam z dyskusji bo ona jest nic nie warta
Pozdrawiam
Krzysztof Szyszka
Przyślij mi jakiś prosty przykład, który pokazuje te błędy, to Ci sprawdzę w XE.
Krzysztof Szyszka
>> ile czasu zajmie przesuwanie tablicy wskażników do pół miliona elementów
>> wystarczy prosty test. Musiałem go puścić 1000 razy w pętli, żeby zobaczyć
>> niezerowy wynik na moim leciwym laptopie.
>
> Zastanów się co mierzysz. Skąd wziąłeś liczbę 1000. Jak opiszesz przypadek że potrzebujesz
> jednorazowo tyle, a co z resztą. Jeżeli wstawiasz to zakładasz utrzymywanie posortowanej
> struktury, czyli musisz najpierw znaleźć miejsce wstawiania. A po drugie wstawiany zostanie każdy
> z 500000 elementów, może w kilku etapach ale jednak.
Sprawdziłem tylko to, co chciałem sprawdzić, czyli jak dużo czasu zajmuje
(średnio) przesuwanie tablicy wskaźników przy milionie elementów, bo czas
wstawiania jednego elementu do listy urósł w tej dyskusji do niebotycznych
rozmiarów.
> Pomiar też jest średnio dokładny, krótkie czasy należy mierzyć GetTickCount, a po drugie w testach
> należy zniwelować wpływ cache. Czas wykonania funkcji move wcale nie jest liniowy względem
> wielkości obszaru pamięci.
>
> Poza tym masz rację. TList może być szybszy od HashTable w pewnych zastosowaniach, złożoność to
> nie to samo co czas wykonania.
Dlatego nie było moim celem porównywanie czasów działania dwóch kontenerów,
bo najpierw musiałbym obu użyć do wykonania tego samego zadania i dodatkowo
poświęcić sporo czasu na dobranie odpowiedniej funkcji hasującej, co jak wiesz
mocno zależy od konkretnych danych.