3

$returnintersection が true の場合、任意の 2 つの入力リストに対して交差のようなリストを返す次の perl コードを書きました。それ以外の場合は、いずれか 1 つの共通要素を返し、何もない場合は 0 を返します。

交差点のように、私はワイルドカードの一致を参照しています.1つのリストからの123 *は、他のリストからの12345と一致します。

入力と対応する出力の例を次に示します。

getintersection (
 ['123*', '999', 'V890', '871'],
 ['10001', '8789', '999', '1234', 'V89*'], 
 1 
)
will return
('999', 'V890', '1234')

パフォーマンスが向上する方法で記述できるかどうか知りたいですか？私はアルゴリズムがそこにある最高のものではないと確信しています。その複雑さを軽減するのに役立つものは何でも高く評価されます! 非常に一般的に呼ばれるルーチンであるため、そのパフォーマンスは非常に重要です。(パフォーマンス => 速度、いずれかのリストに 1 ～ 3000 の要素を含めることができると仮定)

コード -

    sub getintersection {
        my ($l1, $l2, $returnintersection) = @_;
        if (!$l1 || !$l2) {
                return $returnintersection ? undef : 0;
        }
        my ($small, $large);
        if (scalar @$l1 > scalar @$l2 ) {
                ($small, $large) = ($l2, $l1);
        }
        else {
                ($small, $large) = ($l1, $l2);
        }

        my (%lhash, %l_starred, %s_starred, @intersection);
        foreach my $l (@$large) {
                $lhash{$l} = 1;
                if ($l =~ m/^(.+)\*$/) {
                        $l_starred{$1} = 1;
                }
        }
        foreach my $s (@$small) {
                if ($lhash{$s}) {
                        return $s if (!$returnintersection);
                        push @intersection, $s;
                }
                else {
                        foreach my $k (keys %l_starred) {
                                if ($s =~ /^$k/) {
                                        return $s if (!$returnintersection);
                                        push @intersection, $s;
                                }
                        }
                }
                if ($s =~ m/^(.+)\*$/) {
                        $s_starred{$s} = 1;
                }
        }
        foreach my $s (keys %s_starred) {
                foreach my $l (@$large) {
                        if ($l =~ /^$s/) {
                                return $l if (!$returnintersection);
                                push @intersection, $l;
                        }
                }
        }

        return $returnintersection ? @intersection : scalar @intersection;
}
4

2 に答える 2

3

私が読んだように、あなたの実装は、小さなセットと大きなセットを区別することから利益を得ていません。それでも、実際に重要なのは、どのセットにスター付き要素が最も多く含まれているかということです。これらの要素は、線形の複雑さでは処理できないためです。

まず、不一致の可能な組み合わせを見てみましょう。

Set 1       | Set 2
Normal      | None
Starred     | None
None        | Normal
None        | Starred

次に、一致の可能な組み合わせ:

Normal      | Normal
Starred     | Normal
Normal      | Starred
Starred     | Starred

複雑さは線形であるため、ハッシュルックアップを使用して一致できるものはすべて最初に実行する必要があることは明らかです。したがって、アルゴリズムの最初の部分は次のようにする必要があります。

for all elements in set1
    if element is normal, put in %normal_1_lookup
    otherwise put in @star_1
for all elements in set2
    if element is normal, put in %normal_2_lookup
    otherwise put in @star_2

for intersection of %normal_1_lookup, %normal_2_lookup
    put element in result
    delete element from %normal_1_lookup and %normal_2_lookup

交点を計算する最後のループを%normal_2_lookup、

これですべてのライトリフティングが邪魔にならず、既に一致した要素が削除され、どの要素が星でどの要素がそうでないかを知るために何も繰り返す必要はありません.

for all elements is @star_1
    for all elements in %normal_2_lookup
        if star_1 element matches normal_2 element
            put normal_2 element in result set
            delete normal_2 element from %normal_2_lookup

次に、2 つのセットを切り替えて繰り返します。

@star_1最後に、に対してのマッチングを追加できますが@star_2、それが意図されているかどうかはわかりません。

これにより、複雑さが o(n_1 * n_2) のように見えるのではなく、o(s_1 * n_2 + s_2 * n_1) (両方のセットからスター要素を一致させたい場合は s_1 * s_2 を追加) に削減されます。

さらに最適化する場合は、いずれかのセットのすべての要素に対してTriesを使用してマッチングを行うことができます。

于 2013-06-30T19:45:16.503 に答える