以伪随机顺序在列表上进行迭代，而不存储混洗列表 [英] Iterating over a list in pseudo-random order without storing a shuffled list

问题描述

在。

选择中等范围原始根> 43062 43067是一个很好的候选）。

 类序列
 {
 public： 
 uint32_t get（）const {return state;} 
 void advance（）{state =（state * k）％p;} 
 void reset（）{state = k; } 
 private：
 uint32_t state = 43067; 
 const uint32_t k = 43067; 
 const uint32_t p = 64007; 
}; 
  

，64007）一次，以伪随机的方式。

In a game, we use a technique called 'colour picking' to select units.

This means that every visible unit is given a unique colour.

Here is an example of a scene drawn for colour picking:

As some users may have 16-bit displays, these colours can be in the range 0..64K.

However, if we give the units incremental colours e.g. unit0 is 0, unitN is N then the colours are very hard for humans to debug. Units are virtually indistinguishable.

We want to give the units unique and distinctive colours.

We are currently incrementing in a fixed step using a binary tree (C++ map) to store used colours to check for collisions. This is a performance problem on low-end hardware. Even if this were a hash table and avoided using string, temporary memory allocation in game frames is to be frowned upon. So rather than optimising the code as it stands, I'm keen to discover if there are ways to avoid maintaining a history entirely.

Is there a way to iterate over the numbers 0..64K with a large step or randomly such that most of the 64K possible values are used, and avoiding using a history of already-allocated colours to avoid collisions?

^{(It is so unlikely that there are more than 64K visible units on the screen that we do not have to handle that case!)}

解决方案

My try:

1. Pick a prime number near your desired range (64007 is a good candidate here).
2. Find the primitive roots modulo p of this number.

3. Pick a "medium range" primitive root (43062 43067 is a good candidate).

   class Sequence
   {
   public:
        uint32_t get() const {return state;}
        void advance() { state = (state * k)%p;}
        void reset() { state = k; }
   private:
        uint32_t state = 43067;
        const uint32_t k = 43067;
        const uint32_t p = 64007;
   };
   

This cycles all the numbers in range [1, 64007) exactly once, in a pseudo-random fashion.

这篇关于以伪随机顺序在列表上进行迭代，而不存储混洗列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！