Почему Вы не должны возвращать массив касательно?

Итак, вам нужно заполнить заказ пакетами так, чтобы общая цена была максимальной? Это известно как проблема рюкзака . В этой статье Википедии вы найдете несколько решений, написанных на Python.

Точнее, вам нужно решение для неограниченной задачи о ранце, в отличие от популярной проблемы с ранцем 0/1 (где каждый предмет может быть упакован только один раз). Вот рабочий код из Розетты :

from itertools import product


NAME, SIZE, VALUE = range(3)
items = (
    # NAME, SIZE, VALUE
    ('A', 3, 5),
    ('B', 5, 9),
    ('C', 9, 16))

capacity = 13


def knapsack_unbounded_enumeration(items, C):

    # find max of any one item
    max1 = [int(C / item[SIZE]) for item in items]
    itemsizes = [item[SIZE] for item in items]
    itemvalues = [item[VALUE] for item in items]

    # def totvalue(itemscount, =itemsizes, itemvalues=itemvalues, C=C):
    def totvalue(itemscount):
        # nonlocal itemsizes, itemvalues, C

        totsize = sum(n * size for n, size in zip(itemscount, itemsizes))
        totval = sum(n * val for n, val in zip(itemscount, itemvalues))

        return (totval, -totsize) if totsize <= C else (-1, 0)

    # Try all combinations of bounty items from 0 up to max1
    bagged = max(product(*[range(n + 1) for n in max1]), key=totvalue)
    numbagged = sum(bagged)
    value, size = totvalue(bagged)
    size = -size
    # convert to (iten, count) pairs) in name order
    bagged = ['%dx%d' % (n, items[i][SIZE]) for i, n in enumerate(bagged) if n]

    return value, size, numbagged, bagged


if __name__ == '__main__':
    value, size, numbagged, bagged = knapsack_unbounded_enumeration(items, capacity)
    print(value)
    print(bagged)

Вывод:

23
['1x3', '2x5']

Имейте в виду, что это NP-сложная проблема, поэтому она взорвется когда вы вводите несколько больших значений:)

12
задан Community 23 May 2017 в 11:55
поделиться

12 ответов

Вы не должны возвращать ссылку на массив, если это несовместимо с остальной частью Вашего интерфейса. Если все остальное, что Вы работаете со списками возвратов вместо ссылок, не является нечетной уткой, которая заставляет других программистов помнить исключение.

Если у Вас нет больших списков, это - действительно проблема микрооптимизации. Необходимо быть настолько удачливыми, если это - узкое место в программе.

Насколько сложность идет, различие между ссылкой и списком до сих пор снижается в масштабе сложности, что у Вас есть большие проблемы, если Ваши программисты борются с этим. Сложные алгоритмы и рабочие процессы сложны, но это - просто синтаксис.

Сказав все относительно это, я склонен заставлять все возвратить ссылки и сделать интерфейсы согласовывающимися с этим.

23
ответ дан 2 December 2019 в 03:16
поделиться

Нет. Кроме действительно "возвращают $result"; для ясности.

Я не забываю тестировать эффективность тех, и разница в производительности была минимальна для небольших массивов. Для больших массивов, возвращая ссылку был путь быстрее.

Это - действительно вещь удобства для маленького результата. Скорее сделайте это:

($foo,$bar) = barbaz();

Или возврат ссылки:

 $foobar = barbaz();
 $foobar->[0]; # $foo
 $foobar->[1]; # $bar

Другой способ возвратить ссылку:

($foo,$bar) = @{barbaz()};

Как правило, после того как Вы решаете, который способ пойти, просто придерживайтесь его для Вас модуль, так как это делает его путающий для переключения от одного метода до следующего.

Я обычно возвращаю ссылки массива для списков подобных вещей и массив, когда ответ состоит из двух - четырех различных элементов. Больше, чем это, я делаю хеш, с тех пор не, вся вызывающая сторона будет заботиться обо всех элементах ответа.

7
ответ дан 2 December 2019 в 03:16
поделиться

Я скопирую соответствующую часть своего ответа от другого вопроса здесь.

Часто пропущенное второе соображение является интерфейсом. Как возвращенный массив собирается использоваться? Это важно, потому что целое разыменование массива довольно ужасно в Perl. Например:

for my $info (@{ getInfo($some, $args) }) {
    ...
}

Это ужасно. Это намного лучше.

for my $info ( getInfo($some, $args) ) {
    ...
}

Это также предоставляет себя отображению и захвату.

my @info = grep { ... } getInfo($some, $args);

Но возврат массива касательно может быть удобным, если Вы собираетесь выбрать отдельные элементы:

my $address = getInfo($some, $args)->[2];

Это более просто, чем:

my $address = (getInfo($some, $args))[2];

Или:

my @info = getInfo($some, $args);
my $address = $info[2];

Но в той точке, необходимо подвергнуть сомнению, является ли @info действительно списком или хешем.

my $address = getInfo($some, $args)->{address};

В отличие от массивов по сравнению с судьями массива, существует мало причины принять решение возвратиться, хеш по хешу касательно судей Hash позволяют удобную стенографию, как код выше. И противоположность массивов по сравнению с судьями, это делает случай итератора более простым, или по крайней мере избегает переменной посредника.

for my $key (keys %{some_func_that_returns_a_hash_ref}) {
    ...
}

То, что Вы не должны делать, имеют getInfo() возвратите массив касательно в скалярном контексте и массиве в контексте списка. Это запутывает традиционное использование скалярного контекста как длина массива, которая удивит пользователя.

Я хотел бы добавить, что, заставляя все последовательно сделать X хорошее эмпирическое правило, это не первостепенной важности в разработке хорошего интерфейса. Немного зайдите слишком далеко с ним, и можно легко пробиться с боями другие более важные проблемы.

Наконец, я включу свой собственный модуль, Метод:: Подписи, потому что это предлагает компромисс для передачи в ссылках на массив, не имея необходимость использовать массив касательно синтаксиса.

use Method::Signatures;

method foo(\@args) {
    print "@args";      # @args is not a copy
    push @args, 42;   # this alters the caller array
}

my @nums = (1,2,3);
Class->foo(\@nums);   # prints 1 2 3
print "@nums";        # prints 1 2 3 42

Это сделано через волшебство Данных:: Псевдоним.

8
ответ дан 2 December 2019 в 03:16
поделиться

Если массив создается в функции нет никакой причины возвратить массив; просто возвратите ссылку, так как вызывающей стороне гарантируют это только будет одна копия ее (она была просто создана).

Если функция рассматривает ряд глобальных массивов и возвращает одного из них, то приемлемо возвратить ссылку, если вызывающая сторона не изменит его. Если вызывающая сторона могла бы изменить массив, и это не желаемо, то функция должна возвратить копию.

Это действительно исключительно проблема Perl. В Java Вы всегда возвращаете ссылку, и функция препятствует тому, чтобы массив был изменен (если это - Ваша цель) путем завершения и массива и данных, которые это содержит. В Python возвращаются ссылки и нет никакого способа препятствовать тому, чтобы они были изменены; если это важно, ссылка на копию возвращается вместо этого.

2
ответ дан 2 December 2019 в 03:16
поделиться

Я просто хочу прокомментировать идею о неуклюжем синтаксисе обработки ссылки на массив в противоположность списку. Как brian упомянутый, Вы действительно не должны делать этого, если остальная часть системы использует списки. Это - ненужная оптимизация в большинстве случаев.

Однако если это не так, и Вы свободны создать свой собственный стиль, затем одна вещь, которая может сделать кодирование менее вонючим, использует автополе. autobox повороты SCALAR, ARRAY и HASH (а также другие) в "пакеты", такие, что можно кодировать:

my ( $name, $number ) = $obj->get_arrayref()->items( 0, 1 );

вместо немного более неуклюжего:

my ( $name, $number ) = @{ $obj->get_arrayref() };

путем кодирования чего-то вроде этого:

sub ARRAY::slice { 
    my $arr_ref = shift;
    my $length  = @$arr_ref;
    my @subs    = map { abs($_) < $length ? $_ : $_ < 0 ? 0 : $#$arr_ref } @_;
    given ( scalar @subs ) { 
        when ( 0 ) { return $arr_ref; }
        when ( 2 ) { return [ @{$arr_ref}[ $subs[0]..$subs[1] ] ]; }
        default    { return [ @{$arr_ref}[ @subs ] ]; }
    }
    return $arr_ref; # should not get here.
}

sub ARRAY::items { return @{ &ARRAY::slice }; }

Следует иметь в виду это autobox требует, чтобы Вы реализовали все поведения, которые Вы хотите от них. $arr_ref->pop() не работает, пока Вы не определяете sub ARRAY::pop если Вы не используете автополе:: Ядро

2
ответ дан 2 December 2019 в 03:16
поделиться

Существует ли причина, я не должен делать этого, даже для маленьких результатов?

Нет perl-определенной причины, означая, что это корректно и эффективно возвратить ссылку на локальный массив. Единственный недостаток - то, что люди, которые вызывают Вашу функцию, должны иметь дело с возвращенным массивом касательно, и элементы доступа со стрелкой -> или разыменуйте и т.д. Так, это немного более неприятно для вызывающей стороны.

0
ответ дан 2 December 2019 в 03:16
поделиться

Я не думаю, что необходимо чувствовать себя принужденными только к использованию одного или двух методов. Необходимо однако сохранить это последовательным для каждого модуля или набора модулей.

Вот некоторые примеры для размышляния:

sub test1{
  my @arr;
  return @arr;
}
sub test2{
  my @arr;
  return @arr if wantarray;
  return \@arr;
}
sub test3{
  my %hash;
  return %hash;
}
sub test4{
  my %hash;
  return %hash if wantarray;
  return \%hash;
}
sub test5{
  my %hash;
  return $hash{ qw'one two three' } if wantarray;
  return \%hash;
}
{
  package test;
  use Devel::Caller qw'called_as_method';
  sub test6{
    my $out;
    if( wantarray ){
      $out = 'list';
    }else{
      $out = 'scalar';
    }
    $out = "call in $out context";
    if( called_as_method ){
      $out = "method $out";
    }else{
      $out = "simple function $out";
    }
    return $out;
  }
}

Я вижу возможно использование многих из них в будущем проекте, но некоторые из них довольно бессмысленны.

1
ответ дан 2 December 2019 в 03:16
поделиться

Возврат массива приносит некоторую хорошую пользу:

my @foo = get_array(); # Get list and assign to array.
my $foo = get_array(); # Get magnitude of list.
my ($f1, $f2) = get_array(); # Get first two members of list.
my ($f3,$f6) = (get_array())[3,6]; # Get specific members of the list.

sub get_array {
   my @array = 0..9;

   return @array;
}

Если Вы судьи возвращаемого массива, необходимо будет записать несколько нижних индексов, чтобы сделать ту же работу. Кроме того, пустой массив возвращает false в булевом контексте, но пустой массив касательно не делает.

if ( get_array() ) {
    do_stuff();
}

Если Вы судьи возвращаемого массива, то необходимо сделать:

if ( @{ get_array_ref() } ) {
    do_stuff();
}

Кроме того, если get_array_ref () не удается возвратиться касательно, сказать вместо этого и значение undef, у Вас есть программа, останавливающая катастрофический отказ. Одно из следующего поможет:

if ( @{ get_array() || [] } ) {
    do_stuff();
}

if ( eval{ @{get_array()} } ) {
    do_stuff();
}

Таким образом, если преимущества скорости необходимы или если Вам нужен массив касательно (возможно, Вы хотите позволить непосредственное управление элементом набора объекта - фу, но иногда это должно произойти), возвратите массив касательно Иначе, я нахожу преимущества стандартных массивов стоящими сохранения.

Обновление: действительно важно помнить, что то, что Вы возвращаете из стандартной программы, является не всегда массивом или списком. То, что Вы возвращаете, - то, что следует return, или результат последней операции. Ваше возвращаемое значение будет оценено в контексте. Большую часть времени все будет прекрасно, но иногда можно получить неожиданное поведение.

sub foo {
    return $_[0]..$_[1];
}

my $a = foo(9,20);
my @a = foo(9,20);

print "$a\n";
print "@a\n";

Сравните:

sub foo {
    my @foo = ($_[0]..$_[1]);
    return @foo;
}

my $a = foo(9,20);
my @a = foo(9,20);

print "$a\n";
print "@a\n";

Так, когда Вы говорите, "возвращают массив" быть уверенным, что Вы действительно имеете в виду, "возвращают массив". Знайте о том, что Вы возвращаете из своих стандартных программ.

0
ответ дан 2 December 2019 в 03:16
поделиться

Когда Вы используетесь для использования кода так же первый отрывок в Mathieu Longtin ответ, необходимо написать ужасный код как второй отрывок, или это не настолько лучше кодирует:

my ($foo,$bar) = @{barbaz()};

Я думаю, что это - самый большой недостаток при возврате ссылки вместо массива. Если я хочу небольшое количество возврата значений другого вида. Я привык к возвращаемому массиву и присваиваюсь непосредственно к переменным (как используется сделать в Python, например).

my ($status, $result) = do_something();
if ($status eq 'OK') {
    ...

Если сумма значений является большим и различным видом, я используюсь для возврата хеша касательно (лучше для рефакторинга)

my ($status, $data, $foo, $bar, $baz) =
    @{do_something()}{qw(status data foo bar baz)};
if ($status eq 'OK') {
    ...

Если возвращаемые значения являются тем же видом, чем возврат массива или массива касательно спорен в зависимости от суммы.

0
ответ дан 2 December 2019 в 03:16
поделиться

Я не уверен, если возврат ссылки более эффективен в этом случае; т.е. Perl копирует данные, возвращенные подпрограммами?

В целом, если Ваш массив создается полностью в подпрограмме затем нет никакой очевидной проблемы с возвратом ссылки, потому что иначе массив был бы отброшен так или иначе. Однако, если ссылка также передается в другое место прежде, чем возвратить его, у Вас может быть две копии той же ссылки, и это может быть изменено в одном месте, но, как не ожидать, в другом месте.

0
ответ дан 2 December 2019 в 03:16
поделиться

Поскольку никто не упоминал о wantarray , я: -)

Я считаю хорошей практикой позволить вызывающей стороне решить, в каком контексте она хочет получить результат. Например, в приведенном ниже коде вы запрашиваете у Perl контекст, в котором была вызвана подпрограмма, и решаете, что вернуть.

sub get_things {
    my @things;
    ... # populate things
    return wantarray ? @things : \@things;
}

Затем

for my $thing ( get_things() ) {
    ...
}

и

my @things = get_things();

работают правильно из-за контекста списка, и:

my $things = get_things();

вернет ссылка на массив.

Для получения дополнительной информации о wantarray вы можете проверить perldoc -f wantarray .

Edit: Я недооценил один из первых ответы, в которых упоминается wantarray , но я думаю, что этот ответ все еще действителен, потому что он делает его немного понятнее.

3
ответ дан 2 December 2019 в 03:16
поделиться

Важное упущение в приведенных выше ответах: не возвращайте ссылки на личные данные!

Например:

package MyClass;

sub new {
  my($class) = @_;
  bless { _things => [] } => $class;
}

sub add_things {
  my $self = shift;
  push @{ $self->{_things} } => @_;
}

sub things {
  my($self) = @_;
  $self->{_things};  # NO!
}

Да, пользователи могут заглядывать прямо под капот с объектами Perl, реализованными таким образом, но не облегчают пользователям возможность непреднамеренно выстрелить себе в ногу , например, ,

my $obj = MyClass->new;
$obj->add_things(1 .. 3);

...;

my $things = $obj->things;
my $first = shift @$things;

Лучше было бы вернуть (возможно, глубокую) копию ваших личных данных, как в

sub things {
  my($self) = @_;
  @{ $self->{_things} };
}
1
ответ дан 2 December 2019 в 03:16
поделиться
Другие вопросы по тегам:

Похожие вопросы: