Scala-2.13で直積集合を扱う。

By | 2021年3月6日 , Last update: 2022年8月7日

はじめに

GUIのあるアプリケーションやWebのページのテストパターンの作成用に使えるかもしれなさそうなので、集合の直積を考え、その元の一覧を表示するためのプログラムをScala-2.13で作成してみることにしました。

スポンサーリンク

直積集合とは?

プログラムを書く前に、直積集合について調べます…

直積集合 – Wikipedia

…つまり、そういうことです。

掛け合わせる集合の数が$n$で、それらの集合の元の数がすべて2以上であるとすると、直積集合の元の数の下限は$2^n$になります。

$n$が増えれば直積集合の元の数は一般的には指数関数的に増えますので、コンピュータではあまり直接扱いたくないタイプのデータになる予感がします。

問題の設定

ここまでの考察を踏まえ、問題を以下のように設定します。

$n$個の空集合でない集合を入力として、その直積集合の元を
集合1の元,…,集合$n$の元
のような形式で1行ずつ出力するScala-2.13で動かせる簡潔なコードを書け。
なお、入力として与えられる集合の個数及び各集合の元の個数は不定とする。

nが6くらいまでなら多重ループで何とか書けるだろう…、といったあたりのプログラムの簡略化の道を封じる問題の設定です(自画自賛)。

また、カンマ区切りで出力させたデータはそのままCSVフォーマットになりますので、元に対応する文字列を適切に設定することにより入力用のGUI(プルダウンリスト、ラジオボタン、チェックボックス等)のあるアプリケーションやWebのページのテストパターンの一覧として利用することができますので、出力結果をそっち方面の用途に利用することも想定しています。

試行錯誤

前節のように問題設定をしてみましたが、意外に簡潔に書くのは難しいです。

2個の集合の直積集合なら

scala> val a: Seq[Seq[String]] = Seq(Seq("1","2","3","4"),Seq("a","b","c"))
a: Seq[Seq[String]] = List(List(1, 2, 3, 4), List(a, b, c))

scala> (for(aa <- a.head;bb <- a.last) yield "%s,%s".format(aa,bb)).foreach(println)
1,a
1,b
1,c
2,a
2,b
2,c
3,a
3,b
3,c
4,a
4,b
4,c

のような感じのプログラムで書けそうです。


スポンサーリンク

また、3個以上の集合の直積集合ならfoldLeft関数を使って…

scala> val a: Seq[Seq[String]] = Seq(Seq("1","2","3","4"),Seq("a","b","c"),Seq("p","q","r","s","t"))

scala> (a.foldLeft(Seq(""))((v,aa) => for(vv <- v;aaa <- aa) yield "%s,%s".format(vv,aaa))).foreach(l => println(l.substring(1)))
1,a,p
1,a,q
1,a,r
1,a,s
(以下省略)

…のように結果をためておく変数を定義しつつ処理すれば良さそうに思えます。

しかし、直積集合のもとになる集合の数が少しでも増えると、直積集合の元の数は指数関数的に増えるため、上記のプログラムを使って作った直積集合の元をいったんPCのメモリ上にすべてため込むことができるかどうかが怪しくなってきます。

なお、各行の先頭には”,”がついてしまうので、出力の際にそれを1行ごとに除去しているのがどことなくイマイチ感を醸し出してはいますが、そこは気にしないことにします。

実際、上記のコードを組み込んだScalaのプログラムを作ってそれをJARファイルにしたもの(以下、単に「JARファイル」と書きます。)と3~6個の元からなる14個の集合を定義したJSONファイル(directproducttest2.json)を用意し、その直積集合の元を表示させるべく、JARファイルを実行すると…

>java -jar target\scala-2.13\directproduct-assembly-0.0.1-SNAPSHOT.jar -f directproducttest2.json > hoge.txt
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space: failed reallocation of scalar replaced objects

となり、メモリ不足であえなく終了してしまいます。(´・ω・`)

上記の実行の際に入力として使用したJSONファイル(directproducttest2.json)は以下のような感じのファイルです↓

データを見やすくするために各集合に対してキーを付与することでKVS的な定義としています。各集合を表す配列を値として設定しています。

Google先生に聞いてみた。

lazyな処理

直積集合の元をすべていったんPCのメモリ上に載せてから処理をしようとすると処理能力の上限がPCに搭載されているメモリの量に依存してしまいます。


スポンサーリンク

そこで、処理能力の上限を引き上げる方法についての方向性を探るべく、”cartesian product scala lazy”という検索語(直積は「デカルト積」ともいいます。)でGoogle先生に聞いてみると、参考文献[1]のような記事がサクッとヒットします。

上記の記事の中ほどにviewを使った遅延実行を行う関数の記述例が書かれていて、これを使えば解決できそうだ… と思い、前節のfor文の中の

for(vv <- v.view;aaa <- aa)

の部分を、

for(vv <- v;aaa <- aa)

に変えてScala-2.13のREPLで動作の確認をしてみると…

scala> (a.foldLeft(Seq(""))((v,aa) => for(vv <- v.view;aaa <- aa) yield "%s,%s".format(vv,aaa))).foreach(l => println(l.substring(1)))
^
error: type mismatch;
found : scala.collection.View[String]
required: Seq[String]

と返されてしまい、動きません。

Scalaの仕様変更への対応

実はScala-2.13から前節のような書き方ができなくなってしまったようで、scala.collection.Viewをimportした上で、foldLeft関数の第1引数のSeqをViewに変えます。

すると…

scala> import scala.collection.View
import scala.collection.View

scala> (a.foldLeft(View(""))((v,aa) => for(vv <- v.view;aaa <- aa) yield "%s,%s".format(vv,aaa))).foreach(l => println(l.substring(1)))
1,a,p
1,a,q
1,a,r
1,a,s
(以下省略)

となって、実行することができるようになります。

directproducttest2.jsonを処理するためのJARファイルも類似の修正をすると(時間はかかりますが)実行することができて、

2021/03/04 23:29 5,416,761,910 hoge.txt

というように実行結果を出力してくれます。

プログラムの実行のために使ったdynabookのストレージ(SSD)を2TBに増設しておいて良かったと思う瞬間ですね。

まとめ

Scalaの遅延評価(lazy)については知っていましたが、使いどころがわかっていなかった(そもそもviewメソッドの存在自体がノーマークでした。)ので、勉強になりました。

また、Traversableを始めとしていろいろなものがScala-2.13からdeprecatedになっています(Iterableを使うと良いようです。)ので、

「ネットからダウンロードできるコード例を参考にすればいいから、すぐ解決できるよね。」

的な考え方が通用しなくなってきているので、そのようなコード例についても最新の情報と掛け合わせて評価する習慣だけは忘れないようにしたいものです。

この記事は以上です。

References / 参考文献

  1. Lazy Cartesian product of several Seqs in Scala