Class LowStorageShuffler

java.lang.Object
com.github.yellowstonegames.old.v300.LowStorageShuffler
public class LowStorageShuffler extends Object
Gets a sequence of distinct pseudo-random ints (typically used as indices) from 0 to some bound, without storing all 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.
Created by Tommy Ettinger on 9/22/2018.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final 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.
    LowStorageShuffler(int bound, int k0, int k1)
    Constructs a LowStorageShuffler with the given exclusive upper bound and ints k0 and k1.

  • 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.
    boolean
    equals(Object o)
     
    int
    getBound()
     
    int
    getIndex()
     
    int
    getKey0()
     
    int
    getKey1()
     
    int
    hashCode()
     
    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)
     
    LowStorageShuffler
    setIndex(int index)
     
    void
    setKey0(int key0)
     
    void
    setKey1(int key1)
     
    String
    toString()
     

    Methods inherited from class Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

    • bound

      public final int bound

    • index

      protected int index

    • pow4

      protected int pow4

    • halfBits

      protected int halfBits

    • leftMask

      protected int leftMask

    • rightMask

      protected int rightMask

    • key0

      protected int key0

    • key1

      protected int key1

  • 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

    • LowStorageShuffler

      public LowStorageShuffler(int bound, int k0, int k1)
      Constructs a LowStorageShuffler with the given exclusive upper bound and ints k0 and k1. Here, k0 and k1 will be used as the exact keys; this is meant for recreating a LowStorageShuffler, such as for deserialization.
      Parameters:
      bound - how many distinct ints this can return
      k0 - the first key; will be used verbatim
      k1 - the second key; will be used verbatim

  • 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)

    • 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

    • getBound

      public int getBound()

    • getKey0

      public int getKey0()

    • setKey0

      public void setKey0(int key0)

    • getKey1

      public int getKey1()

    • setKey1

      public void setKey1(int key1)

    • getIndex

      public int getIndex()

    • setIndex

      public LowStorageShuffler setIndex(int index)

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object