Excel Forum - Porady, Pomoc,  Excel Help, Excel FAQ Strona Główna
 FAQ  RegulaminRegulamin  Szukaj   Użytkownicy   Grupy   Rejestracja   Profil   Twoje wiadomości   Zaloguj 


Poprzedni temat «» Następny temat
ID tematu: 58602 Skopiuj do schowka Co tak naprawdę siedzi w obiekcie Scripting.Dictionary?
Autor Wiadomość
apollo
ExcelSpec


Pomógł: 1230 razy
Posty: 4257
Wysłany: 09-09-2017, 21:31   Co tak naprawdę siedzi w obiekcie Scripting.Dictionary?

Tym razem zwracam się nie do magików a do grubych, przepraszam, do tęgich głów.

Mam 65015 wartości liczbowych, żadna nie mieści się w zakresie Integer. W jednym arkuszu są to wartości z zakresu Long (górna półka), w drugim - z zakresu Double.
Dodaję 65015 wartości do słownika, nie metodą na brutala. W dwóch przypadkach do słownika dodane są jako teksty. Cztery identyczne procedury a w tych dwóch przypadkach wyniki mam od razu, zaś w pozostałych musiałem iść na kawę i papierosa, a i tak po powrocie jeszcze nie otrzymałem wyników.

Nie znam mechanizmów, i nie wiem, co się dzieje, kiedy dodajemy klucze do słownika, więc nie wiem, dlaczego tak jest.

Czy ktoś zna te mechanizmy, i wie, co tak naprawdę się dzieje przy dodawaniu kluczy i sprawdzaniu istnienia kluczy. Albo ktoś wie, gdzie szukać informacji.

Pozdrawiam

test1.rar
Pobierz Plik ściągnięto 91 raz(y) 244.84 KB

ID posta: 329385 Skopiuj do schowka
 
 
Marecki 
Excel Expert



Wersja: Win Office 2019
Pomógł: 2082 razy
Posty: 6876
Wysłany: 10-09-2017, 10:02   

Cytat:
Czy ktoś zna te mechanizmy, i wie, co tak naprawdę się dzieje przy dodawaniu kluczy i sprawdzaniu istnienia kluczy. Albo ktoś wie, gdzie szukać informacji.
Na to pytanie Ci nie odpowiem, ale podzielę się swoimi obserwacjami, może ktoś wyciągnie z tego jakieś wnioski.

Testy przeprowadzałem na takiej procedurze:
Kod:
Sub test()
    Const From_number = 1000000
    Const LenArr As Long = 10000
    Dim i As Long
    Dim dic As Object
    Dim t As Double
    Dim Tbl(1 To LenArr) As String ' Tu zmieniamy typy 'Long 'Double

    Set dic = CreateObject("scripting.dictionary")

    For i = 1 To LenArr
        Tbl(i) = From_number + i
    Next i

    t = Timer

    For i = 1 To LenArr
        If Not dic.exists(Tbl(i)) Then dic.Add Tbl(i), 0
    Next

    Debug.Print "Tablica " & TypeName(Tbl); " | Czas:" & Format(Timer - t, "0.0000"); "| Długość liczby: " & VBA.Len(From_number); " | Długość tablicy: " & LenArr; " | Liczba typu: " & TypeName(From_number + i)

End Sub

Testy przeprowadzałem na liczbie tylko typu Long, bo wydaje mi się że znaczenie ma tutaj długość liczby, a nie jej typ, wiadomo że jak przekroczymy pewną wartość( "długość") to i typ nam się zmieni )
Teraz założenia:
1.
- Liczba typu Long
- Tablica typu String
- Długość liczby nie ma tu większego znaczenia - dwu czy 10-cio znakowa to czasy są zbliżone
Cytat:
Tablica String() | Czas:0,0625| Długość liczby: 2 | Długość tablicy: 10000 | Liczba typu: Long
Tablica String() | Czas:0,0469| Długość liczby: 2 | Długość tablicy: 10000 | Liczba typu: Long
Tablica String() | Czas:0,0664| Długość liczby: 10 | Długość tablicy: 10000 | Liczba typu: Long
Tablica String() | Czas:0,0469| Długość liczby: 10 | Długość tablicy: 10000 | Liczba typu: Long

2.
- Liczba typu Long
- Tablica typu Long
- Długość liczby ma znaczenie - proszę zwrócić uwagę na przeskok w czasie między 7-mio, a 8-smio cyfrową liczbą
Cytat:
Tablica Long() | Czas:0,0469| Długość liczby: 7 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Long() | Czas:0,0469| Długość liczby: 7 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Long() | Czas:4,0586| Długość liczby: 8 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Long() | Czas:4,0391| Długość liczby: 8 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Long() | Czas:4,0391| Długość liczby: 10 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Long() | Czas:4,0703| Długość liczby: 10 | Długość tablicy: 10000 | Liczba typu: Long

3.
- Liczba typu Long
- Tablica typu Double
- Długość liczby ma znaczenie - jak wyżej
Cytat:
Tablica Double() | Czas:0,0469| Długość liczby: 7 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Double() | Czas:0,0586| Długość liczby: 7 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Double() | Czas:4,2891| Długość liczby: 8 | Długość tablicy: 10000 | Liczba typu: Long
Tablica Double() | Czas:4,3516| Długość liczby: 8 | Długość tablicy: 10000 | Liczba typu: Long

Robiłem jeszcze testy w innych konfiguracjach, ale to już zostawiam ciekawskim ;-)

Z tego co zauważyłem:
- nie ma wielkich różnic pomiędzy tablicami typu Long czy Double, ale już przy typie String są duże.
- przy tablicach typu Long czy Double znaczenie ma długość liczby(łańcucha)
- przy tablicy typu String długość liczby(łańcucha) nie ma większego znaczenia.

Czemu tak to wygląda to sam jestem ciekaw.
_________________
Hardware - ta część komputera, którą można kopnąć kiedy software przestanie funkcjonować.

Szkolenia z Excela , FB
Office 2019 Professional Plus , Windows 10 x64
Pozdrawiam, były mkkk23 teraz Marecki.
ID posta: 329398 Skopiuj do schowka
 
 
apollo
ExcelSpec


Pomógł: 1230 razy
Posty: 4257
Wysłany: 10-09-2017, 12:04   

Ja to wszystko wiem. Testowałem 65015 liczb od 1 do 65015 i dodanie liczb idzie jak burza. Dlatego nie podałem tego przypadku.
Wiem, jak wygląda, ale nie wiem, co w słowniku powoduje, że dodanie liczb trwa wieki a dodanie tekstów daje natychmiast wyniki.

Ciekawe jest poznanie mechanizmu, przyczyny, bo przykłady przecież każdy może wymyślić i testować, i wyciągnąć wnioski. Nie o to mi chodzi.
ID posta: 329406 Skopiuj do schowka
 
 
kulasart
[Usunięty]

Wysłany: 10-09-2017, 18:21   

W bardzo dużym uproszczeniu:

Słownik to zestaw "koszyków", mających swoje identyfikatory. W koszykach lądują pary klucz:wartość. Pary te przypisywane są do odpowiednich "koszyków" na podstawie klucza, a dokładniej rzecz ujmując hasza obliczonego z klucza.

Sprawdzenie czy klucz istnieje w słowniku polega na obliczeniu hasza, przejsciu do "koszyka" oznaczonego owym hashem, i sprawdzenie w pętli wszystkich par klucz:wartość z tego "koszyka" pod względem tego czy przypadkiem nie ma wśród nich klucza, który sprawdzamy.

W większości przypadków hash jest na tyle unikalny, że para klucz:wartość ląduje w swoim własnym koszyku. Jeżeli zdarzy się że hash nie jest unikalny, to para trafia do "koszyka", który ma już w sobie jakieś pary.
Przeszukanie koszyka zawierającego kilka/kilkanaście par jest względnie szybkie.

W przypadku kluczy liczbowych >9999999 lub <-9999999 niezależnie od typu, klucz otrzymuje ten sam hash. Dzięki temu wszystkie wartości wpisywane do słownika wpadają do tego samego "koszyka".

Jeżeli takich kluczy mamy niewiele, to problemu nie zauważymy.
Im więcej takich kluczy, tym wolniejsze staje się dodawanie elementów do słownika.
Przy 10 - słownik musi wykonać 45 iteracji,
przy 20 - 190,
przy 50 - 1225,
przy 100 - 4950,
przy 1000 - 499500
przy 10000 - 49995000

Jeżeli zmierzycie ilość czasu potrzebną na dodanie nowego elementu, to zobaczycie, że rośnie ona przy każdym kluczu liczbowym, który nie mieści się w zakresie od -9999999
do +9999999.

W przypadku kluczy tekstowych dystrybucja haszy (lub jak kto woli ich unikalność) jest dużo lepsza. Dlatego też, w przykładzie podanym przez apollo widać tak duży wzrost wydajności.
ID posta: 329424 Skopiuj do schowka
 
 
apollo
ExcelSpec


Pomógł: 1230 razy
Posty: 4257
Wysłany: 10-09-2017, 20:04   

kulasart napisał/a:
W bardzo dużym uproszczeniu:

Kiedy ja chcę szczegółów ;-)

Dziękuję za zainteresowanie ale jeszcze nie to.

Na poziomu ogólności też mogę sobie coś wymyślić, i zakładać. Chodzi mi o szczegóły.

Rozważmy inny przykład, w którym domyślam, że ktoś stosuje szyfrowanie danych. Ja chcę wiedzieć szczegóły tego szyfrowania. Dopiero wtedy mogę ocenić, czy algorytm jest szybki czy nie, lepszy czy nie.

Hash, czyli konkretnie jak to jest zrobione? Dodać coś do zestaw, czyli jak to jest robione, co to jest zestaw? Mówmy o innym przykładzie. Ktoś powie, że on w swojej metodzie dodaje coś do zestawu. Ale co to znaczy? Że on trzyma jakąś kolekcję, tablicę, drzewo binarne itd., i w swojej metodzie Add dodaje coś do kolekcji, tablicy, drzewa? Chcę wiedzieć o tych konkretach, co on stosuje - kolekcja, tablica, drzewo.

Nawet jeśli stosuje tablicę to ona może być różna. Weźmy przykład pracy z liczbami całkowitymi np. <= 10^7 (ktoś coś robi i dane nie są > 10^7).

On może robi tak: po dodaniu n-tej liczby jego tablica ma n elementów, gdzie Arr(i) = i-ta liczba. Przeszukanie, czy liczba szukana jest w tablicy, polega na przejściu przez tablicę od początku aż do znalezienia szukanej (lub nie).

Ale też może tak: po dodaniu n-tej liczby jego tablica ma k elementów, gdzie k to maksymalna liczba wśród liczb, które zostały dodane do tablicy. I Arr(dodana) = dodana. Przeszukanie, czy liczba szukana jest w tablicy, jest prosta: czy Arr(szukana) jest różna od domyślnej (default).

Chcę wiedzieć o szczegółach, czyli jak liczba zostaje dodana do tablicy. Samo powiedzenie, że ktoś trzyma tablicę i dodaje kolejne liczby do tej tablicy jeszcze nie mówi prawie nic. Dopiero po poznaniu szczegółów mogę ocenić, czy pierwsza metoda zawsze jest lepsza (gorsza) od drugiej. I jeśli jest różnie to w w jakich przypadkach pierwsza jest szybsza od drugiej a w jakich odwrotnie. Bez poznaniu szczegółów nie mogę ocenić.

Wracając do słownika chcę wiedzieć:
1. Co słownik trzyma. Zestaw, koszyk to nic mi nie mówi. Jaka to jest struktura danych? Konkretnie.
2. Czy i jak klucz zostaje obrobiony. Jeśli jakiś "hash" to jak konkretnie to wygląda. No i jak ten "obrobiony" klucz zostaje dodany do struktury danych (kolekcja, tablica rekordów, drzewa wskażników (obiektów) itd.)

