2012-03-16 31 views
8

Tôi muốn tạo và thao tác các mảng lớn (4 byte) số nguyên trong bộ nhớ. Bằng cách lớn, tôi có nghĩa là về thứ tự của hàng trăm triệu. Mỗi ô trong mảng sẽ hoạt động như một bộ đếm cho một vị trí trên một nhiễm sắc thể. Tất cả những gì tôi cần là nó phù hợp với trí nhớ và có thể truy cập nhanh (O (1)) vào các phần tử. Điều tôi đang đếm không phải là một tính năng thưa thớt, vì vậy tôi không thể sử dụng một mảng thưa thớt.C-như mảng trong perl

Tôi không thể làm điều này với danh sách perl thông thường, vì perl (ít nhất là trên máy của tôi) sử dụng 64 byte cho mỗi phần tử, do đó bộ gen của hầu hết các sinh vật tôi làm việc quá lớn. Tôi đã thử lưu trữ dữ liệu trên đĩa thông qua SQLite và băm buộc, và mặc dù chúng hoạt động, rất chậm, đặc biệt là trên các ổ đĩa thông thường. (Nó hoạt động hợp lý ok khi tôi chạy trên cuộc đột kích 4 ổ đĩa 0).

Tôi nghĩ tôi có thể sử dụng các mảng PDL, b/c PDL lưu trữ các mảng của nó giống như C, chỉ sử dụng 4 byte cho mỗi phần tử. Tuy nhiên, tôi thấy rằng tốc độ cập nhật là excruciatingly chậm so với danh sách perl:

use PDL; 
use Benchmark qw/cmpthese/; 

my $N = 1_000_000; 
my @perl = (0 .. $N - 1); 
my $pdl = zeroes $N; 

cmpthese(-1,{ 
    perl => sub{ 
     $perl[int(rand($N))]++; 
    }, 
    pdl => sub{ 
     # note that I'm not even incrementing here just setting to 1 
     $pdl->set(int(rand($N)), 1); 
    } 
}); 

Returns:

  Rate pdl perl 
pdl 481208/s -- -87% 
perl 3640889/s 657% --  

Có ai biết làm thế nào để tăng pdl set() thực hiện, hoặc biết một mô-đun khác nhau có thể thực hiện điều này?

+1

có bạn nhìn các mô-đun perin tin sinh học? – AlfredoVR

Trả lời

8

Tôi không thể biết bạn sẽ nhận được loại hiệu suất nào, nhưng tôi khuyên bạn nên sử dụng hàm vec, được ghi lại here, để chia chuỗi thành các trường bit. Tôi đã thử nghiệm và thấy rằng Perl của tôi sẽ chịu đựng một chuỗi dài tối đa 500_000_000 ký tự. tương ứng với 125.000.000 giá trị 32 bit.

my $data = "\0" x 500_000_000; 
vec($data, 0, 32)++;   # Increment data[0] 
vec($data, 100_000_000, 32)++; # Increment data[100_000_000] 

Nếu điều này là không đủ thì có thể có điều gì đó trong việc xây dựng Perl kiểm soát giới hạn. Hoặc nếu bạn nghĩ rằng bạn có thể nhận được các lĩnh vực nhỏ hơn - nói đếm 16-bit - vec sẽ chấp nhận rộng lĩnh vực bất kỳ sức mạnh của 2 lên đến 32.

Edit: Tôi tin rằng giới hạn kích thước chuỗi có liên quan đến mức tối đa 2GB bộ làm việc riêng trên các quy trình Windows 32 bit. Nếu bạn đang chạy Linux hoặc có một perl 64-bit, bạn có thể may mắn hơn tôi.


tôi đã thêm vào chương trình benchmark của bạn như thế này

my $vec = "\0" x ($N * 4); 

cmpthese(-3,{ 
    perl => sub{ 
     $perl[int(rand($N))]++; 
    }, 
    pdl => sub{ 
     # note that I'm not even incrementing here just setting to 1 
     $pdl->set(int(rand($N)), 1); 
    }, 
    vec => sub { 
     vec($vec, int(rand($N)), 32)++; 
    }, 
}); 

cho những kết quả

  Rate pdl vec perl 
pdl 472429/s -- -76% -85% 
vec 1993101/s 322% -- -37% 
perl 3157570/s 568% 58% -- 

nên sử dụng vec là hai phần ba tốc độ của một mảng có nguồn gốc. Có lẽ đó là chấp nhận được.

2

PDL thắng khi các hoạt động có thể được tạo luồng, dường như nó không được tối ưu hóa để truy cập ngẫu nhiên và gán. Có lẽ ai đó có nhiều kiến ​​thức PDL hơn có thể giúp đỡ.

+0

Nó không phải là truy cập ngẫu nhiên mà là thời gian khởi động để khởi tạo các cấu trúc dữ liệu PDL. Tùy thuộc vào tính toán liên quan, PDL yêu cầu từ 100-1000 phần tử được xử lý trước khi phá vỡ ngay cả trong hoạt động với các hoạt động perl riêng. Với sự hỗ trợ của nó cho vòng lặp ngầm, một dòng mã PDL có thể thay thế nhiều vòng lặp vô hướng lồng nhau hoặc vòng danh sách trong perl đơn giản. – chm

+0

Bạn sẽ là người tốt nhất để biết, cảm ơn cho nhận xét. Chắc chắn có câu trả lời tốt hơn được đăng cho câu hỏi này bây giờ hơn tôi. :-) –

2

Packed::Array trên CPAN có thể hữu ích.

Đóng gói :: Array cung cấp lớp mảng số nguyên có dấu đóng gói. Mảng được xây dựng bằng cách sử dụng Packed :: Array chỉ có thể giữ các số nguyên đã ký khớp với số nguyên gốc nền tảng của bạn, nhưng chỉ nhận được nhiều bộ nhớ thực sự cần thiết để giữ các số nguyên đó. Vì vậy, đối với hệ thống 32 bit, thay vì lấy khoảng 20 byte cho mỗi mục nhập mảng, chúng chỉ mất 4.

+2

Có Tôi đã xem mô-đun này, cũng như 'Tie :: Array :: Gói',' Tie :: Array :: Đóng gói', 'Tie :: VecArray' và' Tie :: Array :: PackedC '. Thật không may là API 'tie' của Perl rất chậm và nhanh nhất (' Tie :: Array :: Packed') vẫn chậm hơn mười lần so với mảng gốc. – Borodin

7

Lệnh PDL bạn muốn là indadd. (Cảm ơn Chris Marshall, PDL Pumpking, vì đã chỉ ra điều đó cho tôi elsewhere.)

PDL được thiết kế cho những gì tôi gọi là các hoạt động "được vectơ hóa". So với các phép toán C, các hoạt động của Perl khá chậm, vì vậy bạn muốn giữ số lượng các lời gọi phương thức PDL ở mức tối thiểu, và có mỗi lời gọi thực hiện rất nhiều công việc. Ví dụ, điểm chuẩn này cho phép bạn chỉ định số lượng các bản cập nhật để thực hiện trong một lần đi (như một tham số dòng lệnh). Phía perl có để lặp, nhưng phía PDL chỉ thực hiện năm hoặc để gọi hàm:

use PDL; 
use Benchmark qw/cmpthese/; 

my $updates_per_round = shift || 1; 

my $N = 1_000_000; 
my @perl = (0 .. $N - 1); 
my $pdl = zeroes $N; 

cmpthese(-1,{ 
    perl => sub{ 
     $perl[int(rand($N))]++ for (1..$updates_per_round); 
    }, 
    pdl => sub{ 
     my $to_update = long(random($updates_per_round) * $N); 
     indadd(1,$to_update,$pdl); 
    } 
}); 

Khi tôi chạy này với một cuộc tranh cãi trong tổng số 1, tôi nhận được hiệu suất thậm chí còn tồi tệ hơn khi sử dụng set, đó là những gì tôi dự kiến:

$ perl script.pl 1 
      Rate pdl perl 
pdl 21354/s -- -98% 
perl 1061925/s 4873% -- 

Đó là rất nhiều điểm để tạo nên! Nhưng giữ trong đó. Nếu chúng ta làm 100 lần lặp mỗi vòng, chúng tôi nhận một sự cải tiến:

$ perl script.pl 100 
     Rate pdl perl 
pdl 16906/s -- -18% 
perl 20577/s 22% -- 

Và với 10.000 cập nhật mỗi vòng, PDL nhanh hơn so với Perl bởi một yếu tố của bốn:

$ perl script.pl 10000 
     Rate perl pdl 
perl 221/s -- -75% 
pdl 881/s 298% -- 

PDL tiếp tục thực hiện nhanh hơn khoảng 4x hơn Perl đơn giản cho các giá trị lớn hơn.

Lưu ý rằng hiệu suất của PDL có thể làm suy giảm cho các hoạt động phức tạp hơn. Điều này là do PDL sẽ phân bổ và phá bỏ các vùng làm việc lớn nhưng tạm thời cho các hoạt động trung gian. Trong trường hợp đó, bạn có thể cân nhắc sử dụng Inline::Pdlpp. Tuy nhiên, đó không phải là công cụ của người mới bắt đầu, vì vậy đừng nhảy đến đó cho đến khi bạn đã xác định nó thực sự là điều tốt nhất cho bạn.

Một thay thế cho tất cả điều này là sử dụng Inline::C như vậy:

use PDL; 
use Benchmark qw/cmpthese/; 

my $updates_per_round = shift || 1; 

my $N = 1_000_000; 
my @perl = (0 .. $N - 1); 
my $pdl = zeroes $N; 
my $inline = pack "d*", @perl; 
my $max_PDL_per_round = 5_000; 

use Inline 'C'; 

cmpthese(-1,{ 
    perl => sub{ 
     $perl[int(rand($N))]++ for (1..$updates_per_round); 
    }, 
    pdl => sub{ 
     my $to_update = long(random($updates_per_round) * $N); 
     indadd(1,$to_update,$pdl); 
    }, 
    inline => sub{ 
     do_inline($inline, $updates_per_round, $N); 
    }, 
}); 


__END__ 

__C__ 

void do_inline(char * packed_data, int N_updates, int N_data) { 
    double * actual_data = (double *) packed_data; 
    int i; 
    for (i = 0; i < N_updates; i++) { 
     int index = rand() % N_data; 
     actual_data[index]++; 
    } 
} 

Đối với tôi, hàm Inline liên tục đánh bại cả hai Perl và PDL. Đối với các giá trị lớn của $updates_per_round, nói 1.000, tôi nhận được Inline::C của phiên bản khoảng 5x nhanh hơn so với Perl tinh khiết và giữa 1.2x và 2x nhanh hơn so với PDL. Ngay cả khi $updates_per_round chỉ là 1, trong đó Perl đánh bại PDL một cách thủ công, mã Inline nhanh hơn 2.5 lần so với mã Perl.

Nếu đây là tất cả bạn cần thực hiện, tôi khuyên bạn nên sử dụng Inline::C.

Nhưng nếu bạn cần thực hiện nhiều thao tác với dữ liệu của mình, bạn nên gắn bó với PDL về sức mạnh, tính linh hoạt và hiệu suất của nó. Xem bên dưới để biết cách bạn có thể sử dụng vec() với dữ liệu PDL.

4

PDL::set()PDL::get() được dự định hỗ trợ học tập nhiều hơn bất kỳ thứ gì khác. Chúng tạo thành cách tối ưu để truy cập các biến PDL. Bạn sẽ tốt hơn rất nhiều khi sử dụng một số quy trình truy cập hàng loạt được tích hợp sẵn. Bản thân hàm tạo PDL chấp nhận danh sách Perl:

$pdl = pdl(@list) 

và có tốc độ khá nhanh. Bạn cũng có thể tải dữ liệu của mình trực tiếp từ tệp ASCII bằng cách sử dụng PDL::rcols hoặc từ tệp nhị phân bằng một trong nhiều thói quen IO.Nếu bạn có các dữ liệu như là một chuỗi được đóng gói theo thứ tự máy, bạn thậm chí có thể được truy cập vào bộ nhớ PDL trực tiếp:

$pdl = PDL->new_from_specification(long,$elements); 
$dr = $pdl->get_dataref; 
$$dr = get_my_packed_string(); 
$pdl->upd_data; 

Cũng lưu ý rằng bạn có thể "có bánh và ăn nó quá" bằng cách sử dụng đối tượng PDL để giữ mảng lại số nguyên, PDL tính toán (chẳng hạn như indadd) cho thao tác quy mô lớn của dữ liệu, mà còn sử dụng vec() trực tiếp trên dữ liệu PDL như là một chuỗi mà bạn có thể nhận được thông qua get_dataref phương pháp:

vec($$dr,int(rand($N)),32); 

Bạn sẽ cần phải bswap4 dữ liệu nếu bạn đang sử dụng hệ thống nhỏ gọn:

$pdl->bswap4; 
$dr = $pdl->get_dataref; 
vec($$dr,int(rand($N)),32)++; 
$pdl->upd_data; 
$pdl->bswap4; 

Et, thì đấy!

2

kể từ khi đã sử dụng nguyên, mà nên là ok để sử dụng với nhiễm sắc thể thử loại này

use PDL; 
use Benchmark qw/cmpthese/; 

my $N = 1_000_000; 
my @perl; 
@perl = (0 .. $N - 1); 
my $pdl; 
$pdl = (zeroes($N)); 

cmpthese(-1,{ 
perl => sub{ 
    $perl[int(rand($N))]++; 
}, 
pdl2 => sub{ 
    # note that I'm not even incrementing here just setting to 1 
    $pdl->set(int(rand($N)), 1); 
    $pdl2 = pack "w*", $pdl; 
} 
}); 

và đặt ra tôi nhận được từ này là ...

  Rate pdl2 perl 
pdl2 46993/s -- -97% 
perl 1641607/s 3393% -- 

trong đó cho thấy một lớn hiệu suất khác biệt từ khi tôi lần đầu tiên dùng thử mã này với số thêm vào 2 xu của tôi, tôi nhận được

  Rate pdl perl 
pdl 201972/s -- -86% 
perl 1472123/s 629% -- 
0

câu trả lời trên của tôi có thể là vô giá trị ... này có thể giúp tho ..

use PDL; 
$x = sequence(45000,45000); 

bây giờ mà wont work trừ khi bạn có 16 gb ram và sử dụng

$PDL::BIGPDL=1; 
Các vấn đề liên quan