Từ perldata:Khi nào có ý nghĩa thống kê một băm?
You can preallocate space for a hash by assigning to the keys() function.
This rounds up the allocated buckets to the next power of two:
keys(%users) = 1000; # allocate 1024 buckets
Có một quy tắc của ngón tay cái khi presizing một hash sẽ cải thiện hiệu suất?
Quy tắc chung là lớn hơn bạn biết Hash sẽ là, bạn càng có nhiều khả năng nhận được giá trị ngoài việc định cỡ trước nó. Hãy xem xét nếu băm của bạn có 10 khe, và bạn bắt đầu thêm một cái sau cái khác, số lượng mở rộng sẽ a) ít (nếu có), và b) nhỏ (vì có ít dữ liệu). Nhưng nếu bạn BIẾT bạn sẽ cần ít nhất 1M mục, thì không có lý do gì để mở rộng, và sao chép các cấu trúc dữ liệu cơ bản và mở rộng bao giờ hết lần này đến lần khác trong khi bảng tăng lên.
Bạn có THÔNG BÁO bản mở rộng này không? Eh, có thể. Máy móc hiện đại khá darn nhanh, nó có thể không đi lên. Nhưng đó là một cơ hội lớn để mở rộng heap, do đó gây ra một GC và một thác của tất cả các loại của sự vật. Vì vậy, nếu bạn biết bạn sẽ sử dụng nó, đó là một sửa chữa "rẻ" để tinh chỉnh thêm một vài milibleems về hiệu suất.
Về cơ bản đó là cánh cửa để tối ưu hóa hiệu suất băm. Hiệu suất Hash phụ thuộc rất nhiều vào cả thuật toán băm được sử dụng và trên dữ liệu bạn đang xử lý, vì vậy hầu như không thể đưa ra quy tắc của ngón tay cái. Dù sao, có thể nói điều gì đó.
Bạn biết rằng mỗi cấu trúc dữ liệu cung cấp một số dư nhất định giữa không gian và hiệu quả thời gian. Các bảng băm đặc biệt tốt về hiệu quả thời gian, cung cấp truy cập thời gian hấp dẫn (0 (1)).
Điều này đúng trừ khi có xung đột. Khi xảy ra va chạm, thời gian truy cập là tuyến tính với kích thước của thùng tương ứng với giá trị va chạm. (Hãy xem this để biết thêm chi tiết). Va chạm, ngoài việc "chậm", chủ yếu là sự gián đoạn của việc đảm bảo thời gian truy cập là khía cạnh quan trọng nhất thường dẫn đến việc chọn bảng băm ngay từ đầu. Lý tưởng nhất, các bảng băm có thể nhắm đến cái được gọi là "băm hoàn hảo" (thực sự khả thi khi bạn có thể tinh chỉnh thuật toán cho loại dữ liệu bạn sẽ xử lý), nhưng điều này không dễ dàng đến vậy đạt được trong trường hợp chung (đây là một euphemism, thực sự). Dù sao, nó là một vấn đề của thực tế là bảng băm lớn hơn (cùng với một thuật toán băm tốt) có thể làm giảm tần suất va chạm, và do đó cải thiện hiệu suất, tại các chi phí của bộ nhớ. Bảng băm nhỏ hơn sẽ thấy nhiều va chạm hơn (do đó sẽ có hiệu suất kém hơn và đảm bảo thời gian truy cập chất lượng thấp hơn) nhưng chiếm ít bộ nhớ hơn. Vì vậy, nếu bạn lập hồ sơ chương trình của mình và thấy rằng truy cập bảng băm là một nút cổ chai (vì bất kỳ lý do nào), bạn có cơ hội giải quyết vấn đề này bằng cách đặt thêm bộ nhớ cho không gian băm (nếu bạn có bộ nhớ).
Trong mọi trường hợp, tôi sẽ không tăng giá trị này một cách ngẫu nhiên, nhưng chỉ sau khi sử dụng kỹ lưỡng, vì nó cũng đúng là sử dụng thuật toán perl được biên dịch (AFAIK) và điều này cũng ảnh hưởng lớn đến hiệu năng băm (nói cách khác, bạn có thể có rất nhiều va chạm ngay cả khi bạn làm cho không gian băm lớn hơn).
Như thường lệ với những điều liên quan đến hiệu suất, nó có thể hữu ích hay không, nó phụ thuộc vào trường hợp cụ thể của bạn.
Tôi cố gắng để mở rộng chi phí chuẩn về trồng băm:
use Benchmark qw(cmpthese);
# few values
cmpthese(-4, {
prealloc => sub {
my %hash;
keys(%hash) = 17576;
$hash{$_} = $_ for 'aaa' .. 'zzz';
},
normal => sub {
my %hash;
$hash{$_} = $_ for 'aaa' .. 'zzz';
},
});
# more values
cmpthese(-8, {
prealloc => sub {
my %hash;
keys(%hash) = 456976;
$hash{$_} = $_ for 'aaaa' .. 'zzzz';
},
normal => sub {
my %hash;
$hash{$_} = $_ for 'aaaa' .. 'zzzz';
},
});
Kết quả không âm thanh như tối ưu hóa lớn, tuy nhiên giảm đống phân mảnh được đề cập bởi Will Hartung có thể là lợi ích. Chạy perl 5.12 trên máy WinXP.
Rate normal prealloc
normal 48.3/s -- -2%
prealloc 49.4/s 2% --
(warning: too few iterations for a reliable count)
s/iter normal prealloc
normal 3.62 -- -1%
prealloc 3.57 1% --