eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingZrandomizowane wyszukiwanie binarneRe: Zrandomizowane wyszukiwanie binarne
  • Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
    atman.pl!.POSTED!not-for-mail
    From: bartekltg <b...@g...com>
    Newsgroups: pl.comp.programming
    Subject: Re: Zrandomizowane wyszukiwanie binarne
    Date: Tue, 30 Sep 2014 11:27:55 +0200
    Organization: ATMAN - ATM S.A.
    Lines: 85
    Message-ID: <m0dt2s$6v4$1@node2.news.atman.pl>
    References: <5...@g...com>
    <m0cm3a$8r6$1@node1.news.atman.pl>
    <b...@g...com>
    NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
    Mime-Version: 1.0
    Content-Type: text/plain; charset=UTF-8; format=flowed
    Content-Transfer-Encoding: 8bit
    X-Trace: node2.news.atman.pl 1412069276 7140 89.73.81.145 (30 Sep 2014 09:27:56 GMT)
    X-Complaints-To: u...@a...pl
    NNTP-Posting-Date: Tue, 30 Sep 2014 09:27:56 +0000 (UTC)
    User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101
    Thunderbird/31.1.2
    In-Reply-To: <b...@g...com>
    Xref: news-archive.icm.edu.pl pl.comp.programming:206682
    [ ukryj nagłówki ]

    On 30.09.2014 07:20, Wojciech Muła wrote:
    > On Tuesday, September 30, 2014 12:22:33 AM UTC+2, bartekltg wrote:
    >> Na pewno normalnym? To z jaką wariancją. Jak radzić sobie z wyjściem
    >> poza [a,b] (rozkłąd normlany o dowolnej średniej i std jest -inf..inf),
    >> co najwyżej odpowiednio doże liczby są w praktyce niemożliwe do
    >> wylosowania.
    >>
    >> Może miałeś na myśli rozkład jednostajny?
    >
    > Tak, jednostajny. Pomyłka (i to nie imię mojej żony :) ).
    >
    >> W cormenie na pewno przy wyszukiwaniu binarnym było wyszukiwanie
    >> interpolacyjne, natomiast losowy wybór elementu dzielącego
    >> był w wersji qsort.
    >>
    >> Czy gdzieś (np w ćwiczeniach) była wersja wyszukiwania z losowaniem,
    >> nie wiem, możesz podać dokładniejsze namiary?
    >
    > Moja kopia Cormena leży 450 km stąd, dlatego zapytałem.
    >
    >> [...]
    >
    > Wielkie dzięki.
    >
    >> Wersja randomizowana jest też logarytmiczna, ale ciut wolniejsza
    >> (jeśli chodzi o liczbę porównań, to tego dojdzie generowani liczb
    >> losowych)
    >> [...]
    >> A, do rzeczy. Skoro algorytm jest wyraźnie gorszy, wątpię, by
    >> ktoś o nim coś więcej i dokładniej pisał. Ale mogę czegoś nie
    >> zauważać.
    >
    > Właśnie miałem nadzieję, że ktoś zauważył - np., że dla jakiegoś szczególnego
    > rozkładu danych wejściowych wersja randomizowana sprawdza się lepiej.


    To najpewniej załatwia ta uwaga:

    >> Po policzeniu nie ma w tym nc zaskakującego;) Wzór [1] na T[L]
    >> to jakaśtam średnia z fukcji
    >> x T(x) + (L-x) T(L-x). [2]
    >
    >> Ma ona symetrie względem L/s, czyli tam jest ekstermum.
    >> Spodziewamy się [pd T(x) funkcji wyglądającej jak logarytm).
    >> x log(x) + (L-x)log(L-x) ma w L/2 minimum.
    >> Lepiej więc wziąć po prostu L/2, niż średnią (a to, dla wartości
    >> oczekiwanej, robimy randomizując punkt podziału).

    Może trochę niewyraźnie napisane. I na pewno nieformalne.
    Z pierwszym problemem sobie poradzimy;)

    Jeszcze raz, wartość oczekiwana czasu obsłużenia tablicy długości
    L zadana jest rekurencyjnym wzorem:
    T[L] = 1+sum(i=1,L-1) ro(i,L) [T[i] (i)/L + T[L-i]*(L-i)/L]

    1 dla porównania jednego elementu,
    sum(i=1,L-1) ro(i,L) [...] to średnia z jakiegoś wyrażenia po
    rozkładzie o gęstości ro.
    a zawartość nawiasu kwadratowego to właśnie nasze wyrażenie,
    które się uśrednia. [T[i] (i)/L + T[L-i]*(L-i)/L]

    Można pokazać (mniejsza o ścisłość, dla logarytmu działa, chyba
    działa dla każdej monotonicznej, wraz z pochodnymi, funkcji), że
    przy pewnych założeniach co do T[x], T[x] *x jest wypukła.
    Więc [T[x] *(x)/L + T[L-x]*(L-x)/L] też.

    Jak poprzednio wspomniałem, jest symetryczna przy x-> L/2 - x
    więc ma w L/2 minimum.


    Wróćmy do głównego równania. Mamy jakiś rozkład, który uśrednia
    funkcję [...]. Ale najmniejszą wartość uzyskamy, jeśli weźmiemy
    tylko minimum. Biorąc cokolwiek innego, nawet z małym
    prawdopodobieństwem, dostajemy gorszy wynik niż biorąc minimum.

    Najmniejsze T wychodzi przy rozkładzie skupionym na środku.


    Z drugiej strony, ktoś o tym pisze:
    http://www.cise.ufl.edu/~yx1/publications/bin_search
    .pdf
    ale nie wczytałem się na tyle, by wiedzieć, po co.

    pzdr
    bartekltg

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: