Forum Coders' city Strona G³ówna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   U¿ytkownicyU¿ytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj siê, by sprawdziæ wiadomo¶ciZaloguj siê, by sprawdziæ wiadomo¶ci   ZalogujZaloguj 

Potrzebujê szybkiej odpowiedzi na moje pytanie... Zasady

Losowanie Liczb

Id¼ do strony Poprzedni  1, 2

 
Odpowiedz do tematu    Forum Coders' city Strona G³ówna -> Pole do popisu (beta testy)
Zobacz poprzedni temat :: Zobacz nastêpny temat  
Autor Wiadomo¶æ
Adept
Go¶æ





PostWys³any: 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 - niepowtarzaj±cych 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 }
Powrót do góry
marcin_an



Do³±czy³: 26 Maj 2005
Posty: 18822

PostWys³any: Pon Sty 02, 2017 4:37 am      Temat postu: Odpowiedz z cytatem Pisownia

Mam nadziejê, ¿e "Panie" to grzeczno¶æ, a nie sarkazm :>.

Nie zrozumia³e¶ jednak, dlaczego tamte algorytmyu s± "do bani". Zrobi³e¶ kolejny, który ma dok³adnie ten sam problem, co poprzednie - próbuje losowaæ "a¿ siê uda". Tym samym nie zrozumia³e¶ wcale, czemu tamte by³y z³e.

Co gorsze: o ile poprzednie - przynajmniej przy nieskoñczenie wielkiej liczbie kroków - dadz± prawid³owy wynik, o tyle ten koñczy siê w przewidywalnym czasie... daj±c wynik b³êdny. Jest tak dlatego, ¿e linia 18 mo¿e wprowadziæ liczbê, która jest ju¿ w tablicy wynikowej. I nie, nie próbuj tego ³ataæ kolejn± pêtl±, któr± potem za³atasz jeszcze nastêpn±, bo nie w tym rzecz - samo podej¶cie, jakie próbujesz zastosowaæ, jest z za³o¿enia b³êdne i nigdy nie uda ci siê zrobiæ w ten sposób dzia³aj±cego rozwi±zania*.

Popatrz, co napisa³em ja i Olo. To s± proste opisy. Je¶li chcesz siê zag³êbiæ w tê sprawê, to na angielskiej Wikipedii masz ca³e serie artyku³ów na ten temat: Fisher-Yates, pseudo-random number sampling lub reservoir sampling - omawiaj± zagadnienie dla ró¿nych za³o¿eñ, nie tylko prostego wyboru ze zbioru dyskretnego z rozk³adem jednostajnym. Nie zrozum mnie ¼le. Bardzo dobrze, ¿e próbujesz co¶ sam wykombinowaæ! Ale w sytuacji, gdy zosta³o pokazane, ¿e to nie zadzia³a, nie ma sensu wywa¿aæ otwartych drzwi.

Na marginesie: to, co próbowa³e¶ uzyskaæ, ale w konwencjonalnej i prostej formie:
Kod:
n: liczba elementów wyniku
w[1], w[2], ..., w[n]: ci±g elementów wyj¶ciowych
max: najwy¿sza mo¿liwa do wylosowania liczba (49 dla Lotto)

DLA i = 1 DO n:
    POWTARZAJ:
        w[i] := losuj od 1 do max
        szukaj_dalej := nie
        j := 1
        DOPÓKI j < i ORAZ szukaj_dalej == nie
            JE¯ELI w[i] = w[j]:
                szukaj_dalej := tak
    DOPÓKI szukaj_dalej

Rozwi±zanie w skrócie: dla ka¿dego elementu wynikowego (linia 5) losuj tak d³ugo (linie 6-13), a¿ wylosowana liczba nie bêdzie wystêpowa³a we wcze¶niej losowanych elementach (linie 10-12). Oczywi¶cie ma ten sam fehler, o którym ca³y czas by³a mowa.

W za³±czniku llosow.png podany jest (czê¶ciowy) rozk³ad prawdopodobieñstwa tego, ¿e uzyskanie zajmie wiêcej ni¿ x losowañ. To powinno ci wyja¶niæ, dlaczego podczas twoich testów program koñczy³ siê zawsze szybko. Prawdopodobieñstwo znacznego opó¼nienia jest zbyt ma³e, by da³o siê je zmierzyæ pojedynczymi testami - szczególnie przy tak mikroskopijnych danych.

Drugi zestaw wykresów pokazuje jednak obraz dla ró¿nych rozmiarów problemu. Przedstawia koszt pobrania danej liczby elementów z 1000 mo¿liwo¶ci, porównuj±c z rozwi±zaniem zaproponowanym przeze mnie (Fisher-Yates) oraz Olo (select+remove). Poniewa¿ rozwi±zanie "próbuj do skutku" jest losowe, jego koszt mo¿na omawiaæ tylko w kategoriach rozk³adu prawdopodobieñstwa, st±d po trzy linie: jedna dla kosztu w przypadku optymistycznym (gdy zawsze od razu uda siê wylosowaæ w³a¶ciwe dane), koszt dla lepszej po³owy przypadków (mediana) i koszt, w którym mie¶ci siê 99.9% przypadków. Oczywi¶cie takie linie - id±ce coraz wy¿ej a¿ do nieskoñczono¶ci - mo¿na rysowaæ dla coraz szerszego zakresu przypadków, wiêc nie nale¿y pomarañczowej linii rozumieæ jako "nigdy nie bêdzie gorzej". W 100 na 100 tysiêcy prób bêdzie gorzej. Koszt mo¿na te¿ wyraziæ jako liczenie ró¿nych operacji: tutaj górny wykres liczy losowania pojedynej liczby, dolny dostêp do pamiêci. Lewe wykresy s± w skali liniowej, ale dla du¿ych warto¶ci jest ona niewygodna - st±d po prawej identyczne dane w skali logarytmicznej.

Co z tych obrazków wynika? Przy wiêkszej liczbie potrzebnych elementów, "próbowanie do skutku" zaczyna byæ bardzo kosztowne, zawsze jest dro¿sze od algorytmy Olo i dla wybierania du¿ego podzbioru bêdzie gorsze od Fisher-Yates**. Prawdziwa tragedia zaczyna siê jednak przy liczeniu odwo³añ do pamiêci. Podej¶cie "do skutku" ma bowiem z³o¿ono¶æ kwadratow± (optymistycznie!), podczas gdy obydwa rozwi±zania alternatywne - liniow±. Nawet dla ma³ych podzbiorów odpadnie w przedbiegach, dla wiêkszych koszt jest tak ogromny, ¿e ¿eby móc porównywaæ te algorytmu, konieczna jest skala logarytmiczna - inaczej Fisher-Yates i wybieranie z usuwaniem bêd± p³ask± lini± przy 0. Olo wygrywa natychmiast, F-Y do³±cza do zwyciêzcy chwilê pó¼niej.
____
* Dla formalno¶ci, ¿eby kto¶ mi nie wytkn±³, ¿e istnieje szczególna klasa sytuacji, gdzie rozwi±zanie przez "losowanie do skutku" dzia³a i ma sens: odpowiadam osobie pocz±tkuj±cej. Je¶li Adept bêdzie w stanie samodzielnie policzyæ koszt oczekiwany alternatywnych podej¶æ dla ró¿nych parametrów i oceniaæ jego znaczenie, to bêdziemy rozmawiaæ na temat probabilistycznych struktur danych i algorytmów. Na razie jest to temat poza rozwa¿aniami.
** I tu poprawka: Fisher-Yates powinien mieæ koszt 1000. Niechc±cy 2-krotnie pogorszy³em swoje w³asne rozwi±zanie ;).



llosow.png
 Opis:

Pobierz
 Nazwa pliku:  llosow.png
 Wielko¶æ pliku:  6.19 KB
 Pobierano:  59 raz(y)


koszt.png
 Opis:

Pobierz
 Nazwa pliku:  koszt.png
 Wielko¶æ pliku:  29.63 KB
 Pobierano:  60 raz(y)

Powrót do góry
Zobacz profil autora Wy¶lij prywatn± wiadomo¶æ
Adept
Go¶æ





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

Cytat:
Co gorsze: o ile poprzednie - przynajmniej przy nieskoñczenie wielkiej liczbie kroków - dadz± prawid³owy wynik, o tyle ten koñczy siê w przewidywalnym czasie... daj±c wynik b³êdny. Jest tak dlatego, ¿e linia 18 mo¿e wprowadziæ liczbê, która jest ju¿ w tablicy wynikowej. I nie, nie próbuj tego ³ataæ kolejn± pêtl±, któr± potem za³atasz jeszcze nastêpn±, bo nie w tym rzecz - samo podej¶cie, jakie próbujesz zastosowaæ, jest z za³o¿enia b³êdne i nigdy nie uda ci siê zrobiæ w ten sposób dzia³aj±cego rozwi±zania*.


Panie Marcinie jest Pan w b³êdzie o to implementacja, która dzia³a i co Pan na to ?



LOSOWANI.PAS
 Opis:

Pobierz
 Nazwa pliku:  LOSOWANI.PAS
 Wielko¶æ pliku:  1.75 KB
 Pobierano:  49 raz(y)

Powrót do góry
Adept
Go¶æ





PostWys³any: Pi± Sty 06, 2017 8:22 pm      Temat postu: Losowanie liczb Odpowiedz z cytatem Pisownia

Niewykluczone, ¿e komu¶ siê przyda
Implementacja algorytmu losuj±cego bez powtórzeñ + algorytm sortowania :)[/url]



LOSOWANI.PAS
 Opis:

Pobierz
 Nazwa pliku:  LOSOWANI.PAS
 Wielko¶æ pliku:  2.8 KB
 Pobierano:  42 raz(y)

Powrót do góry
marcin_an



Do³±czy³: 26 Maj 2005
Posty: 18822

PostWys³any: Pi± Sty 06, 2017 8:54 pm      Temat postu: Odpowiedz z cytatem Pisownia

Adept nie jest zbytnio zainteresowany nauczeniem siê czegokolwiek i ignoruje, co zosta³o do niego napisane, ale gdyby komu¶ przysz³o do g³owy u¿ywaæ jego kodu: wcze¶niejsze posty podaj±, dlaczego to rozwi±zanie nie dzia³a (i dlaczego nowicjuszom mo¿e siê wydawaæ, ¿e "dzia³a").
Powrót do góry
Zobacz profil autora Wy¶lij prywatn± wiadomo¶æ
Adept
Go¶æ





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

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

Moim celem by³o takie opracowanie algorytmu, który losowa³by liczby z ZAKRESU OD DO przy czym TE wylosowane liczby maja siê nie powtarzaæ.

Dodane przez moderatora (³±czenie postów)

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 powtórzeñ, choæ korzysta on z funkcji random.

Oczywi¶cie mo¿na te¿ wykorzystaæ taki algorytm: http://www.algorytm.org/liczby-pseudolosowe/losowanie-bez-powtorzen.html.

Moim zdaniem oba algorytmy s± prawid³owe. Co prawda korzystaj±c z funkcji random czas wykonywania programu jest wprost proporcjonalny do ilo¶ci losowanych liczb. Niemniej przetestowa³em dla zakresu 32767 a ilo¶æ losowanych liczb to 32400 - czas wykonania 28 - 30 sekund.

Zasada dzia³ania algorytmu jest bardzo prosta. Algorytm porównuje bie¿±c± wylosowan± liczbê z liczbami dotychczasowymi i je¶li owa liczba siê nie powtarza to zapisuje do tablicy w przeciwnym razie losuje ponownie.

