Help/Collections/SparseArray.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta http-equiv="Content-Style-Type" content="text/css">
   6 <title></title>
   7 <meta name="Generator" content="Cocoa HTML Writer">
   8 <meta name="CocoaVersion" content="949.43">
   9 <style type="text/css">
  10 p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Helvetica}
  11 p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}
  12 p.p3 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; color: #0021e7}
  13 p.p4 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
  14 p.p5 {margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Helvetica}
  15 p.p6 {margin: 0.0px 0.0px 0.0px 57.0px; text-indent: -57.0px; font: 12.0px Helvetica}
  16 p.p7 {margin: 0.0px 0.0px 0.0px 57.0px; text-indent: -57.0px; font: 12.0px Helvetica; min-height: 14.0px}
  17 p.p8 {margin: 0.0px 0.0px 0.0px 85.0px; text-indent: -85.0px; font: 12.0px Helvetica}
  18 p.p9 {margin: 0.0px 0.0px 0.0px 57.0px; text-indent: -57.0px; font: 9.0px Monaco}
  19 p.p10 {margin: 0.0px 0.0px 0.0px 85.0px; text-indent: -85.0px; font: 12.0px Helvetica; color: #0021e7}
  20 p.p11 {margin: 0.0px 0.0px 0.0px 57.0px; text-indent: -57.0px; font: 9.0px Monaco; color: #ad140d}
  21 p.p12 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #ad140d}
  22 p.p13 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco}
  23 p.p14 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; min-height: 12.0px}
  24 span.s1 {color: #000000}
  25 span.s2 {color: #001bb9}
  26 span.s3 {text-decoration: underline}
  27 span.s4 {color: #2c7014}
  28 span.Apple-tab-span {white-space:pre}
  29 </style>
  30 </head>
  31 <body>
  32 <p class="p1"><b>SparseArray</b></p>
  33 <p class="p2"><br></p>
  34 <p class="p3"><span class="s1"><b>Inherits from: </b><a href="../Core/Object.html"><span class="s2"><b>Object</b></span></a><b> : </b><a href="Collection.html"><b>Collection</b></a><b> : </b><a href="SequenceableCollection.html"><b>SequenceableCollection</b></a><b> : </b><a href="Order.html"><b>Order</b></a></span></p>
  35 <p class="p2"><br></p>
  36 <p class="p4">A sparse array is a data structure that acts in exactly the same manner as an Array. However, data is represented differently in memory, in a way that makes it much more efficient to store very large arrays in which many values are the same.<span class="Apple-converted-space"> </span></p>
  37 <p class="p2"><br></p>
  38 <p class="p4">Take for example an array consisting of a million zeroes, with a 1 appended to the end; SparseArray would compress this array by storing zero as a default value, and only explicitly storing the single value that differs, therefore offering a much more economical use of memory.</p>
  39 <p class="p2"><br></p>
  40 <p class="p4">The benefits of using SparseArray typically arise when creating collections containing many millions of slots.</p>
  41 <p class="p2"><br></p>
  42 <p class="p5"><b>Creation / Class Methods</b></p>
  43 <p class="p2"><br></p>
  44 <p class="p6"><b><span class="Apple-tab-span">  </span>*newClear(size, default)</b></p>
  45 <p class="p7"><b><span class="Apple-tab-span">  </span></b></p>
  46 <p class="p6"><b><span class="Apple-tab-span">  </span><span class="Apple-tab-span">    </span></b>Create a new SparseArray of the specified size, with each slot's value being <b>default.</b></p>
  47 <p class="p8"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span><b>size </b>- Number of slots in the desired array. Note that slots are not explicitly created, so the speed of creation is not related to the array size.</p>
  48 <p class="p8"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span><b>default<span class="Apple-converted-space"> </span></b> - The default value, i.e. the value that all slots should take at first.</p>
  49 <p class="p7"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span></p>
  50 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g = <span class="s2">SparseArray</span>.newClear(20, 3);</p>
  51 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.postcs;</p>
  52 <p class="p2"><br></p>
  53 <p class="p6"><b><span class="Apple-tab-span">  </span>*reduceArray(array, default)</b></p>
  54 <p class="p7"><b><span class="Apple-tab-span">  </span></b></p>
  55 <p class="p6"><b><span class="Apple-tab-span">  </span><span class="Apple-tab-span">    </span></b>Create a new SparseArray holding the same data as <b>array</b>.</p>
  56 <p class="p10"><span class="s1"><span class="Apple-tab-span">   </span><span class="Apple-tab-span">    </span><b>array </b>- Any <a href="ArrayedCollection.html"><span class="s3">ArrayedCollection</span></a>.</span></p>
  57 <p class="p8"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span><b>default<span class="Apple-converted-space"> </span></b> - The default value, i.e. the value that all slots should take at first. For best memory efficiency, you should supply the most common value found in the collection.</p>
  58 <p class="p7"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span></p>
  59 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>a = [4, 7, 4, 4, 4, 4, 4, 4, 9, 9, 8];</p>
  60 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g = <span class="s2">SparseArray</span>.reduceArray(a, 4);</p>
  61 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.postcs;</p>
  62 <p class="p2"><br></p>
  63 <p class="p2"><br></p>
  64 <p class="p2"><br></p>
  65 <p class="p5"><b>Instance Methods</b></p>
  66 <p class="p2"><br></p>
  67 <p class="p6"><b><span class="Apple-tab-span">  </span>put(index, value)</b></p>
  68 <p class="p7"><b><span class="Apple-tab-span">  </span></b></p>
  69 <p class="p6"><b><span class="Apple-tab-span">  </span><span class="Apple-tab-span">    </span></b>Put a value at the desired index. This works just like all ArrayedCollection types. Behind the scenes the class will ensure the compact representation (deciding whether to store the value explicitly or implicitly).</p>
  70 <p class="p7"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span></p>
  71 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g = <span class="s2">SparseArray</span>.newClear(10, 3);</p>
  72 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.put(4, <span class="s4">\horse</span>);</p>
  73 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.put(6, [4,5,6]);</p>
  74 <p class="p11"><span class="s1"><span class="Apple-tab-span">   </span><span class="Apple-tab-span">    </span>g[1] = </span><span class="s4">\hello</span><span class="s1">; </span>// Common compact notation</p>
  75 <p class="p2"><br></p>
  76 <p class="p6"><b><span class="Apple-tab-span">  </span>at(index)</b></p>
  77 <p class="p7"><b><span class="Apple-tab-span">  </span></b></p>
  78 <p class="p6"><b><span class="Apple-tab-span">  </span><span class="Apple-tab-span">    </span></b>Retrieve the value at <b>index</b>.</p>
  79 <p class="p7"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span></p>
  80 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g = <span class="s2">SparseArray</span>.newClear(20, 3);</p>
  81 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.put(4, <span class="s4">\horse</span>);</p>
  82 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.at(4);</p>
  83 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g[4];</p>
  84 <p class="p2"><br></p>
  85 <p class="p6"><b><span class="Apple-tab-span">  </span>asArray</b></p>
  86 <p class="p7"><b><span class="Apple-tab-span">  </span></b></p>
  87 <p class="p6"><b><span class="Apple-tab-span">  </span><span class="Apple-tab-span">    </span></b>Convert to an ordinary <a href="Array.html"><span class="s2">Array</span></a>.</p>
  88 <p class="p7"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span></p>
  89 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g = <span class="s2">SparseArray</span>.newClear(20, 3);</p>
  90 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.postcs;</p>
  91 <p class="p9"><span class="Apple-tab-span">     </span><span class="Apple-tab-span">    </span>g.asArray;</p>
  92 <p class="p2"><br></p>
  93 <p class="p2"><br></p>
  94 <p class="p2"><br></p>
  95 <p class="p2"><br></p>
  96 <p class="p5"><b>Examples</b></p>
  97 <p class="p2"><br></p>
  98 <p class="p4">Here we compare speed of Array vs SparseArray.</p>
  99 <p class="p2"><br></p>
 100 <p class="p12">// Let's create a standard array, big but with only a couple of unusual values hidden in there</p>
 101 <p class="p13">(</p>
 102 <p class="p13">{</p>
 103 <p class="p13"><span class="Apple-tab-span">    </span>a = {10}.dup(1000000);</p>
 104 <p class="p13"><span class="Apple-tab-span">    </span>a[551] = 77;</p>
 105 <p class="p13"><span class="Apple-tab-span">    </span>a[8722] = <span class="s4">\foo</span>;</p>
 106 <p class="p13">}.bench</p>
 107 <p class="p13">)</p>
 108 <p class="p12">// Now a SparseArray made out of exactly the same data</p>
 109 <p class="p13">(</p>
 110 <p class="p13">{</p>
 111 <p class="p13"><span class="Apple-tab-span">    </span>b = <span class="s2">SparseArray</span>.newClear(a.size, 10);</p>
 112 <p class="p13"><span class="Apple-tab-span">    </span>b[551] = 77;</p>
 113 <p class="p13"><span class="Apple-tab-span">    </span>b[8722] = <span class="s4">\foo</span>;</p>
 114 <p class="p13">}.bench</p>
 115 <p class="p13">)</p>
 116 <p class="p14"><br></p>
 117 <p class="p12">// Alternatively you could make the SparseArray out of the existing array, although this is typically not as efficient as starting from scratch since the Array needs to be scanned directly.</p>
 118 <p class="p13">(</p>
 119 <p class="p13">{</p>
 120 <p class="p13"><span class="Apple-tab-span">    </span>b = <span class="s2">SparseArray</span>.reduceArray(a, 10);</p>
 121 <p class="p13">}.bench</p>
 122 <p class="p13">)</p>
 123 <p class="p14"><br></p>
 124 <p class="p12">// accessing:</p>
 125 <p class="p13">{1000.do{ a[a.size.rand] == 60.rand }}.bench</p>
 126 <p class="p13">{1000.do{ b[b.size.rand] == 60.rand }}.bench</p>
 127 <p class="p12">// setting:</p>
 128 <p class="p13">{1000.do{ a[a.size.rand] = 60.rand }}.bench</p>
 129 <p class="p13">{1000.do{ b[b.size.rand] = 60.rand }}.bench</p>
 130 <p class="p14"><br></p>
 131 </body>
 132 </html>