perl - Heap::Simple の二次順序

Question

Perl で Heap::Simple インターフェースに二次順序付けを定義するにはどうすればよいですか?

Answer 1

ドキュメントには、コンストラクターがコード参照を使用して順序を定義すると記載されているため、好きな並べ替え方法を指定できます。

my $heap = Heap::Simple->new(order => \&sort_method);

2 つのキーを比較する必要があるたびに、指定されたコード参照が次のように呼び出されます。

$key1 が $key2 より小さい場合は true 値を返し、それ以外の場合は false 値を返します。$code_reference は全体の順序関係を意味する必要があるため、推移的である必要があります。

「二次順序付け」とは、最初の比較で値が等しいことが示されている場合、2番目の比較が使用されることを意味していると思います。最初の比較が「method1」メソッドで見つかった値であり、2 番目の比較が「method2」の値であるとします。したがって、method1 で値が異なる場合はその結果を返し、それ以外の場合は method2 にフォールバックします。

sub sort_method
{
    my ($val1, $val2) = @_;

    my $result = ($val1->method1 <=> $val2->method1)
                          ||
                 ($val1->method2 <=> $val2->method2);

    return 1 if $result == -1;
}

method1 と method2 が数値ではなく文字列を返す場合は、 のcmp代わりに単に演算子を使用し<=>ます。演算子が正しい値を返す限り、好きなものを使用できます。ほとんどの並べ替え関数は、値 -1、0、1 を使用して、値 1 が値 2 より小さいか、等しいか、または大きいかを示しますが、このモジュールは 1 を使用して val1 < val2 を意味するため、-1、0、1 を収集した後に結果が -1 の場合 (値 1 が値 2 より小さい場合)、1 が返されます。

Answer 2

まず、ヒープに入れたいオブジェクトを 2 つ取り、最初のオブジェクトが 2 番目のオブジェクトより小さい場合は true 値を返し、それ以外の場合は false 値を返す関数を作成します。

それをコードリファレンスとして Heap::Simple に提供します。

Heap::Simple ドキュメントの例は次のとおりです。

use Heap::Simple;

sub more { return $_[0] > $_[1] }

my $heap = Heap::Simple->new(order => \&more);
$heap->insert(8, 3, 14, -1, 3);
print $heap->extract_top, " " for 1..$heap->count;
print "\n";
# Will print: 14 8 3 3 -1