Bash/Octaveで順列・組み合わせ
Bashで計算しようとしたのだが、結論から言うと遅すぎて使えない。
Octaveで計算すると早かったのでそっちを推奨する。
Bash
順列 (nPr)
- bash - Generate combinations of elements with echo - Stack Overflow
- 参考になったが、これはCombinationではなくPermutationだ
#!/bin/bash
n=$1
r=$2
elem=$(echo `seq 1 $n` | tr ' ' ',')
set="{"${elem}"}"
group=$r
for ((i=0; i<$group; i++));
do
repetition=$set$repetition
done
bash -c "echo "$repetition""
組み合わせ (nCr)
- ここのやつをコピペして使おう！
Octave
- Octave Online: Free Interface compatible with MATLAB
- まずは 1～100までの縦ベクトルを設定
- nCr (n=100, r=3)の組み合わせを取得、結果は行列になるのでビジュアルでわかりやすい
- １行ごとに和を求めてみる
- 和が100になるものの数を見る
> A = [1:100]'; > C = nchoosek(A,3); > SUM = sum(C,2) > sum(SUM == 100) ans = 784
-
- 計算結果が見たいので、COMPUTEに行列をとる
- Selecting only a specific number of rows fulfilling a condition
- ちょっとよくわからないけど、これで４列目が100になっているものだけとれる
> COMPUTE = [C SUM]; > idx = ( COMPUTE(:,4)==100 ); > SUMMARIZE = A(idx,:);
結論、行列計算は最高
Javaで簡単な組み合わせの総数 nCr を求めてみる
Aizu Online Judgeをやっていて、求められんかな？と思ったので。
速さとかは遅いと思う。
Java
実働してるやつ
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Set; import java.util.HashSet; public class prog { public static void main(String[] args) { // nCr : n=[1,2,3,4,5],r=3 で試してみる ArrayList<Integer> n1 = new ArrayList<>(Arrays.asList(1,2,3,4,5)); //getCombination(n1,3); // nCr : n=[1,2,3,4,5,6,7],r=4 で試してみる ArrayList<Integer> n2 = new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7)); getCombination(n2,4); } private static Set<ArrayList<Integer>> getCombination(ArrayList<Integer> n, Integer r) { Set<ArrayList<Integer>> ans = new HashSet<ArrayList<Integer>>(); combination(n, r, ans); for (ArrayList<Integer> e : ans) { System.out.println(e.toString()); } return ans; } private static void combination(ArrayList<Integer> n, Integer r, Set<ArrayList<Integer>> ans) { if (n.size() == r) { ans.add(n); return; } for (int i = 0; i < n.size(); i++) { ArrayList<Integer> N = new ArrayList<Integer>(); N.addAll(n); N.remove(i); combination(N,r,ans); } } }
所感
再帰関数は苦手で、自分でも若干どうして動いてるのかわからない部分がある。手続き型の設計書にしろと言われると多分無理（やめたほうがいい）。しかしポイントは以下で、与えられたサイズの配列からremoveで削除して組み合わせを作っているのだが、削除するインデックスがiで徐々にインクリメントされるのでn回試行するといろいろな組み合わせができる。
for (int i = 0; i < n.size(); i++) { ArrayList<Integer> N = new ArrayList<Integer>(); N.addAll(n); N.remove(i); combination(N,r,ans); }
あと、答えの型は
Set<ArrayList<Integer>>
にしておくと、勝手に配列の重複削除されるのです。nCrじゃなくてn-r+1Crを求めたい場合は、SetじゃなくてただのListにすればよいのでは。
Ruby
実働してるやつ
ソースコード
require 'set' def combi(n, r, ans) if n.size == r ans.add(n) return end for i in 0...n.size arr = n.dup arr.delete_at(i) combi(arr, r, ans) end end def get_combination(n, r) ans = Set.new combi(n, r, ans) ans.map do |e| puts e.to_s end ans end n = [1,2,3,4,5] get_combination(n, 3)
答え合わせはこのへんで
組合せ - 高精度計算サイト
Apache PigでZipファイルをロード
経緯
仕事でHadoopを使うとき、gzip/bzipは標準で読み込めるがzipは読み込めなかった。困る。
Hadoopの本流でzipファイルを読む機能がマージされてないまま放置されていることに気づく
1. It does not split the zip files efficiently. This is because there is no way in Java to construct a zip input stream that permits random seeks given a zip entry name.
2. Java's handling of large zip file is not robust.
と、言われてます。１はよくわかりませんが、２については How to iterate zip file records (java.util.zip.ZipFile, java.util.zip.ZipInputStream) - Java Performance Tuning Guide に書かれているように、Java7からは2GB超えファイルにも標準で対応しています。
Map/Reduce
さっきのチケットの中で、Map/Reduceを拡張して読めるようにしてるブログを見つけました。
あと、同じことやってる人を見つけた
つまりはApache PigのLoad関数はHadoopのInputFormatクラスを使用している。それはそれぞれのレコードに対してRecordReaderをとり、そしてTuple（かそれ以外の何か）に変換している。なので、zip圧縮されたファイルを読みたいのならば、どうしても自前のInputFormat/RecordReaderを書く必要がある。上記のサイトはすでにそれを用意してくれている。
使い方
- mvn packageなどを実行してjarファイルを作ってpigスクリプトに追加
%declare ZIPLOADER 'com.cotdp.pigudf.ZipLoader';
REGISTER target/com-cotdp-hadoop-1.0-SNAPSHOT.jar
-- 全ファイル取得
A = LOAD 'src/test/resources/zip-01.zip' USING $ZIPLOADER('');
DUMP A;
-- 改行を区切りにしてbagとして取得
A = LOAD 'src/test/resources/zip-01.zip' USING $ZIPLOADER('\r\n') AS (raw:bytearray);
B = FOREACH A GENERATE FLATTEN($0) AS (raw:chararray);
DUMP B;今はほんとに中身を出力するだけ
