[C++] Usare la STL per trovare media, mediana e moda di un set di dati?

[giuscri]

Qualcuno ha voglia di dare un'occhiata a questo codice? Devo trovare media, moda e mediana di un set \( S \) --circa una 40ina di dati. Ho usato la STL per fare prima ...come va?

// Exercise 1.4 of Bevington+Robinson `Data reduction
// and error analysis', Third Edition, McGraw-Hill
/*
Main idea: construct an ordered *list* of measurements `L', then
map every measure `l' to the number of its occurence: compute the arithmetic mean,
returns the mode, returns the middle-value of ordered list --using a std::vector in
between.
Example of a file that could be read with no problem:
3
7
3
7
\vdots
*/

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <sstream>
#include <map>

double compute_mean_of(std::list<int> list_of_measurements);
double compute_max_of(std::map<int, int> function);

int
main(int argc, char** argv)
{
  if(argc < 2)
  {
    std::cout << "Usage: " << argv[0] << " <name_of_data_file>.txt "
                   << std::endl;
    return 1;
  }
  std::fstream fs (argv[1]);
  if(!fs.good())
  {
    std::cout << "Error while opening file" << std::endl;
    return 1;
  }
  else
  std::cout << "File is open now ..." << std::endl;

  std::list<int> L;
  std::string tmp_line;
  std::getline (fs, tmp_line);
  while(!fs.eof())
  {
    std::istringstream iss (tmp_line);
    int x_i;
    iss >> x_i;
    #ifdef DEBUG
      std::cout << "x_i == " << x_i << std::endl;
    #endif
    L.push_front(x_i);
    std::getline (fs, tmp_line);
  }
  fs.close();
  std::cout << "... now close" << std::endl;

  double mean = compute_mean_of(L);
  std::cout << "Mean of measures == " << mean << std::endl;
  for (int i = 0; i < 50; ++i)
    std::cout << "-";
  std::cout << std::endl;
  L.sort();
  #ifdef DEBUG
    for (std::list<int>::iterator it=L.begin(); it != L.end(); ++it)
      std::cout << ' ' << *it;
    std::cout << std::endl;
  #endif
  std::map<int, int> function_of_the_occurrences;
  std::list<int> keys = L;
  keys.unique();
  for (std::list<int>::iterator it=keys.begin(); it != keys.end(); ++it)
    function_of_the_occurrences[*it] = 0;
  for (std::list<int>::iterator it=L.begin(); it != L.end(); ++it)
    ++function_of_the_occurrences[*it];
  #ifdef DEBUG
    for (std::map<int, int>::iterator it=function_of_the_occurrences.begin();
           it != function_of_the_occurrences.end(); ++it)
      std::cout << it->first << " => " << it->second << std::endl;
  #endif
  double mode = compute_max_of(function_of_the_occurrences);
  std::cout << "Mode of measures == " << mode << std::endl;
  for (int i = 0; i < 50; ++i)
    std::cout << "-";
  std::cout << std::endl;
  std::vector<int> V;
  for (std::list<int>::iterator it=L.begin(); it!=L.end(); ++it)
    V.push_back(*it);
  double median = V[V.size() /2];
    std::cout << "Median of measures == " << median << std::endl;
  return 0;
}

double compute_mean_of(std::list<int> input_list)
{
  double sum_of_input_list = 0.;
  for (std::list<int>::iterator it=input_list.begin(); it!=input_list.end(); ++it)
    sum_of_input_list += *it;
  double computed_mean = sum_of_input_list / input_list.size();
  return computed_mean;
}

double compute_max_of(std::map<int, int> function)
{
  int max_of_function;
  int current_global_max = 0;
  for (std::map<int, int>::iterator it=function.begin(); it!=function.end(); ++it)
  {
    if (it->second > current_global_max)
    {
      max_of_function = it->first;
      current_global_max = it->second;
    }
  }
return max_of_function;
}

Sto schiacciando una mosca con un cannone?

[claudio862]

Per un insieme di 40 elementi va bene qualsiasi cosa.

Non ho guardato con molta attenzione il codice (che si deve essere perso l'indentazione), però in alcuni punti non sfrutti le funzioni offerte dalla STL. Ad esempio:

double sum_of_input_list = 0.;
for (std::list<int>::iterator it = input_list.begin(); it != input_list.end(); ++it)
    sum_of_input_list += *it;

è equivalente a

double sum_of_input_list = std::accumulate(input_list.begin(), input_list.end(), 0);

Inoltre non mi sembra che tu ordini la lista da nessuna parte, quindi quando fai

double median = V[V.size() / 2];

non stai accedendo al vero mediano, ma ad un elemento a caso.

Qualche tempo fa mi ero scritto un paio di funzioni per media e mediana. Ho aggiunto la moda al momento, quindi magari è migliorabile. Lavorano direttamente su iteratori, quindi potresti usarle direttamente su qualsiasi contenitore standard (e non). In realtà però deve essere un iteratore di tipo RandomAccessIterator, perché uso std::sort e std::nth_element, quindi queste funzioni non funzionano per std::list. Però in realtà std::list è abbastanza sopravvalutato, std::vector è quasi sempre la scelta migliore*.

Nota che il calcolo di mediana e moda modifica la sequenza (la ordina, totalmente o parzialmente).

* Ovviamente non è sempre così, faccio giusto un paio di osservazioni:
- Ogni volta che si inserisce un elemento in std::list viene allocata memoria, che è un'operazione lenta.
- Per questo motivo gli elementi della lista sono sparpagliati in memoria, in barba al principio di località.
- Il costo di accesso ad un elementi di std::list è lineare (e non funzionano alcuni algoritmi della STL, quali std::sort e std::nth_element).
std::vector ha altri problemi, ma è una buona scelta quasi sempre.

#include <iterator>
#include <algorithm>
#include <numeric>

#include <vector>
#include <deque>
#include <iostream>

template <typename Iter>
double average(Iter begin, Iter end)
{
    typename Iter::difference_type size = std::distance(begin, end);
    const double val = std::accumulate(begin, end, 0);
    return val / size;
}

template <typename Iter>
typename Iter::value_type median(Iter begin, Iter end)
{
    typename Iter::difference_type size = std::distance(begin, end);
    Iter median = begin;
    std::advance(median, size / 2.0);

    // NOTE: This modifies the sequence.
    std::nth_element(begin, median, end);
    return *median;
}

template <typename Iter>
typename Iter::value_type mode(Iter begin, Iter end)
{
    // NOTE: This modifies the sequence.
    std::sort(begin, end);
    typename Iter::difference_type max = 0;
    Iter m = begin;

    while (begin != end) {
        Iter next = begin;
        while (next != end && *next == *begin) {
            next++;
        }
        typename Iter::difference_type dist = std::distance(begin, next);
        if (dist > max) {
            max = dist;
            m = begin;
        }
        begin = next;
    }

    return *m;
}

template <class T>
std::ostream & operator<<(std::ostream & stream, const std::vector<T> & v)
{
    std::copy(v.begin(), v.end(), std::ostream_iterator<double>(stream, " "));
    return stream;
}

template <class T>
std::ostream & operator<<(std::ostream & stream, const std::deque<T> & v)
{
    std::copy(v.begin(), v.end(), std::ostream_iterator<double>(stream, " "));
    return stream;
}

template <class Container>
void test()
{
    Container v;
    v.push_back(4);
    v.push_back(6);
    v.push_back(3);
    v.push_back(6);
    v.push_back(4);
    v.push_back(3);
    v.push_back(2);
    v.push_back(6);
    v.push_back(8);

    std::cout << "v (before all):    " << v << '\n';

    const double a = average(v.begin(), v.end());

    std::cout << "v (after average): " << v << '\n';

    const typename Container::value_type b = median(v.begin(), v.end());

    std::cout << "v (after median):  " << v << '\n';

    const typename Container::value_type c = mode(v.begin(), v.end());

    std::cout << "v (after mode):    " << v << '\n';

    std::cout << "Average: " << a << '\n';
    std::cout << "Median: " << b << '\n';
    std::cout << "Mode: " << c << '\n';
}

int main()
{
    std::cout << "Test with std::vector<int>" << '\n';
    test<std::vector<int> >();

    std::cout << '\n';

    std::cout << "Test with std::deque<float>" << '\n';
    test<std::deque<float> >();
}

[giuscri]

"claudio86":
Inoltre non mi sembra che tu ordini la lista da nessuna parte, quindi quando fai

double median = V[V.size() / 2];

non stai accedendo al vero mediano, ma ad un elemento a caso.

Piu' tardi mi disosso per bene tutto quanto hai scritto, ma in realta' la lista viene ordinata qui

// ...
L.sort();
// ...
std::map<int, int> function_of_the_occurrences;
// ...