Najlepszy sposób na iterację po tablicy Perla


96

Jaka jest najlepsza implementacja (pod względem szybkości i wykorzystania pamięci) do iteracji po tablicy Perla? Czy jest lepszy sposób? ( @Arraynie trzeba ich zachowywać).

Wdrożenie 1

foreach (@Array)
{
      SubRoutine($_);
}

Wdrożenie 2

while($Element=shift(@Array))
{
      SubRoutine($Element);
}

Wdrożenie 3

while(scalar(@Array) !=0)
{
      $Element=shift(@Array);
      SubRoutine($Element);
}

Wdrożenie 4

for my $i (0 .. $#Array)
{
      SubRoutine($Array[$i]);
}

Wdrożenie 5

map { SubRoutine($_) } @Array ;

2
Dlaczego miałoby istnieć „najlepsze”? Zwłaszcza biorąc pod uwagę, że nie mamy pojęcia, jak zmierzyć jeden z drugim (czy prędkość jest ważniejsza niż użycie pamięci? Jest mapi akceptowalna odpowiedź? Itd.)
Max Lybbert

2
Dwa z trzech, które wysłałeś, sprawiłyby, że powiedziałbym „WTH ?!” chyba że istnieje dodatkowy kontekst otaczający, aby uczynić je rozsądnymi alternatywami. W każdym razie to pytanie jest na poziomie „ Jaki jest najlepszy sposób dodania dwóch liczb? ” W większości przypadków jest tylko jeden sposób. Następnie są takie okoliczności, w których potrzebujesz innego sposobu. Głosowanie za zamknięciem.
Sinan Ünür

4
@ SinanÜnür Rozumiem twoją opinię (że jest tylko jeden sposób na dodanie dwóch liczb), ale analogia nie jest wystarczająco mocna, aby użyć lekceważąco. Oczywiście jest więcej niż jeden sposób, a OP chce zrozumieć, co jest dobrym pomysłem, a co nie.
CodeClown42

2
Rozdział 24 trzeciej edycji Perla Programowanie zawiera sekcję dotyczącą wydajności, którą warto przeczytać. Dotyczy różnych typów wydajności, takich jak czas, programista, konserwator. Sekcja zaczyna się od stwierdzenia „Zauważ, że optymalizacja pod względem czasu może czasami kosztować miejsce lub wydajność programisty (wskazywane przez sprzeczne wskazówki poniżej). To są przerwy”.

1
Jeden sposób na dodanie dwóch liczb? Nie, jeśli spojrzysz na wywołania / implementacje niższego poziomu ... pomyśl o przeniesieniu lookahead, carry save
adders

Odpowiedzi:


76
  • Pod względem szybkości: # 1 i # 4, ale w większości przypadków niewiele.

    Mógłbyś napisać benchmark, aby to potwierdzić, ale podejrzewam, że okaże się, że # 1 i # 4 są nieco szybsze, ponieważ praca iteracyjna jest wykonywana w C zamiast w Perlu i nie ma niepotrzebnego kopiowania elementów tablicy. ( $_jest aliasowany do elementu w # 1, ale # 2 i # 3 faktycznie kopiują skalary z tablicy).

    # 5 może być podobny.

  • Pod względem wykorzystania pamięci: wszystkie są takie same, z wyjątkiem # 5.

    for (@a)ma specjalną wielkość liter, aby uniknąć spłaszczenia tablicy. Pętla wykonuje iterację po indeksach tablicy.

  • Pod względem czytelności: # 1.

  • Pod względem elastyczności: # 1 / # 4 i # 5.

    # 2 nie obsługuje elementów, które są fałszywe. # 2 i # 3 są destrukcyjne.


3
Wow, dodałeś mnóstwo informacji o ciężarówkach w krótkich i prostych zdaniach.
jaypal singh

1
# 2 jest dobry, gdy robisz kolejki (np. Wyszukiwania wszerz):my @todo = $root; while (@todo) { my $node = shift; ...; push @todo, ...; ...; }
ikegami

Czy implementacja 4 nie tworzy pośredniej tablicy indeksów, co mogłoby spowodować wprowadzenie dużej ilości pamięci do wykorzystania? Jeśli tak, wygląda na to, że nie należy stosować tego podejścia. stackoverflow.com/questions/6440723/… rt.cpan.org/Public/Bug/Display.html?id=115863
Thorsten Schöning

@ikegami Wierny stylowi Twojego mistrza - świetna odpowiedź :)
skeetastax

26

Jeśli zależy Ci tylko na elementach @Array, użyj:

for my $el (@Array) {
# ...
}

lub

Jeśli indeksy mają znaczenie, użyj:

for my $i (0 .. $#Array) {
# ...
}

Lub, od perl5.12.1, możesz użyć:

while (my ($i, $el) = each @Array) {
# ...
}

Jeśli potrzebujesz zarówno elementu, jak i jego indeksu w treści pętli, oczekiwałbym za pomocą each być najszybszym, ale wtedyzrezygnujesz z kompatybilności z poprzednimi wersjami 5.12.1 perl.

W pewnych okolicznościach odpowiedni może być inny schemat niż te.


Spodziewałbym się, że eachbędzie najwolniejszy. Wykonuje całą pracę pozostałych bez aliasu, plus przypisanie listy, dwie kopie skalarne i dwa wyczyszczenia skalarne.
ikegami

I, najlepiej jak potrafię, masz rację. Około 45% szybciej dzięki foriteracji po indeksach tablicy i 20% szybciej podczas iteracji po indeksach odwołania do tablicy (mam dostęp $array->[$i]w treści) w porównaniu z użyciem eachw połączeniu z while.
Sinan Ünür

3

