カテゴリー別アーカイブ: CodeIQ

CodeIQの問題と解説

[解説]「再帰関数で逆順並べ替え」

問題文

再帰関数で逆順並べ替え
基本関数だけで逆順アルゴリズムを実現してみよう!
今回の問題は基本的な関数のみを使って、リスト項目を逆順にするアルゴリズムを考えてみます。

問題
4つの関数car, cdr, cons, nullpのみを使って、リストの項目を逆順にする関数reverse_auxとreverse2をつくってください。

例えば、reverse2は['A','B','C','D']を、逆順の['D','C','B','A']に並べ替えます。

reverse2()は1変数、reverse_aux()は2変数のリストを取ります。
最終的には、reverse2が必要なのですが、その前段階としてreverse_auxを作ってください。


reverse_aux(x, y)の性質は以下の通りです。

reverse_auxは、リストx, yを取ります。
例えば、

reverse_aux( [‘A’, ‘B’, ‘C’, ‘D’], [‘E’, ‘F’, ‘G’] )

= [‘D’, ‘C’, ‘B’, ‘A’, ‘E’, ‘F’, ‘G’]

 のように、リストxを逆順にして、リストyはそのままで連結します。 まず、reverse_auxを作ってください。 
●基本関数 使って良い関数はcar, cdr, cons, nullpのみです。
・carは先頭の項目を返す関数です。
例えば、

car([‘A’, ‘B’, ‘C’]) = ‘A’

・cdrは先頭項目を除いたリストを返す関数です。   例えば、

cdr([‘A’, ‘B’, ‘C’]) = [‘B’, ‘C’]

 ・consは一つの項目とリストを引数する関数です。consは項目xをリストyの最初に付け足したリストを返す関数です。
例えば、

cons(‘X’, [‘A’, ‘B’, ‘C’]) = [‘X’, ‘A’, ‘B’, ‘C’]

 ・nullp()は1変数の関数で、true <- nullp([]) となり、それ以外の時(アトムあるいは有限要素数のリストの場合)はfalseを返します。
reverse_auxを定義する前に、予め自分の処理系でcar, cdr, cons, nullpを定義してください。 その時は、どんな組み込み関数を使っても構いませんが、reverse_auxだけは、上記の基本関数のみを使ってください。ただし、ifなどの条件文やreturnなどはOKです。
最後に、reverse_auxを使って、reverse2を作ってください。 名前がreverse2なのは、built-in関数との競合を防ぐためです。問題なければ、reverseでも結構です。 作成したコードは、ファイル名を reverse.txt として、アップロードしてください。

その他注意事項 今回の問題は、純LISP に関する問題です。 LISPで解くと簡単にできますが、他の言語処理系だと基本関数定義の所で手間取るかもしれません。 結構大変かと思いますが、頑張ってください。 言語はPythonを希望しますが、解答の論理構造がわかるものであれば、どの言語処理系でも解答可能です。

解説

今回は純LISPに関する問題です。純LISPとはatom, eq, car, cdr, consとう5つの基本関数でプログラミング言語です。実際には、cond, quote, lambda, defineという関数も必要となりますが、必要最小限のもので、プログラミング言語を作ることができるというのは非常に面白い考えだと思います。まるで、数学の有限の公理で色々な証明を行うのに似ています。

Pythonでの解答例


#!/usr/bin/python

#
# reverse.py
#

def car(x): return x[0]

def cdr(x): return x[1:]

def cons(x, y): return [x] + y

def nullp(x): return len(x) == 0

def reverse_aux(x, y):

print x, y # Show variables
if nullp(x):
return y
else:
return reverse_aux(cdr(x), cons(car(x), y))

def reverse2(x):

return reverse_aux(x, [])

####
print reverse_aux([‘A’,’B’,’C’,’D’], [‘E’,’F’,’G’])


reverse_aux(X, Y) の解説をします。

diagram

X=[‘A’,’B’,’C’,’D’], Y=[‘E’,’F’,’G’] とすると、cdr(X)=[‘B,’C’,’D’]を次のreverse_auxのX’に引き継ぎます。更に、car(X)=’A’とY=[‘E’,’F’,’G’] をcons()で結合したものを次のreverse_auxのY’に引き継ぎます。処理がreverse_auxで再帰的に行われ、X部分の要素が逆順になります。

うまく、再帰関数で定義できたでしょうか。再帰関数を使うと、whileやfor文などを使わずに、繰返し処理が表現できますね。

[問題解説12] 男性と女性の殺人被害者数の関係は?

かなり遅くなってしまいましたが、「男性と女性の殺人被害者数の関係は?」の問題解説をします。

今回の問題は、前回の問題「ヒストグラムと散布図を描いてみよう」の発展問題です。

データとプログラムは下記のGitHubリポジトリーにおいてあります。

問題

世界各国の殺人被害者データを用いて女性被害者数から男性被害者数を予測してみましょう。

UNODC(United Nations Office on Drugs and Crime : 国連薬物犯罪事務所)から公開されている世界176ヶ国の殺人被害者の男女別のデータがあります。女性被害者数から男性被害者数を予測してみましょう。

homicide_log.zipをダウンロードしてください。解凍して、homicide_log.csvを読み込んでください。
男性・女性の殺人被害者数のデータは10を底とする対数化してあります。
元データは下記のページから入手しました。
Global Study on Homicide(殺人に関するグローバル調査)

■課題

1.回帰分析を行ってください。

Rの回帰分析関数 lm() を使用して予測式を求める計算をしてください。

2.予測式の値を答えてください。

男性被害者数をM、女性被害者数をFとすると、以下の予測式が成り立ちます。
M = a * F + b
a, b を小数点3桁まで答えてください。解答方法はプログラムの最終行に以下のように記述してください。
# a = x.xxx
# b = y.yyy
3.散布図を作成し、予測式の直線を表示してください。 X軸は女性被害者、Y軸は男性被害者。2Dの散布図を作成してください。表示範囲はX軸、Y軸ともに[-1,3]とする。 その散布図に重ねて、予測式の直線を青色で表示してください。

■解答方法 R言語のプログラムを作成し、上記1~3の課題に答えてください。プログラムファイル名は predict.txt として、アップロードしてください。 散布図は predict.pdf というファイル名でPDFとして出力するプログラムにしてください。

[問題解説12] 男性と女性の殺人被害者数の関係は? の続きを読む

設問5:PythonでXML解析をしてみよう

CodeIQの設問5について解答します。

問題

日本人の同姓同名データのファイルをXMLパーサのElementTreeを使ってパースしてみよう。

更に、姓と名の漢字の組み合わせを集計してみます。

課題

person_name.xmlファイルを読み込み、PythonのXMLパーサモジュールElementTreeを使って苗字、名前、同姓同名の数を抜き出して、標準出力で表示してください。

同姓同名のファイルを下記からダウンロードしてください。

下記zipファイルを解凍するとperson_name.xmlが入っています。

person_name.zip

※このファイルは「同姓同名辞典」の全国ランキング1位から20000位までのHTMLファイルを修正したものです。

http://www.douseidoumei.net/00/dou01.html

ElementTreeについては以下を参照。

http://d.hatena.ne.jp/hikm/20090206/1233950923

出力するもの

・文字列の両端にある不要な空白は除いてください。

・文字コードはUTF-8にしてください。(難しければ、他の文字コードでも可です)

・ファイル形式はヘッダを一行にして、コンマ区切りで以下のようにしてください。

順位,姓,名,件数

1,田中,実,2620

2,鈴木,茂,2470

課題の提出はプログラムのみです。

完成したら、テキストファイル(.txt)に変換し、ファイルアップロードにて提出してください。

 

解答

問題のプログラムのポイントは以下の3点です。

1. XMLの理解

2. xml.etree.ElementTree

3. 漢字コードの扱い

解答例

#!/usr/bin/python
# -*- coding: utf-8 -*-
#
#                               element.py
#
from xml.etree import ElementTree
def main(i_file, o_file):
o_handle = open(o_file, 'w')
tree = ElementTree.parse(i_file)
elem = tree.getroot()
for tr in list(elem):
td = list(tr)
w = ''
w += '%s,' % td[0].text.encode('utf-8').strip()
w += '%s,' % ','.join(td[1].text.encode('utf-8').strip().split(" "))
w += '%s' % td[2].text.encode('utf-8').strip()
o_handle.write('%s\n' % w)
##############################################################
main('person_name.xml', 'personal_name.txt')

設問6の解説:アッカーマンの呪い

CodeIQに投稿した問題6「アッカーマンの呪い」の解答を解説します。

問題

昔、アッカーマンという人(残念ながらミカサという妙齢の女性ではありません)がいました。

その人の手帳には以下のような式が書かれていました。

A(m, n) =
m = 0 ならば n + 1
n = 0 ならば A(m - 1, 1)
他の場合は A(m - 1, A(m, n - 1))

この関数を計算してみましょう。

A(1,3)の場合は以下のようになります。

A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5

問1A

A(2,1)を手で計算してみましょう。

(解答を提出する必要はありません)

問1B

気力のある人はA(2,2)を手で計算してみましょう。

(解答を提出する必要はありません)

問2A

再帰関数を使ってプログラムを書いてみましょう。

プログラミング言語は問いません。

A(3,4) の値はいくつになりますか。

答えと使った言語名のみを書いて提出してください。

プログラムの提出は必要ありません。

問2B

A(4,1) をプログラムで計算してみましょう。

ただし、スタックオバーフローのエラーが出る恐れがありますので、

パラメータ値の増加には十分注意してください。

ハングアップする恐れがあるので、他の重要なプログラムが走っているときは実行するの

はやめたほうが良いです。

(もし値が計算できたら、3行目に答を書いてください)

【解答方法】

テキストファイルに以下のように解答を書いてください。

完成しましたら、ファイルアップロードより提出してください。

???   # 1 行目 問2Aの答え
???   # 2 行目 プログラミング言語名
???   # 3 行目 問2Bの答え(計算出来なかったら空欄でも構いません)

【補足】

A(4,1) は何とか計算できるかもしれませんが、

A(4,2) はあまりにも値が大きいので普通の方法では計算できないでしょう。

LISP等を使ったほうがすんなり行くかもしれません。

コンピュータを壊さないように気をつけて頑張ってください。

解説

今回の問題はWilhelm Friedrich Ackermannというドイツの数学者が考案したアッカーマン関数を問題としました。残念ながら、進撃の巨人とは何の関係もありません。(ただし、進撃の巨人の舞台がドイツらしいので関係なくはありませんが…)

手計算の結果は以下の通りです。何度も再帰的に計算しているが視覚的に分かるように省略せずに全過程を書いてみました。僅かな数なのに再帰が深くなっているのが分かるでしょうか。

問2.1

A(2,1))
=A(1,A(2,0))
=A(1,A(1,1))
=A(1,A(0,A(1,0))
=A(1,A(0,A(0,1)))
=A(1,A(0,2))
=A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5

問2.2

A(2,2)
=A(1,A(2,1))
=A(1,A(1,A(2,0)))
=A(1,A(1,A(1,1)))
=A(1,A(1,A(0,A(1,0)))
=A(1,A(1,A(0,A(0,1))))
=A(1,A(1,A(0,2)))
=A(1,A(1,3))
=A(1,A(0,A(1,2)))
=A(1,A(0,A(0,A(1,1))))
=A(1,A(0,A(0,A(0,A(1,0)))))
=A(1,A(0,A(0,A(0,A(0,1)))))
=A(1,A(0,A(0,A(0,2))))
=A(1,A(0,A(0,3)))
=A(1,A(0,4))
=A(1,5)
=A(0,A(1,4))
=A(0,A(0,A(1,3)))
=A(0,A(0,A(0,A(1,2))))
=A(0,A(0,A(0,A(0,A(1,1)))))
=A(0,A(0,A(0,A(0,A(0,A(1,0))))))
=A(0,A(0,A(0,A(0,A(0,A(0,1))))))
=A(0,A(0,A(0,A(0,A(0,2)))))
=A(0,A(0,A(0,A(0,3))))
=A(0,A(0,A(0,4)))
=A(0,A(0,5))
=A(0,6)
=7

アッカーマン関数は、自分自身を値として取る再帰関数ですが、簡単な定義にも関わらず、最初の部分でさえ爆発的に大きな値が現れてしまいます。

f:id:infoarchitect:20130625120719p:image:w640

Wikipedia:アッカーマン関数より転載

私が大学の夏期特別講座でこのアッカーマン関数を知りました。当時は、コンピュータは一般的には存在せず、共有の大型コンピュータをかろうじて使うことが出来ましたが、一行書くのに一回リターンキーを押してしまうと二、三分待たなければ、レスポンスが帰ってこないと言う有様でした。年がバレてしまいますがwww。

ですから、自分でこの関数をコンピュータでプログラミングするなんてできませんから、手で計算したのです。ところが、小さな値で計算を始めたにも関わらず、なかなか答えが収束せず、大変な思いをしました。その時、友人が書きすぎて手が痛くなったので、「これはアッカーマンの呪いだ!」と叫んでいました。そこで、これを今回の問題のタイトルにしたというわけです。

Pythonでのプログラミングの例

def ack(m, n):
if m == 0:
return n + 1
if n == 0:
return ack(m - 1, 1)
else:
return ack(m - 1, ack(m, n - 1))
###
print ack(3,4)

挑戦者のtakana32さんがいろいろな言語で書いたアッカーマン関数のプログラムを公開してくれたので、参考にしてください。

https://github.com/Rosetta-Ack

問2A

A(3,4)の答えは125。

問2B

A(4,1)の答えは65533となります。

既にA(4,1)でコンピュータがエラーを吐き出し始めるかと思います。私のUbuntuの場合、パラメータをいじったのですが、A(4,1)はスタックオーバーフローで計算できませんでした。

A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってしまい、通常のやり方では計算不可能です。しかし、PythonやRubyではintegerに収まらない数も扱えるため、既に計算した値を保持することで、A(4,2)等も計算することができます。

スタックオーバーフローの対処方法についてはいくつかありますので、参考にしてみてください。

スタックオーバーフローの対処方法

とにかく、こんな簡単な式でこんな爆発的に大きな数が作れるなんて不思議ですね。しかも、コンピュータの普及していない時代にこんな関数を考えだすなんて数学者ってすごいなと思います。

CodeIQで問題作成してますので、他の問題も挑戦してみてください。

https://codeiq.jp/ace/kawagashira_nobuyuki/

07解説:SQLで行列積の計算???

CodeIQの設問「SQLで行列積の計算???」の解説をします。

問題文

下記のような4×3の疎行列Aがあります。多くの要素が0となっている行列を疎行列(sparse matrix)といいます。

0  1 -3
2  0  0
0  0  0
-1  0  4

この行列Aは列と行の情報で取り出すと、以下のように表現できます。

row_id col_id val_nr
1      2       1
1      3      -3
2      1       2
4      1      -1
4      3       4

行列を疎行列の表として表すことができます。

問1 基本問題

行列AとBが与えれたとすると、AとBの行列の積はどのようにSQLクエリーで表現できるかを考え、行列積ABを表すSQLクエリーをselect文で答えてください。

行列A, Bは以下のようなフィールドの行として表現できます。

(row_id, col_id, val_nr)

答えの行列積の表は (row_id, col_id, val_nr)という形式となります。

AとBの行列の積はAとBの表の結合として表せます。ただし、JOIN文は使いません。

データの表示順は(row_id, col_id)の昇順にしてください。

行列積Cの行列の各要素(i,k)をC(i,k)と表すと、下記の式が成り立ちますので、参考にしてください。

C(i,k) = Σ (j=1 to end) {  A(i,j) * B(j,k) }

計算結果の数値は必要ありません。データは確認用に使ってください。

添付ファイルはこちらからダウンロードしてください。

multiply.txtはpostgreSQLのスクリプトになっていますので、下記のように実行してください。

$ psql yourdb < multiply.txt

前半部分は表作成とデータのロードとなっています。

mysqlやOracle等他のデータベースをお使いの場合は適宜修正して、データを読み込んでください。

問2 発展問題

表Aと表Bにはimg_nrという値が含まれており、下記のようなフィールド形式になっています。

(row_id, col_id, val_nr, img_nr)

val_nrを複素数の実数部、img_nrを複素数の虚数部とみなして、複素数行列A、Bの行列積を計算するSQLクエリーを作ってください。行列積の結果もA, Bと同じフィールド形式になります。

問1と同じく、multiply.txt内に書き込む部分がありますので、書き込んだらmultiply.txtを送ってください。

複素数x, yをx = a + bi, y = c + di (a, b, c, d ∈R, iは虚数)とすると以下の式が成り立つことに注意。

x y = (ac - bd) + (bc + ad)i

練習問題

問題が難しいようでしたら、下記の練習問題がありますので、その練習問題を解いてからこの問題に再挑戦してみてください。

エレガントにベクトル内積計算

解説

問1 基本問題

解答は以下の通りです。

select A.row_id, B.col_id, sum(A.val_nr * B.val_nr) as val_nr
from A, B
where A.col_id = B.row_id
group by A.row_id, B.col_id
order by A.row_id, B.col_id;

表AとBの結合として表現します。制約条件を与えないと、結果がAの全行とBの全行の組み合わせとなってしまうので、制約条件を与えます。結果となる行列の要素C(i,k)について考えると以下の式が成り立ちます。

C(i,k) = Σ (j=1 to end) {  A(i,j) * B(j,k) }
= A(i,1)*B(1,k) + A(i,2)*B(2,k) + ... + A(i,m)*B(m,k)

j は 1,2,…,m の値を取りますが、C(i,k)はAの要素A(i,j)とBの要素B(j,k)を取り出して、かけたものの和になっています。

各項A(i,j)*B(j,k)ではjが共通しており、Aの列jとBの行jが共通しているので、SQLで書くと以下のような条件となります。

where A.col_id = B.row_id

C(i,k)の要素はA(i,j)*B(j,k)の和になっているので、集計関数sum()で和を計算します。

制約条件だけではなく、Cの(i,k)要素毎に結果を求める必要があるので、下記のグループ句が必要となります。

group by A.row_id, B.col_id

最後に計算結果を(i,k)順に表示するため、下記のオーダー句が書き加えます。

order by A.row_id, B.col_id

どうでしょうか。面倒くさそうな計算がSQLの結合を使うと意外と簡単に書けますね。

SQLの出力は以下のようになっていれば、うまく行っています。

row_id | col_id | val_nr
--------+--------+--------
1 |      1 |      3
1 |      2 |     -6
1 |      4 |      4
2 |      2 |      2
2 |      3 |      4
2 |      4 |     -6
4 |      2 |      7
4 |      3 |     -2
4 |      4 |     -1

問2 発展問題

解答は以下の通りです。

select A.row_id, B.col_id,
sum(A.val_nr * B.val_nr - A.img_nr * B.img_nr) as val_nr,
sum(A.val_nr * B.img_nr + A.img_nr * B.val_nr) as img_nr
from A, B
where A.col_id = B.row_id
group by A.row_id, B.col_id
order by A.row_id, B.col_id;

Aの要素の実数部、虚数部をそれぞれReA, ImAとして、Bの要素の実数部、虚数部をReB, ImBとすると次の式が成り立ちます。

(ReA + ImA i) * (ReB + ImB i) = (ReA * ReB – ImA * ImB) + (ReA * ImB + ImA * ReB) i

実数部の間にマイナスがあるので、注意。

従って、行列積要素の実数部と虚数部をSQLで書くと下記の通りになります。

sum(A.val_nr * B.val_nr - A.img_nr * B.img_nr)
sum(A.val_nr * B.img_nr + A.img_nr * B.val_nr)

この問題は、複素数の虚数の扱いを知っていれば、応用なので、簡単ですね。

SQLの出力は以下のようになっていれば、うまく行っています。

row_id | col_id | val_nr | img_nr
--------+--------+--------+--------
1 |      1 |      3 |      3
1 |      2 |     -9 |      7
1 |      4 |      2 |     10
2 |      2 |      2 |      2
2 |      3 |      4 |     -2
2 |      4 |     -6 |      0
4 |      2 |      9 |     -5
4 |      3 |      2 |      9
4 |      4 |      5 |    -26

まとめ

集計関数sum()を使うことを思いつかないとなかなか解答に辿り着くのが難しかったようです。

一旦、気づいてしまうとエレガントに解けて、面白いかと思います。

もう少し簡単にした問題も作成しましたので、予備練習としてこちらの方も解いてみてください。

エレガントにベクトル内積計算

「アッカーマンの呪い」のスタックオーバーフローの対処方法

数多くの方々の「アッカーマンの呪い」への挑戦ありがとうございます。

プログラムは再帰関数で解くのが答えとなっていますが、A(4,1), A(4,2)の計算あたりで、計算爆発が起こり、スタックオーバーフローのエラーが発生し、計算終了となってしまいます。

挑戦者からの解答も参考にしながら、対処法をいくつか、書いてみたいと思います。

A(4,1)は65533となります。

A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってします。プログラミング言語が19729桁まで表現できるかというのも、チェックする必要があります。

1. スタックオーバーフローの対処

アッカーマン関数の計算は再帰が深くなるので、スタックサイズをできるだけ増やす必要があります。

Rubyでは、2.0で環境変数RUBY_THREAD_VM_STACK_SIZEが導入されたので、4MB等に設定してみてはどうでしょうか。

Pythonでは下記のようにsys.setrecursionlimit()でスタックサイズを増やせます。

import sys
sys.setrecursionlimit(10**9)

私の環境では、これでもA(4,1)は計算できませんでした。

2. 計算結果を保持する方法

m✕nの格納場所を確保しておき、一度計算したA(m,n)の結果をメモリに保存しておくと、スタックも深くならず、計算速度も向上します。

3. m=3以下のものを公式で置き換える

この方法は挑戦者のだいじゅさんから頂いた解答です。下記のようにアッカーマン関数の公式があるので、m=3以下の場合について公式で置き換えます。

If m=0 or m=1 then A(m,n) = n + 1 + m

If m=2 then A(2,n) = 2 * n + 3

If m=3 then A(3,n) = 2^(n+3) – 3

import sys
sys.setrecursionlimit(5000)
def A(m, n):
if m < 2:
return n + 1 + m
elif m == 2:
return 2*n + 3
elif m == 3:
return (2 ** (n+3)) - 3
elif n == 0:
return A(m-1, 1)
else:
return A(m-1, A(m, n-1))
def do(m, n):
try:
return A(m, n)
except RuntimeError:
raise RuntimeError, "maximum recursion depth exceeded"
except:
print "Error"
#######################
print A(4, 2)

このプログラムですと、驚くほど早くA(4,2)が求まります。

A(4,3)については、私の環境では28GBのバーチャルメモリを食い、画面は固まったまま、三日後にエラーがでて終了しました。

A(4,2)は 2^65536 – 3 になり、19729桁の十進数です。そもそも全宇宙の水素原子の数が10^80個、つまり81桁だから、既に全宇宙の水素原子数を超えている。

A(4,3)=2^(2^65536) – 3 だから、途方もない数になります。なんか、くらくらしてきた。

08解説:SQLでエレガントにベクトル内積計算

CodeIQの設問「SQLでエレガントにベクトル内積計算」の解説を行います。

問題文

問1

下記のような要素4の縦ベクトルが2つあります。

U    V
[1   [1
3    2
5    3
7]   4]

例えば、ベクトルUはリレーショナルデータベースの表として以下のように表現されます。

Uも同様に表現されます。

row_id val_nr
1      1
2      3
3      5
4      7

2つのベクトルUとVの内積はどのようにSQLクエリーで表現できるかを考え、内積U・Vを表すSQLクエリーをselect文で答えてください。

UとVの内積はUとVの表の結合として表せます。ただし、JOIN文は使いません。

内積の計算は以下の図式になります。

U.row_id=V.row_id=1の要素同士をかけて、次のU.row_id=V.row_id=2の要素同士をかけたものを順次足していくと行くという操作になります。

U.row_id
[1 3 5 7] [1  V.row_id
2
3
4]
= 1×1 + 3×2 + 5×3 + 7×4

SQLでの表の結合は表内のすべての要素の組み合わせを試して、結果を出力するので、何らかの条件統制が必要となります。

要素mの表と要素nの表の結合を行うとm×n個の要素が結果として出てしまいます。

答えのSQLは以下のような形式になります。

select sum( ... )
from U, V
where ... = ... ;

計算結果は50となります。

答えのSQLを書き加えたvector.txtを送ってください。

問2 ステップ問題

以下のような行列Wがあります。

W =
1  2  3  4]
[5  6  7  8]
[9 10 11 12

この行列は表で以下のように表現できます。

row_id col_id val_nr
1      1      1
1      2      2
1      3      3
1      4      4
2      1      5
2      2      6
2      3      7
2      4      8
3      1      9
3      2      10
3      3      11
3      4      12

この行列Wと前問のVの積を計算してください。その計算を実現するSQLを考えてください。

W               V
1  2  3  4]  [1
[5  6  7  8]   2
[9 10 11 12  3
4]

答えは各row_id毎の結果を求めてください。

計算結果は以下のような表になります。

row_id sum
1      30
2      70
3      110

Wの行列要素は(W.row_id, W.col_id)のように行と列に分かれてしまっているので、

何らかの条件統制が必要となります。

答えのrow_id=1の場合について考えてみましょう。

W.row_id=1という条件で絞れば、以下のようにベクトルの内積となります。

W.col_id=
1 2 3 4
W.row_id=1 [1 2 3 4] [1  V.row_id=1
2           2
3           3
4]          4

row_id=1の計算結果はW.col_idとV.row_idが一致する各W, Vの要素のかけたものの和となっています。計算結果のrow_idとW.row_idは同じものです。

各row_idについて計算結果が欲しいので、W.row_idでグルーピングすれば、各row_idについて計算することができます。

解答のSQL文は以下の形式になります。

select W.row_id, sum( ... )
from W, V
where ... = ...
group by ... ;

解答方法

計算結果の数値は必要ありません。データは確認用に使ってください。

添付ファイルはこちらからダウンロードしてください。

vector.txtはpostgreSQLのスクリプトになっていますので、下記のように実行してください。

$ psql yourdb < vector.txt

前半部分は表作成とデータのロードとなっています。

MySQLやOracle等他のデータベースをお使いの場合は適宜修正して、データを読み込んでください。

発展問題

この問題ができた方は、次のレベルの問題がありますので、挑戦してみてください。

「SQLで行列積の計算???」

https://codeiq.jp/ace/kawagashira_nobuyuki/q379

解説

問1

答えは以下の通り。

select sum(U.val_nr * V.val_nr)
from U, V
where U.row_id = V.row_id;

Uの各要素をU(i)(iはrow_id)、Vの各要素をV(i)(iはrow_id)とすると、UとVのベクトル積は以下の式になる。要素数はnとする。

U・V = U(1) V(1) + U(2) V(2) + U(3) V(3) + … + U(n) V(n)

つまり、Uの各要素とVの各要素の和の形になっているので、求めるものはsum(U.val_nr * V.val_nr)となる。

ここで、ベクトル積の各項の添字iはrow_idで、UとVのrow_idが常に同じだから、U.row_id = V.row_idという制約条件をつける必要があります。

もし、ここで制約条件を付けないと、UとVの全要素の組み合わせが集計されてしまい、以下のような計算結果となってしまいます。

U(1) V(1) + U(1) V(2) + U(1) V(3) + … + U(1) V(n) +

U(2) V(1) + U(2) V(2) + U(2) V(3) + … + U(2) V(n) +

U(3) V(1) + U(3) V(2) + U(3) V(3) + … + U(3) V(n) +

U(n) V(1) + U(n) V(2) + U(n) V(3) + … + U(n) V(n)

問2 ステップ問題

答えは以下の通り。

select W.row_id, sum(W.val_nr * V.val_nr)
from W, V
where W.col_id = V.row_id
group by W.row_id;

計算結果の表をZとすると、計算結果の要素はZ(1), Z(2), Z(3),…,Z(m)となります。

mは計算結果の要素数で、W.row_idの列数です。

問題文にも書きましたが、計算結果Zの要素 row_id=k は、W(row_id=k)とVのベクトル積になるので、Z(row_id=k)についてSQL文を作成します。

Z(row_id=k) = W(k,1) V(1) + W(k,2) V(2) + W(k,3) V(3) + … + W(k,n) V(n)

計算の値はベクトル積なので、問1と同様に、sum(W.val_nr * V.val_n)となります。計算結果の要素番号、つまりrow_idを表示する必要があるので、W.row_idを要素番号としてselectの項目に付け足します。

Z(row_id=k)の和の各項はWのcol_idとVのrow_idが同じとなっているので、W.col_id = V.row_idという制約条件を付け加えます。

更に、row_id毎に掲載結果を集計する必要があるので、group by W.row_idというグループ句を付け加えます。

答えのSQLはシンプルですが、論理は結構複雑ですね。正しいSQL文が出来ましたでしょうか。

この問題ができた方は、行列積の計算にも挑戦してみてください。

SQLで行列積の計算???