Autor Téma: TDictionary: závisí rýchlosť vyhľadávania od veľkosti TRecord?  (Přečteno 329 krát)

Offline mibainfo

  • Nováček
  • *
  • Příspěvků: 44
  • Karma: 3
    • Verze Delphi: D1,2,3,4,7,2005,2009,XE8,S,B, Tokyo
Je treba z tohoto hľadiska šetriť každý byte?
Konkrétny príklad: TDictionary<String, TCity>

Prípadne existuje pre podobný prípad niečo rýchlejšie pre uloženia a svižné vyhľadávanie, než je TDictionary ?
TCity má v tomto prípade iba pár bajtov. Nie sú tam žiadne stringy.
Počet položiek cca 400.
Záleží na rýchlosti vyhľadávania. Na každej milisekunde. Napĺňaní môže byť relatívne pomalé.

Online Delfin

  • Hrdina
  • ****
  • Příspěvků: 439
  • Karma: 23
  • SW konzultant
    • Verze Delphi: 2009, Tokyo
Je treba z tohoto hľadiska šetriť každý byte?
Konkrétny príklad: TDictionary<String, TCity>

Prípadne existuje pre podobný prípad niečo rýchlejšie pre uloženia a svižné vyhľadávanie, než je TDictionary ?
TCity má v tomto prípade iba pár bajtov. Nie sú tam žiadne stringy.
Počet položiek cca 400.
Záleží na rýchlosti vyhľadávania. Na každej milisekunde. Napĺňaní môže byť relatívne pomalé.

Chapu ze ses asi chtel zeptat jak zavisi efektivita kalkulace hash recordu v zavislosti na jeho velikosti. Pro priklad jsi vsak pouzil jako klic string, ne record. Pro takovy pripad:

Co se tyce rychlosti. 400 polozek neni moc, mozna by mohl byt rychlejsi setrideny string list (nedavno jsme se tu o tom bavili; zacalo to tady).

Co se tyce kopirovani hodnotovych typu; v tomto pripade nemusis do kolekce ukladat record, ale referenci na nej (pointer). To byva v mnoha pripadech i praktictejsi. Zaznamy "sedi" na jednom miste a vyrabi se pro ne za pomoci referenci "pohledy" (zalezi samozrejme na ucelu).
« Poslední změna: 01-12-2017, 18:12:59 od Delfin »
A co chudinky ovce? Koupíš jim snad plovací vesty? Nebo jim nasadíš chůdy? Ještě lepší, kdybys je zkřížil s delfíny na ovce hopkavé!

Online Delfin

  • Hrdina
  • ****
  • Příspěvků: 439
  • Karma: 23
  • SW konzultant
    • Verze Delphi: 2009, Tokyo
Pro record pouzity jako klic je vysvetleni trochu obsahlejsi... Byl to preklep? Nebo chces TDictionary<String, TCity>?
A co chudinky ovce? Koupíš jim snad plovací vesty? Nebo jim nasadíš chůdy? Ještě lepší, kdybys je zkřížil s delfíny na ovce hopkavé!

Offline mibainfo

  • Nováček
  • *
  • Příspěvků: 44
  • Karma: 3
    • Verze Delphi: D1,2,3,4,7,2005,2009,XE8,S,B, Tokyo
Pro record pouzity jako klic je vysvetleni trochu obsahlejsi... Byl to preklep? Nebo chces TDictionary<String, TCity>?
Presne
TDictionary<String, TCity>
Kluc je string.
TCity je class, ktory obsahuje dva az tri integery.

Ide o to, ci sa tam oplati vobec nejak setrit. Alebo je uplne jedno, ci do class TCity, pridam dalsi 64 bit int. V skutocnosti je to SET of .. V dosledku int64.
Potrebujem nielen najst, ale aj okamzite rozhodovat podla priznakov, v ziskanom/najdenom class.
Inak tu https://stackoverflow.com/questions/3709784/how-can-i-search-faster-for-name-value-pairs-in-a-delphi-tstringlist sa pise, ze TDictionary je radovo rychlejsie aj nez THasedStringList.
Tak asi to riesenie je najlepsie.
Pointer by bol v tom zmysle, ze ukazuje na polozky zoznamu tried, vytvorenom mimo TDictionary na baze
dynamic array ?



