整数の均等分割 (Groovy)

整数を均等に分割する

なるべく均等に整数を指定の数に分割する関数。
マッチングの処理なんかで使う事があったので、
その時に実装したものを。
検索すると既にいっぱい出て来たので、
あまり需要はないかもと、思いつつも自分のメモとして残しておく。
標準ライブラリにあってもいい気がするんですが、
僕は見つけられなかったです…。
何処かにあったりしないのかな？

整数の均等分割の関数

def integerPartition1(int n, int d) {
    int div = n / d
    int rem = n % d
    def arr = []
    for(int i = 0; i<d; i++){
        arr << (div + ((i < rem)? 1 : 0))
    }
    return arr
}

def ret = integerPartition1(10,3)
println ret
// ==> [4,3,3]

分割した数をリストで返してくれる。
リストの先頭側に余りの数は配置される。

余りを末尾にしたい場合はこちら。

def integerPartition2(int n, int d) {
    int div = n / d
    int rem = n % d
    def arr = []
    for(int i=d; 0<i; i--){
        arr << (div + ((i <= rem)? 1 : 0))
    }
    return arr
}

def ret = integerPartition2(10,3)
println ret
// ==> [3,3,4]

ここで紹介されているものも、groovyで書いてみた。

http://qiita.com/keisuke-nakata/items/c18cda4ded06d3159109

def integerPartition3(int n, int d) {
    def arr = []
    for(int i = 0; i<d; i++){
        arr << (int)((n + i) / d)
    }
    return arr
}

def ret = integerPartition３(10,3)
println ret
// ==> [3,3,4]

確かに均等分割されているが、forループ内で割り算が都度走るので、前者の方がエコですね。
割り算は四則演算の中でも1番重い処理なので。

一応どのくらい速度差があるのか調べてみた。

int n=1000000
int d=777777

(1..3).each {
    long processStart = System.nanoTime();

    def ret = "integerPartition$it"(n, d)

    long processEnd = System.nanoTime();
    int milliSec = (processEnd - processStart) / 1000000

    //println ret
    println "PROCESS_TIME($it): $milliSec[ms]"
}

// ==> PROCESS_TIME(1): 64[ms]
// ==> PROCESS_TIME(2): 64[ms]
// ==> PROCESS_TIME(3): 11319[ms]

分割数が多いとやはり、integerPartition3は劇的に遅いようだ。