StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I tackled the problem writing my own implementation before looking at your code. My first attempt was very similar to what you already had :)</p> <pre><code>%# some parameters NUM_ITER = 100000; %# number of simulations to run DRAW_SZ = 12; %# number of cards we are dealing SET_SZ = 3; %# number of cards in a set FEAT_NUM = 4; %# number of features (symbol,color,number,shading) FEAT_SZ = 3; %# number of values per feature (eg: red/purple/green, ...) %# cards features features = { 'oval' 'squiggle' 'diamond' ; %# symbol 'red' 'purple' 'green' ; %# color 'one' 'two' 'three' ; %# number 'solid' 'striped' 'open' %# shading }; fIdx = arrayfun(@(k) grp2idx(features(k,:)), 1:FEAT_NUM, 'UniformOutput',0); %# list of all cards. Each card: [symbol,color,number,shading] [W X Y Z] = ndgrid(fIdx{:}); cards = [W(:) X(:) Y(:) Z(:)]; %# all possible sets: choose 3 from 12 setsInd = nchoosek(1:DRAW_SZ,SET_SZ); %# count number of valid sets in random draws of 12 cards counterValidSet = 0; for i=1:NUM_ITER %# pick 12 cards ord = randperm( size(cards,1) ); cardsDrawn = cards(ord(1:DRAW_SZ),:); %# check for valid sets: features are all the same or all different for s=1:size(setsInd,1) %# set of 3 cards set = cardsDrawn(setsInd(s,:),:); %# check if set is valid count = arrayfun(@(k) numel(unique(set(:,k))), 1:FEAT_NUM); isValid = (count==1|count==3); %# increment counter if isValid counterValidSet = counterValidSet + 1; break %# break early if found valid set among candidates end end end %# ratio of found-to-notfound fprintf('Size=%d, Set=%d, NoSet=%d, Set:NoSet=%g\n', ... DRAW_SZ, counterValidSet, (NUM_ITER-counterValidSet), ... counterValidSet/(NUM_ITER-counterValidSet)) </code></pre> <p>After using the Profiler to discover hot spots, some improvement can be made mainly by early-break'ing out of loops when possible. The main bottleneck is the call to the UNIQUE function. Those two lines above where we check for valid sets can be rewritten as:</p> <pre><code>%# check if set is valid isValid = true; for k=1:FEAT_NUM count = numel(unique(set(:,k))); if count~=1 && count~=3 isValid = false; break %# break early if one of the features doesnt meet conditions end end </code></pre> <p>Unfortunately, the simulation is still slow for larger simulation. Thus my next solution is a vectorized version, where for each iteration, we build a single matrix of all possible sets of 3 cards from the hand of 12 drawn cards. For all these candidate sets, we use logical vectors to indicate what feature is present, thus avoiding the calls to UNIQUE/NUMEL (we want features all the same or all different on each card of the set).</p> <p>I admit that the code is now less readable and harder to follow (thus I posted both versions for comparison). The reason being that I tried to optimize the code as much as possible, so that each iteration-loop is fully vectorized. Here is the final code:</p> <pre><code>%# some parameters NUM_ITER = 100000; %# number of simulations to run DRAW_SZ = 12; %# number of cards we are dealing SET_SZ = 3; %# number of cards in a set FEAT_NUM = 4; %# number of features (symbol,color,number,shading) FEAT_SZ = 3; %# number of values per feature (eg: red/purple/green, ...) %# cards features features = { 'oval' 'squiggle' 'diamond' ; %# symbol 'red' 'purple' 'green' ; %# color 'one' 'two' 'three' ; %# number 'solid' 'striped' 'open' %# shading }; fIdx = arrayfun(@(k) grp2idx(features(k,:)), 1:FEAT_NUM, 'UniformOutput',0); %# list of all cards. Each card: [symbol,color,number,shading] [W X Y Z] = ndgrid(fIdx{:}); cards = [W(:) X(:) Y(:) Z(:)]; %# all possible sets: choose 3 from 12 setsInd = nchoosek(1:DRAW_SZ,SET_SZ); %# optimizations: some calculations taken out of the loop ss = setsInd(:); set_sz2 = numel(ss)*FEAT_NUM/SET_SZ; col = repmat(1:set_sz2,SET_SZ,1); col = FEAT_SZ.*(col(:)-1); M = false(FEAT_SZ,set_sz2); %# progress indication %#hWait = waitbar(0./NUM_ITER, 'Simulation...'); %# count number of valid sets in random draws of 12 cards counterValidSet = 0; for i=1:NUM_ITER %# update progress %#waitbar(i./NUM_ITER, hWait); %# pick 12 cards ord = randperm( size(cards,1) ); cardsDrawn = cards(ord(1:DRAW_SZ),:); %# put all possible sets of 3 cards next to each other set = reshape(cardsDrawn(ss,:)',[],SET_SZ)'; set = set(:); %# check for valid sets: features are all the same or all different M(:) = false; %# if using PARFOR, it will complain about this M(set+col) = true; isValid = all(reshape(sum(M)~=2,FEAT_NUM,[])); %# increment counter if there is at least one valid set in all candidates if any(isValid) counterValidSet = counterValidSet + 1; end end %# ratio of found-to-notfound fprintf('Size=%d, Set=%d, NoSet=%d, Set:NoSet=%g\n', ... DRAW_SZ, counterValidSet, (NUM_ITER-counterValidSet), ... counterValidSet/(NUM_ITER-counterValidSet)) %# close progress bar %#close(hWait) </code></pre> <p>If you have the Parallel Processing Toolbox, you can easily replace the plain FOR-loop with a parallel PARFOR (you might want to move the initialization of the matrix <code>M</code> inside the loop again: replace <code>M(:) = false;</code> with <code>M = false(FEAT_SZ,set_sz2);</code>)</p> <p>Here are some sample outputs of 50000 simulations (PARFOR used with a pool of 2 local instances):</p> <pre><code>» tic, SET_game2, toc Size=12, Set=48376, NoSet=1624, Set:NoSet=29.7882 Elapsed time is 5.653933 seconds. » tic, SET_game2, toc Size=15, Set=49981, NoSet=19, Set:NoSet=2630.58 Elapsed time is 9.414917 seconds. </code></pre> <p>And with a million iterations (PARFOR for 12, no-PARFOR for 15):</p> <pre><code>» tic, SET_game2, toc Size=12, Set=967516, NoSet=32484, Set:NoSet=29.7844 Elapsed time is 110.719903 seconds. » tic, SET_game2, toc Size=15, Set=999630, NoSet=370, Set:NoSet=2701.7 Elapsed time is 372.110412 seconds. </code></pre> <p>The odds ratio agree with the results reported by <a href="http://norvig.com/SET.html" rel="nofollow">Peter Norvig</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload