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;今はほんとに中身を出力するだけ
Hadoop関連ソフトウェアを手っ取り早くパッケージでインストールする
Apache Bigtop
Bigtop is an Apache Foundation project for Infrastructure Engineers and Data Scientists looking for comprehensive packaging, testing, and configuration of the leading open source big data components. Bigtop supports a wide range of components/projects, including, but not limited to, Hadoop, HBase and Spark.
Bittopは包括的なパッケージ、テストそしてオープンソースのビッグデータ構成要素の設定を探しているインフラエンジニアやデータサイエンティストのためのApacheソフトウェア財団のプロジェクトです。Bigtopは広い範囲の構成要素/プロジェクトを含んでおり、しかしながらその範囲はHadoop、HBaseやSparkに限りません。
