Coders' city Nasza pasja to programowanie!    Pomoc   Szukaj   Użytkownicy   Grupy  Rejestracja  Archiwum starego forum + teoria    RSS & Panel/SideBar  Profil   Zaloguj się, by sprawdzić wiadomości   Zaloguj  Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady Losowanie Liczb Idź do strony Poprzedni  1, 2      Forum Coders' city Strona Główna -> Pole do popisu (beta testy) 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 ;). llosow.png  Opis: Pobierz  Nazwa pliku:  llosow.png  Wielkość pliku:  6.19 KB  Pobierano:  65 raz(y) koszt.png  Opis: Pobierz  Nazwa pliku:  koszt.png  Wielkość pliku:  29.63 KB  Pobierano:  66 raz(y) _________________ Nieaktywny od 2017-04-01 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 ? LOSOWANI.PAS  Opis: Pobierz  Nazwa pliku:  LOSOWANI.PAS  Wielkość pliku:  1.75 KB  Pobierano:  54 raz(y) Powrót do góry Adept Gość Wysłany: Pią Sty 06, 2017 8:22 pm      Temat postu: Losowanie liczb 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:  47 raz(y) 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"). _________________ Nieaktywny od 2017-04-01 Powrót do góry Adept Gość Wysłany: Sob Sty 07, 2017 12:26 pm      Temat postu: Losowanie liczb 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 ją 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:  42 raz(y) 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. _________________ Nieaktywny od 2017-04-01 Powrót do góry Wyświetl posty z ostatnich: Wszystkie Posty1 Dzień7 Dni2 Tygodnie1 Miesiąc3 Miesiące6 Miesięcy1 Rok Najpierw StarszeNajpierw Nowsze     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: Wybierz forum Podział tematyczny----------------Algorytmy + inżynieria oprogramowaniaBazy danychBibliotekiOprogramowanie biuroweWebmasterstwoElektronika, programowanie niskopoziomoweSprawy dotyczące forum Środowiska i języki----------------C i C++Visual Studio: C#, VB, VC++, …Pascal, Delphi, ...JavaPHPECMAScriptPythonInne języki skryptowe, przetwarzanie danychInne języki Luźne działy----------------Sieci komputerowe i InternetKomputeryOferowana praca / współpracaGiełdaPole do popisu (beta testy)Inne  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.12120 sekund, zapytan = 13

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