当前位置：文江博客话题详情

堆中的次要顺序::简单

发布于 2024-09-08 03:00:54 字数 41 浏览 6 评论 0原文

如何在 Perl 中定义 Heap::Simple 接口的二级排序？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

治碍 2024-09-15 03:00:54

文档指出构造函数采用代码引用来定义
顺序，因此您可以指定您喜欢的任何排序方法：

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

每次需要比较两个键时，都会调用给定的代码引用，如下所示：
$less = $code_reference->($key1, $key2);
如果 $key1 小于 $key2，则应返回 true 值，如果 $key1 小于 $key2，则应返回 false
否则价值。 $code_reference 应该暗示全序关系，所以它
需要是传递性的。

通过“二次排序”，我假设您的意思是使用第二次比较，如果
第一个显示值相等。假设第一个比较是
通过“method1”方法找到的值，第二个比较是
来自“方法2”的值。因此，如果通过 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 指示 value1 是否小于、等于或
大于 value2，但此模块喜欢 1 表示 val1 < val2，所以之后
收集 -1, 0, 1 结果，如果结果为 -1，则返回 1（其中
值 1 小于值 2)。

The documentation states that the constructor takes a code reference to define
the order, so you can specify any sort method you like:

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

Every time two keys need to be compared, the given code reference will be called like:
$less = $code_reference->($key1, $key2);
This should return a true value if $key1 is smaller than $key2 and a false
value otherwise. $code_reference should imply a total order relation, so it
needs to be transitive.

By "secondary ordering" I assume you mean that a second comparison is used if
the first one shows the values to be equal. Let's say the first comparison is
of values found via the "method1" method, and the second comparison is of
values from "method2". So, if by method1 the values are different, return
that result, and otherwise fall back to method2:

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

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

    return 1 if $result == -1;
}

If method1 and method2 return strings instead of numeric values, simply use
the cmp operator instead of <=>. You can use anything you like, as long
as the operator returns the right values. Most sort functions like using the
values -1, 0 and 1 to indicate whether value1 is less than, equal to, or
greater than value2, but this module likes 1 to mean val1 < val2, so after
gathering the -1, 0, 1 result, one then returns 1 if the result is -1 (where
value1 is less than value2).

回复收藏 0 原文

魔 2024-09-15 03:00:54

首先，编写一个函数，它接受两个要放入堆中的对象，如果第一个对象小于第二个对象，则返回 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

First of all, you write a function that takes two of the objects you want to put in the heap, and returns a true value if the first one is smaller than the second, and false otherwise.

Then supply that as a coderef to Heap::Simple.

The example from the Heap::Simple docs is as follows:

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

回复收藏 0 原文

~没有更多了~