Câu hỏi liên quan

0 Phiếu
0 Câu trả lời
0 Phiếu
4 Câu trả lời
0 Phiếu
0 Câu trả lời
+1 Phiếu
1 Trả lời
Đã hỏi 24/4/2016 bởi Guvkocik (350 điểm)

MATLAB lặp lại số dựa trên một vector độ dài


0 Phiếu
Đã hỏi 23/5/2016 bởi bsEbsen (370 điểm)
Có một cách vectorised để làm những điều sau đây? (thể hiện bởi một ví dụ):
input_lengths = [ 1 1 1 4       3     2   1 ]
result =        [ 1 2 3 4 4 4 4 5 5 5 6 6 7 ]
tôi có khoảng cách trong các input_lengths vì vậy, nó rất dễ dàng để hiểu làm thế nào kết quả thu được vectơ kết quả là chiều dài: sum(lengths). Tôi đang tính toán result bằng cách sử dụng các vòng lặp:
result = ones(1, sum(input_lengths ));
counter = 1;
for i = 1:length(input_lengths)
    start_index = counter;
    end_index = counter + input_lengths (i) - 1;
    result(start_index:end_index) = i;
    counter = end_index + 1;
end
EDIT: tôi cũng có thể làm điều này bằng cách sử dụng arrayfun (mặc dù đó là không chính xác là một chức năng vectorised)
cell_result = arrayfun(@(x) repmat(x, 1, input_lengths(x)), 1:length(input_lengths), 'UniformOutput', false);
cell_result : {[1], [2], [3], [4 4 4 4], [5 5 5], [6 6], [7]}
result = [cell_result{:}];
result : [ 1 2 3 4 4 4 4 5 5 5 6 6 7 ]

6 Câu trả lời

0 Phiếu
Đã trả lời 03/6/2016 bởi GurAdded (480 điểm)
được bình chọn là câu trả lời hay nhất 04/6/2016 bởi VfVuoso
 
Câu trả lời hay nhất
Tôi tìm kiếm một giải pháp thanh lịch, và tôi nghĩ rằng David giải pháp là một khởi đầu tốt. Những gì tôi có trong tâm trí là rằng một trong những có thể tạo ra các danh mục nơi để thêm một từ trước nguyên tố. Cho rằng, nếu chúng tôi tính toán cumsum input vector, chúng tôi nhận được:
cumsum(input_lengths)
ans = 1     2     3     7    10    12    13
đây là chỉ số kết thúc của chuỗi số giống hệt nhau. Đó không phải là những gì chúng tôi muốn, do đó, chúng tôi lật véc tơ hai lần để có được sự khởi đầu:
fliplr(sum(input_lengths)+1-cumsum(fliplr(input_lengths)))
ans = 1     2     3     4     8    11    13
đây là lừa. Bạn lật véc tơ, cumsum để có được kết thúc của vector lộn, và sau đó lật lại; nhưng bạn phải trừ vector từ tổng chiều dài output vector (+ 1 vì chỉ số bắt đầu lúc 1) bởi vì cumsum áp dụng trên vector lộn. Một khi bạn đã làm điều này, nó là rất đơn giản, bạn chỉ cần đặt 1 tại tính toán chỉ số và 0 ở nơi khác và cumsum nó:
idx_begs = fliplr(sum(input_lengths)+1-cumsum(fliplr(input_lengths)));
result = zeros(1,sum(input_lengths));
result(idx_begs) = 1;
result = cumsum(result);
EDIT đầu tiên, xin vui lòng có một cái nhìn tại Luis Mendo giải pháp , nó là rất gần gũi với tôi nhưng đơn giản hơn và nhanh hơn một chút (tôi sẽ không chỉnh sửa tôi ngay cả khi nó là rất gần). Tôi nghĩ rằng vào ngày này, đây là giải pháp nhanh nhất từ tất cả. Thứ hai, trong khi nhìn vào những người khác giải pháp, tôi đã thực hiện thành một one-liner, một chút khác nhau từ giải pháp ban đầu của tôi và khác one-liner. OK, điều này sẽ không rất có thể đọc được, vì vậy, mất một hơi thở:
result = cumsum( full(sparse(cumsum([1,input_lengths(1:end-1)]), ...
ones(1,length(input_lengths)), 1, sum(input_lengths),1)) );
cắt trên hai dòng. OK bây giờ chúng ta hãy giải thích nó. Phần tương tự như là để xây dựng các mảng của các chỉ số tăng value của các yếu tố hiện tại từ đâu. Tôi sử dụng các giải pháp của Luis Mendo cho điều đó. Để xây dựng trong một dòng vector giải pháp, ở đây tôi sử dụng một thực tế rằng đó là trong thực tế là một đại diện thưa thớt của vector nhị phân, một trong chúng ta sẽ cumsum cuối. Vector thưa thớt này là xây dựng bằng cách sử dụng của chúng tôi tính toán chỉ số vector như x vị trí, một vector 1 là vị trí y và 1 như là value để đặt tại các địa điểm. Đối số thứ tư được trao cho chính xác tổng kích thước của vector (quan trọng nếu element input_lengths, cuối cùng không phải là 1). Sau đó chúng tôi nhận được đại diện đầy đủ của vector thưa thớt này (khác kết quả là một vector thưa thớt với không có nguyên tố trống) và chúng tôi có thể cumsum. Có là không có sử dụng giải pháp này khác hơn để cung cấp một giải pháp cho vấn đề này. Một điểm chuẩn có thể hiển thị nó là chậm hơn so với giải pháp ban đầu của tôi, bởi vì một tải nặng hơn bộ nhớ.
Đã bình luận 04/6/2016 bởi VfVuoso (110 điểm)
code 'cell_result' của bạn không làm việc, hoặc.
0 Phiếu
Đã trả lời 30/5/2016 bởi Hgv9869 (150 điểm)
More of a comment than anything, but I did some tests. I tried a for loop, and an arrayfun, and I tested your for loop and arrayfun version. Your for loop was the fastest. I think this is because it is simple, and allows the JIT compilation to do the most optimisation. I am using Matlab, octave might be different. And the timing:
Solution:     With JIT   Without JIT  
Sam for       0.74       1.22    
Sam arrayfun  2.85       2.85    
My for        0.62       2.57    
My arrayfun   1.27       3.81    
Divakar       0.26       0.28    
Bentoy        0.07       0.06    
Daniel        0.15       0.16
Luis Mendo    0.07       0.06
So Bentoy's code is really fast, and Luis Mendo's is almost exactly the same speed. And I rely on JIT way too much!
And the code for my attempts
clc,clear
input_lengths = randi(20,[1 10000]);
% My for loop
tic()
C=cumsum(input_lengths);
D=diff(C);
results=zeros(1,C(end));
results(1,1:C(1))=1;
for i=2:length(input_lengths)
    results(1,C(i-1)+1:C(i))=i*ones(1,D(i-1));
end
toc()
tic()
A=arrayfun(@(i) i*ones(1,input_lengths(i)),1:length(input_lengths),'UniformOutput',false);
R=[A{:}];
toc()
Đã bình luận 31/5/2016 bởi answer (470 điểm)
không chắc chắn rằng một function "vectorized" sẽ nhanh hơn một cho loop ở đây... bạn có thể test với arrayfun và xem... cũng nhìn thấy ở đây http://stackoverflow.com/questions/ 12522888 /arrayfun-can-be-significantly-slower-than-an-explicit-loop-in-matlab-why
0 Phiếu
Đã trả lời 03/6/2016 bởi micki (507,110 điểm)
Một phiên bản đầy đủ vectorized:
selector=bsxfun(@le,[1:max(input_lengths)]',input_lengths);
V=repmat([1:size(selector,2)],size(selector,1),1);
result=V(selector);
nhược điểm là, sử dụng bộ nhớ O(numel(input_lengths)*max(input_lengths))
Đã bình luận 03/6/2016 bởi Sha_Hier (100 điểm)
Của bạn 'cho' loop không có vẻ làm việc. 'sum(input_lengths)' là lớn hơn 'length(input_lengths)' để 'input_lengths(i)' cho một error cho tôi (Matlab).
0 Phiếu
Đã trả lời 03/6/2016 bởi Louro (500 điểm)
result = zeros(1,sum(input_lengths));
result(cumsum([1 input_lengths(1:end-1)])) = 1;
result = cumsum(result);
điều này nên khá nhanh. Và sử dụng bộ nhớ tối thiểu nhất có thể. Một phiên bản tối ưu hóa các mã ở trên, do Bentoy13 (xem của ông rất chi tiết điểm chuẩn ):
result = zeros(1,sum(input_lengths));
result(1) = 1;
result(1+cumsum(input_lengths(1:end-1))) = 1;
result = cumsum(result);
+1 Phiếu
Đã trả lời 03/6/2016 bởi YourInte (600 điểm)
result = zeros(1,sum(input_lengths));
result(cumsum([1 input_lengths(1:end-1)])) = 1;
result = cumsum(result);
điều này nên khá nhanh. Và sử dụng bộ nhớ tối thiểu nhất có thể. Một phiên bản tối ưu hóa các mã ở trên, do Bentoy13 (xem của ông rất chi tiết điểm chuẩn ):
result = zeros(1,sum(input_lengths));
result(1) = 1;
result(1+cumsum(input_lengths(1:end-1))) = 1;
result = cumsum(result);
0 Phiếu
Đã trả lời 03/6/2016 bởi yva_Link (820 điểm)

điểm chuẩn của tất cả các giải pháp

theo trước điểm chuẩn , tôi nhóm tất cả các giải pháp được đưa ra ở đây trong một script và chạy nó một vài giờ cho một chuẩn mực. Tôi đã làm điều này bởi vì tôi nghĩ rằng nó là tốt để xem những gì là hiệu suất của mỗi giải pháp đề xuất với chiều dài cddf 500 5c8b8440fde07ee037ee50130 như là tham số - ý định của tôi không ở đây để đặt xuống chất lượng của một trong trước đó cho biết thêm thông tin về tác dụng của JIT. Hơn nữa, và mọi người tham gia có vẻ đồng ý với điều đó, khá tốt công việc được thực hiện trong tất cả các câu trả lời, do đó, bài viết tuyệt vời này xứng đáng là một bài luận. Tôi sẽ không đăng code script ở đây, điều này là khá dài và rất uninteresting. procedure điểm chuẩn là chạy mỗi giải pháp cho một tập hợp của các độ dài khác nhau của 5c8b8440fde07ee037ee50130 500 cddf vector: 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000, 500000, 1000000. Cho mỗi 500 5c8b8440fde07ee037ee50130 cddf chiều dài, tôi đã tạo ra một ngẫu nhiên 5c8b8440fde07ee037ee50130 500 cddf vector dựa trên luật Poisson với các tham số 0.8 (để tránh lớn giá trị):
input_lengths = round(-log(1-rand(1,ILen(i)))/poisson_alpha)+1;
cuối cùng, tôi trung bình thời gian tính toán qua 100 chạy mỗi 5c8b8440fde07ee037ee50130 500 cddf chiều dài. Tôi đã chạy script trên máy tính máy tính xách tay của tôi (core I7) với Matlab R2013b; JIT được kích hoạt. Và đây là kết quả plotted (xin lỗi, màu đường), trong một quy mô đăng nhập-đăng nhập (trục x: 5c8b8440fde07ee037ee50130 500 cddf chiều dài; trục: tính toán thời gian bằng giây): Benchmark 100 trials, all solutions vì vậy Luis Mendo là người chiến thắng rõ ràng, congrats! Cho bất cứ ai muốn kết quả số và/hoặc muốn replot họ, ở đây chúng (cắt table thành 2 phần và ước chừng 3 chữ số cho một hiển thị tốt hơn):
N                   10          20          50          100         200         500         1e+03       2e+03
-------------------------------------------------------------------------------------------------------------
OP's for-loop       8.02e-05    0.000133    0.00029     0.00036     0.000581    0.00137     0.00248     0.00542 
OP's arrayfun       0.00072     0.00117     0.00255     0.00326     0.00514     0.0124      0.0222      0.047
Daniel              0.000132    0.000132    0.000148    0.000118    0.000126    0.000325    0.000397    0.000651
Divakar             0.00012     0.000114    0.000132    0.000106    0.000115    0.000292    0.000367    0.000641
David's for-loop    9.15e-05    0.000149    0.000322    0.00041     0.000654    0.00157     0.00275     0.00622
David's arrayfun    0.00052     0.000761    0.00152     0.00188     0.0029      0.00689     0.0122      0.0272
Luis Mendo          4.15e-05    4.37e-05    4.66e-05    3.49e-05    3.36e-05    4.37e-05    5.87e-05    0.000108
Bentoy13's cumsum   0.000104    0.000107    0.000111    7.9e-05     7.19e-05    8.69e-05    0.000102    0.000165
Bentoy13's sparse   8.9e-05     8.82e-05    9.23e-05    6.78e-05    6.44e-05    8.61e-05    0.000114    0.0002
Luis Mendo's optim. 3.99e-05    3.96e-05    4.08e-05    4.3e-05     4.61e-05    5.86e-05    7.66e-05    0.000111
N                   5e+03       1e+04       2e+04       5e+04       1e+05       2e+05       5e+05       1e+06
-------------------------------------------------------------------------------------------------------------
OP's for-loop       0.0138      0.0278      0.0588      0.16        0.264       0.525       1.35        2.73
OP's arrayfun       0.118       0.239       0.533       1.46        2.42        4.83        12.2        24.8
Daniel              0.00105     0.0021      0.00461     0.0138      0.0242      0.0504      0.126       0.264
Divakar             0.00127     0.00284     0.00655     0.0203      0.0335      0.0684      0.185       0.396
David's for-loop    0.015       0.0286      0.065       0.175       0.3         0.605       1.56        3.16
David's arrayfun    0.0668      0.129       0.299       0.803       1.33        2.64        6.76        13.6
Luis Mendo          0.000236    0.000446    0.000863    0.00221     0.0049      0.0118      0.0299      0.0637
Bentoy13's cumsum   0.000318    0.000638    0.00107     0.00261     0.00498     0.0114      0.0283      0.0526
Bentoy13's sparse   0.000414    0.000774    0.00148     0.00451     0.00814     0.0191      0.0441      0.0877
Luis Mendo's optim. 0.000224    0.000413    0.000754    0.00207     0.00353     0.00832     0.0216      0.0441
Ok, tôi đã thêm một giải pháp cho danh sách... Tôi không thể ngăn bản thân mình để tối ưu hóa các giải pháp tốt nhất xa của Luis Mendo. Không có tín dụng cho rằng, đó là chỉ cần một biến thể từ Luis Mendo, tôi sẽ giải thích sau đó. Rõ ràng, các giải pháp bằng cách sử dụng arrayfun là rất tốn thời gian. Các giải pháp bằng cách sử dụng một rõ ràng cho loop được nhanh hơn, nhưng vẫn còn chậm so với những người khác giải pháp. Vì vậy, Yeah, vectorizing vẫn là một lựa chọn chính cho việc tối ưu hóa một kịch bản Matlab. Benchmark 1000 trials, best solutions (No table here, unless you really want to, it's quite the same numbers as before) As it was remarked, the solution by Daniel is a little faster than the one by Divakar because it seems that the use of bsxfun with @times is slower than using repmat. Still, they are 10 times faster than for-loop solutions: clearly, vectorizing in Matlab is a good thing. The solutions of Bentoy13 and Luis Mendo are very close; the first one uses more instructions, but the second one uses an extra allocation when concatenating 1 to cumsum(input_lengths(1:end-1)). And that's why we see that Bentoy13's solution tends to be a bit faster with big input lengths (above 5.10^5), because there is no extra allocation. From this consideration, I've made an optimized solution where there is no extra allocation; here is the code (Luis Mendo can put this one in his answer if he wants to :) ):
result = zeros(1,sum(input_lengths));
result(1) = 1;
result(1+cumsum(input_lengths(1:end-1))) = 1;
result = cumsum(result);
Any comment for improvement is welcome.

ToughDev Q&A là gì?

Trang web hỏi đáp cho các bạn đam mê lập trình, phát triển phần mềm và các vấn đề kỹ thuật khác. Với sự giúp đỡ của bạn, chúng tôi hy vọng sẽ xây dựng thành công một thư viện đầy đủ các câu hỏi và trả lời về tất cả các vấn đề có liên quan đến lập trình!







...