lib/counter.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Simple numerical statistical analysis and presentation
  16 module counter
  17
  18 import poset
  19
  20 # A counter counts occurrences of things
  21 # Use this instead of a `HashMap[E, Int]`
  22 #
  23 # ~~~
  24 # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
  25 # assert c["a"]   == 2
  26 # assert c["b"]   == 3
  27 # assert c["c"]   == 1
  28 # assert c["d"]   == 0
  29 # ~~~
  30 #
  31 # The counter class can also be used to gather statistical informations.
  32 #
  33 # ~~~~
  34 # assert c.length == 3   # because 3 distinct values
  35 # assert c.max    == "b" # because "b" has the most count (3)
  36 # assert c.avg    == 2.0 # because it is the mean of the counts
  37 # ~~~~
  38 class Counter[E]
  39         super Map[E, Int]
  40
  41         # Total number of counted occurrences
  42         #
  43         # ~~~
  44         # var c = new Counter[String]
  45         # assert c.sum == 0
  46         # c.inc_all(["a", "a", "b", "b", "b", "c"])
  47         # assert c.sum == 6
  48         # ~~~
  49         var sum: Int = 0
  50
  51         private var map = new HashMap[E, Int]
  52
  53         redef fun iterator do return map.iterator
  54
  55         # The number of counted occurrences of `e`
  56         redef fun [](e)
  57         do
  58                 var map = self.map
  59                 if map.has_key(e) then return map[e]
  60                 return 0
  61         end
  62
  63         redef fun []=(e, value)
  64         do
  65                 sum -= self[e]
  66                 self.map[e] = value
  67                 sum += value
  68         end
  69
  70         redef fun keys do return map.keys
  71
  72         redef fun values do return map.values
  73
  74         redef fun length do return map.length
  75
  76         redef fun is_empty do return map.is_empty
  77
  78         redef fun clear do
  79                 sum = 0
  80                 map.clear
  81         end
  82
  83         # Count one more occurrence of `e`
  84         fun inc(e: E)
  85         do
  86                 self.map[e] = self[e] + 1
  87                 sum += 1
  88         end
  89
  90         # Count one more for each element of `es`
  91         fun inc_all(es: Collection[E])
  92         do
  93                 for e in es do inc(e)
  94         end
  95
  96         # Decrement the value of `e` by 1
  97         fun dec(e: E) do
  98                 if not has_key(e) then
  99                         self.map[e] = 0
 100                 else
 101                         self.map[e] = self[e] - 1
 102                         sum += - 1
 103                 end
 104         end
 105
 106         # Decrement the value for each element of `es`
 107         fun dec_all(es: Collection[E])
 108         do
 109                 for e in es do dec(e)
 110         end
 111
 112         # A new Counter initialized with `inc_all`.
 113         init from(es: Collection[E])
 114         do
 115                 inc_all(es)
 116         end
 117
 118         # Return an array of elements sorted by occurrences
 119         #
 120         # ~~~
 121         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 122         # assert c.sort == ["c", "a", "b"]
 123         # ~~~
 124         fun sort: Array[E]
 125         do
 126                 var res = map.keys.to_a
 127                 var sorter = new CounterComparator[E](self)
 128                 sorter.sort(res)
 129                 return res
 130         end
 131
 132         # The method used to display an element
 133         # @toimplement by default just call `to_s` on the element
 134         protected fun element_to_s(e: E): String
 135         do
 136                 return e.to_s
 137         end
 138
 139         # Display statistical information
 140         fun print_summary
 141         do
 142                 var list = self.sort
 143                 print " population: {list.length}"
 144                 if list.is_empty then return
 145                 print " minimum value: {self[list.first]}"
 146                 print " maximum value: {self[list.last]}"
 147                 print " total value: {self.sum}"
 148                 print " average value: {div(self.sum,list.length)}"
 149                 print " distribution:"
 150                 var count = 0
 151                 var sum = 0
 152                 var limit = self[list.first]
 153                 for t in list do
 154                         if self[t] > limit then
 155                                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 156                                 count = 0
 157                                 sum = 0
 158                                 while self[t] > limit do
 159                                         limit = limit * 2
 160                                         if limit == 0 then limit = 1
 161                                 end
 162                         end
 163                         count += 1
 164                         sum += self[t]
 165                 end
 166                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 167         end
 168
 169         # Display up to `count` most used elements and `count` least used elements
 170         # Use `element_to_s` to display the element
 171         fun print_elements(count: Int)
 172         do
 173                 print " list:"
 174                 var list = self.sort
 175                 var min = count
 176                 if list.length <= count*2 then min = list.length
 177                 for i in [0..min[ do
 178                         var t = list[list.length-i-1]
 179                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 180                 end
 181                 if list.length <= count*2 then return
 182                 print "  ..."
 183                 for i in [0..min[ do
 184                         var t = list[min-i-1]
 185                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 186                 end
 187         end
 188
 189         # Return the element with the highest value (aka. the mode)
 190         #
 191         # ~~~
 192         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 193         # assert c.max == "b"
 194         # ~~~
 195         #
 196         # If more than one max exists, the first one is returned.
 197         fun max: nullable E do
 198                 var max: nullable Int = null
 199                 var elem: nullable E = null
 200                 for e in map.keys do
 201                         var v = map[e]
 202                         if max == null or v > max then
 203                                 max = v
 204                                 elem = e
 205                         end
 206                 end
 207                 return elem
 208         end
 209
 210         # Return the couple with the lowest value
 211         #
 212         # ~~~
 213         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 214         # assert c.min == "c"
 215         # ~~~
 216         #
 217         # If more than one min exists, the first one is returned.
 218         fun min: nullable E do
 219                 var min: nullable Int = null
 220                 var elem: nullable E = null
 221                 for e in map.keys do
 222                         var v = map[e]
 223                         if min == null or v < min then
 224                                 min = v
 225                                 elem = e
 226                         end
 227                 end
 228                 return elem
 229         end
 230
 231         # Values average (aka. arithmetic mean)
 232         #
 233         # ~~~
 234         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 235         # assert c.avg == 2.0
 236         # ~~~
 237         fun avg: Float do
 238                 if values.is_empty then return 0.0
 239                 return (sum / values.length).to_f
 240         end
 241
 242         # The standard derivation of the counter values
 243         #
 244         # ~~~
 245         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 246         # assert c.std_dev > 0.81
 247         # assert c.std_dev < 0.82
 248         # ~~~
 249         fun std_dev: Float do
 250                 var avg = self.avg
 251                 var sum = 0.0
 252                 for value in map.values do
 253                         sum += (value.to_f - avg).pow(2.0)
 254                 end
 255                 return (sum / map.length.to_f).sqrt
 256         end
 257
 258         # The information entropy (Shannon entropy) of the elements in the counter (in bits).
 259         fun entropy: Float
 260         do
 261                 var res = 0.0
 262                 var sum = self.sum.to_f
 263                 for k, v in self do
 264                         var f = v.to_f / sum
 265                         res = res - f * f.log_base(2.0)
 266                 end
 267                 return res
 268         end
 269 end
 270
 271 redef class Collection[E]
 272         # Create and fill up a counter with the elements of `self.
 273         #
 274         # ~~~
 275         # var cpt = "abaa".chars.to_counter
 276         # assert cpt['a'] == 3
 277         # assert cpt['b'] == 1
 278         # assert cpt.length == 2
 279         # assert cpt.sum == 4
 280         # ~~~
 281         fun to_counter: Counter[E]
 282         do
 283                 var res = new Counter[E]
 284                 res.inc_all(self)
 285                 return res
 286         end
 287 end
 288
 289 private class CounterComparator[E]
 290         super Comparator
 291         redef type COMPARED: E
 292         var counter: Counter[E]
 293         redef fun compare(a,b) do return self.counter.map[a] <=> self.counter.map[b]
 294 end
 295
 296 redef class POSet[E]
 297         private fun show_counter(c: Counter[Int])
 298         do
 299                 var list = c.sort
 300                 default_comparator.sort(list)
 301                 for e in list do
 302                         print " {e} -> {c[e]} times ({div(c[e]*100, c.sum)}%)"
 303                 end
 304         end
 305
 306         # Display exhaustive metrics about the poset
 307         fun print_metrics
 308         do
 309                 var nb_greaters = new Counter[E]
 310                 var nb_direct_greaters = new Counter[E]
 311                 var nb_smallers = new Counter[E]
 312                 var nb_direct_smallers = new Counter[E]
 313                 var nb_direct_edges = 0
 314                 var nb_edges = 0
 315                 for n in self do
 316                         var ne = self[n]
 317                         nb_edges += ne.greaters.length
 318                         nb_direct_edges += ne.direct_greaters.length
 319                         nb_greaters[n] = ne.greaters.length
 320                         nb_direct_greaters[n] = ne.direct_greaters.length
 321                         nb_smallers[n] = ne.smallers.length
 322                         nb_direct_smallers[n] = ne.direct_smallers.length
 323                 end
 324                 print "Number of nodes: {self.length}"
 325                 print "Number of edges: {nb_edges} ({div(nb_edges,self.length)} per node)"
 326                 print "Number of direct edges: {nb_direct_edges} ({div(nb_direct_edges,self.length)} per node)"
 327                 print "Distribution of greaters"
 328                 nb_greaters.print_summary
 329                 print "Distribution of direct greaters"
 330                 nb_direct_greaters.print_summary
 331                 print "Distribution of smallers"
 332                 nb_smallers.print_summary
 333                 print "Distribution of direct smallers"
 334                 nb_direct_smallers.print_summary
 335         end
 336 end
 337
 338 # Helper function to display `n/d` and handle division by 0
 339 fun div(n: Int, d: Int): String
 340 do
 341         if d == 0 then return "na"
 342         return ((100*n/d).to_f/100.0).to_precision(2)
 343 end