 |
Coders' city Nasza pasja to programowanie!
|
Zobacz poprzedni temat :: Zobacz nastêpny temat |
Autor |
Wiadomo¶æ |
Adept Go¶æ
|
Wys³any: Nie Sty 01, 2017 10:12 pm Temat postu: Losowanie liczb |
|
|
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
|
Wys³any: Pon Sty 02, 2017 4:37 am Temat postu: |
|
|
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 ;).
Opis: |
|
 Pobierz |
Nazwa pliku: |
llosow.png |
Wielko¶æ pliku: |
6.19 KB |
Pobierano: |
59 raz(y) |
Opis: |
|
 Pobierz |
Nazwa pliku: |
koszt.png |
Wielko¶æ pliku: |
29.63 KB |
Pobierano: |
60 raz(y) |
|
|
Powrót do góry |
|
 |
Adept Go¶æ
|
Wys³any: Wto Sty 03, 2017 1:44 pm Temat postu: Losowanie liczb |
|
|
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 ?
Opis: |
|
 Pobierz |
Nazwa pliku: |
LOSOWANI.PAS |
Wielko¶æ pliku: |
1.75 KB |
Pobierano: |
49 raz(y) |
|
|
Powrót do góry |
|
 |
Adept Go¶æ
|
|
Powrót do góry |
|
 |
marcin_an
Do³±czy³: 26 Maj 2005 Posty: 18822
|
Wys³any: Pi± Sty 06, 2017 8:54 pm Temat postu: |
|
|
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 |
|
 |
Adept Go¶æ
|
|
Powrót do góry |
|
 |
marcin_an
Do³±czy³: 26 Maj 2005 Posty: 18822
|
Wys³any: Sob Sty 07, 2017 6:06 pm Temat postu: |
|
|
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:- ¯adna z u¿ytych funkcji nie daje w/w gwarancji w specyfikacji.
- Java (i Groovy) mog± u¿yæ metody java.util.Random.nextInt(int), która ma nieokre¶lony czas dzia³ania*.
- 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 |
|
 |
|
|
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
|