1. Куча / Говнокод #13631

    +125

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    int prev, next;
// next should not be equal to prev;
next = radnom(MAX);
if (next = prev)
    next = random(MAX);

    Просто передаю концепцию на общеславянском.
    Будет интересно посчитать насколько всё-таки это говно уменьшает вероятность совпадения при разных MAX.

    Запостил: vistefan, 21 Августа 2013

    Комментарии (33) RSS

    • ava someone 21.08.2013 10:43 # −3 

      do {
    next = random(MAX);
} while (next == prev);


      Fixed?
      Ответить

    • ava kegdan 21.08.2013 11:16 # 0

      зависит от качества рандома. при хорошем рандоме условие блока if почти никогда не будет удолетворено, так что при хорошем рандоме код почти наверняка будет работать верно.

      Другое дело, что так делать нельзя)
      Ответить

      • ava zasedanie 21.08.2013 11:17 # +2

        > при хорошем рандоме
        При любом рандоме (кроме каноничного result = 3;) на небольших MAX условие будет отрабатывать систематически.
        Ответить

        • ava vistefan 21.08.2013 11:26 # 0

          Ну вообще говоря на идеально равномерном рандоме при MAX = 10 имеем некий prev. Тогда вероятность его повторения 0.1, а вероятность после ифа снова получить то же число = 0.1 * 0.1 = 0.01, и с ростом MAX убывает, но максималистические начала во мне всё равно заставляют с недоверием смотреть на такой код.
          Ответить

          • ava CapCoffee 21.08.2013 11:48 # −1

            Кажется выборка "шаров" здесь не повторная, а значит вероятность вытащить заданный шар 1/MAX.
            Ответить

          • ava kegdan 21.08.2013 11:49 # 0

            Вот вам код на шарпе - хотите - потестите. у меня максимум был 5 %
            using System;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication32
{
    class Program
    {
        static readonly Random Random = new Random(DateTime.Now.Millisecond);
        private static int _counterTrue = 0;
        private static int _counterFalse = 0;
        private const int _MaxRand = int.MaxValue;
        private const int testLimit = 10000000;

        static void Main(string[] args)
        {
            Parallel.For(0, testLimit, (i) => Test());
            Console.WriteLine(_counterTrue);
            Console.WriteLine(_counterFalse);
            Console.WriteLine(_counterFalse/(float)(testLimit));
            Console.ReadKey();

        }
        static private void Test()
        {
            var first = Random.Next(_MaxRand);
            var second = Random.Next(_MaxRand);
            if (first == second)
            {
                second = Random.Next(_MaxRand);
            }
            if (first == second)
            {
                Interlocked.Increment(ref  _counterTrue);
            }
            else
            {
                Interlocked.Increment(ref  _counterFalse);
            }
        }
    }
}
            Ответить

            • ava vistefan 21.08.2013 11:54 # 0

              С таким кодом вам тред новый надо было создавать.
              Ответить

            • ava roman-kashitsyn 21.08.2013 13:01 # +1

              Быстрокод на haskell
              module Main where

import System.Random

toCheck = 1000

numEq (x:r@(y:_)) = if x == y then 1 + numEq r else numEq r
numEq _ = 0

go :: Int -> Int
go max = numEq . take toCheck . randomRs (0, max) . mkStdGen $ 0

pairs lst = zip lst $ map go lst

printPair (x, y) = putStrLn $ show x ++ " " ++ show y

main = do
     putStrLn "MAX N"
     mapM_ printPair $ pairs [2..1000]
              Ответить

              • ava roman-kashitsyn 21.08.2013 13:09 # 0

                Единственное отклонение - числа генерятся от 0 до MAX включительно, поэтому реально будет MAX+1 вариантов.
                Ответить

        • ava guest 03.09.2013 20:51 # −2

          Систематически будет лишь топор над головой висеть с таким кодом. Вопрос в том, что случится в случае совпадения next и prev. Если "тетрис" повиснет - потешно, а если это будет несколько тысяч транзакций или какие-нибудь промышленные роботы на сборочном конвейере переплетутся то лулзов будет столько, что главный инженер или кто-то еще может и сесть не понарошку. :)
          Ответить

      • ava roman-kashitsyn 21.08.2013 11:59 # +1

        Совпадение чисел, последовательно возвращаемых генератором, не означает, что он зациклился. Проверил на стандартном хаскелевском System.Random. Генерил 1000 случайных чисел, смотрел, сколько последовательных повторений при различных значениях MAX. При MAX=2 вероятность совпадения ~ 37%, при MAX=3 ~ 23%, при MAX=5 ~ 13%, при MAX > 100 обычно менее 1%.
        Ответить

        • ava vistefan 21.08.2013 12:07 # 0

          Вы спутали, читая второпях "верно" с "вечно"? Он же вроде и не говорил про зацикливание.
          Ответить

          • ava roman-kashitsyn 21.08.2013 12:51 # 0

            Нет, не спутал. У всех псевдослучайных генераторов есть цикл, и чем он больше, тем лучше генератор. Соответственно, даже если генератор хороший, выпадение одинаковых чисел не означает цикла.
            Ну а вероятность выпадения двух одинаковых значений подряд легко посчитать теоретически: p = 1 / MAX.
            Ответить

            • ava vistefan 21.08.2013 13:03 # 0

              Вопрос не в устройстве генератора, а в том, что бы в данном конкретном коде исключить повторение двух одинаковых чисел подряд, и то, как это сделано в ОП-коде - математически опровержимое говнецо.
              Ответить

              • ava roman-kashitsyn 21.08.2013 13:07 # 0

                > зависит от качества рандома
                > код почти наверняка будет работать верно
                > Вопрос не в устройстве генератора
                Ну я какбэ и говорю, что от качества рандома мало что зависит, нет?
                Ответить

                • ava kegdan 21.08.2013 13:21 # +1

                  >Ну я какбэ и говорю, что от качества рандома мало что зависит, нет?

                  если рандом трушный - он выдает любое число с одинаковой вероятностью. А программировании, строго говоря, это не совсем так. Чем ближе выдаваемая выборка к равномерному распределению - тем лучше рандом.
                  Ответить

                  • ava roman-kashitsyn 21.08.2013 13:23 # −1

                    Это и так понятно, но даже хороший рандом даёт вероятность выпадения пары 1/MAX, что не так уж и мало.
                    Ответить

                    • ava roman-kashitsyn 21.08.2013 13:26 # +2

                      Упс, мы смотрим вероятность выпасть трижды подряд. тогда действительно 1 / (MAX*MAX).
                      Ответить

                      • ava kegdan 21.08.2013 13:34 # 0

                        тогда уж 1/(MAX^3)

                        гоню, все правильно 1/(MAX^2).

                        Если матожидание ярко выражено, то шанс попадания в одно и тоже число увеличивается. Хотя врятли в рардом будут засовывать нормальное распределение вместо равномерного. Но исключать такое развитие событий не следует)

                        Ответить

                      • ava vistefan 21.08.2013 14:34 # 0

                        Я сразу говорил
                        Ответить

    • ava defecate-plusplus 21.08.2013 12:08 # +6

      > radnom
      раскусил, да?
      Ответить

    • ava defecate-plusplus 21.08.2013 13:10 # 0

      а накой это надо?
      знание, что после одного псевдослучайного числа обязано сгенерироваться отличное от него, снижает стойкость
      Ответить

      • ava vistefan 21.08.2013 13:32 # 0

        Юзер жмёт на кнопку и переходит на рандомную страницу. Не к лицу софту, если он будет иногда отдавать одну и ту же страницу (то есть на вид нихрена не изменится и юзер подумает что кнопка сломалась). Речь не о стойкости.
        Ответить

    Добавить комментарий