Package squidpony.squidmath

Class LowStorageShuffler

java.lang.Object
squidpony.squidmath.LowStorageShuffler
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
ShuffledIntSequence
public class LowStorageShuffler
extends Object
implements Serializable
Gets a sequence of distinct pseudo-random ints (typically used as indices) from 0 to some bound, without storing all of the sequence in memory. Uses a Feistel network, as described in this post by Alan Wolfe. The API is very simple; you construct a LowStorageShuffler by specifying how many items it can shuffle, and you can optionally use a seed (it will be random if you don't specify a seed). Call next() on a LowStorageShuffler to get the next distinct int in the shuffled ordering; next() will return -1 if there are no more distinct ints (if bound items have already been returned). You can go back to the previous item with previous(), which similarly returns -1 if it can't go earlier in the sequence. You can restart the sequence with restart() to use the same sequence over again, or restart(int) to use a different seed (the bound is fixed).
This differs from the version in Alan Wolfe's example code and blog post; it uses a very different round function, and it only uses 2 rounds of it (instead of 4). Wolfe's round function is MurmurHash2, but as far as I can tell the version he uses doesn't have anything like MurmurHash3's fmix32() to adequately avalanche bits, and since all keys are small keys with the usage of MurmurHash2 in his code, avalanche is the most important thing. It's also perfectly fine to use irreversible operations in a Feistel network round function, and I do that since it seems to improve randomness slightly. The round(int, int) method used here acts like an unbalanced, irreversible PRNG with two states, and that turns out to be just fine for a Feistel network. Using 4 rounds turns out to be overkill in this case. This also uses a different seed for each round.
This class is similar to ShuffledIntSequence, which extends this class and uses different behavior so it "re-shuffles" the results when all results have been produced.
Created by Tommy Ettinger on 9/22/2018.
Author:
Alan Wolfe, Tommy Ettinger
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    int bound  
    protected int halfBits  
    protected int index  
    protected int key0  
    protected int key1  
    protected int leftMask  
    protected int pow4  
    protected int rightMask  

  • Constructor Summary

    Constructors 
    Constructor Description
    LowStorageShuffler()
    Constructs a LowStorageShuffler with a random seed and a bound of 10.
    LowStorageShuffler​(int bound)
    Constructs a LowStorageShuffler with the given exclusive upper bound and a random seed.
    LowStorageShuffler​(int bound, int seed)
    Constructs a LowStorageShuffler with the given exclusive upper bound and int seed.

  • Method Summary

    Modifier and Type Method Description
    static int determine​(int z)
    Used to rearrange the bits of seeds this is given in a way that should partly randomize them.
    int encode​(int index)
    Encodes an index with a 2-round Feistel network.
    int next()
    Gets the next distinct int in the sequence, or -1 if all distinct ints have been returned that are non-negative and less than bound.
    int previous()
    Gets the previous returned int from the sequence (as yielded by next()), or -1 if next() has never been called (or the LowStorageShuffler has reached the beginning from repeated calls to this method).
    void restart()
    Starts the same sequence over from the beginning.
    void restart​(int seed)
    Starts the sequence over, but can change the seed (completely changing the sequence).
    static int round​(int data, int seed)
    An irreversible mixing function that seems to give good results; GWT-compatible.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

  • Constructor Details

    • LowStorageShuffler

      public LowStorageShuffler()
      Constructs a LowStorageShuffler with a random seed and a bound of 10.

    • LowStorageShuffler

      public LowStorageShuffler​(int bound)
      Constructs a LowStorageShuffler with the given exclusive upper bound and a random seed.
      Parameters:
      bound - how many distinct ints this can return

    • LowStorageShuffler

      public LowStorageShuffler​(int bound, int seed)
      Constructs a LowStorageShuffler with the given exclusive upper bound and int seed.
      Parameters:
      bound - how many distinct ints this can return
      seed - any int; will be used to get several seeds used internally

  • Method Details

    • next

      public int next()
      Gets the next distinct int in the sequence, or -1 if all distinct ints have been returned that are non-negative and less than bound.
      Returns:
      the next item in the sequence, or -1 if the sequence has been exhausted

    • previous

      public int previous()
      Gets the previous returned int from the sequence (as yielded by next()), or -1 if next() has never been called (or the LowStorageShuffler has reached the beginning from repeated calls to this method).
      Returns:
      the previously-given item in the sequence, or -1 if this can't go earlier

    • restart

      public void restart()
      Starts the same sequence over from the beginning.

    • determine

      public static int determine​(int z)
      Used to rearrange the bits of seeds this is given in a way that should partly randomize them. A high-quality 32-bit input, 32-bit output unary hash is pretty hard to find.
      Parameters:
      z - any int
      Returns:
      a pseudo-random but deterministic change of z

    • restart

      public void restart​(int seed)
      Starts the sequence over, but can change the seed (completely changing the sequence). If seed is the same as the seed given in the constructor, this will use the same sequence, acting like restart().
      Parameters:
      seed - any int; will be used to get several seeds used internally

    • round

      public static int round​(int data, int seed)
      An irreversible mixing function that seems to give good results; GWT-compatible. This is similar to SilkRNG's way of combining two states, but because this doesn't need to be reversible or even evenly distributed, it has been significantly simplified. It uses one int multiplication, two additions, two subtractions, two XORs, two unsigned right shifts, and one signed right shift.
      Parameters:
      data - the data being ciphered
      seed - the current seed
      Returns:
      the ciphered data

    • encode

      public int encode​(int index)
      Encodes an index with a 2-round Feistel network. It is possible that someone would want to override this method to use more or less rounds, but there must always be an even number.
      Parameters:
      index - the index to cipher; must be between 0 and pow4, inclusive
      Returns:
      the ciphered index, which might not be less than bound but will be less than or equal to pow4