HelpSource/Classes/SparseArray.schelp

   1 CLASS::SparseArray
   2 categories::Collections>Ordered
   3 summary:: Array that stores duplicated values more efficiently
   4
   5 DESCRIPTION::
   6 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.
   7
   8 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.
   9
  10 The benefits of using SparseArray typically arise when creating collections containing many millions of slots.
  11
  12 CLASSMETHODS::
  13
  14 method::newClear
  15 Create a new SparseArray of the specified strong::size::, with each slot's value being strong::default::.
  16 code::
  17 g = SparseArray.newClear(20, 3);
  18 g.postcs;
  19 ::
  20 argument::size
  21 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.
  22 argument::default
  23 The default value, i.e. the value that all slots should take at first.
  24
  25 method::reduceArray
  26 Create a new SparseArray holding the same data as strong::array::.
  27 code::
  28 a = [4, 7, 4, 4, 4, 4, 4, 4, 9, 9, 8];
  29 g = SparseArray.reduceArray(a, 4);
  30 g.postcs;
  31 ::
  32 argument::array
  33 Any link::Classes/ArrayedCollection::.
  34 argument::default
  35 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.
  36
  37 INSTANCEMETHODS::
  38
  39 private::prPutSlot
  40
  41 method::put
  42 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).
  43 code::
  44 g = SparseArray.newClear(10, 3);
  45 g.put(4, \horse);
  46 g.put(6, [4,5,6]);
  47 g[1] = \hello; // Common compact notation
  48 ::
  49
  50 method::at
  51 Retrieve the value at index.
  52 code::
  53 g = SparseArray.newClear(20, 3);
  54 g.put(4, \horse);
  55 g.at(4);
  56 g[4];
  57 ::
  58
  59 method::asArray
  60 Convert to an ordinary link::Classes/Array::.
  61 code::
  62 g = SparseArray.newClear(20, 3);
  63 g.postcs;
  64 g.asArray;
  65 ::
  66
  67 EXAMPLES::
  68
  69 Here we compare speed of Array vs SparseArray.
  70
  71 code::
  72 // Let's create a standard array, big but with only a couple of unusual values hidden in there
  73 (
  74 {
  75         a = {10}.dup(1000000);
  76         a[551] = 77;
  77         a[8722] = \foo;
  78 }.bench
  79 )
  80 // Now a SparseArray made out of exactly the same data
  81 (
  82 {
  83         b = SparseArray.newClear(a.size, 10);
  84         b[551] = 77;
  85         b[8722] = \foo;
  86 }.bench
  87 )
  88
  89 // Alternatively you could make the SparseArray out of the existing array,
  90 // although this is typically not as efficient as starting from scratch
  91 // since the Array needs to be scanned directly.
  92 (
  93 {
  94         b = SparseArray.reduceArray(a, 10);
  95 }.bench
  96 )
  97
  98 // accessing:
  99 {1000.do{ a[a.size.rand] == 60.rand }}.bench
 100 {1000.do{ b[b.size.rand] == 60.rand }}.bench
 101 // setting:
 102 {1000.do{ a[a.size.rand] = 60.rand }}.bench
 103 {1000.do{ b[b.size.rand] = 60.rand }}.bench
 104 ::