Я решил проблему, написав свою собственную реализацию, прежде чем смотреть ваш код. Моя первая попытка была очень похожа на то, что у вас уже было :)
%# 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))
После использования Профилировщика для обнаружения горячих точек некоторые улучшения могут быть достигнуты, главным образом, за счет раннего выхода из циклов, когда это возможно. Основным узким местом является вызов функции UNIQUE. Те две строки выше, где мы проверяем допустимые наборы, можно переписать как:
%# 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
К сожалению, симуляция все еще медленная для более крупной симуляции. Таким образом, мое следующее решение — это векторизованная версия, где для каждой итерации мы строим единую матрицу всех возможных наборов из 3 карт из руки из 12 вытянутых карт. Для всех этих наборов-кандидатов мы используем логические векторы, чтобы указать, какая функция присутствует, избегая, таким образом, вызовов UNIQUE/NUMEL (мы хотим, чтобы на каждой карте набора были все одинаковые или все разные функции).
Я признаю, что код стал менее читаемым и трудным для понимания (поэтому я выложил обе версии для сравнения). Причина в том, что я пытался максимально оптимизировать код, чтобы каждый итерационный цикл был полностью векторизован. Вот окончательный код:
%# 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)
Если у вас есть Parallel Processing Toolbox, вы можете легко заменить простой цикл FOR параллельным PARFOR (вы можете снова переместить инициализацию матрицы M внутрь цикла: замените M(:) = false; на M = false(FEAT_SZ,set_sz2);)
Вот некоторые примеры результатов 50000 симуляций (используется PARFOR с пулом из 2 локальных экземпляров):
» 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.
И с миллионом итераций (PARFOR на 12, no-PARFOR на 15):
» 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.
Отношение шансов согласуется с результатами, представленными Петером Норвигом.
person
Amro
schedule
11.07.2011
