eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingBisekcja...
Ilość wypowiedzi w tym wątku: 16

  • 11. Data: 2018-12-12 14:27:11
    Temat: Re: Bisekcja...
    Od: DMR <m...@g...com>

    Pythona, to ja... Wiem, że coś takiego jest. :-)



    > Dlaczego nie jakies hashowanie ?


    Postudiowałem temat, bardzo fajna sprawa jeśli klucze występują według... klucza. :-)

    A skoro o tym mowa, to wyszła zmiana założeń.
    Klucze mają być jednak 120-bitowe (16 znakowe stringi, zera nie liczę).


    Czyli teraz muszę zrobić:

    A -> B -> A -> CKI
    A -> B -> A -> DROWICZ
    A -> B -> A -> FIUK

    B -> A -> BACKI
    B -> A -> CEWICZ
    B -> E -> CIKOWSKI

    itd.

    Czyli skorowidz. :-)

    Biorąc pod uwagę to, że do stworzenia klucza dozwolone będzie użycie niecałej setki
    znaków, nawet jeśli kolejne znaki-klucze wrzucę na zwykłe listy, to w najbardziej
    perfidnym przypadku dotarcie do właściwego klucza będzie wymagało co najwyżej 15*100
    porównań - przy czym przypadek taki NIGDY nie nastąpi, z uwagi na ilość elementów
    znikomą w porównaniu z liczbą możliwych kombinacji znaków w kluczu.

    Ale na pewno da się coś tu poprawić... Drzewo drzew? ;-]


  • 12. Data: 2018-12-12 20:53:41
    Temat: Re: Bisekcja...
    Od: Wojciech Muła <w...@g...com>

    On Wednesday, December 12, 2018 at 2:27:12 PM UTC+1, DMR wrote:
    > Pythona, to ja... Wiem, że coś takiego jest. :-)
    >
    >
    >
    > > Dlaczego nie jakies hashowanie ?
    >
    >
    > Postudiowałem temat, bardzo fajna sprawa jeśli klucze występują według... klucza.
    :-)
    >
    > A skoro o tym mowa, to wyszła zmiana założeń.
    > Klucze mają być jednak 120-bitowe (16 znakowe stringi, zera nie liczę).
    >
    >
    > Czyli teraz muszę zrobić:
    >
    > A -> B -> A -> CKI
    > A -> B -> A -> DROWICZ
    > A -> B -> A -> FIUK
    >
    > B -> A -> BACKI
    > B -> A -> CEWICZ
    > B -> E -> CIKOWSKI
    >
    > itd.
    >
    > Czyli skorowidz. :-)
    >
    > Biorąc pod uwagę to, że do stworzenia klucza dozwolone będzie użycie niecałej setki
    znaków, nawet jeśli kolejne znaki-klucze wrzucę na zwykłe listy, to w najbardziej
    perfidnym przypadku dotarcie do właściwego klucza będzie wymagało co najwyżej 15*100
    porównań - przy czym przypadek taki NIGDY nie nastąpi, z uwagi na ilość elementów
    znikomą w porównaniu z liczbą możliwych kombinacji znaków w kluczu.
    >
    > Ale na pewno da się coś tu poprawić... Drzewo drzew? ;-]

    W jakim języku masz to napisać?

    w.


  • 13. Data: 2018-12-12 23:46:23
    Temat: Re: Bisekcja...
    Od: DMR <m...@g...com>

    > W jakim języku masz to napisać?

    C/C++

    Ale nie o język tu chodzi, tylko o podejście do problemu.
    Takie w sumie szkolne. :-)

    Program już dawno działa, teraz próbuję się bez spiny czegoś mądrego nauczyć.
    Np. okazało się, że w poprzednim wpisie odkryłem drzewa trie, nawet takie
    wybajerzone, z listami wskaźników w postaci drzew... ;-)


  • 14. Data: 2018-12-14 09:28:11
    Temat: Re: Bisekcja...
    Od: DMR <m...@g...com>

    > ...a po co od razu drzewa? Dlaczego nie jakies hashowanie ?


    No, ktoś ma tu browara! :-)

    Postudiowałem, przespałem się z tematem i jest!
    Pierwszym krokiem do uniknięcia kolizji jest zadbanie o unikalność klucza każdego
    elementu.
    Jako że identyfikatorem ma być łańcuch 15 z dozwolonych 63 znaków, to najłatwiej
    potraktować go jako zapis liczby w systemie "63-kowym" i przeliczyć na dziesiętny.
    Daje to zakres 63^15 = ~10^27... Trochę dużo, nawet, jak na 64 bity. :-)
    Żeby się wstrzelić w zakres 32 bitowego int-a można zrobić co najwyżej 63^5...

    No i się wszystko zgadza - można przecież przeliczać piątkami. :-)
    Da to co najwyżej jedną bardzo teoretyczną kolizje z samego identyfikatora (dobrze
    kombinuję?)

    A dalej, to już klasyka gatunku - indeks leci jako modulo z rozmiaru tablicy
    haszującej (daję ~2x większą, przy kilkudziesięciu tysiącach elementów nie wylazło mi
    nigdy więcej niż 5 powtórzeń na ~10% kluczy), do szybkiego odcedzenia w kolizji
    używam identyfikatora.

    No i gra! :-)


    Dzięki!


  • 15. Data: 2018-12-14 09:37:39
    Temat: Re: Bisekcja...
    Od: DMR <m...@g...com>

    > przy kilkudziesięciu tysiącach elementów nie wylazło mi nigdy więcej
    > niż 5 powtórzeń na ~10% kluczy


    Na ~1% kluczy, pardon.

    Bloga se chyba założę, tylko brakuje sweet-foci z dziubkiem...... ;-)


  • 16. Data: 2019-08-09 09:27:57
    Temat: Re: Bisekcja...
    Od: Borneq <b...@a...hidden.pl>

    On 12/14/18 9:28 AM, DMR wrote:
    > Jako że identyfikatorem ma być łańcuch 15 z dozwolonych 63 znaków, to najłatwiej
    potraktować go jako zapis liczby w systemie "63-kowym" i przeliczyć na dziesiętny.
    > Daje to zakres 63^15 = ~10^27... Trochę dużo, nawet, jak na 64 bity. :-)
    > Żeby się wstrzelić w zakres 32 bitowego int-a można zrobić co najwyżej 63^5...

    Nie lepiej dodać jeden znak dozwolony i mieć system 64-kowy?

strony : 1 . [ 2 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: