2

問題：

監視サービスを使用してディレクトリの入力を監視しているため、2 つの (半) 一致する入力ファイルがあればイベントを発生させることができます。私が抱えている問題は次のとおりです。2 つのリストがあり、それぞれに異なる文字列が含まれている場合、リストが発生したときに一致するルートを見つけるにはどうすればよいでしょうか。

ファイル名の構造は次のようになります。

<companyname>-<ordernum><postfix>.csv

たとえば、次のようになります。

list1 could contain: 
    mycomp-1234.csv
    mycomp-4567.csv
    newcomp-7891.csv
    oldcomp-3376.csv

list2 could contain:
    mycomp-2232_items.csv
    newcomp-13123_items.csv
    oldcomp-87078777_items.csv
    mycomp-1234_items.csv

リスト間で一致が発生したらすぐにイベントを見つけて発生させたいと思います。サフィックスを除いた任意のファイル名が一致します。つまり、mycomp-1234 は両方のリストの一致を返します。

私が探しているもの

これを行うための最も効率的な方法を探しています。値を比較する各リストを反復できることはわかっていますが、これを行うためのより効率的な方法があると確信しています。

コードは必要ありません。自分で学習したいので、正しい方向へのプッシュは完璧です。指でコードを書こうとするなら、できるだけ多くの言語に役立つように疑似コードを書いてください。

いいえ、これは宿題ではありません。非常に好奇心旺盛な方のために、これは csv から X12 EDI ファイルへの EDI 変換を実行することです。

4

3 に答える 3

-1

オンラインの方法: 現在のすべてのファイル名を含むバイナリ検索ツリーを維持します。ファイル名の関連ビットをキーとして使用します。たとえば、newcomp-7891.csvまたはのキーnewcomp-7891_itemsは ですnewcomp-7891。監視サービスがディレクトリ イベントを報告するたびに、使用されていない名前を削除したり、新しい名前をツリーに追加したりできます。キーがすでにツリーにある場合は、目的のイベントを発生させます。

ファイル名が削除されたときにハッシュ実装がキーの削除をサポートしている場合は、ハッシュテーブルも同様に使用できます。

この質問は、「これを行うための最も効率的な方法」を求めています。この方法は、ディレクトリ イベントが発生するたびにリストを最初から並べ替えるよりもはるかに効率的であることに注意してください。k回の追加と削除を伴うイベントでは、データセットにn個のエントリがある場合、O(k・lg n)時間を使用するため、平均ツリーサイズがnでm回の追加/削除が発生する期間では、uディレクトリイベントで、それは O(m·lg n) の仕事をします。対照的に、他の回答で提案されているソートごとの方法は、O(u・n・lg n) の作業を行いますが、これははるかに多くのことです。

于 2013-05-07T15:58:33.920 に答える