Javaでリスト生成遅延
動機
必要なだけ要素が作られる無限リストを生成したい。
元ネタ
Haskellを使う人に有名なフィボナッチ数列の生成方法がある。
fib = 0:1:zipWith (+) fib (tail fib)
これで無限に続くフィボナッチ数列ができる。
Haskellのよいところは、遅延評価(lazy evaluation)なので
n番目が必要になるまで、n番目が計算されないこと。
これをJavaでやりたい。
方針
(5/9更新)
「必要なだけ」といいながら1個先回りして作っていることに気づいた。
暇があったら改善しよう。
iterator.next()が最初に呼ばれた時に次の要素を生成するようにする。
そこで、リストの次の要素を計算するメソッドnextValueと、次のラッパーオブジェクト生成getInstanceをもつ、Iterableな抽象クラスLazyListを用意する。
iterator().nextで次の要素への参照がない場合に、getInstanceでオブジェクトを生成する。
package list;
import java.util.Iterator;
import com.sun.xml.internal.ws.addressing.model.ActionNotSupportedException;
public abstract class LazyList<E> implements Iterable<E> {
protected E value;
private LazyList<E> next;
public LazyList(E value) {
this.value = value;
}
public abstract LazyList<E> getInstance(E value);
protected abstract E nextValue();
@Override
public Iterator<E> iterator() {
return new Iterator<E>(){
private LazyList<E> pointer = LazyList.this;
@Override
public boolean hasNext() {
return true;
}
@Override
public E next() {
//nextではなく、this.value
E value = pointer.value;
//生成遅延
if(pointer.next == null){
pointer.next = pointer.getInstance(
pointer.nextValue());
}
pointer = pointer.next;
return value;
}
@Override
public void remove() {
throw new ActionNotSupportedException("remove not supported");
}
};
}
}
実装
倍々ゲーム
次の要素は現在の要素の倍、という単純な無限リスト。
intだとすぐにオーバーフローするのでBigIntegerで。
package list;
import java.math.BigInteger;
public class DoubleGen extends LazyList<BigInteger>{
public DoubleGen(BigInteger value) {
super(value);
}
@Override
public LazyList<BigInteger> getInstance(BigInteger value) {
return new DoubleGen(value);
}
@Override
protected BigInteger nextValue() {
return super.value.multiply(new BigInteger("2"));
}
public static void main(String[] args) {
DoubleGen bid = new DoubleGen(new BigInteger("1"));
for (BigInteger i : bid) {
if(i.compareTo(new BigInteger("1000000000000")) > 0){
break;
}
System.out.println(i);
}
}
}
フィボナッチ数列
前の要素を使わないとフィボナッチ数列の次の値が計算できないので、
コンストラクタで自分を次に渡す。
package list;
import java.math.BigInteger;
import java.util.Iterator;
public class FibGen extends LazyList<BigInteger>{
public static final BigInteger N0 = BigInteger.ZERO;
public static final BigInteger N1 = BigInteger.ONE;
//ひとつ前への参照
private FibGen prev;
public FibGen(BigInteger value, FibGen prev) {
super(value);
this.prev = prev;
}
//自身の参照を次に渡す
@Override
public LazyList<BigInteger> getInstance(BigInteger value) {
return new FibGen(value, this);
}
@Override
protected BigInteger nextValue() {
//f(1) = N1
if(prev == null){
return N1;
}
//f(n) = f(n-1) + f(n-2)
return prev.value.add(value);
}
public static void main(String[] args) {
//f(0) = N0
FibGen fibGen = new FibGen(N0, null);
for (BigInteger i : fibGen) {
if(i.compareTo(new BigInteger("1000000000000")) > 0){
break;
}
System.out.println(i);
}
}
}
参照ではなく、イテレータを共有する場合。
nextを一回呼ぶとポインタが一個進むことを利用する。
package list;
import java.math.BigInteger;
import java.util.Iterator;
public class FibGen2 extends LazyList<BigInteger>{
public static final BigInteger N0 = BigInteger.ZERO;
public static final BigInteger N1 = BigInteger.ONE;
private Iterator<BigInteger> prev;
public FibGen2(BigInteger value, Iterator<BigInteger> prev) {
super(value);
this.prev = prev;
}
@Override
public LazyList<BigInteger> getInstance(BigInteger value) {
if(prev == null){
return new FibGen2(value, this.iterator());
}
return new FibGen2(value, prev);
}
@Override
protected BigInteger nextValue() {
if(prev == null){
return N1;
}
return prev.next().add(value);
}
public static void main(String[] args) {
FibGen2 fibGen = new FibGen2(N0, null);
for (BigInteger i : fibGen) {
if(i.compareTo(new BigInteger("1000000000000")) > 0){
break;
}
System.out.println(i);
}
}
}
実行結果
0 1 1 2 3 5 8 13 (以下略)
素数生成
素数を生成してみる。
判定方法は、sqrt(n)よりも小さい素数全てで割り切れなければnは素数。
出力も含めて1000万までで10秒くらい。
package list;
public class PrimeGen extends LazyList<Integer> {
public static PrimeGen primes;
public static PrimeGen getPrimes(){
if(primes == null){
//2は最初の素数
primes = new PrimeGen(2);
}
return primes;
}
public PrimeGen(Integer value) {
super(value);
}
@Override
public LazyList<Integer> getInstance(Integer value) {
return new PrimeGen(value);
}
@Override
protected Integer nextValue() {
//再帰を避けるため、2,3,5が必要
if(value == 2){
return 3;
}
if(value == 3){
return 5;
}
//次の素数候補n
for(int n = value + 1;;n++){
//テスト素数p
for(int p : getPrimes()){
//sqrt(n)よりもテスト素数が大きくなったらnは素数
if(p * p > n){
return n;
}
//sqrt(n)以下の素数で割り切れたらnは素数ではない
if(n % p == 0){
break;
}
}
}
}
public static void main(String[] args) {
PrimeGen primes = getPrimes();
for (int i : primes) {
if(i > 10000000){
break;
}
System.out.println(i);
}
}
}
実行結果
2 3 5 7 11 (以下略)
ちなみにHaskellだと2行くらいで書ける。
primes = 2:filter (nodivisor primes) [3..] nodivisor ps n = all (\n' -> n `mod` n' /= 0) $ takeWhile (\n' -> n'* n' <= n) ps
