C# - 我可以从原始种子中检索 n 次迭代的种子值吗？

问题描述 投票：0回答：2

我不知道这个功能是否可行，但这对我当前的项目非常有帮助。

我希望能够生成一个可以在以后重新生成的字符列表。所以我将字符列表播种为 0，并获得设计的 80 个字符。

现在，稍后我需要能够生成此字符列表，但我不需要前 20 个字符。我不想将其设定为相同的值，然后不得不放弃大部分工作。有没有一种方法可以确定种子值是多少，或者是否有可能让它以这种方式运行，我在一代中开始，然后继续，就像我在旧种子上一样。

例如，我生成以下列表：

56, 12, 0, 84, 24, ...n,...95, 25, 72, 57, 15

现在，我只需要从列表中生成最后 5 个值。即：95、25、72、57、15。

有没有办法在随机生成算法中“跳转”到这一点，而不必像这样重新运行所有随机调用？需要明确的是，我不想执行以下操作：

Random.seed = 123;
for(int i = 0; i < skippableRandomValues; ++i)
{
    Random.Range(0,1);
}
GenerateRandomCharacter();

例如，如果我可以缓存所需的种子以从列表中的特定点开始生成，那么我可以加载缓存的种子，并启动生成过程，而无需消耗我的 CPU。像这样的东西：

Random.seed = 123;
for(int i = 0; i < CharactersToGenerate; ++i)
{
    int seedVal = Random.GetContinuousSeedVal();
    CharacterSeedStartValues[i]=seedVal
    GenerateRandomCharacter();
}

所以

CharacterSeedStartValues
的第一个值是123，然后，生成后，我可以存储生成字符1所需的值，然后是2，...，n。

然后，当我只想生成字符54时，我可以简单地调用：

Random.seed = CharacterSeedStartValues[53];
GenerateRandomCharacter();

这样的事情可能吗？

c# random
2个回答
2
投票

您可以编写自己的像样 RNG 实现，例如 XorShift。然后您可以添加自己的方法来返回当前的 RNG 状态，以便您可以恢复它以跳过任意次数的迭代。

例如，这里是 XorShift 版本的 C# 实现：

public sealed class XorShift : System.Random
{
    public XorShift(ulong seed1, ulong seed2)
    {
        if (seed1 == 0 && seed2 == 0)
            throw new ArgumentException("seed1 and seed 2 cannot both be zero.");

        _s[0] = seed1;
        _s[1] = seed2;

        init();
    }

    public XorShift() : this(Guid.NewGuid())
    {
    }

    public XorShift(Guid seed)
    {
        var bytes = seed.ToByteArray();

        _s[0] = BitConverter.ToUInt64(bytes, 0);
        _s[1] = BitConverter.ToUInt64(bytes, 8);

        init();
    }

    public XorShift(int p, ulong[] s)
    {
        if (s.Length != 16)
            throw new ArgumentOutOfRangeException("s", "s must be exactly 16 long.");

        _p = p;
        _s = s.ToArray();
    }

    public (int P, ulong[] S) State()
    {
        return (_p, _s.ToArray());
    }

    public ulong NextUlong()
    {
        unchecked
        {
            ulong s0 = _s[_p];
            _p = (_p + 1) & 15;
            ulong s1 = _s[_p];
            s1 ^= s1 << 31;
            _s[_p] = s1 ^ s0 ^ (s1 >> 11) ^ (s0 >> 30);
            return _s[_p] * 0x9e3779b97f4a7c13UL;
        }
    }

    public long NextLong(long maxValue)
    {
        return NextLong(0, maxValue);
    }

    public long NextLong(long minValue, long maxValue)
    {
        if (minValue == maxValue || minValue == maxValue - 1)
            return minValue;

        double range = (double)maxValue - minValue;
        var result = (long)(NextDouble() * range) + minValue;

        return result;
    }

    public override int Next()
    {
        var result = (int)NextLong(0, int.MaxValue);
        return result;
    }

    public override int Next(int maxValue)
    {
        var result = (int)NextLong(0, maxValue);
        return result;
    }

    public override int Next(int minValue, int maxValue)
    {
        var result = (int)NextLong(minValue, maxValue);
        return result;
    }

    public override void NextBytes(byte[] buffer)
    {
        int remaining = buffer.Length;

        while (remaining > 0)
        {
            var next = BitConverter.GetBytes(NextUlong());
            int n = Math.Min(next.Length, remaining);

            Array.Copy(next, 0, buffer, buffer.Length - remaining, n);
            remaining -= n;
        }
    }

    public override double NextDouble()
    {
        var result = NextUlong() / (ulong.MaxValue + 1.0);
        return result;
    }

    static readonly ulong[] _jump =
    [
        0x84242f96eca9c41d,
        0xa3c65b8776f96855,
        0x5b34a39f070b5837,
        0x4489affce4f31a1e,
        0x2ffeeb0a48316f40,
        0xdc2d9891fe68c022,
        0x3659132bb12fea70,
        0xaac17d8efa43cab8,
        0xc4cb815590989b13,
        0x5ee975283d71c93b,
        0x691548c86c1bd540,
        0x7910c41d10a1e6a5,
        0x0b5fc64563b3e2a8,
        0x047f7684e9fc949d,
        0xb99181f2d8f685ca,
        0x284600e3f30e38c3
    ];

