EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)

May 2013

I have learned XorShift by OgieKako,hama_du,wleiteandtomerun.

source code

import static org.junit.Assert.assertEquals;

import java.util.Random;

import org.junit.Test;

public final class XorShift {
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;
private int w = 88675123;

/**
* Returns the next pseudorandom {@code int} value, greater than or equal to {@code Integer.MIN_VALUE} and less than or equal to {@code Integer.MAX_VALUE}.
*
* @return the next pseudorandom
*/
public final int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

/**
* Returns the next pseudorandom {@code double} value, greater than or equal to {@code 0.0} and less than {@code 1.0}.
*
* @return the next pseudorandom
*/
public final double nextDouble() {
return (double) (nextInt() + (1L << 31)) / (1L << 32);
}

/**
* Returns the next pseudorandom {@code long} value.
*
* @return the next pseudorandom
*/
public final long nextLong() {
return ((long) nextInt() << 32) ^ (((long) nextInt() << 32) >>> 32);
}

@Test
public void testLong() {
XorShift xs = new XorShift();
// for (int i = 0; i < 1e6; i++)
{
long nextLong = xs.nextLong();
System.out.format("%d\n", nextLong);
}
}

@Test
public void testMax() {
XorShift xs = new XorShift();
xs.x = -1044973;
xs.y = -96493;
xs.z = 1670;
xs.w = 59770;
assertEquals(Integer.MAX_VALUE, xs.nextInt());
xs.x = -1044973;
xs.y = -96493;
xs.z = 1670;
xs.w = 59770;
assertEquals(1.0, xs.nextDouble(), 1e-9);
}

@Test
public void testMin() {
XorShift xs = new XorShift();
xs.x = -1044908;
xs.y = 25266;
xs.z = 13753;
xs.w = -183547;
assertEquals(Integer.MIN_VALUE, xs.nextInt());
xs.x = -1044908;
xs.y = 25266;
xs.z = 13753;
xs.w = -183547;
assertEquals(0, xs.nextDouble(), 0);
}

@Test
public void test() {
System.out.format("%f %f\n", timeXorShift(), timeRandom());
assertEquals(true, timeXorShift() < timeRandom());
}

private double timeRandom() {
Random random = new Random();
long start = System.nanoTime();
for (int i = 0; i < 1e6; i++) {
random.nextDouble();
}
return (System.nanoTime() - start) / 1e9;
}

private double timeXorShift() {
XorShift random = new XorShift();
long start = System.nanoTime();
for (int i = 0; i < 1e6; i++) {
random.nextDouble();
}
return (System.nanoTime() - start) / 1e9;
}
}


I have learned BitSet by farnetto's code.

source code

import java.util.Arrays;
import java.util.BitSet;

import org.junit.Test;

public class BitSetExample {
@Test
public void test() {
final int n = 10;
debug("2", getMultiple(n, 2));
debug("3", getMultiple(n, 3));
{
BitSet two = getMultiple(n, 2);
two.or(getMultiple(n, 3));
debug("or", two);
}
{
BitSet two = getMultiple(n, 2);
two.and(getMultiple(n, 3));
debug("and", two);
}
{
BitSet two = getMultiple(n, 2);
two.xor(getMultiple(n, 3));
debug("xor", two);
}
{
BitSet two = getMultiple(n, 2);
two.andNot(getMultiple(n, 3));
debug("andNot", two);
}
{
BitSet three = getMultiple(n, 3);
three.andNot(getMultiple(n, 2));
debug("andNot", three);
}
{
debug("intersects", getMultiple(n, 2).intersects(getMultiple(n, 3)));
}
{
debug("cardinality", getMultiple(n, 2).cardinality());
debug("cardinality", getMultiple(n, 3).cardinality());
}
}

private BitSet getMultiple(int n, int m) {
BitSet multiple = new BitSet();
for (int i = 1; i <= n; i++) {
if (i % m == 0) {
multiple.set(i);
}
}
return multiple;
}

private static final boolean DEBUG = true;

private static final void debug(Object... o) {
if (DEBUG)
System.err.println(Arrays.deepToString(o));
}

}


このページのトップヘ