私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ユニークな項目を数えよう」（CodeIQ）を参照してください。
あなたはデータベースの再設計を任されており、インデックス設計のため、まずデータのカーディナリティ（cardinality）を調査するよう依頼されました。
カーディナリティとは列内に含まれるデータの一意性を示すもので、性別のように反復データが多い場合は「低く」、一方名前のように一意のデータが多い場合は「高く」なります。
今回はまず列ごとにどれだけユニークな（一意な）項目の数があるか、元データであるCSVファイルから計測することにしました。
本設問で求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、CSV形式のASCII文字のみで構成された行列データが送られる
CSVの先頭行はタイトル行、２行目以降を集計対象であるデータ行とする
CSVは1行あたり、最大80文字、最大４項目とする
CSVは最大で10,000行とする
CSVの項目は、文字列または数値とする
項目が一意かどうかの判定は、一致しているかのみで決めること（正規化は不要）
CSVの項目の中には制御文字や、エスケープを要する文字は含まれないものとする
CSVはカンマ(,)区切りであり、項目を囲む括り文字はないものとする
各列のユニークな項目の数を、CSV形式にて一行で標準出力に返すこと
以下、入力と出力例です。
入力 出力 uri_path
app
search/main
search/main
main/category
categories
4 first_name,pyint
Corey,4309
Michael,801
Stacey,6172
Rebecca,4309
Corey,4309
Michael,496
Rebecca,3574
Corey,3574
Corey,4309
Michael,6172
1
データベースのインデックス設計において、カーディナリティはパフォーマンスやサイズを決める重要な指標です。
一般に低すぎるカーディナリティの列に対して、インデックスを作成するのは得策ではないため、複数列を対象とした複合インデックスが検討されたりします。
それでは、是非挑戦してみてくださいね。
なお、本設問で用いるデータはすべて架空のものであることをご了承ください。
【問題】
標準入力から、CSV形式の行列データが送られます。
この入力から、列ごとにユニークな項目の数をCSV形式で標準出力に返してください。
Rubyで解答しています。
#!/usr/bin/ruby
def count(inputs)
ret = []
for i in inputs
ret << i.size
end
return ret
end
# main
i = 0
inputs = nil
while line = gets
line.strip!
next if line.empty?
arr = line.split(',')
if i == 0 then
inputs = Array.new(arr.size)
for j in 0...arr.size
inputs[j] = {}
end
else
for j in 0...arr.size
inputs[j][arr[j]] = true
end
end
i += 1
end
puts count(inputs).join(',')
簡単です。
入力値をコンマで分割し、要素番号ごとにinputの配列に{"文字列" => true}という形式の連想配列として保持します。
count()でinputsの各要素の要素数を配列で取得し、フォーマットして印字します。
inputsの各要素の集合の要素数を配列で返します。
setの様な集合を扱えるデータ構造があれば簡単に実装できます。
そして、多分それが最速だと思うのですが、もっと速い方法があるのでしょうか？