    void init()
    {
        ulong[] t = new ulong[16];

        for (int i = 0; i < t.Length; i++)
        {
            for (int b = 0; b < 64; b++)
            {
                if ((_jump[i] & 1UL << b) != 0)
                    for (int j = 0; j < 16; j++)
                        t[j] ^= _s[(j + _p) & 15];

                NextUlong();
            }
        }

        for (int j = 0; j < 16; j++)
            _s[(j + _p) & 15] = t[j];
    }

    readonly ulong[] _s = new ulong[16];
    int _p;
}

请注意我为了返回状态而添加的 

public (int P, ulong[] S) State()
方法。

然后您可以使用它来保存/恢复状态，以便跳过迭代，如下所示：

XorShift rng1 = new XorShift(Guid.NewGuid());

for (int i = 0; i < 10_000; i++) // Skip 10K random numbers.
{
    rng1.Next();
}

var state = rng1.State(); // RNG state after first 10K iterations.

Console.WriteLine("From first RNG:");

for (int i = 0; i < 10; ++i)
    Console.WriteLine(rng1.Next());

Console.WriteLine("\nFrom second RNG:");
var rng2 = new XorShift(state.P, state.S);

for (int i = 0; i < 10; ++i)
    Console.WriteLine(rng2.Next());

其输出是：

From first RNG:
1129543872
1219337207
1574241099
1340742741
892399437
671519662
1202729140
563207978
2085904688
679406100

From second RNG:
1129543872
1219337207
1574241099
1340742741
892399437
671519662
1202729140
563207978
2085904688
679406100

这表明在生成 10K 个数字后，第二个 RNG 的结果与第一个 RNG 的结果相同。

0
投票

您可以使用线性同余生成器，它能够进行逆运算（从结果返回到原始结果）以及跳入 O(log(N)) 到前后序列中的任意点，有关详细信息，请参阅 F.Brown 论文参考。下面是 C++ 代码，如果你需要的话我可以将其变成 C# 并询问

class lcg_PLE63
{
    public: typedef uint_fast64_t result_type;
    public: typedef result_type   seed_type;

    public: static constexpr result_type  nbits = 63ULL;
    public: static constexpr result_type  mod   = 1ULL << nbits;
    public: static constexpr result_type  mask  = mod - 1ULL;

    // those values are from P.L'Ecuyer "Efficient and Portable Combined RNGs", Comm.ACM 31(6): 742-749, 774 (1988)
    public: static constexpr result_type  mult  = 2806196910506780709ULL;
    public: static constexpr result_type  add   = 1ULL;

    public: static constexpr seed_type  default_seed   = 1ULL;        

    public: static constexpr float        norm  = float{1.0842021724855044340074528008699e-19};

    private: mutable seed_type _seed;

    public: lcg_PLE63(seed_type seed = default_seed):
        _seed{seed}
    {
    }

    public: lcg_PLE63(lcg_PLE63 const& r):
        _seed{r._seed}
    {
    }

    public: lcg_PLE63(lcg_PLE63&& r):
        _seed{std::move(r._seed)}
    {
    }        

    public: lcg_PLE63& operator=(lcg_PLE63 const& r)
    {
        _seed = r._seed;
        return *this;
    }

    public: lcg_PLE63& operator=(lcg_PLE63&& r)
    {
        _seed = std::move(r._seed);
        return *this;
    }

    public: ~lcg_PLE63()
    {
    }

    public: seed_type seed() const
    {
        return _seed;
    }



int64_t compute_nskip(int64_t ns)
{
    int64_t nskip = ns;
    while (nskip < 0LL)
    {
        uint64_t t = uint64_t(nskip) + mod;
        nskip = int64_t(t);
    }
    return nskip & mask; // keep it inside our bit-range
}

result_type skip(int64_t ns, seed_type seed)
{
    // compute positive number of seeds to skip
    int64_t nskip = compute_nskip(ns);

    // The algorithm here to determine the parameters used to skip ahead is
    // described in the paper F. Brown, "Random Number Generation with Arbitrary Stride,"
    // Trans. Am. Nucl. Soc. (Nov. 1994). This algorithm is able to skip ahead in
    // O(log2(N)) operations instead of O(N). It computes parameters
    // M and C which can then be used to find x_N = M*x_0 + C mod 2^M.

    // initialize constants
    result_type m{ mult }; // original multiplicative constant
    result_type c{ add };  // original additive constant

    result_type m_next{ 1ULL }; // new effective multiplicative constant
    result_type c_next{ 0ULL }; // new effective additive constant

    while (nskip > 0LL)
    {
        if (nskip & 1LL) // check least significant bit for being 1
        {
            m_next = (m_next * m) & mask;
            c_next = (c_next * m + c) & mask;
        }

        c = ((m + 1ULL) * c) & mask;
        m = (m * m) & mask;

        nskip = nskip >> 1LL; // shift right, dropping least significant bit
    }

    // with G and C, we can now find the new seed
    return (m_next * seed + c_next) & mask;
}

    public: static result_type sample(seed_type seed)
    {
        return (mult * seed + add) & mask;
    }

    public: void sample() const
    {
        _seed = sample(_seed);
    }

    public: float number() const
    {
        sample();
        return float(_seed) * norm;
    }

    public: void skip(int64_t ns) const
    {
        _seed = skip(ns, _seed);
    }
};
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.