IMO, implementacja nr 1 jest typowa i krótka i idiomatyczna dla Perla przewyższa inne tylko w tym zakresie. Wzorzec trzech opcji może przynajmniej dać ci wgląd w szybkość.


2

1 różni się zasadniczo od 2 i 3, ponieważ pozostawia tablicę w takcie, podczas gdy pozostałe dwie pozostawiają ją pustą.

Powiedziałbym, że numer 3 jest dość zwariowany i prawdopodobnie mniej wydajny, więc zapomnij o tym.

Co daje ci # 1 i # 2, a oni nie robią tego samego, więc jeden nie może być „lepszy” od drugiego. Jeśli tablica jest duża i nie musisz jej utrzymywać, ogólnie zakres się nią zajmie ( ale zobacz UWAGA ), więc ogólnie rzecz biorąc , # 1 jest nadal najbardziej przejrzystą i najprostszą metodą. Wyłączenie każdego elementu niczego nie przyspieszy. Nawet jeśli istnieje potrzeba uwolnienia tablicy od odniesienia, po prostu zrobiłbym:

undef @Array;

kiedy skończysz.

  • UWAGA : Procedura zawierająca zasięg tablicy faktycznie zachowuje tablicę i następnym razem ponownie wykorzystuje spację. Generalnie powinno wystarczyć (patrz komentarze).

@Array = ();nie zwalnia podstawowej tablicy. Nawet wyjście poza zakres by tego nie zrobiło. Gdybyś chciał zwolnić podstawową tablicę, użyłbyś undef @Array;.
ikegami

2
Próbny; perl -MDevel::Peek -e'my @a; Dump(\@a,1); @a=qw( a b c ); Dump(\@a,1); @a=(); Dump(\@a,1); undef @a; Dump(\@a,1);' 2>&1 | grep ARRAY
ikegami

CO??? Myślałem, że cały punkt GC był kiedyś liczbą ref == 0, zaangażowana pamięć może zostać poddana recyklingowi.
CodeClown42

@ikegami: Rozumiem, co dotyczy ()vs undef, ale jeśli wyjście poza zakres nie zwalnia pamięci używanej przez tablicę lokalną w tym zakresie, czy nie czyni to z Perla wycieku katastrofy? To nie może być prawda.
CodeClown42

One też nie przeciekają. Subskrybent nadal jest ich właścicielem i użyje ich ponownie przy następnym wywołaniu. Zoptymalizowany pod kątem szybkości.
ikegami

1

W jednym wierszu, aby wydrukować element lub tablicę.

print $ _ for (@array);

UWAGA: pamiętaj, że $ _ odwołuje się wewnętrznie do elementu @array w pętli. Wszelkie zmiany wprowadzone w $ _ zostaną odzwierciedlone w @array; dawny.

my @array = qw( 1 2 3 );
for (@array) {
        $_ = $_ *2 ;
}
print "@array";

wyjście: 2 4 6


0

Najlepszy sposób decydowania o takich pytaniach w celu ich porównania:

use strict;
use warnings;
use Benchmark qw(:all);

our @input_array = (0..1000);

my $a = sub {
    my @array = @{[ @input_array ]};
    my $index = 0;
    foreach my $element (@array) {
       die unless $index == $element;
       $index++;
    }
};

my $b = sub {
    my @array = @{[ @input_array ]};
    my $index = 0;
    while (defined(my $element = shift @array)) {
       die unless $index == $element;
       $index++;
    }
};

my $c = sub {
    my @array = @{[ @input_array ]};
    my $index = 0;
    while (scalar(@array) !=0) {
       my $element = shift(@array);
       die unless $index == $element;
       $index++;
    }
};

my $d = sub {
    my @array = @{[ @input_array ]};
    foreach my $index (0.. $#array) {
       my $element = $array[$index];
       die unless $index == $element;
    }
};

my $e = sub {
    my @array = @{[ @input_array ]};
    for (my $index = 0; $index <= $#array; $index++) {
       my $element = $array[$index];
       die unless $index == $element;
    }
};

my $f = sub {
    my @array = @{[ @input_array ]};
    while (my ($index, $element) = each @array) {
       die unless $index == $element;
    }
};

my $count;
timethese($count, {
   '1' => $a,
   '2' => $b,
   '3' => $c,
   '4' => $d,
   '5' => $e,
   '6' => $f,
});

I uruchamiając to na perlu 5, wersja 24, subversion 1 (v5.24.1) zbudowanym dla x86_64-linux-gnu-thread-multi

Dostaję:

Benchmark: running 1, 2, 3, 4, 5, 6 for at least 3 CPU seconds...
         1:  3 wallclock secs ( 3.16 usr +  0.00 sys =  3.16 CPU) @ 12560.13/s (n=39690)
         2:  3 wallclock secs ( 3.18 usr +  0.00 sys =  3.18 CPU) @ 7828.30/s (n=24894)
         3:  3 wallclock secs ( 3.23 usr +  0.00 sys =  3.23 CPU) @ 6763.47/s (n=21846)
         4:  4 wallclock secs ( 3.15 usr +  0.00 sys =  3.15 CPU) @ 9596.83/s (n=30230)
         5:  4 wallclock secs ( 3.20 usr +  0.00 sys =  3.20 CPU) @ 6826.88/s (n=21846)
         6:  3 wallclock secs ( 3.12 usr +  0.00 sys =  3.12 CPU) @ 5653.53/s (n=17639)

Zatem „foreach (@Array)” jest około dwa razy szybszy niż pozostałe. Wszystkie inne są bardzo podobne.

@ikegami wskazuje również, że istnieje kilka różnic w tych implementacjach innych niż szybkość.


1
Porównanie $index < $#arraypowinno faktycznie odbywać się, $index <= $#arrayponieważ $#arraynie jest to długość tablicy, ale jej ostatni indeks.
josch
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.