Forum Coders' city Strona Gwna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UytkownicyUytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj si, by sprawdzi wiadomociZaloguj si, by sprawdzi wiadomoci   ZalogujZaloguj 

Potrzebuj szybkiej odpowiedzi na moje pytanie... Zasady

Losowanie Liczb

Id do strony Poprzedni  1, 2

 
Odpowiedz do tematu    Forum Coders' city Strona Gwna -> Pole do popisu (beta testy)
Zobacz poprzedni temat :: Zobacz nastpny temat  
Autor Wiadomo
Adept
Go





PostWysany: Nie Sty 01, 2017 10:12 pm      Temat postu: Losowanie liczb Odpowiedz z cytatem Pisownia

Panie Marcinie ma Pan racje tamte algorytmy s do bani o to nowa wersja :)
Kod:
{ algorytm losowania - niepowtarzajcych si liczb}
          i := 1;
               repeat
                     if i = 1 then
                         begin
                              losowe_liczby[i] := random(6);
                         end
                     else
                         begin
                              { writeln('wartosc i = ',i); }
                              losowe_liczby[i] := random(6);
                              j := i - 1;
                              poprzednia := j;
                              repeat
                                    if losowe_liczby[i] = losowe_liczby[j] then
                                       begin
                                            { writeln(i,' ',j); }
                                            losowe_liczby[i] := random(6);
                                            j := poprzednia
                                       end
                                    else
                                        j := j - 1;
                              until j < 1;
                         end;
               write(losowe_liczby[i]:4);
               i := i + 1;
               until i > 6;
{ koniec algorytmu }
Powrt do gry
marcin_an



Doczy: 26 Maj 2005
Posty: 18818

PostWysany: Pon Sty 02, 2017 4:37 am      Temat postu: Odpowiedz z cytatem Pisownia

Mam nadziej, e "Panie" to grzeczno, a nie sarkazm :>.

Nie zrozumiae jednak, dlaczego tamte algorytmyu s "do bani". Zrobie kolejny, ktry ma dokadnie ten sam problem, co poprzednie - prbuje losowa "a si uda". Tym samym nie zrozumiae wcale, czemu tamte byy ze.

Co gorsze: o ile poprzednie - przynajmniej przy nieskoczenie wielkiej liczbie krokw - dadz prawidowy wynik, o tyle ten koczy siw przewidywalnym czasie... dajc wynik bdny. Jest tak dlatego, e linia 18 moe wprowadzi liczb, ktra jest ju w tablicy wynikowej. I nie, nie prbuj tego ata kolejn ptl, ktr potem zaatasz jeszcze nastpn, bo nie w tym rzecz - samo podejcie, jakie prbujesz zastosowa, jest z zaoenia bdne i nigdy nie uda ci sizrobi w ten sposb dziaajcego rozwizania*.

Popatrz, co napisaem ja i Olo. To sproste opisy. Jeli chcesz sizagbi w tspraw, to na angielskiej Wikipedii masz cae serie artykuw na ten temat: Fisher-Yates, pseudo-random number sampling lub reservoir sampling - omawiaj zagadnienie dla rnych zaoe, nie tylko prostego wyboru ze zbioru dyskretnego z rozkadem jednostajnym. Nie zrozum mnie le. Bardzo dobrze, e prbujesz cosam wykombinowa! Ale w sytuacji, gdy zostao pokazane, e to nie zadziaa, nie ma sensu wywaa otwartych drzwi.

Na marginesie: to, co prbowae uzyska, ale w konwencjonalnej i prostej formie:
Kod:
n: liczba elementw wyniku
w[1], w[2], ..., w[n]: cig elementw wyjciowych
max: najwysza moliwa do wylosowania liczba (49 dla Lotto)

DLA i = 1 DO n:
    POWTARZAJ:
        w[i] := losuj od 1 do max
        szukaj_dalej := nie
        j := 1
        DOPKI j < i ORAZ szukaj_dalej == nie
            JEELI w[i] = w[j]:
                szukaj_dalej := tak
    DOPKI szukaj_dalej

Rozwizanie w skrcie: dla kadego elementu wynikowego (linia 5) losuj tak dugo (linie 6-13), a wylosowana liczba nie bdzie wystpowaa we wczeniej losowanych elementach (linie 10-12). Oczywicie ma ten sam fehler, o ktrym cay czas bya mowa.

W zaczniku llosow.png podany jest (czciowy) rozkad prawdopodobiestwa tego, e uzyskanie zajmie wicej ni x losowa. To powinno ci wyjani, dlaczego podczas twoich testw program koczy sizawsze szybko. Prawdopodobiestwo znacznego opnienia jest zbyt mae, by dao si je zmierzy pojedynczymi testami - szczeglnie przy tak mikroskopijnych danych.

Drugi zestaw wykresw pokazuje jednak obraz dla rnych rozmiarw problemu. Przedstawia koszt pobrania danej liczby elementw z 1000 moliwoci, porwnujc z rozwizaniem zaproponowanym przeze mnie (Fisher-Yates) oraz Olo (select+remove). Poniewa rozwizanie "prbuj do skutku" jest losowe, jego koszt mona omawia tylko w kategoriach rozkadu prawdopodobiestwa, std po trzy linie: jedna dla kosztu w przypadku optymistycznym (gdy zawsze od razu uda siwylosowa waciwe dane), koszt dla lepszej poowy przypadkw (mediana) i koszt, w ktrym mieci si 99.9% przypadkw. Oczywicie takie linie - idce coraz wyej a do nieskoczonoci - mona rysowa dla coraz szerszego zakresu przypadkw, wic nie naley pomaraczowej linii rozumie jako "nigdy nie bdzie gorzej". W 100 na 100 tysicy prb bdzie gorzej. Koszt mona te wyrazi jako liczenie rnych operacji: tutaj grny wykres liczy losowania pojedynej liczby, dolny dostp do pamici. Lewe wykresy s w skali liniowej, ale dla duych wartoci jest ona niewygodna - std po prawej identyczne dane w skali logarytmicznej.

Co z tych obrazkw wynika? Przy wikszej liczbie potrzebnych elementw, "prbowanie do skutku" zaczyna by bardzo kosztowne, zawsze jest drosze od algorytmy Olo i dla wybierania duego podzbioru bdzie gorsze od Fisher-Yates**. Prawdziwa tragedia zaczyna si jednak przy liczeniu odwoa do pamici. Podejcie "do skutku" ma bowiem zoono kwadratow (optymistycznie!), podczas gdy obydwa rozwizania alternatywne - liniow. Nawet dla maych podzbiorw odpadnie w przedbiegach, dla wikszych koszt jest tak ogromny, e eby mc porwnywa te algorytmu, konieczna jest skala logarytmiczna - inaczej Fisher-Yates i wybieranie z usuwaniem bd pask lini przy 0. Olo wygrywa natychmiast, F-Y docza do zwycizcy chwil pniej.
____
* Dla formalnoci, eby kto mi nie wytkn, e istnieje szczeglna klasa sytuacji, gdzie rozwizanie przez "losowanie do skutku" dziaa i ma sens: odpowiadam osobie pocztkujcej. Jeli Adept bdzie w stanie samodzielnie policzy koszt oczekiwany alternatywnych podej dla rnych parametrw i ocenia jego znaczenie, to bdziemy rozmawia na temat probabilistycznych struktur danych i algorytmw. Na razie jest to temat poza rozwaaniami.
** I tu poprawka: Fisher-Yates powinien mie koszt 1000. Niechccy 2-krotnie pogorszyem swoje wasne rozwizanie ;).



llosow.png
 Opis:

Pobierz
 Nazwa pliku:  llosow.png
 Wielko pliku:  6.19 KB
 Pobierano:  41 raz(y)


koszt.png
 Opis:

Pobierz
 Nazwa pliku:  koszt.png
 Wielko pliku:  29.63 KB
 Pobierano:  38 raz(y)

Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo
Adept
Go





PostWysany: Wto Sty 03, 2017 1:44 pm      Temat postu: Losowanie liczb Odpowiedz z cytatem Pisownia

Cytat:
Co gorsze: o ile poprzednie - przynajmniej przy nieskoczenie wielkiej liczbie krokw - dadz prawidowy wynik, o tyle ten koczy si w przewidywalnym czasie... dajc wynik bdny. Jest tak dlatego, e linia 18 moe wprowadzi liczb, ktra jest ju w tablicy wynikowej. I nie, nie prbuj tego ata kolejn ptl, ktr potem zaatasz jeszcze nastpn, bo nie w tym rzecz - samo podejcie, jakie prbujesz zastosowa, jest z zaoenia bdne i nigdy nie uda ci si zrobi w ten sposb dziaajcego rozwizania*.


Panie Marcinie jest Pan w bdzie o to implementacja, ktra dziaa i co Pan na to ?



LOSOWANI.PAS
 Opis:

Pobierz
 Nazwa pliku:  LOSOWANI.PAS
 Wielko pliku:  1.75 KB
 Pobierano:  29 raz(y)

Powrt do gry
Adept
Go





PostWysany: Pi Sty 06, 2017 8:22 pm      Temat postu: Losowanie liczb Odpowiedz z cytatem Pisownia

Niewykluczone, e komu si przyda
Implementacja algorytmu losujcego bez powtrze + algorytm sortowania :)[/url]



LOSOWANI.PAS
 Opis:

Pobierz
 Nazwa pliku:  LOSOWANI.PAS
 Wielko pliku:  2.8 KB
 Pobierano:  21 raz(y)

Powrt do gry
marcin_an



Doczy: 26 Maj 2005
Posty: 18818

PostWysany: Pi Sty 06, 2017 8:54 pm      Temat postu: Odpowiedz z cytatem Pisownia

Adept nie jest zbytnio zainteresowany nauczeniem siczegokolwiek i ignoruje, co zostao do niego napisane, ale gdyby komuprzyszo do gowy uywa jego kodu: wczeniejsze posty podaj, dlaczego to rozwizanie nie dziaa (i dlaczego nowicjuszom moe siwydawa, e "dziaa").
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo
Adept
Go





PostWysany: Sob Sty 07, 2017 12:26 pm      Temat postu: Losowanie liczb Odpowiedz z cytatem Pisownia

NIE JESTEM ZAWODOWYM PROGRAMISTA !!! TYLKO PASJONATEM !!!

Moim celem byo takie opracowanie algorytmu, ktry losowaby liczby z ZAKRESU OD DO przy czym TE wylosowane liczby maja si nie powtarza.

Dodane przez moderatora (czenie postw)

Miedzy innymi ten temat jest odpowiedzi na tego typu wpisy http://www.elektroda.pl/rtvforum/topic1314669.html, http://forum.pasja-informatyki.pl/21511/ponowne-losowanie-liczby,http://www.gry-online.pl/S043.asp?ID=12893772

Zmieniona wersja tego samego paragramu dobitnie pokazuje, e program losuje liczby bez powtrze, cho korzysta on z funkcji random.

Oczywicie mona te wykorzysta taki algorytm: http://www.algorytm.org/liczby-pseudolosowe/losowanie-bez-powtorzen.html.

Moim zdaniem oba algorytmy s prawidowe. Co prawda korzystajc z funkcji random czas wykonywania programu jest wprost proporcjonalny do iloci losowanych liczb. Niemniej przetestowaem dla zakresu 32767 a ilo losowanych liczb to 32400 - czas wykonania 28 - 30 sekund.

Zasada dziaania algorytmu jest bardzo prosta. Algorytm porwnuje biec wylosowan liczb z liczbami dotychczasowymi i jeli owa liczba si nie powtarza to zapisuje j do tablicy w przeciwnym razie losuje ponownie.

Co do zarzutw Pana Marcina:

Zostaje pytanie o celowo w jakim celu ? :). Przecie kady kto szuka odpowiedzi na powysze wpisy tu znajduje rozwizanie. Co innego dla naukowca, wynalazcy, zawodowego programisty pracujcego przy ambitnym projekcie, ale dla podanych linkw ? Jaki pasjonat miaby przetwarza due zbiory liczb i w jakim celu ?



LOSOWANI.PAS
 Opis:

Pobierz
 Nazwa pliku:  LOSOWANI.PAS
 Wielko pliku:  2.79 KB
 Pobierano:  18 raz(y)

Powrt do gry
marcin_an



Doczy: 26 Maj 2005
Posty: 18818

PostWysany: Sob Sty 07, 2017 6:06 pm      Temat postu: Odpowiedz z cytatem Pisownia

Zrobi sobie rur gazow z papieru, bo jestem amatorem, a nie zawodowcem. Co z tego, e obok ley prawdziwy wyk, ktry jest lepszy, wygodniejszy i atwiejszy w uyciu? Prawdziwe s dla zawodowcw i naukowcw, a nie hobbystw. A potem pjd na forum dla gazownikw, zapytam o opini i bd krci nosem, e opinidostaj. I jeszcze tumaczy si, e wszystko gra, bo moje rozwizanie nie jest specjalnie dla zawodowcw, tylko amatorw.

Osoby, ktre chciayby uy powyszego kodu: w tym wtku na pierwszej stronie podane s dwa naprawd dziaajce rozwizania, o wiele prostsze i wygodniejsze do zastosowania. Rozwizanie Adepta nie dziaa i nigdy nie bdzie dziaao, a przyczyna tego (oraz tego, dlaczego ma zudzenie, e co mu tam "dziaa") jest opisana kilka postw wyej.

Implementacje oparte o Fisher-Yates dla kilku popularnych jzykw, eby kolejni nie musieli wynajdywa od nowa koa:
Python:
Kod:
#!/usr/bin/env python
import random

for element in random.sample(range(1, 49), 6):
    print(element)

Groovy:
Kod:
#!/usr/bin/env groovy

def values = (1..49) as ArrayList
Collections.shuffle(values, new Random())
values.stream().limit(6).forEach {println(it)}

Java:
Kod:
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public final class Main {
    
    public static void main(final String[] args) {
        final List<Integer> input
              = IntStream.range(1, 49).boxed().collect(Collectors.toList());
        Collections.shuffle(input, new Random());
        input.stream().limit(6).forEach(System.out::println);
    }
}

PHP:
Kod:
<?php
$input = range(1, 49);
shuffle($input);
for ($i = 0; $i < 6; ++$i) {
    echo $input[$i], "\n";
}

C++:
Kod:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
#include <cstdlib>
using namespace ::std;

template <class T>
    class SequenceGenerator
    {
        public:
            explicit SequenceGenerator(T const& value)
                : value(value) {}
            
            T operator()()
            {
                return value++;
            }
        
        private:
            T value;
    };

int main()
{
    vector<int> input;
    
    generate_n(back_insert_iterator<vector<int>>(input),
          49, SequenceGenerator<int>(1));
    shuffle(input.begin(), input.end(), mt19937(random_device()()));
    copy_n(input.begin(), 6, ostream_iterator<int>(cout, "\n"));
    
    return EXIT_SUCCESS;
}


Alternatywnie mona sobie zaimplementowa rozwizanie Olo.

Dla zastosowa hobbystycznych nie ma to znacenia, ale powysze kody zakadaj prawidow implementacj generatora pseudolosowego i jego uycie, co jest zalene od jakoci dostarczanej biblioteki standardowej. W szczeglnoci:
  1. adna z uytych funkcji nie daje w/w gwarancji w specyfikacji.
  2. Java (i Groovy) moguy metody java.util.Random.nextInt(int), ktra ma nieokrelony czas dziaania*.
  3. Java (i Groovy) uywaj LCG. Lepsze wyniki da org.apache.commons.math3.random.MersenneTwister.
Jeli komuzaley na okrelonych parametrach, naley upewni sico do jakoci implementacji lub dostarczy inny generator.
____
* Sytuacja analogiczna jak w kodzie Adepta, ale z lepszym rozkadem prawdopodobiestwa zakoczenia.
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo
Wywietl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Gwna -> Pole do popisu (beta testy) Wszystkie czasy w strefie CET (Europa)
Id do strony Poprzedni  1, 2
Strona 2 z 2

 
Skocz do:  
Moesz pisa nowe tematy
Moesz odpowiada w tematach
Nie moesz zmienia swoich postw
Nie moesz usuwa swoich postw
Nie moesz gosowa w ankietach
Moesz dodawa zaczniki na tym forum
Moesz pobiera pliki z tego forum




Debug: strone wygenerowano w 0.08517 sekund, zapytan = 13
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |