eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzybki algorytm na permutację
Ilość wypowiedzi w tym wątku: 7

  • 1. Data: 2016-04-22 00:22:33
    Temat: Szybki algorytm na permutację
    Od: Borneq <b...@a...hidden.pl>

    z wykorzystaniem random()
    Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    drugą, początkowo wielkości 0.
    Z posortowanych wybieram za pomocą random(n) któryś element, i
    najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    element ostatni.
    Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    I tak dalej


  • 2. Data: 2016-04-22 18:43:45
    Temat: Re: Szybki algorytm na permutację
    Od: "M.M." <m...@g...com>

    On Friday, April 22, 2016 at 12:22:35 AM UTC+2, Borneq wrote:
    > z wykorzystaniem random()
    > Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    > drugą, początkowo wielkości 0.
    > Z posortowanych wybieram za pomocą random(n) któryś element, i
    > najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    > element ostatni.
    > Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    > I tak dalej

    Może tak?
    for( int i=1 ; i<=N ; i++ )
    tab[i] = i;
    for( int i=0 ; i<N*2 ; i++ )
    swp( tab[rand()%N] , tab[rand()%N] );


  • 3. Data: 2016-04-23 01:47:08
    Temat: Re: Szybki algorytm na permutację
    Od: bartekltg <b...@g...com>

    On 22.04.2016 18:43, M.M. wrote:
    > On Friday, April 22, 2016 at 12:22:35 AM UTC+2, Borneq wrote:
    >> z wykorzystaniem random()
    >> Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    >> drugą, początkowo wielkości 0.
    >> Z posortowanych wybieram za pomocą random(n) któryś element, i
    >> najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    >> element ostatni.
    >> Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    >> I tak dalej

    >
    > Może tak?
    > for( int i=1 ; i<=N ; i++ )
    > tab[i] = i;
    > for( int i=0 ; i<N*2 ; i++ )
    > swp( tab[rand()%N] , tab[rand()%N] );

    Bardzo źle.
    Wynonujesz 4N losowań.
    Czy rozkład wyniku jest równomierny, wcale bym się nie zakładał.

    pzdr
    bartekltg




  • 4. Data: 2016-04-23 01:54:49
    Temat: Re: Szybki algorytm na permutację
    Od: bartekltg <b...@g...com>

    On 22.04.2016 00:22, Borneq wrote:
    > z wykorzystaniem random()
    > Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    > drugą, początkowo wielkości 0.
    > Z posortowanych wybieram za pomocą random(n) któryś element, i
    > najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    > element ostatni.
    > Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    > I tak dalej



    Prawie idealnie. Z tym, ze nie potrzebujesz wcale osobnej tablicy,
    Masz jedną tablicę, idziesz po niej plętlą

    Wszytko co przed indeksem i traktujesz jak swoją drugą tablicę
    (tam są losowo zmieszane) a tablice od i (włącznie) w górę
    traktujesz jak swoją pierwszą tablicę (źródło nieuzytych liczb).
    I robisz tak samo, czyli losujesz z niej jeden element, zamiast
    jednak przesyłąć go do innej tablicy i zatykać największym,
    przestawiasz go w miejsce i, a dzirę zatykasz tym, co było na miejscu i.

    To tzw, "Knuth shuffle".

    https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_s
    huffle#The_modern_algorithm

    -- To shuffle an array a of n elements (indices 0..n-1):
    for i from 0 to n-2 do
    j <- random integer such that 0 <= j < n-i
    exchange a[i] and a[i+j]

    Wydawało mi się, że jest powszechnie znany. Niczym qsort.
    To on siedzie (być mozę w wersji 'od tyłu') w std::random_shuffle.

    pzdr
    bartekltg


  • 5. Data: 2016-04-23 11:38:32
    Temat: Re: Szybki algorytm na permutację
    Od: "M.M." <m...@g...com>

    On Saturday, April 23, 2016 at 1:47:09 AM UTC+2, bartekltg wrote:
    > On 22.04.2016 18:43, M.M. wrote:
    > > On Friday, April 22, 2016 at 12:22:35 AM UTC+2, Borneq wrote:
    > >> z wykorzystaniem random()
    > >> Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    > >> drugą, początkowo wielkości 0.
    > >> Z posortowanych wybieram za pomocą random(n) któryś element, i
    > >> najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    > >> element ostatni.
    > >> Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    > >> I tak dalej
    >
    > >
    > > Może tak?
    > > for( int i=1 ; i<=N ; i++ )
    > > tab[i] = i;
    > > for( int i=0 ; i<N*2 ; i++ )
    > > swp( tab[rand()%N] , tab[rand()%N] );
    >
    > Bardzo źle.
    > Wynonujesz 4N losowań.
    > Czy rozkład wyniku jest równomierny, wcale bym się nie zakładał.
    >
    > pzdr
    > bartekltg

    Nie wiem, też bym się nie założył, ale na pewno Knuth shuffle dał
    mniejsze odchylenie standardowe w kilku testach:


    #include <cstdio>
    #include <cstdlib>
    #include <ctime>
    #include <QHash>
    #include <QString>
    #include <cmath>

    #define N (10000000)
    #define M (5)

    static void swp( int &a , int &b ) {
    const int x = a;
    a = b;
    b = x;
    }

    static QHash<QString,int> test1() {
    QHash<QString,int> hash;
    for( int i=0 ; i<N ; i++ ) {
    int tab[M];
    for( int j=0 ; j<M ; j++ )
    tab[j] = j;
    for( int j=0 ; j<M*2 ; j++ )
    swp( tab[rand()%M] , tab[rand()%M] );
    QString p;
    for( int j=0 ; j<M ; j++ )
    p.append( QString::number(tab[j]) );
    if( hash.contains(p) )
    hash[p]++;
    else
    hash.insert(p,1);
    }
    return hash;
    }


    static QHash<QString,int> test2() {
    QHash<QString,int> hash;
    for( int i=0 ; i<N ; i++ ) {
    int tab[M];
    for( int j=0 ; j<M ; j++ )
    tab[j] = j;
    for( int j=0 ; j<M-1 ; j++ )
    swp( tab[j] , tab[ j + rand()%(M-j) ] );
    QString p;
    for( int j=0 ; j<M ; j++ )
    p.append( QString::number(tab[j]) );
    if( hash.contains(p) )
    hash[p]++;
    else
    hash.insert(p,1);
    }
    return hash;
    }


    static void stat( const QHash<QString,int> &hash ) {
    double sum=0, sum2=0, avg, cnt=0, min=1, max=0;
    for( QHash<QString,int>::const_iterator i=hash.begin() ; i!=hash.end() ; ++i ) {
    const double tmp = (double) i.value() / N;
    sum += tmp;
    cnt ++ ;
    if( min > tmp ) min = tmp;
    if( max < tmp ) max = tmp;
    }
    avg = sum / cnt;
    for( QHash<QString,int>::const_iterator i=hash.begin() ; i!=hash.end() ; ++i ) {
    const double tmp = (double) i.value() / N;
    sum2 += (tmp-avg) * (tmp-avg);
    }

    printf("cnt=%.0lf sum=%lf min=%lf max=%lf avg=%lf std=%lf\n" , cnt , sum , min ,
    max , avg , sqrt( sum2 / cnt ) );
    fflush(stdout);

    }

    int main(int argc, char *argv[])
    {
    const uint seed = (uint)time(NULL);
    printf("seed = %u\n",seed);

    srand( seed );
    {
    const QHash<QString,int> hash = test1();
    stat(hash);
    }

    srand( seed );
    {
    const QHash<QString,int> hash = test2();
    stat(hash);
    }

    return 0;
    }

    seed = 1461404107
    cnt=120 sum=1.000000 min=0.008029 max=0.009185 avg=0.008333 std=0.000209
    cnt=120 sum=1.000000 min=0.008270 max=0.008425 avg=0.008333 std=0.000029


  • 6. Data: 2016-04-23 11:47:44
    Temat: Re: Szybki algorytm na permutację
    Od: bartekltg <b...@g...com>

    On 23.04.2016 11:38, M.M. wrote:
    > On Saturday, April 23, 2016 at 1:47:09 AM UTC+2, bartekltg wrote:
    >> >On 22.04.2016 18:43, M.M. wrote:
    >>> > >On Friday, April 22, 2016 at 12:22:35 AM UTC+2, Borneq wrote:
    >>>> > >>z wykorzystaniem random()
    >>>> > >>Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    >>>> > >>drugą, początkowo wielkości 0.
    >>>> > >>Z posortowanych wybieram za pomocą random(n) któryś element, i
    >>>> > >>najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    >>>> > >>element ostatni.
    >>>> > >>Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    >>>> > >>I tak dalej
    >> >
    >>> > >
    >>> > >Może tak?
    >>> > >for( int i=1 ; i<=N ; i++ )
    >>> > > tab[i] = i;
    >>> > >for( int i=0 ; i<N*2 ; i++ )
    >>> > > swp( tab[rand()%N] , tab[rand()%N] );
    >> >
    >> >Bardzo źle.
    >> >Wynonujesz 4N losowań.
    >> >Czy rozkład wyniku jest równomierny, wcale bym się nie zakładał.
    >> >
    >> >pzdr
    >> >bartekltg
    > Nie wiem, też bym się nie założył, ale na pewno Knuth shuffle dał
    > mniejsze odchylenie standardowe w kilku testach:


    Knutha możęsz policzyć. Bardzo prosto. Wymyśl dowolną
    permutację i licz prawdopodobieństwo, że ją wylosujesz.
    W każdym kroku musisz wybrać właściwa liczbę i nie ma potem
    możliwośći popsucia. 1 liczba z n, 1 liczba z n-1....
    Łącznie prawdopodobieństwo 1/n! Identyczne dla dowolnej permutacji.


    BTW, dlaczego wołasz srand( seed ); dwa razy?


    pzdr
    bartekltg


  • 7. Data: 2016-04-23 12:10:05
    Temat: Re: Szybki algorytm na permutację
    Od: "M.M." <m...@g...com>

    On Saturday, April 23, 2016 at 11:47:45 AM UTC+2, bartekltg wrote:
    > On 23.04.2016 11:38, M.M. wrote:
    > > On Saturday, April 23, 2016 at 1:47:09 AM UTC+2, bartekltg wrote:
    > >> >On 22.04.2016 18:43, M.M. wrote:
    > >>> > >On Friday, April 22, 2016 at 12:22:35 AM UTC+2, Borneq wrote:
    > >>>> > >>z wykorzystaniem random()
    > >>>> > >>Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    > >>>> > >>drugą, początkowo wielkości 0.
    > >>>> > >>Z posortowanych wybieram za pomocą random(n) któryś element, i
    > >>>> > >>najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    > >>>> > >>element ostatni.
    > >>>> > >>Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    > >>>> > >>I tak dalej
    > >> >
    > >>> > >
    > >>> > >Może tak?
    > >>> > >for( int i=1 ; i<=N ; i++ )
    > >>> > > tab[i] = i;
    > >>> > >for( int i=0 ; i<N*2 ; i++ )
    > >>> > > swp( tab[rand()%N] , tab[rand()%N] );
    > >> >
    > >> >Bardzo źle.
    > >> >Wynonujesz 4N losowań.
    > >> >Czy rozkład wyniku jest równomierny, wcale bym się nie zakładał.
    > >> >
    > >> >pzdr
    > >> >bartekltg
    > > Nie wiem, też bym się nie założył, ale na pewno Knuth shuffle dał
    > > mniejsze odchylenie standardowe w kilku testach:
    >
    >
    > Knutha możęsz policzyć. Bardzo prosto. Wymyśl dowolną
    > permutację i licz prawdopodobieństwo, że ją wylosujesz.
    > W każdym kroku musisz wybrać właściwa liczbę i nie ma potem
    > możliwośći popsucia. 1 liczba z n, 1 liczba z n-1....
    > Łącznie prawdopodobieństwo 1/n! Identyczne dla dowolnej permutacji.

    Tak, zaletą knutha jest to, że można łatwo przeprowadzić dowód.



    > BTW, dlaczego wołasz srand( seed ); dwa razy?
    Chyba z rozpędu, zazwyczaj trzeba zadbać o to, aby obie metody dostały
    ten sam losowy ciąg, ale tutaj jest inna ilość losowań, więc
    nic to nie daje.

    Pozdrawiam

strony : [ 1 ]


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: