O(n log(n))

sortがO(n log(n))だということを忘れて、このようなフィルタにしたら猛烈に時間がかかって終わらない。

find dir -type f | xargs sed -e 's/<[^>]*>//g;' | tr -d '\r' | kakasi -w -c | \
 awk '{for(i=1;i<=NR;i++){print $i;}}' | sort -u

以下のようにすると、まだマシになる。マージ(sort -m -u)はO(n)なので、全体ではO(m*n log(n))になり、このnは小さくなってm*nが以前のnになるから、計算量を減らせるためだ。一時ファイルはきれいじゃない、なんて言ってるヒマはない。

FILES="" for i in $(find dir -type f); do FILE=$(mktemp /tmp/wakachiXXXXXX); \
 FILES="$FILES $FILE"; sed -e 's/<[^>]*>//g;' $i | tr -d '\r' | kakasi -w -c | \
 awk '{for(i=1;i<=NR;i++){print $i;}}' | sort -u > $FILE ; done ; sort -m -u $FILES ; \
 [ -z "$FILES" ] || rm $FILES

やってることは、単なる単語の羅列です。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です