Cytat:

W przypadku kluczy tekstowych dystrybucja haszy (lub jak kto woli ich unikalność) jest dużo lepsza

Czyli konkretnie jak to wygląda?

Ja chcę wiedzieć o szczegółach. Jeśli ktoś wie, bo ma dostęp do dokumentacji (wątpię, czy istnieje), bo przeczyta gdzieś, gdzie ktoś biegły w tych sprawach opisuje, jak to mogłoby być. Albo jeśli ktoś sam biegły w tych sprawach opisuje, jak to najprawdopodobniej mogłoby być. Wszyscy tacy są mile widziani.

Pozostali również ;-)

Pozdrawiam
ID posta: 329430 Skopiuj do schowka
 
 
kulasart
[Usunięty]

Wysłany: 10-09-2017, 20:26   

apollo, dałem ogólny opis żeby także inne osoby mogły z niego trochę wyciągnąć.

Chcesz trochę więcej "teorii" wraz z "praktyką" zerknij tutaj: http://www.vbforums.com/s...-VB6-Hash-table
Kiedyś widziałem opis jak jest skonstruowany słownik (przedstawiony przez profesora Politechniki Poznańskiej na jednym z wykładów) i całość wyglądała bardzo, bardzo podobnie.

Obawiam się że kod źródłowy słownika z scrrun.dll jest tajemnicą MS i raczej go nie znajdziesz w sieci. Można kombinować z inżynierią wsteczna. Czy warto? Szczerze mówiąc wątpię, chyba że w celach czysto naukowych.
ID posta: 329431 Skopiuj do schowka
 
 
apollo
ExcelSpec


Pomógł: 1230 razy
Posty: 4257
Wysłany: 10-09-2017, 20:55   

kulasart napisał/a:

Kiedyś widziałem opis jak jest skonstruowany słownik (przedstawiony przez profesora Politechniki Poznańskiej na jednym z wykładów) i całość wyglądała bardzo, bardzo podobnie.

Tak, o coś takiego chodzi. Chętnie poznam taki opis.
Cytat:

Obawiam się że kod źródłowy słownika z scrrun.dll jest tajemnicą MS i raczej go nie znajdziesz w sieci.

Dlatego pisałem, że wątpię w istnienie tej dokumentacji. A dokładnie to ona na pewno jest ale nie jest udostępniona.
Cytat:

Można kombinować z inżynierią wsteczna. Czy warto? Szczerze mówiąc wątpię, chyba że w celach czysto naukowych.

Nie chcę robić swojego słownika lub podobnych rzeczy. Chcę wiedzieć, jak jest, jak najprawdopodobniej jest w Dictionary. Ponieważ wątpię, że MS udostępnił dokumentację, więc chodzi mi raczej o to, czy ktoś gdzieś poczytał, jak najprawdopodobniej jest w Dictionary. Czyli np. że kulasart poczytał, że profesor Politechniki Poznańskiej bla bla, i w Dictionary mogłoby być bardzo podobnie. Jeśli bla bla jest szczegółowe to chciałbym poznać.
ID posta: 329435 Skopiuj do schowka
 
 
Wyświetl posty z ostatnich:   
Odpowiedz do tematu
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Nie możesz załączać plików na tym forum
Możesz ściągać załączniki na tym forum
Dodaj temat do Ulubionych
Wersja do druku

Skocz do:  

Powered by phpBB modified by Przemo © 2003 phpBB Group
Theme xandgreen created by spleen& Programosy modified v0.3 by warna
Opieka techniczna www.marketingNET.pl

Archiwum

Strona używa plików cookies.

Kliknij tutaj, żeby dowiedzieć się jaki jest cel używania cookies oraz jak zmienić ustawienia cookie w przeglądarce.
Korzystając ze strony użytkownik wyraża zgodę na używanie plików cookies, zgodnie z bieżącymi ustawieniami przeglądarki.
Sprawdź, w jaki sposób przetwarzamy dane osobowe