eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingWyszukiwanieRe: Wyszukiwanie
  • Data: 2016-05-02 08:07:17
    Temat: Re: Wyszukiwanie
    Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    On Saturday, April 30, 2016 at 11:23:10 PM UTC+2, Wojciech Muła wrote:
    > On Thursday, April 28, 2016 at 10:41:03 PM UTC+2, M.M. wrote:
    > > Jak powinien wyglądać dobry algorytm do wyszukiwania w posortowanym
    > > ciągu? Można wyszukiwać binarnie lub metodą pełnego przeglądu.
    > > Można także wyszukiwać interpolacyjnie. Każda z metod nadaje się
    > > tylko do określonego przypadku. Metoda pełnego przeglądu jest
    > > bardzo skuteczna dla małych ciągów. Interpolacyjne jest dobre
    > > dla ogromnych ciągów dających się dobrze aproksymować jakąś
    > > wzajemnie jednoznaczną funkcją. Wyszukiwanie binarne to stabilna
    > > metoda, nawet pesymistycznie działa w czasie LogN, jednak
    > > ma narzut liniowy. Zresztą interpolacyjne ma jeszcze większy
    > > narzut.
    > >
    > > Jak powinno wyglądać adaptatywne wyszukiwanie?
    > >
    > > Czy może wyglądać tak: Pierwszy raz szukamy binarnie i
    > > zapamiętujemy przybliżony czas. Potem szukamy metodą
    > > pełnego przeglądu, jeśli czas jest większy, to
    > > przerywamy i wyszukujemy binarnie. Potem z... nie
    > > wiem ile... z 20 razy wyszukujemy binarnie, bo
    > > działało najszybciej. Potem znowu jakaś próba... może z
    > > wyszukiwaniem interpolacyjnym. Jeśli czas przekroczy
    > > binarne, to przerywamy i znowu z 20 razy binarnie? Aha,
    > > dane po każdym wyszukiwaniu mogą się zmienić co do
    > > ilości i jakości.
    > >
    > > Czy wystarczy zrobić to chamsko? Typu jeśli ilość danych
    > > większa niż N to binarnie, a poza tym pełen przegląd?
    > >
    > > Druga sprawa, czy interpoluje się tylko liniowo, czy
    > > warto próbować jeszcze jakąś inną funkcją?
    >

    Dzięki za odpowiedź, dzięki za artykuł. Podoba mi się pomysł z
    wykorzystaniem długich rejestrów.

    > Po pierwsze zapomnij o wyszukiwaniu interpolacyjnym. Dla
    > niejednostajnych rozkładów danych jest wolniejsze niż
    > binarne.
    Zapominam o dosłownym stosowaniu wyszukiwania interpolacyjnego. Ciekawy
    jednak jestem jakby działało 'wyszukiwanie adaptatywne' - tę nazwę
    wymyśliłem w tej chwili. Jaki algorytm mógłby się kryć za wyszukiwaniem
    adaptatywnym? Byłaby to kombinacja wyszukiwania binarnego i interpolacyjnego.
    Wyszukiwanie binarne dzieli zbiór (prawie) na pół (N/2,N/2).
    Interpolacyjne może nawet podzielić zbiór na (N-1,1). Wystarczyłoby dać
    jakieś ograniczenie M z przedziału np. od 0.1 do 0.9. Następnie
    zbiór byłby dzielony na ( N*M , N*(1-M) ). Pozostaje tylko ustalić
    optymalną wartość M. Ilość wyszukiwań dla takiego algorytmu wahałaby się
    pomiędzy Log2N a Log10N.





    > Ja bym został przy binarnym, raczej w ogólnym przypadku
    > szybciej tego nie zrobisz. Masz przy 1 milionie elementów
    > 20 porównań, naprawdę ciężko to przebić. Ale chętnie
    > bym się mylił w tym miejscu. :)
    W ogólnym pewnie się nie mylisz. Ale jakby z każdym wyszukiwaniem
    coraz lepiej dopasować wartość M, to może dla niektórych przypadków
    dałoby się zejść do 6 wyszukiwań dla miliona?



    > Chociaż pytanie, co porównujesz? Jak masz typy proste (int, float),
    > gdzie porównania mapują się na instrukcje procesora, możesz
    > spróbować instrukcji SIMD. Przy czy to już dla naprawdę dużych
    > danych daje jakieś mierzalne efekty -- możesz zerknąć na mój
    > artykuł. Pobawiłem się tym, ale jeszcze nie stosowałem w praktyce:
    > http://0x80.pl/articles/simd-search.html
    Widać że daje. Dziękuję za artykuł. Podoba mi się pomysł z
    wykorzystaniem SIMD.


    > Patrząc z trochę innej strony: czy skoro dane w Twoim
    > zastosowaniu się zmieniają nawet co jedno wyszukanie, to
    > czy w ogóle sens je sortować? Może szybciej wyjdzie pominięcie
    > sortowania i szukanie liniowo za każdym razem.
    W moim zastosowaniu będą (chyba) trzy generalne przypadki użycia. W
    jednym dane często będą się zmieniały, w drugim rzadko, w trzecim w
    ogóle nie będą się zmieniały i wyszukiwanie może być 'gorącym punktem'.
    Dlatego zamarzyło mi się 'wyszukiwanie idealne'. Co rozumiem przez
    wyszukiwanie idealne? Ano coś takiego, że programista sam definiuje,
    jaki procent czasu procesora ma być przeznaczony na auto-tuning.
    Pewnie napisanie powyższego algorytmu byłoby bardzo trudne, albo
    niemożliwe. Natomiast jest nadzieja, że opłaci się automatyczny
    dobór parametru M. Jak dobierać te M? Może tak, że jeśli wyszukiwana
    wartość znajduje się w większym przedziale, to M lekko zmieniamy w
    kierunku wartości 0.5, a jeśli w mniejszym przedziale, to M zmieniamy
    w kierunku 0.1 albo nawet 0.01. Np. raz modyfikujemy tak:
    M = (M * 0.999) + 0.5 * 0.001
    drugi raz tak:
    M = (M * 0.999) + 0.01 * 0.001

    Jeśli szukana wartość częściej będzie w mniejszym zbiorze, to M po
    kilku tysiącach wyszukiwań osiągnie wartość 0.01, w przeciwnym razie
    będzie oscylowało w okolicach 0.5.

    Może się mylę, ale dostęp do danych w których wyszukujemy jest powolny, bo
    to strzały w niebuforowaną pamięć. Wartość M zawsze procesor
    będzie miał pod ręką, może nawet w rejestrze, więc operowanie na M nie
    powinno dawać dużego narzutu liniowego.


    Pozdrawiam

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

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: