0

バックグラウンド

これは最適化問題です。Oracle Forms XMLファイルには、次のような要素があります。

<Trigger TriggerName="name" TriggerText="SELECT * FROM DUAL" ... />

ここで、TriggerTextは任意のSQLコードです。各SQLステートメントは、次のような一意の名前のファイルに抽出されています。

sql/module=DIAL_ACCESS+trigger=KEY-LISTVAL+filename=d_access.fmb.sql     
sql/module=REP_PAT_SEEN+trigger=KEY-LISTVAL+filename=rep_pat_seen.fmb.sql

私は、ブルートフォースアプローチを使用して正確な重複のリストを生成するスクリプトを作成しました。

問題

互いに比較する37,497個のファイルがあります。1つのファイルを他のすべてのファイルと比較するのに8分かかります。論理的には、A = BおよびA = Cの場合、。かどうかを確認する必要はありませんB = C。したがって、問題は次のとおりです。冗長な比較をどのように排除しますか？

スクリプトは約208日で完了します。

スクリプトソースコード

比較スクリプトは次のとおりです。

#!/bin/bash

echo Loading directory ...

for i in $(find sql/ -type f -name \*.sql); do
        echo Comparing $i ...

        for j in $(find sql/ -type f -name \*.sql); do
                if [ "$i" = "$j" ]; then
                        continue;
                fi

                # Case insensitive compare, ignore spaces
                diff -IEbwBaq $i $j > /dev/null

                # 0 = no difference (i.e., duplicate code)
                if [ $? = 0 ]; then
                        echo $i :: $j >> clones.txt
                fi
        done
done

質問

複製されたコードのチェックが数桁速くなるように、スクリプトをどのように最適化しますか？

アイデア＃1

一致するファイルを別のディレクトリに移動して、2回検査する必要がないようにします。

システムの制約

SSDでクアッドコアCPUを使用する。可能であれば、クラウドサービスの使用を避けようとします。このシステムは、CygwinがインストールされたWindowsベースのマシンです。他の言語のアルゴリズムやソリューションを歓迎します。

ありがとうございました！

4

3 に答える 3

1

あなたの解決策とsputnickの解決策はどちらもO（n ^ 2）の時間がかかります。これは、ファイルを並べ替えてリストマージを使用することにより、O（nlog n）時間で実行できます。ファイル自体ではなく、ファイルのMD5（またはその他の暗号的に強力なハッシュ関数）を比較することで、さらに高速化できます。

あなたがsqlディレクトリにいると仮定します：

md5sum * | sort > ../md5sums
perl -lane 'print if $F[0] eq $lastMd5; $last = $_; $lastMd5 = $F[0]' < ../md5sums

上記のコードを使用すると、正確なバイト単位の重複のみが報告されます。この比較の目的で、2つの同一でないファイルを同等と見なす場合（たとえば、大文字と小文字を区別しない場合）、最初に各ファイルの正規化されたコピーを作成します（たとえば、すべての文字を小文字に変換しますtr A-Z a-z < infile > outfile） 。

于 2012-10-23T05:17:45.110 に答える
0

これを行う最良の方法は、SHA-1のように各ファイルをハッシュしてから、セットを使用することです。bashがこれを実行できるかどうかはわかりませんが、pythonは実行できます。ただし、最高のパフォーマンスが必要な場合は、C++が最適です。

于 2012-10-23T05:22:33.067 に答える
-1

ファイルの比較を最適化するには：

#!/bin/bash

for i; do
    for j; do
        [[ "$i" != "$j" ]] &&
            if diff -IEbwBaq "$i" "$j" > /dev/null; then
                echo "$i & $j are the same"
            else
                echo "$i & $j are different"
            fi
    done
done

利用方法

./script /dir/*
于 2012-10-23T01:47:44.700 に答える