Co do zarzutów Pana Marcina:

Zostaje pytanie o celowo¶æ w jakim celu ? :). Przecie¿ ka¿dy kto szuka odpowiedzi na powy¿sze wpisy tu znajduje rozwi±zanie. Co innego dla naukowca, wynalazcy, zawodowego programisty pracuj±cego przy ambitnym projekcie, ale dla podanych linków ? Jaki pasjonat mia³by przetwarzaæ du¿e zbiory liczb i w jakim celu ?



LOSOWANI.PAS
 Opis:

Pobierz
 Nazwa pliku:  LOSOWANI.PAS
 Wielko¶æ pliku:  2.79 KB
 Pobierano:  37 raz(y)

Powrót do góry
marcin_an



Do³±czy³: 26 Maj 2005
Posty: 18822

PostWys³any: 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 le¿y prawdziwy wê¿yk, który jest lepszy, wygodniejszy i ³atwiejszy w u¿yciu? Prawdziwe s± dla zawodowców i naukowców, a nie hobbystów. A potem pójdê na forum dla gazowników, zapytam o opiniê i bêdê krêci³ nosem, ¿e opiniê dostajê. I jeszcze t³umaczy³ siê, ¿e wszystko gra, bo moje rozwi±zanie nie jest specjalnie dla zawodowców, tylko amatorów.

Osoby, które chcia³yby u¿yæ powy¿szego kodu: w tym w±tku na pierwszej stronie podane s± dwa naprawdê dzia³aj±ce rozwi±zania, o wiele prostsze i wygodniejsze do zastosowania. Rozwi±zanie Adepta nie dzia³a i nigdy nie bêdzie dzia³a³o, a przyczyna tego (oraz tego, dlaczego ma z³udzenie, ¿e co¶ mu tam "dzia³a") jest opisana kilka postów wy¿ej.

Implementacje oparte o Fisher-Yates dla kilku popularnych jêzyków, ¿eby kolejni nie musieli wynajdywaæ od nowa ko³a:
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 mo¿na sobie zaimplementowaæ rozwi±zanie Olo.

Dla zastosowañ hobbystycznych nie ma to znacenia, ale powy¿sze kody zak³adaj± prawid³ow± implementacjê generatora pseudolosowego i jego u¿ycie, co jest zale¿ne od jako¶ci dostarczanej biblioteki standardowej. W szczególno¶ci:
  1. ¯adna z u¿ytych funkcji nie daje w/w gwarancji w specyfikacji.
  2. Java (i Groovy) mog± u¿yæ metody java.util.Random.nextInt(int), która ma nieokre¶lony czas dzia³ania*.
  3. Java (i Groovy) u¿ywaj± LCG. Lepsze wyniki da org.apache.commons.math3.random.MersenneTwister.
Je¶li komu¶ zale¿y na okre¶lonych parametrach, nale¿y upewniæ siê co do jako¶ci implementacji lub dostarczyæ inny generator.
____
* Sytuacja analogiczna jak w kodzie Adepta, ale z lepszym rozk³adem prawdopodobieñstwa zakoñczenia.
Powrót do góry
Zobacz profil autora Wy¶lij prywatn± wiadomo¶æ
Wy¶wietl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona G³ówna -> Pole do popisu (beta testy) Wszystkie czasy w strefie CET (Europa)
Id¼ do strony Poprzedni  1, 2
Strona 2 z 2

 
Skocz do:  
Mo¿esz pisaæ nowe tematy
Mo¿esz odpowiadaæ w tematach
Nie mo¿esz zmieniaæ swoich postów
Nie mo¿esz usuwaæ swoich postów
Nie mo¿esz g³osowaæ w ankietach
Mo¿esz dodawaæ za³±czniki na tym forum
Mo¿esz pobieraæ pliki z tego forum




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

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