Online Delfin

  • Hrdina
  • ****
  • Příspěvků: 439
  • Karma: 23
  • SW konzultant
    • Verze Delphi: 2009, Tokyo
Ide o to, ci sa tam oplati vobec nejak setrit. Alebo je uplne jedno, ci do class TCity, pridam dalsi 64 bit int.
V skutocnosti je to SET of .. V dosledku int64.

Skutecny set of je 1 byte, tj. kombinace maximalne 255 elementu. Ale hleda se klic, coz je tedy u Tebe string. U hodnot zalezi zda jsou referenciho typu nebo hodnotoveho. V pripade typu record jde o hodnotovy typ a do kolekce se ukladaji kopie pridanych recordu (record se zkopiruje). V pripade referencnich typu, jako napr. instance tridy, se ulozi jen reference na instanci.

Potrebujem nielen najst, ale aj okamzite rozhodovat podla priznakov, v ziskanom/najdenom class.
Inak tu https://stackoverflow.com/questions/3709784/how-can-i-search-faster-for-name-value-pairs-in-a-delphi-tstringlist sa pise, ze TDictionary je radovo rychlejsie aj nez THasedStringList.
Tak asi to riesenie je najlepsie.

Nemel jsem na mysli zadnou hash kolekci. Jen cisty, setrideny TStringList. Jeho binary search muze byt mnohem rychlejsi nez hashovani klice a hledani v kyblicich dictionary. Co zabira cas je prave hashovani. Chci rict, ze pomoci binary search algoritmu setrideneho string listu muzes dosahnout hledaneho vysledku driv nez bys vytvoril hash pro dictionary.

Predstav si napr., ze mas na startu zavodu string list a dictionary, rekneme s 1 polozkou. I kdyby nebyl string list setrideny a namisto binary search prochazel polozku po polozce, k vysledku se dostane mnohem rychleji nez dictionary u ktereho se pred samotnym hledanim z klice musi vytvorit hash.

Pointer by bol v tom zmysle, ze ukazuje na polozky zoznamu tried, vytvorenom mimo TDictionary na baze
dynamic array ?

Ano, v podstate tak (muze jit i o komplexni kolekci jako TList<TMyRecord>, jde jen o to ze se data ulozi jednou a pak se na ne jen ukazuje). To by vsak melo smysl jen v pripade typu record, ne u instanci trid (jak uz jsem zminil, record se do dictionary kopiruje, instance tridy se do nej uklada uz jako reference; tedy pointer).

Dotaz jsem chapal tak ze se tu bavime o typu record (videl jsem v titulku TRecord), ne o instanci tridy. V pripade instanci trid by tento krok nemel vyznam, protoze uz jde o referenci.
« Poslední změna: 01-12-2017, 23:46:32 od Delfin »
A co chudinky ovce? Koupíš jim snad plovací vesty? Nebo jim nasadíš chůdy? Ještě lepší, kdybys je zkřížil s delfíny na ovce hopkavé!

Online Delfin

  • Hrdina
  • ****
  • Příspěvků: 439
  • Karma: 23
  • SW konzultant
    • Verze Delphi: 2009, Tokyo
Skutecny set of je 1 byte, tj. kombinace maximalne 255 elementu.

256 ::) :)
A co chudinky ovce? Koupíš jim snad plovací vesty? Nebo jim nasadíš chůdy? Ještě lepší, kdybys je zkřížil s delfíny na ovce hopkavé!

Offline pf1957

  • Padawan
  • ******
  • Příspěvků: 1870
  • Karma: 92
    • Verze Delphi: D2007, XE3, DX10
Skutecny set of je 1 byte, tj. kombinace maximalne 255 elementu.

256 ::) :)
Nooo, skutecny set of je 256/8 [bit] = 32 [byte] :)

Online Delfin

  • Hrdina
  • ****
  • Příspěvků: 439
  • Karma: 23
  • SW konzultant
    • Verze Delphi: 2009, Tokyo
Skutecny set of je 1 byte, tj. kombinace maximalne 255 elementu.

256 ::) :)
Nooo, skutecny set of je 256/8 [bit] = 32 [byte] :)

Asi nechapu ::) V Delphi ma set maximalne 256 elementu (bitu). Coz je 1 byte. Rekl jsem to spatne?

Je to na me moc po ranu ;D
« Poslední změna: 02-12-2017, 06:28:01 od Delfin »
A co chudinky ovce? Koupíš jim snad plovací vesty? Nebo jim nasadíš chůdy? Ještě lepší, kdybys je zkřížil s delfíny na ovce hopkavé!

Offline pf1957

  • Padawan
  • ******
  • Příspěvků: 1870
  • Karma: 92
    • Verze Delphi: D2007, XE3, DX10
Excellent
Rated 1 time
256 elementu (bitu). Coz je 1 byte. Rekl jsem to spatne?
Nevim jak ve Spanelsku, ale ve zbytku sveta: 1 byte = 8 bitu ;-)

Offline vandrovnik

  • Hrdina
  • ****
  • Příspěvků: 287
  • Karma: 17
    • Verze Delphi: 10.2
Excellent
Rated 1 time
Asi nechapu ::) V Delphi ma set maximalne 256 elementu (bitu). Coz je 1 byte. Rekl jsem to spatne?

No do jednoho Byte  se dá uložit číslo od 0 do 255.
Jenže na set of..., které může mít až 256 prvků, je potřeba celkem 256 příznaků, jestli ten který prvek v množině je nebo není obsažený. Proto 256/8=32 byte.

Offline mibainfo

  • Nováček
  • *
  • Příspěvků: 44
  • Karma: 3
    • Verze Delphi: D1,2,3,4,7,2005,2009,XE8,S,B, Tokyo
Hmm, neviem. Volakedy bolo SET 1 byte a dalo sa uschovat max 8 poloziek.
Ale teraz mam v sete realne 64 vymenovanych poloziek a z toho prislusny SET OF..
Delphi neprotestuje. Vysledky su OK, nie je problem.
Jedine, co musi uzivatel ustriehnut je velkost 1, 2, 4, 8 byte vtedy, ked chce previest set na cislo.
Alebo naspat z cisla na set.
Ak by islo o vymenovane polozky, tak tam je to obycajny ORD a Delhi si to sam upravi. Ale u setu, uzivatel musi pouzit integer presneho typu. Inak by sa prevod nevykonal, alebo by sa nevykonal spravne.


Offline pf1957

  • Padawan
  • ******
  • Příspěvků: 1870
  • Karma: 92
    • Verze Delphi: D2007, XE3, DX10
Hmm, neviem. Volakedy bolo SET 1 byte a dalo sa uschovat max 8 poloziek.
To si IMHO pletes, protoze uz Turbo Pascal mel 256 elementu viz treba https://books.google.cz/books?id=XFaB8rDpUjYC&pg=PA455&lpg=PA455&dq=TurboPascal+type+set+of&source=bl&ots=rPm8C3W15X&sig=bsH6-6ZIMCvzAWxyn1Yjx6dkDFQ&hl=en&sa=X&ved=0ahUKEwiAzq_U4evXAhWL2aQKHfe5BnkQ6AEINTAC#v=onepage&q=TurboPascal%20type%20set%20of&f=false.

Jak mel velky set treba M.I.T. Pascal, ktery existoval jeste pred Turbo Pascalem, zatim marne vzpominam

Online Delfin

  • Hrdina
  • ****
  • Příspěvků: 439
  • Karma: 23
  • SW konzultant
    • Verze Delphi: 2009, Tokyo
Asi nechapu ::) V Delphi ma set maximalne 256 elementu (bitu). Coz je 1 byte. Rekl jsem to spatne?

No do jednoho Byte  se dá uložit číslo od 0 do 255.
Jenže na set of..., které může mít až 256 prvků, je potřeba celkem 256 příznaků, jestli ten který prvek v množině je nebo není obsažený. Proto 256/8=32 byte.

Jsem to ale kus neceho co by neproslo cenzurou. Radeji jsem si jeste jednou precetl co jsem tu v noci vyplodil. Zbytek je snad spravne. Je mi jako kdybych usnul na poli a prejel me traktor :)

256 elementu (bitu). Coz je 1 byte. Rekl jsem to spatne?
Nevim jak ve Spanelsku, ale ve zbytku sveta: 1 byte = 8 bitu ;-)

My tu mame vseho hodne ;D
A co chudinky ovce? Koupíš jim snad plovací vesty? Nebo jim nasadíš chůdy? Ještě lepší, kdybys je zkřížil s delfíny na ovce hopkavé!

Offline mibainfo

  • Nováček
  • *
  • Příspěvků: 44
  • Karma: 3
    • Verze Delphi: D1,2,3,4,7,2005,2009,XE8,S,B, Tokyo
Hmm, neviem. Volakedy bolo SET 1 byte a dalo sa uschovat max 8 poloziek.
To si IMHO pletes, protoze uz Turbo Pascal mel 256 elementu viz treba https://books.google.cz/books?id=XFaB8rDpUjYC&pg=PA455&lpg=PA455&dq=TurboPascal+type+set+of&source=bl&ots=rPm8C3W15X&sig=bsH6-6ZIMCvzAWxyn1Yjx6dkDFQ&hl=en&sa=X&ved=0ahUKEwiAzq_U4evXAhWL2aQKHfe5BnkQ6AEINTAC#v=onepage&q=TurboPascal%20type%20set%20of&f=false.

Jak mel velky set treba M.I.T. Pascal, ktery existoval jeste pred Turbo Pascalem, zatim marne vzpominam
Ospravedlnujem sa za tvrdenie o velksoti set 1 Byte v rannom Delphi.
Je to davno. 
Prvy Pascal som zazil na Sinclair 48.
Nahraval sa 3 minuty. Moc pamate nezostalo. Program pre vypocet plosnych teplotnych poli, som prepisal z Basicu. Ten Pascal dokazal pojat o 15% vacsiu siet ako dokazal SMEP za milion Kc. Beh 7 min vs 45 min vyzeral menej optimisticky, ale iba preto, ze ZX nemal matemat. koproc. Pascal bol fakt rychly. Kody sa fotil klasickou technikou z obrazovky a vyvolaval. Aby bolo viac obrazoviek k dispozicii. S moznostami a najma s RAM-kou, to bolo predtym na ZX81 a 1 KB RAM. Tak sa setrilo.. Na sklonku ZX81cky, nepomohol ani modul so 16KB, lebo stale za jazdy vypadaval..
Robotron s 8bit proc a s 8palcovymi disketami, mal uz Turbo Pascal od Borlandu.
V Pascale na 8bit pocitacoch som set urcite nevyuzival.
Na PC s Delphi prerelease, som bol este hodne zvyknuty setrit pamat.
Nerad by som rozprudil velku debatu, ale mam pocit, ze v prepinaci CASE xy OF (tam casto pouzivam prvky mnoziny) to boli dlhsiu dobu max 16 bit cele cisla. Mozno aj v inych podobnych pripadoch.
Presne info si nespominam. Roky frcia rychlo, spomienky blednu.
Plny rozsah mnozin som sa naucil vyuzivat az v poslednej dobe.
Preddtym to boli zakladne Exclude, Include, In a k tomu Case.
Pre prevod mnoziny na cislo, alebo naopak som pouzival techniku nacitavania bitov v cykle. Dnes je to jedno priradenie (znovu v smere tam i spat.. mam na mysli mnozinu nie prvok).
Uzitocne napr. pri zapise/citani settings.txt, alebo databazy.
Nasobenie, scitanie, odcitanie mnozin ma stale nadchynaju.
Dokonca aj matematicke lahodky. Mam jednu, ktora je nad ramec beznych bitovych operacii, periodicky ju potrebujem, umoznuje dokonalu skratku pri bitovych vypoctoch. Vzdy ubehne dlhsi cas, tak ju periodicky hladam na webe. Dokonca som si ju aj niekde uchoval, ale neviem ju najst, Aj to je uz davno..
Dan za nedostatok klasickeho IT vzdelania.. Nebyt pana Sinclaira a jedineho stretnutia so starym spoluziakom, v zivote by ma pocitace ani nenapadli. Akorat to prislo po vysokej. Preto sa necitim byt kompetentny viest spory s odbornikmi. Naopak, napriek tej vsetkej dlhej dobe si rad necham poradit :)

 

S rychlou odpovědí můžete používat BB kódy a emotikony jako v běžném okně pro odpověď, ale daleko rychleji.

Jméno: E-mail:
Ověření:
Datový typ v Delphi, který má True a False: