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: Object]
  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: E): Int
  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: E, value: Int)
  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         # A new Counter initialized with `inc_all`.
  97         init from(es: Collection[E])
  98         do
  99                 inc_all(es)
 100         end
 101
 102         # Return an array of elements sorted by occurrences
 103         #
 104         # ~~~
 105         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 106         # assert c.sort == ["c", "a", "b"]
 107         # ~~~
 108         fun sort: Array[E]
 109         do
 110                 var res = map.keys.to_a
 111                 var sorter = new CounterComparator[E](self)
 112                 sorter.sort(res)
 113                 return res
 114         end
 115
 116         # The method used to display an element
 117         # @toimplement by default just call `to_s` on the element
 118         protected fun element_to_s(e: E): String
 119         do
 120                 return e.to_s
 121         end
 122
 123         # Display statistical information
 124         fun print_summary
 125         do
 126                 var list = self.sort
 127                 print " population: {list.length}"
 128                 if list.is_empty then return
 129                 print " minimum value: {self[list.first]}"
 130                 print " maximum value: {self[list.last]}"
 131                 print " total value: {self.sum}"
 132                 print " average value: {div(self.sum,list.length)}"
 133                 print " distribution:"
 134                 var count = 0
 135                 var sum = 0
 136                 var limit = self[list.first]
 137                 for t in list do
 138                         if self[t] > limit then
 139                                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 140                                 count = 0
 141                                 sum = 0
 142                                 while self[t] > limit do
 143                                         limit = limit * 2
 144                                         if limit == 0 then limit = 1
 145                                 end
 146                         end
 147                         count += 1
 148                         sum += self[t]
 149                 end
 150                 print "  <={limit}: sub-population={count} ({div(count*100,list.length)}%); cumulated value={sum} ({div(sum*100,self.sum)}%)"
 151         end
 152
 153         # Display up to `count` most used elements and `count` least used elements
 154         # Use `element_to_s` to display the element
 155         fun print_elements(count: Int)
 156         do
 157                 print " list:"
 158                 var list = self.sort
 159                 var min = count
 160                 if list.length <= count*2 then min = list.length
 161                 for i in [0..min[ do
 162                         var t = list[list.length-i-1]
 163                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 164                 end
 165                 if list.length <= count*2 then return
 166                 print "  ..."
 167                 for i in [0..min[ do
 168                         var t = list[min-i-1]
 169                         print "  {element_to_s(t)}: {self[t]} ({div(self[t]*100,self.sum)}%)"
 170                 end
 171         end
 172
 173         # Return the element with the highest value (aka. the mode)
 174         #
 175         # ~~~
 176         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 177         # assert c.max == "b"
 178         # ~~~
 179         #
 180         # If more than one max exists, the first one is returned.
 181         fun max: nullable E do
 182                 var max: nullable Int = null
 183                 var elem: nullable E = null
 184                 for e, v in map do
 185                         if max == null or v > max then
 186                                 max = v
 187                                 elem = e
 188                         end
 189                 end
 190                 return elem
 191         end
 192
 193         # Return the couple with the lowest value
 194         #
 195         # ~~~
 196         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 197         # assert c.min == "c"
 198         # ~~~
 199         #
 200         # If more than one min exists, the first one is returned.
 201         fun min: nullable E do
 202                 var min: nullable Int = null
 203                 var elem: nullable E = null
 204                 for e, v in map do
 205                         if min == null or v < min then
 206                                 min = v
 207                                 elem = e
 208                         end
 209                 end
 210                 return elem
 211         end
 212
 213         # Values average (aka. arithmetic mean)
 214         #
 215         # ~~~
 216         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 217         # assert c.avg == 2.0
 218         # ~~~
 219         fun avg: Float do
 220                 if values.is_empty then return 0.0
 221                 return (sum / values.length).to_f
 222         end
 223
 224         # The standard derivation of the counter values
 225         #
 226         # ~~~
 227         # var c = new Counter[String].from(["a", "a", "b", "b", "b", "c"])
 228         # assert c.std_dev > 0.81
 229         # assert c.std_dev < 0.82
 230         # ~~~
 231         fun std_dev: Float do
 232                 var avg = self.avg
 233                 var sum = 0.0
 234                 for value in map.values do
 235                         sum += (value.to_f - avg).pow(2.0)
 236                 end
 237                 return (sum / map.length.to_f).sqrt
 238         end
 239 end
 240
 241 private class CounterComparator[E: Object]
 242         super Comparator
 243         redef type COMPARED: E
 244         var counter: Counter[E]
 245         redef fun compare(a,b) do return self.counter.map[a] <=> self.counter.map[b]
 246 end
 247
 248 redef class POSet[E]
 249         private fun show_counter(c: Counter[Int])
 250         do
 251                 var list = c.sort
 252                 default_comparator.sort(list)
 253                 for e in list do
 254                         print " {e} -> {c[e]} times ({div(c[e]*100, c.sum)}%)"
 255                 end
 256         end
 257
 258         # Display exhaustive metrics about the poset
 259         fun print_metrics
 260         do
 261                 var nb_greaters = new Counter[E]
 262                 var nb_direct_greaters = new Counter[E]
 263                 var nb_smallers = new Counter[E]
 264                 var nb_direct_smallers = new Counter[E]
 265                 var nb_direct_edges = 0
 266                 var nb_edges = 0
 267                 for n in self do
 268                         var ne = self[n]
 269                         nb_edges += ne.greaters.length
 270                         nb_direct_edges += ne.direct_greaters.length
 271                         nb_greaters[n] = ne.greaters.length
 272                         nb_direct_greaters[n] = ne.direct_greaters.length
 273                         nb_smallers[n] = ne.smallers.length
 274                         nb_direct_smallers[n] = ne.direct_smallers.length
 275                 end
 276                 print "Number of nodes: {self.length}"
 277                 print "Number of edges: {nb_edges} ({div(nb_edges,self.length)} per node)"
 278                 print "Number of direct edges: {nb_direct_edges} ({div(nb_direct_edges,self.length)} per node)"
 279                 print "Distribution of greaters"
 280                 nb_greaters.print_summary
 281                 print "Distribution of direct greaters"
 282                 nb_direct_greaters.print_summary
 283                 print "Distribution of smallers"
 284                 nb_smallers.print_summary
 285                 print "Distribution of direct smallers"
 286                 nb_direct_smallers.print_summary
 287         end
 288 end
 289
 290 # Helper function to display `n/d` and handle division by 0
 291 fun div(n: Int, d: Int): String
 292 do
 293         if d == 0 then return "na"
 294         return ((100*n/d).to_f/100.0).to_precision(2)
 295 end