Problem 42676. Histogram of histogram

Created by Peng Liu

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Histogram of histogram (HoH) is a useful measure concerning the distribution of random data, which has diverse applications in data science, statistics, information theory, etc.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In this problem, given an n-by-m array x of integer numbers {1,2,...,S}, return the HoH along every column of x: f = HoH(x). An example for n = 5, m = 4, and S = 6 follows.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ x = [1 2 2 3\n 2 3 3 6\n 1 3 1 1\n 6 3 2 5\n 2 2 4 2]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Histogram</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ h = [2 0 1 1\n 2 2 2 1\n 0 3 1 1\n 0 0 1 0\n 0 0 0 1\n 1 0 0 1]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>where the r-th (r=1,...,S) row of h is the histogram bin counts for number r along every column of x.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>HoH</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ f = [1 0 3 5\n 2 1 1 0\n 0 1 0 0]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>where f is a max(h(:))-by-m matrix, with the p-th row representing the histogram of number p along every column of h.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Hint</w:t></w:r><w:r><w:t> : A straightforward reference scheme to obtain f could be:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ h = histc(x,1:max(x(:)),1); \n f = histc(h,1:max(h(:)),1);]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is simple but inefficient in terms of both performance and memory (It will crash for the last test case). Note that the ultimate goal is to find f (HoH); thus, it is not necessary to go through exactly the same h as described above. Try your best to improve your code in terms of both</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>speed</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>memory</w:t></w:r><w:r><w:t>. Your score will be based on the</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>speed</w:t></w:r><w:r><w:t> of your code.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Histogram of histogram (HoH) is a useful measure concerning the distribution of random data, which has diverse applications in data science, statistics, information theory, etc.In this problem, given an n-by-m array x of integer numbers {1,2,...,S}, return the HoH along every column of x: f = HoH(x). An example for n = 5, m = 4, and S = 6 follows.Input<pre> x = [1 2 2 3
 2 3 3 6
 1 3 1 1
 6 3 2 5
 2 2 4 2]</pre>Histogram<pre> h = [2 0 1 1
 2 2 2 1
 0 3 1 1
 0 0 1 0
 0 0 0 1
 1 0 0 1]</pre>where the r-th (r=1,...,S) row of h is the histogram bin counts for number r along every column of x.HoH<pre> f = [1 0 3 5
 2 1 1 0
 0 1 0 0]</pre>where f is a max(h(:))-by-m matrix, with the p-th row representing the histogram of number p along every column of h.Hint : A straightforward reference scheme to obtain f could be:<pre> h = histc(x,1:max(x(:)),1); 
 f = histc(h,1:max(h(:)),1);</pre>This is simple but inefficient in terms of both performance and memory (It will crash for the last test case). Note that the ultimate goal is to find f (HoH); thus, it is not necessary to go through exactly the same h as described above. Try your best to improve your code in terms of both speed and memory. Your score will be based on the speed of your code.

Histogram of histogram (HoH) is a useful measure concerning the distribution of random data, which has diverse applications in data science, statistics, information theory, etc.

In this problem, given an n-by-m array x of integer numbers {1,2,...,S}, return the HoH along every column of x: f = HoH(x). An example for n = 5, m = 4, and S = 6 follows.

*Input*

x = [1  2  2  3
                      2  3  3  6
                      1  3  1  1
                      6  3  2  5
                      2  2  4  2]

*Histogram*

h = [2  0  1  1
                      2  2  2  1
                      0  3  1  1
                      0  0  1  0
                      0  0  0  1
                      1  0  0  1]

where the r-th (r=1,...,S) row of h is the histogram bin counts for number r along every column of x.

*HoH*

f = [1  0  3  5
                      2  1  1  0
                      0  1  0  0]

where f is a max(h(:))-by-m matrix, with the p-th row representing the histogram of number p along every column of h.

*Hint* : A straightforward reference scheme to obtain f could be:

h = histc(x,1:max(x(:)),1);         
    f = histc(h,1:max(h(:)),1);

This is simple but inefficient in terms of both performance and memory (It will crash for the last test case). Note that the ultimate goal is to find f (HoH); thus, it is not necessary to go through exactly the same h as described above. Try your best to improve your code in terms of both *speed* and *memory*. Your score will be based on the *speed* of your code.

Solve

Solution Stats

46 Solutions
12 Solvers

Last Solution submitted on Apr 20, 2021

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Dennis Gimlin on 4 Sep 2020

I've tried multiple schemes, some are faster than histc, but not fast enough. Hint?

Solution Comments

Solution 773068

1 Comment

1 Comment

LY Cao on 7 Nov 2015

This is nearly 30% slower than Solution 772002(size 35) on my PC(win 10 pro x64,i7 4700mq)

Solution 771853

1 Comment

1 Comment

Peng Liu on 6 Nov 2015

Hi Alfonso, I noticed that a faster solution is often beat by a slower solution (according to my own computer) when running on Cody. Could you share your knowledge or some guess on this issue? Thanks.

Problem Recent Solvers12

Problem Tags

histogram matrix manipulation

Community Treasure Hunt

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

Start Hunting!