{"id":43,"date":"2006-06-28T06:26:40","date_gmt":"2006-06-28T11:26:40","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=43"},"modified":"2017-04-25T11:13:58","modified_gmt":"2017-04-25T16:13:58","slug":"inverse-mapping-update","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2006\/06\/28\/inverse-mapping-update\/","title":{"rendered":"Inverse Mapping (update)"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>In a follow up comment to the <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=41\">inverse mapping post<\/a>, Lucio noted that <tt>loopFR<\/tt> could be fully vectorized and he is right.  Rather than update that post directly, I thought I republish the loop-free code\r\n         here and compare times again.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#2\">Recap the Problem<\/a><\/li>\r\n         <li><a href=\"#3\">Sample Input and Results<\/a><\/li>\r\n         <li><a href=\"#5\">Algorithms<\/a><\/li>\r\n         <li><a href=\"#8\">Time the New Algorithm and Retime the Former Ones<\/a><\/li>\r\n         <li><a href=\"#9\">Timing Results<\/a><\/li>\r\n         <li><a href=\"#10\">Comments<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>Tidy up to start.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">clear\r\nformat <span style=\"color: #A020F0\">short<\/span> <span style=\"color: #A020F0\">g<\/span><\/pre><h3>Recap the Problem<a name=\"2\"><\/a><\/h3>\r\n   <h3>Sample Input and Results<a name=\"3\"><\/a><\/h3>\r\n   <p>Supppose array <tt>a<\/tt> contains values that we expect to see in another array, <tt>Minit<\/tt>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">a = [1 3 5 7 8]\r\nMinit = [1 3 5; <span style=\"color: #0000FF\">...<\/span>\r\n    3 5 7; <span style=\"color: #0000FF\">...<\/span>\r\n    3 7 8]<\/pre><pre style=\"font-style:oblique\">a =\r\n     1     3     5     7     8\r\nMinit =\r\n     1     3     5\r\n     3     5     7\r\n     3     7     8\r\n<\/pre><p>Let's build a replacement matrix for <tt>Minit<\/tt> in which its values are replaced with their indices in the list <tt>a<\/tt>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">Mwanted = [1 2 3; <span style=\"color: #0000FF\">...<\/span>\r\n     2 3 4; <span style=\"color: #0000FF\">...<\/span>\r\n     2 4 5]<\/pre><pre style=\"font-style:oblique\">Mwanted =\r\n     1     2     3\r\n     2     3     4\r\n     2     4     5\r\n<\/pre><h3>Algorithms<a name=\"5\"><\/a><\/h3>\r\n   <p>We previously compared these algorithms:<\/p>\r\n   <div>\r\n      <ul>\r\n         <li>loop (via <tt>loopFR<\/tt>)\r\n         <\/li>\r\n         <li><tt>ismember<\/tt><\/li>\r\n         <li><tt>histc<\/tt><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>Here's <tt>loopFR<\/tt>, for reference:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">dbtype <span style=\"color: #A020F0\">loopFR<\/span><\/pre><pre style=\"font-style:oblique\">\r\n1     function M1 = loopFR(M,A)\r\n2     % loopFR replaces M with its indices from A.\r\n3     \r\n4     % First set up the inverse mapping array.  Initialize it to zero, and the\r\n5     % size is the maximum number the array.  Note that I get away with this\r\n6     % here because all of my numbers in both A and M are positive integers.\r\n7     imap = zeros(1,max(A));  % inverse mapping array\r\n8     % Now fill the inverse map, but placing in the location specified in each\r\n9     % element of A, the index of that element in A.\r\n10    % If A = [1 5 4], then imap = [1 0 0 3 2].\r\n11    imap(A) = 1:length(A);  \r\n12    M1 = M;\r\n13    for k = 1:numel(M)\r\n14        M1(k) = imap(M(k));\r\n15    end\r\n<\/pre><p>and let's now add the fully vectorized version, <tt>vecIM<\/tt> to our comparison.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">type <span style=\"color: #A020F0\">vecIM<\/span><\/pre><pre style=\"font-style:oblique\">\r\nfunction M1 = vecIM(M,a) \r\n%vecIM Inverse mapping. \r\nimap(a) = 1:length(a);\r\nM1 = imap(M);\r\n\r\n<\/pre><h3>Time the New Algorithm and Retime the Former Ones<a name=\"8\"><\/a><\/h3><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">N = [1 10 100 1000 10000 100000];  <span style=\"color: #228B22\">% repetitions to test<\/span>\r\nt = zeros(length(N),4); <span style=\"color: #228B22\">% set up the timing collection array<\/span>\r\n<span style=\"color: #0000FF\">for<\/span> n = 1:length(N)\r\n    <span style=\"color: #228B22\">% Make a larger matrix to search.<\/span>\r\n    <span style=\"color: #228B22\">% loopFR<\/span>\r\n    M = repmat(Minit,N(n),1);\r\n    tic;\r\n    M1 = loopFR(M,a);\r\n    t(n,1) = toc;\r\n    <span style=\"color: #228B22\">% ismember<\/span>\r\n    tic;\r\n    [M2,M2] = ismember(M,a);\r\n    t(n,2) = toc;\r\n    <span style=\"color: #228B22\">% histc<\/span>\r\n    tic;\r\n    [M3,M3] = histc(M,a);\r\n    t(n,3) = toc;\r\n    <span style=\"color: #228B22\">% vecIM<\/span>\r\n    tic;\r\n    M4 = vecIM(M,a);\r\n    t(n,4) = toc;\r\n    <span style=\"color: #0000FF\">if<\/span> ~isequal(M1,M2,M3,M4)\r\n        disp(<span style=\"color: #A020F0\">'oops'<\/span>)\r\n    <span style=\"color: #0000FF\">end<\/span>\r\n<span style=\"color: #0000FF\">end<\/span><\/pre><h3>Timing Results<a name=\"9\"><\/a><\/h3><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">disp(<span style=\"color: #A020F0\">'       Counter     loop       ismember     histc        vecIM'<\/span>)\r\ndisp([N' t]);\r\nsubplot(1,2,1)\r\nplot(N', t, <span style=\"color: #A020F0\">'--*'<\/span>)\r\nxlabel(<span style=\"color: #A020F0\">'Number of repeated arrays'<\/span>)\r\nylabel(<span style=\"color: #A020F0\">'Execution time'<\/span>)\r\nlegend({<span style=\"color: #A020F0\">'loop'<\/span>,<span style=\"color: #A020F0\">'ismember'<\/span>,<span style=\"color: #A020F0\">'histc'<\/span> <span style=\"color: #A020F0\">'vecIM'<\/span>},<span style=\"color: #A020F0\">'Location'<\/span>, <span style=\"color: #A020F0\">'NorthWest'<\/span>)\r\nsubplot(1,2,2)\r\nsemilogx(N', t, <span style=\"color: #A020F0\">'--*'<\/span>)\r\nxlabel(<span style=\"color: #A020F0\">'Number of repeated arrays'<\/span>)\r\nylabel(<span style=\"color: #A020F0\">'Execution time'<\/span>)\r\nlegend({<span style=\"color: #A020F0\">'loop'<\/span>,<span style=\"color: #A020F0\">'ismember'<\/span>,<span style=\"color: #A020F0\">'histc'<\/span> <span style=\"color: #A020F0\">'vecIM'<\/span>},<span style=\"color: #A020F0\">'Location'<\/span>, <span style=\"color: #A020F0\">'NorthWest'<\/span>)<\/pre><pre style=\"font-style:oblique\">       Counter     loop       ismember     histc        vecIM\r\n            1  9.0514e-005   0.00028691  2.2349e-005  5.5594e-005\r\n           10  7.2635e-005   0.00024612  3.1568e-005  5.9225e-005\r\n          100   0.00018522   0.00054839   0.00018131   0.00014471\r\n         1000     0.001263    0.0034977    0.0013865   0.00097079\r\n        10000     0.012539     0.035746     0.014809     0.010385\r\n       1e+005      0.13758      0.40348      0.15652      0.11654\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/43\/loopFreeIM_01.png\"> <h3>Comments<a name=\"10\"><\/a><\/h3>\r\n   <p>I made a mistake in the original post by not recognizing that <tt>loopFR<\/tt> was completely vectorizable.  It's often true that if you have the same indexing expression on the right- and left-hand sides,\r\n      such as on line 14 in <tt>loopFR<\/tt>, you can get rid of the loop completely.  As you can see, the fully vectorized solution <tt>vecIM<\/tt> has the least overhead of all the solutions posted so far. Any more comments, algorithms, or new results?  Please add them below.\r\n   <\/p>\r\n   <p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br>\r\n      Published with MATLAB&reg; 7.2<br><\/p>\r\n<\/div>\r\n<!--\r\n##### SOURCE BEGIN #####\r\n%% Inverse Mapping (update)\r\n% In a follow up comment to the \r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=41 inverse mapping post>, Lucio\r\n% noted that |loopFR| could be fully vectorized and he is right.  Rather\r\n% than update that post directly, I thought I republish the loop-free code\r\n% here and compare times again.\r\n%%\r\n% Tidy up to start.\r\nclear\r\nformat short g\r\n%% Recap the Problem\r\n%% Sample Input and Results\r\n% Supppose array |a| contains values that we expect to see in\r\n% another array, |Minit|.\r\na = [1 3 5 7 8]\r\nMinit = [1 3 5; ...\r\n    3 5 7; ...\r\n    3 7 8]\r\n%%\r\n% Let's build a replacement matrix for |Minit| in which its values\r\n% are replaced with their indices in the list |a|.\r\nMwanted = [1 2 3; ...\r\n     2 3 4; ...\r\n     2 4 5]\r\n%% Algorithms\r\n% We previously compared these algorithms:\r\n%\r\n% * loop (via |loopFR|) \r\n% * |ismember| \r\n% * |histc|\r\n%\r\n%%\r\n% Here's |loopFR|, for reference:\r\ndbtype loopFR\r\n%%\r\n% and let's now add the fully vectorized version, |vecIM| to our\r\n% comparison.\r\ntype vecIM\r\n%% Time the New Algorithm and Retime the Former Ones\r\nN = [1 10 100 1000 10000 100000];  % repetitions to test\r\nt = zeros(length(N),4); % set up the timing collection array\r\nfor n = 1:length(N)\r\n    % Make a larger matrix to search.\r\n    % loopFR\r\n    M = repmat(Minit,N(n),1);\r\n    tic;\r\n    M1 = loopFR(M,a);\r\n    t(n,1) = toc;\r\n    % ismember\r\n    tic;\r\n    [M2,M2] = ismember(M,a);\r\n    t(n,2) = toc;\r\n    % histc\r\n    tic;\r\n    [M3,M3] = histc(M,a);\r\n    t(n,3) = toc;\r\n    % vecIM\r\n    tic;\r\n    M4 = vecIM(M,a);\r\n    t(n,4) = toc;\r\n    if ~isequal(M1,M2,M3,M4)\r\n        disp('oops')\r\n    end\r\nend\r\n\r\n%% Timing Results\r\ndisp('       Counter     loop       ismember     histc        vecIM')\r\ndisp([N' t]);\r\nsubplot(1,2,1)\r\nplot(N', t, 'REPLACE_WITH_DASH_DASH*')\r\nxlabel('Number of repeated arrays')\r\nylabel('Execution time')\r\nlegend({'loop','ismember','histc' 'vecIM'},'Location', 'NorthWest')\r\nsubplot(1,2,2)\r\nsemilogx(N', t, 'REPLACE_WITH_DASH_DASH*')\r\nxlabel('Number of repeated arrays')\r\nylabel('Execution time')\r\nlegend({'loop','ismember','histc' 'vecIM'},'Location', 'NorthWest')\r\n%% Comments\r\n% I made a mistake in the original post by not recognizing that |loopFR|\r\n% was completely vectorizable.  It's often true that if you have the same\r\n% indexing expression on the right- and left-hand sides, such as on line 14\r\n% in |loopFR|, you can get rid of the loop completely.  As you can see, the\r\n% fully vectorized solution |vecIM| has the least overhead of all the\r\n% solutions posted so far.\r\n% Any more comments, algorithms, or new results?  Please add them\r\n% <http:?p=43\/Respond here>.\r\n\r\n##### SOURCE END #####\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      In a follow up comment to the inverse mapping post, Lucio noted that loopFR could be fully vectorized and he is right.  Rather than update that post directly, I thought I republish the... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2006\/06\/28\/inverse-mapping-update\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[12],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/43"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=43"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/43\/revisions"}],"predecessor-version":[{"id":2321,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/43\/revisions\/2321"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=43"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=43"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=43"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}