2010-03-20 84 views
6

Tôi đã thực hiện một thử nghiệm nhỏ như được hiển thị bên dưới và có vẻ như một vòng lặp while nhanh hơn vòng lặp for trong Perl. Nhưng vì thí nghiệm khá thô lỗ, và chủ đề có thể phức tạp hơn rất nhiều, tôi muốn nghe những gì bạn nói về điều này. Cảm ơn mọi người luôn luôn nhận xét/đề xuất :)Trong Perl, là một vòng lặp trong khi thường nhanh hơn một vòng lặp for?

Trong hai tập lệnh nhỏ sau đây, tôi đã thử trong khi và cho các vòng riêng để tính giai thừa 100.000. Một trong đó có vòng lặp while mất 57 phút 17 giây để hoàn thành trong khi vòng lặp tương đương mất 1 giờ 7 phút 54 giây.

Script có vòng lặp while:

use strict; 
use warnings; 
use bigint; 

my $now = time; 

my $n = shift; 
my $s = 1; 

while(1){ 
$s *= $n; 
$n--; 
last if $n==2; 
} 

print $s*$n; 
$now = time - $now; 
printf("\n\nTotal running time: %02d:%02d:%02d\n\n", int($now/3600), 
      int(($now % 3600)/60), int($now % 60)); 

Script có vòng lặp for:

use strict; 
use warnings; 
use bigint; 

my $now = time; 

my $n =shift; 
my $s=1; 

for (my $i=2; $i<=$n;$i++) { 
$s = $s*$i; 
} 

print $s; 
$now = time - $now; 
printf("\n\nTotal running time: %02d:%02d:%02d\n\n", int($now/3600), 
      int(($now % 3600)/60), int($now % 60)); 
+3

Có thể bạn đang cố gắng tối ưu hóa điều sai. Tôi tự hỏi tại sao bạn nghĩ rằng phần đặc biệt của ngôn ngữ này lại quan trọng đến vậy? – Ether

+0

Hãy chạy chúng một vài lần, và chúng có thể trung bình với cùng một khoảng – CaffGeek

+0

@Chad, thực sự tôi đã thử nghiệm mã này một vài lần. Họ đã mất nhiều thời gian khác nhau để hoàn thành công việc tương tự. Tôi nghĩ rằng lời giải thích của @Jonathan Leffler với mã minh họa có ý nghĩa rất tốt. – Mike

Trả lời

8

Các vòng lặp không tương đương, và bạn chủ yếu là đập vỡ gói bigint và nó không liên quan gì với for vs while mỗi lần.

Vòng lặp while sử dụng ký hiệu '$s *= $i' nhưng vòng lặp for sử dụng '$s = $s * $i'. Đơn giản là đủ để chứng minh rằng chúng không giống nhau. Ngoài ra, một vòng lặp đếm lên; người khác đếm ngược. Điều này ảnh hưởng đến cách nhân các số lớn. Đó là một hiệu ứng thứ hai - nhưng không hoàn toàn không đáng kể.

[Cập nhật: sửa đổi để chỉ hiển thị một phiên bản của mã, với thời gian phụ thứ hai. Có chỗ để nghĩ rằng việc in ấn nên được loại trừ khỏi các tính toán thời gian; mà làm cho mọi thứ rối tung hơn, vì vậy tôi đã không làm phiền. Tôi đã sửa lỗi trong phiên bản trước: vòng 4 cũng giống như vòng lặp 3 - bây giờ nó không phải là. Tôi cũng đã tarted lên định dạng đầu ra (mặc dù xử lý phụ thứ hai có thể được cải thiện - một bài tập cho người đọc), và có 'báo cáo tiến độ' tốt hơn.]

Kết quả thời gian trên máy Mac Mini (Snow Leopard 10.6.2) là:

Count up $s *= $i:  00:00:12.663337 
Count up $s = $s * $i: 00:00:20.686111 
Count down $s *= $i:  00:00:14.201797 
Count down $s = $s * $i: 00:00:23.269874 

Kịch bản:

use Time::HiRes qw(gettimeofday); 
use strict; 
use warnings; 
use bigint; 
use constant factorial_of => 13000; 

sub delta_t 
{ 
    my($tag, $t1, $t2) = @_; 
    my($d) = int($t2 - $t1); 
    my($f) = ($t2 - $t1) - $d; 
    my($s) = sprintf("%.6f", $f); 
    $s =~ s/^0//; 
    printf "%-25s %02d:%02d:%02d%s\n", 
      $tag, int($d/3600), int(($d % 3600)/60), int($d % 60), $s; 
} 

my $t1 = gettimeofday; 

{ 
    my $n = factorial_of; 
    my $s = 1; 
    for (my $i = 2; $i <= $n; $i++) 
    { 
     $s *= $i; 
    } 
    print "$s\n: Loop 1\n"; 
} 

my $t2 = gettimeofday; 
delta_t('Count up $s *= $i:',  $t1, $t2); 

{ 
    my $n = factorial_of; 
    my $s = 1; 
    for (my $i = 2; $i <= $n; $i++) 
    { 
     $s = $s * $i; 
    } 
    print "$s\n: Loop 2\n"; 
} 

my $t3 = gettimeofday; 
delta_t('Count up $s *= $i:',  $t1, $t2); 
delta_t('Count up $s = $s * $i:', $t2, $t3); 

{ 
    my $n = factorial_of; 
    my $s = 1; 
    for (my $i = $n; $i > 1; $i--) 
    { 
     $s *= $i; 
    } 
    print "$s\n: Loop 3\n"; 
} 

my $t4 = gettimeofday; 
delta_t('Count up $s *= $i:',  $t1, $t2); 
delta_t('Count up $s = $s * $i:', $t2, $t3); 
delta_t('Count down $s *= $i:',  $t3, $t4); 

{ 
    my $n = factorial_of; 
    my $s = 1; 
    for (my $i = $n; $i > 1; $i--) 
    { 
     $s = $s * $i; 
    } 
    print "$s\n: Loop 4\n"; 
} 

my $t5 = gettimeofday; 
delta_t('Count up $s *= $i:',  $t1, $t2); 
delta_t('Count up $s = $s * $i:', $t2, $t3); 
delta_t('Count down $s *= $i:',  $t3, $t4); 
delta_t('Count down $s = $s * $i:', $t4, $t5); 

Và đây là một phiên bản nhỏ gọn hơn nhiều của đoạn mã trên, được mở rộng để kiểm tra các vòng lặp 'while' cũng như 'for'. Nó cũng đề cập đến hầu hết các vấn đề về thời gian. Điều duy nhất không lý tưởng (với tôi) là nó sử dụng một vài biến toàn cầu, và tôi băm mã trong mã refs một chút để tất cả phù hợp trên một dòng mà không kích hoạt một thanh cuộn (trên màn hình của tôi, anyway). Rõ ràng, với công việc nhiều hơn một chút, thử nghiệm có thể được bao bọc thành một mảng, do đó việc kiểm tra sẽ được thực hiện lặp đi lặp lại - một vòng lặp thông qua mảng chạy chức năng hẹn giờ trên thông tin trong mảng. Vv ...đó là SMOP - Vấn đề lập trình đơn giản. (Nó in băm MD5 của giai thừa, chứ không phải giai thừa, vì nó dễ dàng so sánh kết quả, vv. Nó đã chỉ ra một vài lỗi khi tôi đang tái cấu trúc mã ở trên. Có, MD5 không an toàn - nhưng tôi không sử dụng nó cho an ninh; chỉ để phát hiện những thay đổi chủ ý)

use Time::HiRes qw(gettimeofday); 
use Digest::MD5 qw(md5_hex); 
use strict; 
use warnings; 
use bigint; 
use constant factorial_of => 13000; 

my ($s, $i); 

my $l1 = sub {my($n) = @_; for ($i = 2; $i <= $n; $i++) { $s *= $i;  }}; 
my $l2 = sub {my($n) = @_; for ($i = 2; $i <= $n; $i++) { $s = $s * $i; }}; 
my $l3 = sub {my($n) = @_; for ($i = $n; $i > 1; $i--) { $s *= $i;  }}; 
my $l4 = sub {my($n) = @_; for ($i = $n; $i > 1; $i--) { $s = $s * $i; }}; 
my $l5 = sub {my($n) = @_; $i = 2; while ($i <= $n) { $s *= $i;  $i++; }}; 
my $l6 = sub {my($n) = @_; $i = 2; while ($i <= $n) { $s = $s * $i; $i++; }}; 
my $l7 = sub {my($n) = @_; $i = $n; while ($i > 1) { $s *= $i;  $i--; }}; 
my $l8 = sub {my($n) = @_; $i = $n; while ($i > 1) { $s = $s * $i; $i--; }}; 

sub timer 
{ 
    my($n, $code, $tag) = @_; 
    my $t1 = gettimeofday; 
    $s = 1; 
    &$code(factorial_of); 
    my $t2 = gettimeofday; 
    my $md5 = md5_hex($s); 
    printf "Loop %d: %-33s %09.6f (%s)\n", $n, $tag, $t2 - $t1, $md5; 
} 

my $count = 1; 
timer($count++, $l1, 'for - Count up $s *= $i:'); 
timer($count++, $l2, 'for - Count up $s = $s * $i:'); 
timer($count++, $l3, 'for - Count down $s *= $i:'); 
timer($count++, $l4, 'for - Count down $s = $s * $i:'); 
timer($count++, $l5, 'while - Count up $s *= $i:'); 
timer($count++, $l6, 'while - Count up $s = $s * $i:'); 
timer($count++, $l7, 'while - Count down $s *= $i:'); 
timer($count++, $l8, 'while - Count down $s = $s * $i:'); 

Ví dụ đầu ra (MD5 checksum nén để tránh dòng bẻ - giá trị đầy đủ là 584b3ab832577fd1390970043efc0ec8):

Loop 1: for - Count up $s *= $i:  12.853630 (584b3ab8...3efc0ec8) 
Loop 2: for - Count up $s = $s * $i: 20.854735 (584b3ab8...3efc0ec8) 
Loop 3: for - Count down $s *= $i:  14.798155 (584b3ab8...3efc0ec8) 
Loop 4: for - Count down $s = $s * $i: 23.699913 (584b3ab8...3efc0ec8) 
Loop 5: while - Count up $s *= $i:  12.972428 (584b3ab8...3efc0ec8) 
Loop 6: while - Count up $s = $s * $i: 21.192956 (584b3ab8...3efc0ec8) 
Loop 7: while - Count down $s *= $i:  14.555620 (584b3ab8...3efc0ec8) 
Loop 8: while - Count down $s = $s * $i: 23.790795 (584b3ab8...3efc0ec8) 

tôi. liên tục thấy một hình phạt nhỏ (< 1%) cho vòng lặp 'while' qua vòng lặp 'for' tương ứng, nhưng tôi không có giải thích tốt cho nó.

+0

@ Jonathan Leffler, cảm ơn rất nhiều! Mã minh họa của bạn rất hữu ích đối với tôi. Cảm ơn :) – Mike

+0

@ Joanthan, cảm ơn bạn đã cập nhật mã. Tôi luôn nghĩ $ s * = $ i 'và' $ s = $ s * $ i 'và $ i ++ và $ i-- đang làm điều tương tự trong các cách xử lý khác nhau nhưng tôi đã sai.Cảm ơn rất nhiều vì đã chỉ ra điều này :) Bây giờ tôi đã thay đổi trong khi so với các tập lệnh và bây giờ tôi đã có: my $ now = time; my $ n = shift; my $ i = 2; my $ s = 1; cho (; $ i <= $ n; $ i ++) { $ s * = $ i; } Và my $ n = shift; my $ i = 2; my $ s = 1; trong khi ($ i <= $ n) { $ s * = $ n; $ i ++; } Chúng trông giống nhau. Kết quả: trong khi nhanh hơn. Tôi không chắc nhưng có điều gì sai với thiết kế thử nghiệm của tôi không? Tôi đã chạy mã của bạn, kết quả là trong khi chậm hơn. – Mike

+1

@ Giống: Tôi không có cảm giác tốt về những vấn đề còn lại là gì. Các điểm chính là (1) vấn đề chủ yếu là 'bigint' và (2) có khả năng phần còn lại 'trong khi so với' các khác biệt được chôn sâu trong mã byte Perl. Tôi đã có một số thay đổi trong thời gian - chủ yếu là thứ tự của 0,1 giây hoặc lâu hơn, trừ khi cũng có một bản sao lưu đang chạy (TimeMachine đến một TimeCapsule); Tôi đã chọn 13000 làm số thử nghiệm của mình để có được số lượng đủ lớn để có được thời gian hợp lý trong khi không quá lớn để làm cho nó khó chịu khi chạy thử nghiệm (ví dụ: 1 giờ quá dài). –

5

tôi sẽ rơi xuống sốc nếu thực sự có bất kỳ "thực" chênh lệch giữa thời gian và cho vòng . Giả sử rằng họ đang làm điều tương tự "chính xác", họ nên được tối ưu hóa bởi người thông dịch để ít nhiều giống hệt nhau.

Tôi sẽ đặt cược rằng sự khác biệt có lẽ không có gì khác hơn so với các quy trình khác đang cạnh tranh khác nhau đối với tài nguyên trong hai lần thực hiện.

Ngay cả khi có sự khác biệt, đừng bị cuốn vào The Sad Tragedy of Micro-Optimization Theater.

+0

@Morinar, tôi vừa hoàn thành bài viết bạn đề xuất. Tôi thấy điểm bạn đang làm, cảm ơn. – Mike

5

Một chìa khóa để đo điểm chuẩn là đơn giản hóa. Vấn đề đặt ra là tốc độ for so với while. Nhưng thử nghiệm liên quan đến một số phức tạp không cần thiết.

  • Hai vòng không giống như chúng có thể. Một sử dụng $s *= $n và một sử dụng khác $s = $s * $i (như Jonathan Leffler chỉ ra). Một người sử dụng $n-- và người kia sử dụng $i++ (ai biết họ có khác về tốc độ không?).

  • Nếu chúng tôi quan tâm đến for so với while, không cần phải liên quan đến bigint. Điều đó chỉ làm lẫn lộn chủ đề. Cụ thể, tập lệnh while của bạn chỉ phụ thuộc vào một đối tượng bigint ($s), trong khi tập lệnh for của bạn sử dụng hai trong số đó ($s$i). Nó không làm tôi ngạc nhiên khi tập lệnh for chậm hơn.

Viết lại vòng của bạn sẽ được như tương tự càng tốt, giữ cho thừa đủ nhỏ để bạn không cần phải sử dụng bigint, và sử dụng các mô-đun Benchmark. Sau đó, bạn có thể chạy một cuộc đua công bằng-đầu-đầu của for so với while. Tôi sẽ tò mò để xem những gì bạn tìm thấy.

+1

@FM, thử nghiệm của tôi được thiết kế kém đến mức suy luận của tôi từ kết quả gần như hoàn toàn không liên quan đến câu hỏi tôi đã đăng. Đây là một thất bại hoàn toàn. Vâng, dù sao, cảm ơn vì đã để lại cho tôi những lời bình luận này. Có vẻ như tôi luôn có thể học được một vài điều từ các bạn :) – Mike

+1

@Mike Đừng quá khó khăn với bản thân. Điểm chuẩn là khó khăn, và thậm chí lập trình viên có kinh nghiệm làm cho những sai lầm trong việc thiết lập chúng. Ví dụ: http://stackoverflow.com/questions/1083269/is-perls-unpack-ever-faster-than-substr và http://stackoverflow.com/questions/1960779/why-does-perls-tr-n -get-slow-và-chậm-as-line-length-tăng. Điểm chuẩn của bạn có thể đã bị thiếu sót, nhưng câu hỏi đã thành công vì bạn đã học được một số điều hữu ích. :) – FMc

Các vấn đề liên quan