Efficient construction of positive and negative matrix

2 次查看（过去 30 天）
Adam Shaw
Adam Shaw 2022-11-6
编辑： Bruno Luong 2022-11-7
I am trying to efficiently constuct a vector along the lines of the following paradigmatic code:
% Setup
N = 20;
B = de2bi((1:2^N)-1,N);
P = [1 3 8 18]; % Some random integers from 1 to N
% Actual code to optimize
tic;
C = 2*B-1;
D = C(:,P);
R = prod(D,2); % result
toc;
Essentially, the desired result is to construct a binary positive/negative vector, which is negative when an odd number of bits within a given subset (P) are 0, and is positive otherwise. Any help would be appreciated - my implementation here is fine, but only works decently up to N in the low to mid 20s. I have tried tricks with bitand, bitset, etc but have not found anything more efficient on my own.
I'll add that ultimately what I actually want is to take the sum of this vector R with another vector, A, like so:
A = rand(2^N,1);
R2 = sum(R.*A); % Actual result I ultimately want
This is similar to a recent question I asked here (https://www.mathworks.com/matlabcentral/answers/1826493-efficient-multiplication-by-large-structured-matrix-of-ones-and-zeros?s_tid=srchtitle), but is made more complicated because the vector R is positive/negative instead of binary, but perhaps similar tricks apply. Any solution which also addresses constructing R2 would be very appreciated.
  4 个评论
显示 2更早的评论
Adam Shaw
Adam Shaw 2022-11-6
Thanks for switching the dec2bin to de2bi, sorry I was a bit lazy rewriting the code here and let that slip through!

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Steven Lord
Steven Lord 2022-11-6
Ran in:
Instead of creating a very large binary matrix in order to extract a handful of columns, why not use bitget?
x = (0:7).'
x = 8×1
0 1 2 3 4 5 6 7
b = [bitget(x, 3) bitget(x, 2) bitget(x, 1)]
b = 8×3
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
  1 个评论
Adam Shaw
Adam Shaw 2022-11-7
At least on my machine, this is slower than the method based on using the pregenerated binary matrix (which is assumed to be given, and not part of the timing).

请先登录，再进行评论。

Bruno Luong
Bruno Luong 2022-11-7
编辑：Bruno Luong 2022-11-7
Ran in:
If your B is given then the 2nd method in this script is faster
P = [1 3 8 18];
N = 20;
B = fliplr(dec2bin((1:2^N)-1,N)-'0');
tic
C = 2*B-1;
D = C(:,P);
R2 = prod(D,2);
toc
Elapsed time is 0.054876 seconds.
tic
x = zeros(N,1);
x(P) = 2;
R3 = 1-mod(B*x,4);
toc
Elapsed time is 0.015032 seconds.
isequal(R2,R3)
ans = logical
1

类别

在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by