Java8のラムダ式
最近ぼちぼちJavaをやり始めたところタイミング良くJava8がリリースされたので新機能であるラムダ式について少し見ていこうと思います．
まず，Java8におけるラムダ式は一体何なのかというと，それはずばり抽象メソッドを一つだけ持つインタフェースのインスタンスです．例えば以下のようなインタフェースがあったとして，
public interface IntFunc{ public int func(int x); }
従来では
IntFunc f1 = new IntFunc(){ @Override public int func(int x){ return x*x; } };
と書いていたのがラムダ式によって
IntFunc f2 = (int x) -> {return x*x;};
と書けるようになります．実際には型および引数が一つの場合は括弧，return文のみの場合はreturnが省略できるので以下のように書けます．
// 型の省略 IntFunc f3 = (x) -> {return x*x;}; // 括弧 & returnの省略 IntFunc f4 = x -> x*x;
ラムダ式によって抽象メソッドが実際に定義されたわけで，関数を呼ぶには以下のようにします．
// 以下どれも同じ f1.func(3); // => 9 f2.func(3); f3.func(3); f4.func(3); ((IntFunc)x->x*x).func(3);
ラムダ式はキャストすることも出来るので最後の例のようにも書けます．
インタフェースがラムダ式を受け付けることを明示的に@FunctionalInterfaceをつけることで宣言できます．また，Java8で追加されたインタフェースのデフォルトメソッドは抽象メソッドとはカウントされません(それプラスtoString()とかのObjectのメソッドも)．したがって以下のインタフェースは有効です．
@FunctionalInterface public interface IntFunc{ public int func(int x); } @FunctionalInterface public interface IntFunc2 extends IntFunc{ default public int doubleFunc(int x){ return func(x)+func(x); } } IntFunc2 f = x -> x*x; f.doubleFunc(3); // => 18
@FunctionalIntefaceがついているものとして代表的なものにはRunnableがあります．なので，以下のようにできます．
Runnable r = () -> System.out.println("Yeah"); Thread t = new Thread(r); t.start(); new Thread(()->{System.out.println("YYY");}).start(); ((Runnable)()->{System.out.println("ZZZ");}).run();
自分で使いたいラムダ式用にインタフェースを用意してもいいですが，よく使うと思われるものに関してはjava.util.function以下にいろいろと定義されています．
// 引数の型T, 戻り値の型Rの関数 public interface Function<T, R>{ R apply(T t); ... } // 戻り値がbooleanな関数 public interface Predicate<T> { boolean test(T t); ... } // 型Tの引数を受け取って何かする関数 public interface Consumer<T> { void accept(T t); ... } ...
デフォルトメソッドとしてFunctionには関数合成のためのcompose()であったり，Predicateにはand()やor()が用意されています．PredicateとConsumerの使用例:
public class Person { private String name; private int age; public Person(String name, int age){ this.name = name; this.age = age; } public String getName(){ return name; } public int getAge(){ return age; } public void check(Predicate<Person> predicate, Consumer<Person> consumer){ if(predicate.test(this)){ consumer.accept(this); } } public static void main(String[] args){ Person j = new Person("John",15); Predicate<Person> greaterThan12 = x -> x.getAge() > 12; Predicate<Person> lessThan20 = x -> x.getAge() < 20; Predicate<Person> isTeenage = greaterThan12.and(lessThan20); Consumer<Person> printName = x -> System.out.println(x.getName()); j.check(isTeenage,printName); // => John } }
いまいちあれな例ですが，check()は引数としてPredicateとConsumerを受け取り，Predicateの結果が真ならConsumerを実行します．
java.util.functionには他にも多くの関数があり，特にプリミティブ型向けに定義されているものが多いです．例えばIntFunction,LongBinaryOperator,DoubleUnaryFunction等々．この辺りはjavadocを読むより直接ソースをみて定義を確認した方が分かりやすいと思います．なぜプリミティブ型用のインタフェースが定義されているかというと，よく使うからという理由の他にジェネリクスではプリミティブ型が直接扱えないためラップクラスを使う必要があり，無駄なオブジェクトが生成されてしまうからです．具体的に以下の例を考えてみます．
Function<Integer,Integer> f1 = (x) -> x*x; IntUnaryOperator f2 = (x) -> x*x; long t1 = System.currentTimeMillis(); for(int i = 0;i < 1000000000;i++){ f1.apply(i); } long t2 = System.currentTimeMillis(); System.out.println(t2-t1); t1 = System.currentTimeMillis(); for(int i = 0;i < 1000000000;i++){ f2.applyAsInt(i); } t2 = System.currentTimeMillis(); System.out.println(t2-t1);
ここで，最初はFunction
Function<Integer,Integer> : 3420ms IntUnaryOperator : 4ms
2番目の方は早すぎてちゃんと計測できているか若干疑問ですが，とりあえず圧倒的にFunction
ラムダ式のスコープはラムダ式が宣言されているクラスになります．また，ラムダ式ではローカル変数の値を変更することはできません．ということでよくあるような以下のようなカウンタは作れません．
// NG public static IntSupplier makeCount(){ int count = 0; return ((IntSupplier)()-> { count += 1; return count;}); }
まぁこういうことをしたければ素直にクラスを作れということでしょうか．
さて，ここまでいろいろとラムダ式について見てきましたが，実際一番よく使うことになるのは以下のようにstream()と合わせた時な気がします．
List<Integer> xs = Arrays.asList(-3,-2,-1,0,1,2,3); xs.forEach((x)->{System.out.println(x);});
forEach()でリストの中身を順に処理できます．Java8から以下のようにしてメソッドを引数として渡すことができるようになりました．
xs.forEach(System.out::println);
stream()で返ってくるStreamクラスには他にもfilter()やmap(),reduce()といった関数が用意されています．
xs.stream().filter(x -> x > 0).forEach(x -> System.out.println(x*2)); // xsの総和 System.out.println(xs.stream().reduce(0,(x,y) -> x + y)); // xsの総和 (Integer::sumを使用) System.out.println(xs.stream().reduce(0,Integer::sum)); // xsの二乗和 System.out.println(xs.stream().map(x -> x*x).reduce(0,Integer::sum)); // xsの最大値 System.out.println(xs.stream().reduce(Integer.MIN_VALUE,Integer::max));
streamはparalellStreamを使うと並列になるようです．
xs.parallelStream().filter(x -> x > 0).forEach(x -> System.out.println(x*2));
この場合並列に処理されるので出力順は実行する毎に異なります．
また，Streamにはgenerator()というものがあります．以下のようにlimit()と合わせて使うようです．
Supplier<Double> random = Math::random; Stream.generate(random).limit(10).forEach(System.out::println); //10個の乱数を生成
generator()に似た物としてiterator()もあります．
Stream.iterate(1, y -> y*2).limit(10).forEach(System.out::println); // => 1,2,4,8,16,32,64,128,256,512
以下のようにすればカウンタも作れます．
Stream<Long> count = Stream.iterate(0L,y -> y+1); count.limit(10).forEach(System.out::println); // => 0,1,2,3,4,5,6,7,8,9
Stream.iterate()の実装を真似て以下のようにフィボナッチ数列のストリームを作ってみました．
public static Iterator<Long> getFibIterator(){ return new Iterator<Long>(){ private Long a = 1L; private Long b = 1L; private boolean first = true; private boolean second = true; @Override public boolean hasNext(){ return true; } @Override public Long next(){ if(first){ first = false; return 1L; }else if(second){ second = false; return 1L; } Long c = a + b; b = a; a = c; return c; } }; } public static Stream<Long> fibGen(){ return StreamSupport.stream(Spliterators.spliteratorUnknownSize( getFibIterator(), Spliterator.ORDERED | Spliterator.IMMUTABLE), false); }
以下のように使えます．
Stream<Long> fibStream = fibGen(); fibStream.limit(10).forEach(System.out::println); // => 1,1,2,3,5,8,13,21,34,55
再び同じfibStreamを読み込むと今度は89から値が得られます．
ということでJava8のラムダ式について少し見てきました．java.util.functionにいろいろあるのでそこのソースを見るのが一番いいんじゃないかなぁと思います．JavaではEnumはクラスですが，ラムダ式も実際にはインタフェースのインスタンスな訳で，そういう発想がJavaらしいし面白いなぁと個人的には思いました(それが嫌なら他の言語使うよね)．
参考
Maurice Naftalin's Lambda FAQ
Trying Out Lambda Expressions in the Eclipse IDE
Java 8 Tutorial: Streams Part 2 -- map, reduce, and specialized numbe…
グラフ(ネットワーク)を奇麗に描画するアルゴリズム
グラフはノードと辺の集合から構成されているだけなので，その描画方法は任意です．例として，以下の3つのグラフはどれも同じです．
グラフをどうやって奇麗に描画するかという研究は昔からおこなわれていて，そのうちの一つに力学モデルがあります(Wikipedia)．このモデルではノード間にある力が作用すると考えてそれが安定するような場所を探します．簡単な例ではノードを電荷だと仮定してそれぞれに働くクーロン力を計算し，それをもとにノード位置の修正をおこないます．
力学モデルのアルゴリズムで代表的なものにFruchterman-Reingold アルゴリズムがあります．このアルゴリズムは多くのグラフを扱うライブラリでサポートされているようです．
このアルゴリズムの考え方はシンプルで，ノードに影響する力が2つあります．一つは自分以外の全てのノードからの斥力，もう一つが隣接ノードからの引力です．斥力f_rと引力f_aは以下の式で定義されます．
ここで k は以下の式で定義されます．
areaは描画領域の面積(横幅W,縦幅Lだとするとarea = W*L)，|V|は頂点数，cはある定数です．f_rとf_aの関係を図にすると以下のようになります(k=10の場合)．
図に示したように，d=kのときf_a + f_rは0となります．アルゴリズムではdをノード間の距離だとして，それぞれのノードがなるべくkだけ離れているような場所を探します．つまり，kはノード間の理想距離として定義されています．もしあるノード間の距離がkよりも大きくはずれていたらそれを修正するように力が働きます．
斥力と引力の式は実験的に求めたもので，どちらもフックの法則に似ています．論文では斥力・引力の候補として
を考えてみたものの，この場合だと極所解に陥ることが多かったということが書かれています．
また，もう一つアルゴリズムにおける重要な考えとして，温度パラメータtがあります．この温度パラメータは，変位の最大値を決定します．つまり，引力と斥力の影響を考慮してノードを動かすわけですが，あまり大きく動いてしまっても困るので，t以下に制限するわけです．いまいちこの温度パラメータに関しては論文に載っていないような気がしますが，一つの例としてはtの初期値を病が領域の横幅の10分の1とし，それを1回の繰り返しごとに徐々に減少させていく方法があります．
実際のアルゴリズムの処理の流れは以下のようになります．
1. 各頂点間に働く引力/斥力を計算
2. 1. で計算した値をもとに頂点を動かす．ただし，このとき枠外に出ないようにする．また，動かす変位の大きさは温度パラメータt以下とする．
3. 温度パラメータを下げる
4. 以上の処理をある一定回数繰り返す．
基本的な計算量はO(|V|^2 + |E|)になります．計算を高速化する手法として論文では領域をいくつかに分割し，ある領域内にいるノードはその領域内の他のノードからのみ力を受けると仮定して計算する方法が書かれています(この辺りちゃんと読んでない..)．計算の終了条件がただのループのみなので，一定時間での計算が保障されています．斥力は自分以外の全てのノードから，引力は自分が繋がっているノードからのみ受けるという点も割とポイントだと思います．
さて，このアルゴリズムを実際にpythonで実装をしてみます．グラフ自体の表現にはNetworkXを使います (なお，NetworkXではspring_layoutがFruchterman-Reingold アルゴリズムの実装です．デフォルトでNetowkXで描画するとこのアルゴリズムが使用されます)．論文に擬似コードが載っていますので，そのまま素直に実装します．
fruchterman_reingold()が実際のアルゴリズム部分です．この実装では領域は中心(0.5,0.5)，半径0.5の円としています(領域を四角にしてしまうとグラフが四角くなりやすくなるため)．
実際にグラフの構造が変化する流れは以下のようになります(この例ではわざとtを小さくとって1回の変化を小さくしています)．
before
after
NetworkXにもともとあるfruchterman-reingoldを使って描画すると以下のようになります．
こんなものですかね．NetworkXの方が若干良さそうな感じがしなくもないですが．
別の例
ということで以上のような感じで比較的シンプルにグラフを奇麗に描画することができます．ちなみに上のpythonの例ではほぼ擬似コードそのままで最適化もなにもしていないしそもそも計算方法自体が最も基本的なものなので遅いです．まぁ参考ということで．NetworkXなら素直にspring_layout使いましょう．
NetworkXによるスモールワールドネットワークの生成
NetworkXはpython製の複雑ネットワークのためのライブラリです．NetworkXを使うと，お手軽にグラフ構造が作成できます．平均経路長(2点のノード間の平均距離)やクラスタリング係数(隣接ノード同士が接続している割合)といったネットワークの特徴量を求める関数が用意されているのは勿論のこと，経路探索や，さらにはPageRankやHITSといったものも簡単に計算できます．また，matplotlibを使うことで描画もできます．
インストールは
$ pip install networkx matplotlib
でできます（ちなみにMac OS 10.9ではln -s /usr/local/opt/freetype/include/freetype2 /usr/local/include/freetypeしないと駄目でした）．
NetworkXのサンプルは以下のようになります(以下python3です)．
#!/usr/bin/env python import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() G.add_node(1) G.add_node(2) G.add_node(3) G.add_edge(1,2) G.add_edge(2,3) nx.draw(G) plt.savefig("a.png")
これで以下のグラフが生成されます．
見たままですね．ちなみにadd_node()では基本的にどんなオブジェクトでも追加できます．今回はこのNetworkXを使ってスモールワールドネットワークの検証をしてみることにしました．
スモールワールドネットワークとは複雑系ネットワークに分類されるネットワークの一種で，簡単にいってしまうと
(1)全体のノード数に対して各ノードが持つリンク数（辺の数）が小さいが，平均経路長は短い，
(2)クラスタリング係数が高い
という性質を持つネットワークです．これは現実世界のネットワークがよく持つ性質です．例えば，人間関係のネットワークを考えてみると，全人口に対して一人の人間が持つリンク数(知人数)は小さいです．また，ある人の友人同士が友人である確率はそれ以外の場合に比べると高い(クラスタリング係数は高い)と考えられます．平均経路長が短いというのは直感には合わないかもしれませんが，有名なミルグラムの実験の結果で示されるように，どんな人でも友人を辿っていけば6人以下でほぼ到達できることが分かっています．
1998年にWatssらがこのスモールワールドネットワークを定式化し，生成する方法を発表しました（論文はこれ）．この論文の登場によって一気に複雑系ネットワークの研究が進んだそうで，引用数2万overとよく分からないことになってます．
この論文でのスモールワールドネットワーク生成方法は発表者の氏名をとってWatts & Strogtzモデル(WSモデル)と呼ばれます．WSモデルの生成方法は以下のようになります．
1. グラフ内にN個のノードを追加する（それぞれ1~Nと番号をつける)
2. 各ノードを隣接k個のノードと接続する (例えばk=1ならノード1はノード2とノードN と接続)
3. グラフ内の各辺それぞれについて，確率pでリンクを適当なノードに繋ぎ変える（重複は禁止）
ここでp=0の場合は何も繋ぎ変えが起こらず，この場合平均経路長は長く，クラスタリング係数は大きくなります．またp=1の場合はいわゆるランダムネットワークが生成され，平均経路長が短く，クラスタリング係数は小さくなります．pが中間ぐらいのとき，先ほどの言った平均経路長が短くクラスタリング係数が高いというスモールワールドネットワークが生成されます．
NetworkXにはこのWSモデルでネットワークを生成する関数が当然ながら用意されているのですが，まぁ折角なので自分で論文の方法に忠実に作ってみました．
make_small_world_netork()がWSモデルによるスモールワールドネットワーク生成関数です．ただ作るだけでは意味がないので，論文と同じように確率pを変化させ平均経路長L(p)とクラスタリング係数C(p)のp=0に対する比のグラフを生成してみます．ノード数と各ノード辺の数はそれぞれ1000と10です．
(データはこちら．左からp,L(p)/L0,C(p)/C0です）
論文のFigure2と同じような結果が得られました(ならないと困りますが..)．x軸は対数スケールです．このグラフから(1)平均経路長はp=0.01でも十分小さい(p=1のランダムネットワークの平均経路長に近い），(2)一方pが1付近でなければクラスタリング係数はランダムネットワークよりも十分大きい(p=0のクラスタリング係数に近い)，ということが分かります．これがスモールワールドネットワークの持つ性質です．
さて，論文の後半ではこのスモールワールドネットワークを使って簡単な病気の伝染のシミュレーションをおこなっているので，それもやってみることにします．シミュレーションの流れは以下のようになります．
1. スモールワールドネットワークを生成する．(各ノードが人を表す)
2. ノード0 が伝染病に感染しているとする(初期条件)
3. 確率rで感染しているノードの隣接ノードに感染する
4. 感染したノードは一定ステップ後に取り除かれる(死亡)
5. 全てのノードが感染 or 感染しているノードが存在しなくなったらシミュレーションを終了
論文にはノードの大きさや辺の数が書いていないようなので，先ほどと同じノード数1000，各ノードのリンク数10，また感染してから死亡するまでの時間を2としてシミュレーションをしてみました．コードは以下のようになります．
実行結果
最初の図は各pに対してrを変化させ，半分以上のノードが感染する確率r_halfをグラフにしたものです．また，2番目の図はr=1(常に隣接ノードに感染)と固定した場合に全てのノードが感染するまでにかかる時間T(p)をp=0のときの値T0で割ったグラフです(データはこちら．左からp,r_half,T(p)/T0,L(p)/L0です）．x軸は先ほど同様に対数スケールです．これらの図は論文のFigure3に相当します．この図から(1)r_halfはpが小さいところで急激に減少する(p > 0.1 ではあまり変化がない)，(2)T(p)/T(0)のグラフはL(p)/L(0)のグラフに近く，つまりpが0.01程度でも急速に感染が進む，ということが分かります．
また，r=1のときにp=0,0.05,1のそれぞれについてどのように伝染していくか図にしてみると以下のようになります(ソース)
(1) p = 0
必要ステップ数: 101
平均経路長: 50.450450450450454
クラスタリング係数: 0.6666666666666636
(2) p = 0.05
必要ステップ数: 9
平均経路長: 5.318636636636636
クラスタリング係数: 0.5792653735153729
(3) p = 1
必要ステップ数: 5
平均経路長: 3.2708968968968968
クラスタリング係数: 0.009309777477424539
このようにp=0.05でも十分平均経路長は短く，あっという間に伝染していく様子が観察できます．平均経路長が短くなる理由は，辺の繋ぎ変えをおこなうことで遠くのノード同士を繋ぐショートカットが生成されるからです．
さて，このような感じでとても簡単な方法でスモールワールドネットワークが生成できて，現実世界のネットワークをよく近似しますが，実は現実世界のネットワークはスモールワールドネットワークが持っていない重要なある性質を持っています．それはスケールフリー性です．スケールフリー性を持つネットワークは次数分布(次数はあるノードにおける辺の数のこと)がベキ分布に従い，高次元のノード数が少なく，低次元のノードが多くなります(WSモデルでは全てのノードの辺の数は等しいです）．このスケールフリー性を持つネットワーク（スケールフリーネットワーク）を生成する方法がWSモデルの1年後の1999年にBarabasiらによって発表されました．例えば，Twitterなんかではごく一部のユーザのみが膨大なフォロワー数を持っていますね．勿論NetworkXにはスケールフリーネットワークを生成する関数が用意されています．
スケールフリーネットッワークについては次回?
PageRank 解説
Mining of Massive Datasetsというのを輪読していて、PageRankに関する部分のスライドを折角作ったのでslidshareに置いておきました。
最後のRでのPageRankの実装について補足をしておくと、Rで固有値を求める場合行列の全ての固有値・固有ベクトルを求めているので全然フェアではないです。反復法が断トツで早いのには変わりはないですが。
こうして実装してみると非常に簡単ですが実際には行列の次元が100万~10億以上になるので計算には相当な工夫が必要だと思います(次の5.2章が実装についての話）。
あとPageRankの特許はスタンフォード大が保持していてgoogleに独占でライセンスしているらしいのでアメリカで勝手に実装すると本当はアウトなんですかね。googleが訴訟したことは一度もないらしいですが。まぁ、そもそももうgoogleはこのPageRankをそのまま使ってないでしょうけど。
bootstrapめも
CSSとか書きたくないんだけどナビゲーションバーぐらい欲しい..
って思って少し調べてたらbootstrapをcdnで配信してるのが見つかったので利用してみることに。
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title></title> <link href="//netdna.bootstrapcdn.com/bootstrap/3.0.3/css/bootstrap.min.css" rel="stylesheet"> <style> body{ padding-top: 20px; } </style> </head> <body> <div class="container"> <div class="navbar navbar-default" role="navigation"> <ul class="nav navbar-nav"> <li><a href="#">foo</a></li> <li><a href="#">bar</a></li> <li><a href="#">baz</a></li> </ul> </div> <div class="jumbotron"> <h2> This is title!! </h2> <p> ooohooooo </p> </div> <div class="panel panel-default"> <div class="panel-heading">panel title</div> <div class="panel-body"> body </div> </div> </div> </body> </html>
これだけ覚えとけばなんとかなりそう。
pythonのitertoolsのrecipeのメモ
公式にitertoolsのrecipe集があるのでそれのメモ．
バージョン: python3.3
参考: itertools — Functions creating iterators for efficient looping — Python 3.7.3 documentation
・take(n,iterable)
最初のn個の要素をリストとして返します
from itertools import islice def take(n, iterable): return list(islice(iterable, n))
例
In [76]: take(3,[1,2,3,4,5]) Out[76]: [1, 2, 3]
・tabulate(function,start=0)
function(0),function(1),... を返すイテレータを返します．
from itertools import count def tabulate(function, start=0): return map(function, count(start))
例
In [82]: i = tabulate(lambda x: x*x) In [83]: next(i) Out[83]: 0 In [84]: next(i) Out[84]: 1 In [85]: next(i) Out[85]: 4 In [86]: next(i) Out[86]: 9
・consume(iterator,n)
イテレータをn進める，もしnがNoneならイテレータを末尾まで進める
import collections from itertools import islice def consume(iterator, n): if n is None: collections.deque(iterator, maxlen=0) else: next(islice(iterator, n, n), None)
例
In [105]: it = iter([1,2,3,4,5,6,7,8,9,10]) In [106]: consume(it,n=5) In [107]: for i in it: .....: print(i) .....: 6 7 8 9 10
・nth(iterable,n,default=None)
n番目の要素を返します．もしnが範囲外ならdefaultを返します
from itertools import islice def nth(iterable, n, default=None): return next(islice(iterable, n, None), default)
例
In [110]: nth([1,2,3],2) Out[110]: 3
・quantify(iterable,pred=bool)
predがTrueになる要素の数を返します
def quantify(iterable, pred=bool): return sum(map(pred, iterable))
例
In [115]: quantify([1,2,3,4,5],pred=lambda x: x<3) Out[115]: 2 # 3より小さい数の数
・padnone(iterable):
iterableな要素の後にNoneを付け加えたイテレータを返す
from itertools imprt chain,repeat def padnone(iterable): return chain(iterable, repeat(None))
例
In [125]: a = padnone([1,2,3]) In [126]: next(a) Out[126]: 1 In [127]: next(a) Out[127]: 2 In [128]: next(a) Out[128]: 3 In [129]: next(a)
・ncycles(iterable,n):
iterableをn回繰り返すイテレータを返す
frmo itertools import chain,repeat def ncycles(iterable, n): return chain.from_iterable(repeat(tuple(iterable), n))
例
In [136]: it = ncycles([1,2],3) In [137]: for i in it: .....: print(i) .....: 1 2 1 2 1 2
・dotproduct(vec1,vec2)
vec1,vec2の内積を返します．
import operator def dotproduct(vec1, vec2): return sum(map(operator.mul, vec1, vec2))
例
In [141]: dotproduct([1,2],[3,4]) Out[141]: 11
・flatten(listOfLists)
リストのリストを一つのリストにまとめます
from itertools import chain def flatten(listOfLists): return chain.from_iterable(listOfLists)
例
In [144]: it = flatten([[1,2],['a','b']]) In [145]: for i in it: .....: print(i) .....: 1 2 a b
・repeatfunc(func,times=None,*args)
funcをtimes回リピートした結果を返すイテレータを返します．
timesを指定しない場合は無限リストになります．
from itertools import starmap,repeat def repeatfunc(func, times=None, *args): if times is None: return starmap(func, repeat(args)) return starmap(func, repeat(args, times))
例
In [150]: r = repeatfunc(random.random) In [151]: next(r) Out[151]: 0.5425125491886116 In [152]: next(r) Out[152]: 0.37101369831757924
・pairwise(iterable)
1つだけ指す場所が違う2つのイテレータを返します．連続した2つの要素を操作するのに使えます．
from itertools import tee def pairwise(iterable): a, b = tee(iterable) next(b, None) return zip(a, b)
例
In [163]: xs = [1,4,9,16,25] # xs[i] - xs[i-1] を計算したい In [164]: for a,b in pairwise(xs): .....: print(b-a) .....: 3 5 7 9
・grouper(n,iterable,fillvalue=None)
要素をn個ずつにまとめます．要素数がnで割り切れなかったらfillvalueで埋められます．
from itertools import zip_longest def grouper(n, iterable, fillvalue=None): args = [iter(iterable)] * n return zip_longest(*args, fillvalue=fillvalue)
例
In [168]: it = grouper(3,'ABCDEFG','x') In [169]: for i in it: .....: print(i) .....: ('A', 'B', 'C') ('D', 'E', 'F') ('G', 'x', 'x')
なんでこういう動作をするかというと，args = [iter(iterable)]*n とイテレータを複製していますが，このイテレータは全て同一であるため，いずれか一つのイテレータを操作すると他のイテレータも操作されるためです．
・roundrobin(*iterables)
それぞれのiterableなものから順番に要素をとってきます．
from itertools import cycle,islice def roundrobin(*iterables): # Recipe credited to George Sakkis pending = len(iterables) nexts = cycle(iter(it).__next__ for it in iterables) while pending: try: for next in nexts: yield next() except StopIteration: pending -= 1 nexts = cycle(islice(nexts, pending))
例
In [171]: it = roundrobin([1,2],'AB','xy') In [172]: for i in it: .....: print(i) .....: 1 A x 2 B y
・partition(pred,iterable)
predがTrueかどうかに応じてiterableを2つに分割します
from itertools import filterfalse def partition(pred, iterable): t1, t2 = tee(iterable) return filterfalse(pred, t1), filter(pred, t2)
例
In [174]: it1,it2 = partition(lambda x: x<3, [1,2,3,4,5]) In [175]: for i in it1: print(i) .....: 3 4 5 In [176]: for i in it2: print(i) .....: 1 2
・powerset(iterable):
iterableの冪集合を返します
from itertools import chain,combinations def powerset(iterable): s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
例
In [178]: it = powerset([1,2,3]) In [179]: for i in it: .....: print(i) .....: () (1,) (2,) (3,) (1, 2) (1, 3) (2, 3) (1, 2, 3)
・unique_everseen(iterable,key=None)
iterableな要素のうちユニークなもののみを返すイテレータを返します
from itertools import filterfalse def unique_everseen(iterable, key=None): seen = set() seen_add = seen.add if key is None: for element in filterfalse(seen.__contains__, iterable): seen_add(element) yield element else: for element in iterable: k = key(element) if k not in seen: seen_add(k) yield element
例
In [189]: it = unique_everseen([1,2,1,1,2,4,2,5]) In [190]: for i in it: print(i) .....: 1 2 4 5
・unique_justseen(iterable,key=None)
連続する要素を1つにまとめます．
from operator import itemgetter from itertools import groupby def unique_justseen(iterable, key=None): return map(next, map(itemgetter(1), groupby(iterable, key)))
例
In [200]: it = unique_justseen([1,1,2,3,3,1,2,2]) In [201]: for i in it: .....: print(i) .....: 1 2 3 1 2
下の例でも結果は同じだけど上のようにやると遅延評価できる
In [206]: def unique_justseen(iterable,key=None): return map(itemgetter(0),itertools.groupby(iterable,key)) .....: In [207]: for i in it: print(i) .....: In [208]: it = unique_justseen([1,1,2,3,3,1,2,2]) In [209]: for i in it: print(i) .....: 1 2 3 1 2
・iter_except(func,exception,first=None)
funcを例外が発生するまで呼び続けます．firstは最初に1回だけ実行される(dbの初期化とかに使う)．
def iter_except(func, exception, first=None): try: if first is not None: yield first() while 1: yield func() except exception: pass
例
In [219]: it = iter_except(d.popitem,KeyError) In [220]: for i in it: # KeyErrorで中断されることなく処理できる .....: print(i) .....: ('a', 1) ('b', 2) ('c', 3)
・random_product(*args,repeat=1)
直積をランダムに1つ返します
import random def random_product(*args, repeat=1): pools = [tuple(pool) for pool in args] * repeat return tuple(random.choice(pool) for pool in pools)
例
In [277]: random_product([1,2],['x','y']) Out[277]: (1, 'x') In [278]: random_product([1,2],['x','y']) Out[278]: (1, 'y')
・random_permutation(iterable,r=None)
順列をランダムに1つ返します
import random def random_permutation(iterable, r=None): pool = tuple(iterable) r = len(pool) if r is None else r return tuple(random.sample(pool, r))
例
In [267]: random_permutation([1,2,3]) Out[267]: (2, 1, 3) In [268]: random_permutation([1,2,3]) Out[268]: (3, 2, 1)
・random_combination(iterable,r)
組み合わせをランダムに一つ返します
import random def random_combination(iterable, r): pool = tuple(iterable) n = len(pool) indices = sorted(random.sample(range(n), r)) return tuple(pool[i] for i in indices)
例
In [280]: random_combination([1,2,3],2) Out[280]: (1, 3) In [281]: random_combination([1,2,3],2) Out[281]: (1, 2)
・random_combination_with_replacement(iterable,r)
重複組み合わせをランダムに一つ返します
def random_combination_with_replacement(iterable, r): pool = tuple(iterable) n = len(pool) indices = sorted(random.randrange(n) for i in range(r)) return tuple(pool[i] for i in indices)
例
In [286]: random_combination([1,2,3],2) Out[286]: (3, 3) In [287]: random_combination([1,2,3],2) Out[287]: (1, 3)
pythonのitertoolsメモ
バージョン: python3.3
参考: http://docs.python.org/3/library/itertools.html
itertoolsのpythonによる実装が書いてあるので勉強になります．
・itertools.accumulate(iterable[, func])
In [2]: it = itertools.accumulate([1,2,3]) In [3]: for i in it: ...: print(i) ...: 1 3 # 1+2 6 # 3+3 In [6]: it = itertools.accumulate([1,2,3],lambda x,y: x*y) In [7]: for i in it: ...: print(i) ...: 1 2 # 1*2 6 # 2*3
python3.2で追加されてfuncは3.3から指定できるようになったらしい．
・itertools.chain(*iterables)
iterableなアイテムをつなげたイテレータを返す
In [10]: it = itertools.chain([1,2,3],['a','b','c']) In [11]: for i in it: ....: print(i) ....: 1 2 3 a b c
・itertools.chain.from_iterable(iterable)
iteratools.chain(*iterables)と似てるけど引数が一つのリスト
In [13]: it = itertools.chain.from_iterable([[1,2,3],['a','b','c']]) In [14]: for i in it: ....: print(i) ....: 1 2 3 a b c
・itertools.combinations(iterable,r)
長さrの組み合わせを返します
In [15]: it = itertools.combinations([1,2,3],2) In [16]: for i in it: ....: print(i) ....: (1, 2) (1, 3) (2, 3)
・itertools.combinations_with_replacement(iterable,r)
重複を含めた長さrの組み合わせを返します
In [17]: it = itertools.combinations_with_replacement([1,2,3],2) in [18]: for i in it: ....: print(i) ....: (1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)
・itertools.compress(data,selectors)
selectorsがTrueの要素のdataについてのイテレータを返します
例を見た方が早い．
In [21]: it = itertools.compress(['A','B','C'],[True,False,True]) In [22]: for i in it: ....: print(i) ....: A C
python3.1で追加
・itertools.count(start=0,step=1)
startから初めてstepずつ増えてくiteratorを返します
In [27]: def generator(): ....: for i in range(10): ....: yield i In [30]: for i,v in zip(generator(),itertools.count()): print("{0}:{1}".format(i,v)) ....: 0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 9:9
ちなみにpython3ではzip()がpython2のitertools.izip()に相当します．
・itetools.cycle(iterable)
iterableなものを巡回するイテレータを返します．
In [2]: it = itertools.cycle([1,2,3]) In [3]: next(it) Out[3]: 1 In [4]: next(it) Out[4]: 2 In [5]: next(it) Out[5]: 3 In [6]: next(it) Out[6]: 1 In [7]: next(it) Out[7]: 2 In [8]: next(it) Out[8]: 3 ||<k ・itertools.dropwhile(predicate,iterable) 先頭から見ていって初めてpredicateがFalseになる要素の前までの要素を除いたイテレータを返します >|python| In [12]: it = itertools.dropwhile(lambda x : x < 5, [1,2,4,2,5,3,6,2]) In [13]: for i in it: ...: print(i) ...: 5 3 6 2
・itertools.filterfalse(predicate,iterable)
iterableをpredicateでフィルターした結果を返すイテレータを返します
In [14]: it = itertools.filterfalse(lambda x : x < 5, [1,2,4,2,5,3,6,2]) In [15]: for i in it: ....: print(i) ....: 5 6
・itetools.groupby(iterable,key=None)
連続する要素をkeyで比較して一致した場合には一つにまとめる．keyを指定しない場合は同じ要素が連続した場合一つにまとめます
uniqコマンド的な．
戻り値は2つあって，1つがキー，もう一つが連続する要素をまとめたもの（これもイテレータ）.
In [24]: for k,g in itertools.groupby('AAABDDDCCC'): print(k) print(list(g)) ....: A ['A', 'A', 'A'] B ['B'] D ['D', 'D', 'D'] C ['C', 'C', 'C']
・itertools.islice(iterable,stop), itertools.islice(iterable,start,stoip[,step])
iterableな要素の中で選択した範囲を返すイテレータを返します
In [25]: it = itertools.islice('ABCDEFG',1,5,2) In [26]: for i in it: ....: print(i) ....: B D
・itertools.permutation(iterable,r=None)
長さrの順列を返します．rを指定しない場合はiterableの長さがrになります．
In [27]: it = itertools.permutations('ABC') In [28]: for i in it: ....: print(i) ....: ('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')
・itertools.product(*iterables,repeat=1)
直積を返します．product([0,1],repeat=3)はproduct([0,1],[0,1],[0,1])と同じ意味．
In [34]: it = itertools.product([0,1],['x','y']) In [35]: for i in it: ....: print(i) ....: (0, 'x') (0, 'y') (1, 'x') (1, 'y')
・itertools.repeat(object[, times])
objectをtimes回繰り返すイテレータを返します．timesを指定しない場合無限リストになります．
主な使い方としてはmap()やzip()に一定値を与えるのに使うみたい
In [37]: list(map(pow,range(10),itertools.repeat(2))) Out[37]: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
・itertools.starmap(function,iterable)
iterableな各要素についてfunctionで計算した結果のイテレータを返します．
map()に似てるけど要はmapの引数が既にzip化されてるときに使います．
In [46]: [i for i in itertools.starmap(pow,[(2,5),(3,2),(10,3)])] Out[46]: [32, 9, 1000]
これと等価
In [50]: x = zip([2,3,10],[5,2,3]) In [51]: for i in itertools.starmap(pow,x): print(i) ....: 32 9 1000
ちなみにmap()を使うなら
In [52]: [i for i in map(pow,[2,3,10],[5,2,3])] Out[53]: [32, 9, 1000]
・itertools.takewhile(predicate,iterable)
先頭から見ていってpredicateが初めてFalseになるまでの要素を返すイテレータを返す．
In [64]: it = itertools.dropwhile(lambda x:x<5, [1,2,3,5,2,1]) In [65]: for i in it: ....: print(i) ....: 5 2 1
・itertools.tee(iterable,n = 2)
1つのiterableからn個のイテレータを返します．nのデフォルトは2です．
In [66]: it1,it2 = itertools.tee([1,2,3]) In [67]: for i in it1: ....: print(i) ....: 1 2 3 In [68]: for i in it2: ....: print(i) ....: 1 2 3
teeで複数イテレータを作ったあと元のiterableを操作することはイテレータが勝手に進んだりするのやめましょう．イテレータを複数作るのに比べてteeのメリットは何かというと，teeを使った方がバッファリングをするためI/Oが少なくなり，動作が速くなる可能性があります．逆に言うとメモリをよく消費します．このことはteeの実装を見ると分かります．
def tee(iterable, n=2): it = iter(iterable) deques = [collections.deque() for i in range(n)] def gen(mydeque): while True: if not mydeque: # when the local deque is empty newval = next(it) # fetch a new value and for d in deques: # load it to all the deques d.append(newval) yield mydeque.popleft() return tuple(gen(d) for d in deques)
この用に，teeで何をしているかというと，iterableから一つイテレータを作って，それからn個のdequeを用意して，いずれかのteeの戻り値のイテレータがが新しい値を取り出す度に他のdequeに値を追加していきます．
・itertools.zip_longest(*iterables,fillvalue=None)
zip()に似ていますが，zipと違うのはiterablesの長さが異なる場合，短いiterableが
終わるとそれ以降対応する場所はfillvalueで埋められます．
In [69]: it = itertools.zip_longest(['A','B','C','D'],[1,2],fillvalue='-') In [70]: for i in it: ....: print(i) ....: ('A', 1) ('B', 2) ('C', '-') ('D', '-')
