PHP: il punto e’ dentro o fuori dal poligono convesso?

Pentagono regolareQuesta classe PHP determina se un certo punto di coordinate P(x,y) si trova all’interno di un poligono convesso oppure no. Inoltre calcola la lunghezza di ciascun lato, il perimetro, l’area, e l’ampiezza di ciascun angolo.Può essere applicata a qualsiasi poligono convesso di cui si abbiano le coordinate cartesiane dei vertici in 2D. Le coordinate dei vertici verranno fornite in stretta successione, non importa se in senso orario o antiorario, in un array multidimensionale. E’ stato scelto di considerare solo poligoni convessi, per semplificare il calcolo degli angoli interni che risulteranno tutti < di 180°. La condizione che il poligono fornito sia convesso viene controllata verificando che il segno di ogni lato con il vertice successivo non cambi. Con lo stesso metodo viene verificato se un punto dato si trova all’interno o all’esterno del poligono. Infine, per semplificare, ho considerato che se il punto giace su uno dei lati, viene considerato interno.
La classe è compatibile con PHP 4.

Funzionamento:

Dati due punti A(x0,y0); e B(x1,y1), possiamo definire l’equazione canonica della retta passante per i due punti come:
x (y0 − y1) - y (x0 − x1) + x0 y1 - x1 y0 = 0
Il polinomio che è rappresentato dal primo membro dell’equazione, sarà = 0 nel caso di un punto sulla retta, produrrà valori positivi se si trova su un lato e negativi se si trova sul lato opposto.
E’ dunque chiaro che per verificare se un punto si trova all’interno del poligono è sufficiente confrontare il segno che assume l’equazione, sostituendo ad x e y le coordinate del punto, rispetto ad ogni lato. Se il segno cambia, si trova all’esterno.
Poiché ho imposto che il poligono sia convesso, ho potuto ridurre l’algoritmo confrontando il risultato del segno fra ogni lato e il punto dato, solo con il segno del primo lato e il vertice successivo (nei poligoni convessi ogni lato “gira” dalla stessa parte).

Il calcolo della misura di ciascun lato viene fatto usando la formula della distanza fra due punti:

Formula della distanza fra due punti

Si intendono p(px,py) e q(qx,qy) due vertici del poligono.

Il calcolo della misura di ciascun angolo viene fatto usando la formula del coseno:

a2 = b2 + c2 - 2 bc cos α

In cui α è l’angolo compreso fra b e c.

L’area viene calcolata usando la formula Shoelace:

Formula Shoelace

Considerando che: (xn + 1; yn + 1) = (x1; y1).

Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
<?php
class ConvexPolygon2D
{
  var $EPSILON = 0.000001;
  var $points = array();
  var $polySides = array();
  var $polyAngles = array();
  var $nVertex = 0;
  var $polySign = 0;
 
  function ConvexPolygon2D($points)
  {
    $this->points = $points;
    $this->nVertex = count($points);
    $this->polySign = $this->sign($points[0],$points[1],$points[2]);
    if (!$this->isConvexHull()) die ("This polygon is not convex!"); 
    $this->sides();
    $this->angles();
  }  
 
  function sign ($a, $b, $p)
  {
    $c = $p[0] * ($a[1] - $b[1]) - $p[1] * ($a[0] - $b[0]) + 
         $a[0] * $b[1] - $a[1] *$b[0];
    if (abs($c)< $EPSILON)    
    {
      return 0;
    }
    elseif ($c > 0)
    {
      return 1;
    }
    else
    {
      return -1;
    }
  }
 
  function isConvexHull()
  {
    for ($i=0; $i<$this->nVertex-1; $i++)
    {
      $lastVertex = $i+2;
      if ($lastVertex>=$this->nVertex)
         $lastVertex = 0;
      $psign = $this->polySign * 
               $this->sign($this->points[$i],
               $this->points[$i+1],
               $this->points[$lastVertex]);
      if($psign==0) die ("Two sides on the same line!"); 
      if ($psign<0)
      {
        return false;
      }
 
    }
    return true;
  }
 
  function isInConvexHull ($p)
  {
    for ($i=0; $i<=$this->nVertex-1; $i++)
    {
      $lastVertex = $i+1;
      if ($lastVertex>=$this->nVertex)
         $lastVertex = 0;
         $psign = $this->polySign * 
                $this->sign($this->points[$i],$this->points[$lastVertex],$p);
 
      if ($psign<0)
      {
        return false;
      }
 
    }
    return true;
  }  
 
  function RadToDeg($radians)
  {
    return $radians * 180 / M_PI;
  }
 
  function vertexDist($a,$b)
  {
    return sqrt(pow(($b[0]-$a[0]),2)+pow(($b[1]-$a[1]),2));
  }
 
  function perimeter()
  {
    return array_sum($this->polySides);
  }
 
 
  function sides()
  {
    for ($i=0; $i<$this->nVertex; $i++)    
    {
      $lastVertex = $i+1;
      if ($lastVertex>=$this->nVertex)
         $lastVertex = 0;
      $this->polySides[] = $this->vertexDist($this->points[$i],
                           $this->points[$lastVertex]);
    }
    return true; 
  }
 
  function angles()
  {
    for ($i=0; $i<$this->nVertex; $i++)    
    {
      $this->polyAngles[] = $this->angle($i);
    }
    return true;    
  }
 
  function angle($vertex)
  {
    //Teorema del coseno: a² = b² + c² - 2bc cosα
    $a = empty($vertex) ? $this->vertexDist($this->points[$this->nVertex-1],
        $this->points[1]) : 
        ($vertex==$this->nVertex-1 ? $this->vertexDist($this->points[$vertex-1],
        $this->points[0]) : $this->vertexDist($this->points[$vertex-1],
        $this->points[$vertex+1]));
 
    $b = $this->polySides[$vertex];
    $c = empty($vertex) ? $this->polySides[$this->nVertex-1] : 
        $this->polySides[$vertex-1];
 
    $res = (pow($b,2) + pow($c,2) - pow($a,2)) / (2 * $b * $c);
    return $this->RadToDeg(acos($res));
  }
 
  function area()
  {
    //Calcolo dell'area con la Shoelace formula.
    $dArea = 0;
    for ($i=0; $i<$this->nVertex; $i++)    
    {
      $lastVertex = $i+1;
      if ($lastVertex>=$this->nVertex)
         $lastVertex = 0;
      $dArea += ($this->points[$i][0]*$this->points[$lastVertex][1]) - 
                ($this->points[$lastVertex][0]*$this->points[$i][1]);
    }
    return abs($dArea) /2;  
  }
}
?>

Un esempio del funzionamento della classe è visibile qui. Per rendere graficamente le figure dei poligoni e dei punti ho utilizzato le librerie JavaScript VectorGraphics di Walter Zorn. E’ necessario, quindi, che Javascript sia attivo nel browser.

Nota: le librerie grafiche utilizzano <div>; di tipo canvas, e con Internet Explorer, alcune figure vengono disegnate in modo non perfetto, mentre con Mozilla non ci sono problemi

Il pacchetto completo è scaricabile qui

Riferimenti ed approfondimenti:

Ajax e PHP: una progress bar V-meter style

Progress bar V-meter styleEcco un’idea per una progress bar un po’ diversa dal solito. L’aspetto è quello dei V-meter digitali degli apparecchi audio. Solo che l’andamento della progressione non è logaritmico ma decimale e percentuale.
Può essere utilizzata come strumento di monitoraggio di operazioni lunghe eseguite sul server perché, grazie alla tecnologia Ajax, è possibile recuperare valori ad intervelli regolari da uno script PHP.

I requisiti per un corretto funzionamento sono:

  • Javascript abilitato
  • PHP con supporto GD 2.0.1 o successivi
  • FreeType library

La progress bar viene generata dinamicamente da uno script PHP che esegue l’eco di un’immagine in formato PNG. I valori passati in querystring servono per colorare le barre. La percentuale viene calcolata normalizzando il valore sul minimo e il massimo, con un’approssimazione per difetto alla decina inferiore. (p.e.: 52% accende 5 barre). Il default per il minimo e il massimo è rispettivamente 0 e 100

Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//==============================================================================
// PROGRESS BAR V-METER STYLE
//==============================================================================
if (!empty($_GET['value'])){
  $value = intval($_GET['value']);
  $min = empty($_GET['min']) ? 0 : intval($_GET['min']);
  $max = empty($_GET['max']) ? 100 : intval($_GET['max']);
}
else{
  $value = 0;
  $min = 0;
  $max = 100;
}
  $nValue = floor((($value-$min) / ($max-$min)) * 100);
  header("Content-type: image/png");
  $string = $nValue." %";
  $font = 'arial.ttf';
  $width  = 110; 
  $height = $width;
  $im = @imagecreatetruecolor ($width,$height);
  $width -=5;
  $height -=5;
  $background_color = imageColorAllocate($im, 0, 0, 0);
  $color = imageColorAllocate($im, 0, 255, 0);
  imagefill($im, 0, 0, $background_color);
  for($i=0;$i&lt;10;$i++){
    $x1 = $width;
    $y1 = $height-2 - ($i*10);
    $x2 = $width-10 - ($i*10);
    $y2 = $height-10 - ($i*10);
    if ($i&lt;(floor($nValue/10))){
      imageFilledRectangle($im, $x1, $y1, $x2,  $y2, $color);
    }
    else{
      imagerectangle($im, $x1, $y1, $x2,  $y2, $color);
    }
  }
  $text_color = imagecolorallocate ($im, 255, 255, 255);
  imagettftext($im, 14, 0, 5, $height-10, $text_color, $font, $string);
  imagepng($im);
  imagedestroy($im);

Volendo una più ampia compatibilità, è possibile evitare di utilizzare la funzione imagettftext() sostituendola con imagestring(), in questo caso vengono utilizzati i font interni con codifica latin2. Però non sono altrettanto belli e le dimensioni possibili sono solo 5. Il valore più grande restituisce una dimensione di carattere piuttosto piccola… ove possibile è preferibile usare i TTF

Questo è il codice di esempio per rappresentare la progress bar in una pagina web con un po’ di Ajax per rigenerare dinamicamente l’immagine ogni 2 secondi:

1
2
3
4
5
6
7
8
9
10
11
12
 
 
 
 
 
  <script type="text/javascript" language="javascript">
    <!-- var xml = ""; function getPage() { var url = "./randgen.php"; if (window.XMLHttpRequest) { xml = new XMLHttpRequest(); } else if (window.ActiveXObject) { xml = new ActiveXObject("Microsoft.XMLHTTP"); } else { alert("Your browser lacks the needed ability to use Ajax"); return false; } xml.onreadystatechange = processPage; xml.open("GET", url, true); xml.send(""); setTimeout('getPage()', 2*1000); } function processPage() { if (xml.readyState == 4) { if (xml.status == 200) { document.getElementById("myProgBar").src="./progbar.php?value=" + xml.responseText; } else { alert("There was a problem retrieving the XML data:\n" + xml.statusText); } } } //-->  
  </script>
 
  <script type="text/javascript" language="javascript">
  getPage();
  </script>

Test della progress bar V-meter style

 

progress bar

 

1
 

Lo script randgen.php genera dei numeri casuali da 0 a 100 solo a scopo dimostrativo, nella pratica dovrà generare il valore da rappresentare nella progress bar.

randgen.php:

1
2
3
4
5
6
7
8
$min = empty($_GET['min']) ? 0 : intval($_GET['min']);
$max = empty($_GET['max']) ? 100 : intval($_GET['max']);
// headers are sent to prevent browsers from caching
header('Expires: Fri, 25 Dec 1980 00:00:00 GMT'); // time in the past
header('Last-Modified: ' . gmdate('D, d M Y H:i:s') . 'GMT'); 
header('Cache-Control: no-cache, must-revalidate'); 
header('Pragma: no-cache');
echo rand($min,$max);

Il pacchetto completo è scaricabile qui

Conclusioni:

Siccome adoro i V-meter analogici, per capirci quelli che si trovavano sui grandi amplificatori HiFi degli anni ’70, stavo pensando anche a qualcosa del genere per il futuro, peccato che con la grafica ho qualche difficoltà…!

Riferimenti ed approfondimenti:

PHP: connettere un database MS Access

Connessione PHP-MS AccessIn questo post propongo una mini web-application in linguaggio PHP che consente di interagire con un database Microsoft Access. La limitazione principale è che il server deve girare in ambiente Windows. La connessione al database sfrutta la classe COM che fornisce un ambiente idoneo all’utilizzo di diversi tipi di componenti COM come per esempio applicazioni Word, Excel e Powerpoint, ma anche ADO. Questa classe, nel pacchetto PHP per Windows, è integrata nella distribuzione, e non è necessaria nessuna installazione. Per quanto riguarda la versione, sembra che quella minima sia la 4.1.x, ma non ho avuto modo di fare prove. Suggerirei comunque di utilizzare le versioni 5.2.x per stare tranquilli!

Una generica connessione ad un database MS Access, ed il riempimento di un recordset può essere avviata con queste istruzioni:

1
2
3
4
5
6
7
8
$cn = new COM("ADODB.Connection");
$cnStr = "DRIVER={Microsoft Access Driver (*.mdb)}; DBQ=".
            realpath("./nomeDatabase.mdb").";";
$cn-&gt;open($cnStr);
$rs = $cn-&gt;execute("SELECT * FROM nomeTabella");
...
$rs-&gt;Close();
$cn-&gt;Close();

Tornando alla mini-applicazione che ha uno scopo prettamente dimostrativo, le sue funzioni sono:

  • Selezionare una tabella di un file MS Access e mostrare l’elenco dei records
  • Selezionare attraverso la chiave primaria un record e modificare uno o più campi
  • Selezionare attraverso la chiave primaria un record e cancellarlo
  • Inserire un nuovo record

Per poter utilizzare l’applicazione, è necessario innanzitutto modificare le impostazioni definite nel file config.php definendo il nome e il percorso del database, il nome della tabella, il nome e la posizione della chiave primaria e la possibilità di attivare o meno la modifica e cancellazione dei record attraverso i link alla chiave primaria.

Il codice del file principale che mostra la lista dei record e i form per le modfiche, le cancellazioni e gli inserimenti è disponibile leggendo il file test.php.
Un ultimo file: modify.php si occupa di gestire le POST ed effettuare le query di inserimento, aggiornamento e cancellazione.

Alcune annotazioni: per semplificarsi la vita con Access è bene non dare mai il nome “note” ad un campo, perché è una parola chiave. Se proprio fosse necessario, bisognerà riferirsi a quel campo con la forma nometabella.note.
Altra considerazione: se in PHP è attiva la direttiva magic_quotes_gpc le variabili POST verranno trattate con i caratteri di escape per l’apostrofo.
Per memorizzare questi dati nel database, sarà quindi necessario fare prima uno stripslahes() e poi rimpiazzare gli apostrofi raddoppiandoli (che è il modo di “escapare” in Access!).
Infine, per motivi di tempo non ho gestito gli errori della classe COM, però è possibile farlo controllando le eccezione tramite la classe com_exception.

Molte curiosità sull’argomento trovano risposta in questa FAQ

Download:

Il pacchetto comprendente tutti i file PHP, il foglio stile e il database MS Access fatture.mdb è scaricabile qui.

Uno screenshot:

Screenshot dell'applicazione
Screenshot dell’applicazione

Conclusioni:

Sono convinto che le cose che sono nate per stare in coppia diano i risultati migliori, quindi PHP con MySQL. Però avere a disposizione la possibilità di interagire con un database così diffuso e così fortemente legato alle applicazioni Microsoft (Access si sposa bene con Visual Basic!) è un’ottima cosa. Non fosse altro per poter gestire delle emergenze, uno scambio di dati, la migrazione dei dati e via dicendo. O magari semplicemente per non perdere tempo e riutilizzare vecchie applicazioni con il vantaggio delle web-application.

Riferimenti ed approfondimenti:


andrea ha scritto:

l’esempio riportato è perfetto!

Alex ha scritto:

Molto utile, sono del parere che gli esempi pratici siano molto più efficaci e comprensibili di una una tonnellata di teoria.
Grazie

PHP: calcolare la deviazione standard, la varianza, la covarianza e la correlazione

Karl PearsonPer rimanere nel tema del precedente post sulla regressione lineare, cioè la statistica, vi propongo una funzione PHP davvero semplicissima che calcola altri quattro fra i più utilizzati indici della cosiddetta “statistica descrittiva”:

1. deviazione standard
2. varianza
3. covarianza
4. correlazione di Pearson

Vediamo brevemente cosa rappresentano e come si calcolano.

Le prime due (deviazione standard e varianza) sono strettamente legate, e servono a fornire la dimensione della dispersione dei dati. Per capire meglio, immaginiamo due serie di dati: a = { 2, 4, 3, 2.5, 3.5, 3 } e b = { 1, 5, 9, -3, -12, 18 }.
In entrambi i casi la media è 3, mentre la deviazione standard di a è = 0.6455 e quella di b è = 9.3986. La deviazione standard ci dice che i dati di b sono molto più dispersi di quelli di a ( …per chi non lo avesse già capito ad occhio!). Bisogna però pensare che la serie potrebbe essere molto lunga e a quel punto il metodo “occhio-metrico”, ovviamente non ci sarebbe di aiuto!

La deviazione standard viene calcolata facendo la radice quadrata della media dei quadrati degli scarti. In effetti elevando al quadrato gli scarti, ci si mette al riparo dalla compensazione che potrebbe essere data dagli scarti positivi e quelli negativi che altrimenti, si annullerebbero

La formula per il calcolo della deviazione standard è:

Deviazione standard

La varianza è il quadrato della deviazione standard, e non ci dice nulla di più o di meno…

Formula della varianza:

Varianza.png

La covarianza ci indica invece quanto sia contemporanea la variazione di due variabili. E’ interessante notare che, se le due variabili coincidono, ovvero x=y la covarianza diventa la varianza di x.

La formula è:

Covarianza.png

I valori che assume la covarianza, non sono troppo leggibili… nel senso che non danno immediatamente il senso della variazione, se non agli addetti ai lavori. In nostro soccorso però, esiste un’altra misura che già dal nome, ci pare di più immediata leggibilità: la correlazione.

Indice di correlazione di Pearson:

Correlazione

La correlazione di Pearson (nella foto in alto) è il risultato della covarianza diviso il prodotto delle deviazioni standard delle due variabili che si stanno confrontando. Questa misura serve a capire quanto due serie di variabili casuali siano legate fra loro, si dice, appunto: correlate.

Questo coefficiente assume sempre valori compresi fra -1 e +1 e rileggendo le definizioni dei parametri precedenti, è facile capire il perché!

Analizzando il risultato possiamo stabilire che:

  • se ρxy > 0 esiste una correlazione positiva, tanto maggiore quanto ci si avvicina a ρxy = 1
  • se ρxy = 0 non c’è correlazione fra le due variabili, ovvero sono indipendenti
  • se ρxy < 0 esiste una correlazione negativa, tanto maggiore quanto ci si avvicina a ρxy = -1

Sembra piuttosto semplice, ma attenzione alle trappole della statistica: se due variabili danno come risultato del coefficiente di correlazione: 0.87, non è necessariamente detto che abbiano un rapporto di causalità diretto (x dipende da y o viceversa). E’ altrettanto probabile che entrambe dipendano da una terza variabile z che rappresenta una causa comune.

Ed ecco dunque il codice PHP della funzione che restituisce queste misure statistiche. (Ho liberamente tradotto il codice di un programma GW-BASIC scritto da Roberto Vacca e pubblicato sul libro “Anche tu matematico” che è possibile acquistare qui e che consiglio vivamente a tutti di leggere!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function correl($X,$Y)
{
  if (!is_array($X) && !is_array($Y)) return false;
  if (count($X) <> count($Y)) return false;
  if (empty($X) || empty($Y)) return false;
 
  $n = count($X);
  $mediaX = array_sum($X)/$n; // media delle x
  $mediaY = array_sum($Y)/$n; // media delle y
 
  $SS = 0;
  $SX = 0;
  $SY = 0;
 
  for($i=0;$i<$n;$i++){
    $SS += ($X[$i] - $mediaX) * ($Y[$i] - $mediaY);
    $SX += pow(($X[$i] - $mediaX),2);
    $SY += pow(($Y[$i] - $mediaY),2);
  }
 
  $M = sqrt($SX)/sqrt($n);
  $M2 = pow($M,2);
  $N = sqrt($SY)/sqrt($n);
  $N2 = pow($N,2);
  $RR = $SS / (sqrt($SX) * sqrt($SY));
 
  $res = array("media x"=>$mediaX, 
               "media y"=>$mediaY,
               "correlazione"=>$RR,
               "varianza x"=>$M2,
               "varianza y"=>$N2,
               "dev. standard x"=>$M,
               "dev. standard y"=>$N
              );
 
  return $res;
}

Conclusioni:

La statistica viene spesso usata per trarre conclusioni tanto categoriche quanto errate. Questo perché a fronte di una certa difficoltà nell’eseguire i calcoli, sembra molto semplice trarre le conclusioni. Ma le cose non stanno proprio così perché, riprendendo appunto una citazione latina dal libro di Roberto Vacca: “Post hoc, ergo propter hoc” (trad.: “dopo di questo, quindi a causa di questo”) è una conclusione semplicistica che non rispecchia quasi mai la realtà, che si presenta spesso decisamente più complessa!

Riferimenti ed approfondimenti:

PHP: calcolare la retta di regressione lineare con i minimi quadrati

Grafico della retta di regressione lineare
Grafico della retta di regressione lineare

Uno strumento statistico molto usato in tutti i campi è la regressione lineare con il metodo dei minimi quadrati. Questa procedura serve a trovare una curva che interpoli al meglio una serie di dati campionari, che siano in una certa relazione fra di loro. Esaminiamo il caso più semplice, quello in cui la relazione sia lineare e quindi la migliore curva interpolante sia una retta.
Il metodo dei minimi quadrati si basa sul principio per il quale la migliore curva interpolante di un dato insieme di punti è la curva che ha la proprietà di avere minima la somma degli scarti quadratici, ovvero le differenze elevate al quadrato delle singole distanze fra i punti dati e i punti corrispondenti della retta interpolante.

Il procedimento per determinare i punti della nostra retta viene calcolato risolvendo:

Equazione della retta dei minimi quadrati

sapendo che il termine noto si ricava da:

termine noto della retta dei minimi quadrati

sostituendo q e sviluppando il quadrato si ottiene:

equazione parabola

… a vederla così sembra bruttina, ma con le opportune sostituzioni rispetto a m:

sostituzioni rispetto a m

otteniamo:

equazione parabola semplice

… adesso è più leggibile, è una equazione di una parabola. Trovare il valore minimo equivale a trovare il vertice. Qui bisognerebbe recuperare qualche reminiscenza sul calcolo delle derivate, comunque la soluzione è:

vertice della parabola

m, guarda caso… è anche il coefficiente angolare della nostra retta: quello che ci mancava!
Ora abbiamo in mano tutti i dati per costruire l’algoritmo.
Ecco quindi il codice della funzione, sviluppato in linguaggio PHP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function regressione($X,$Y)
{
  if (!is_array($X) &amp;&amp; !is_array($Y)) return false;
  if (count($X) &lt;&gt; count($Y)) return false;
  if (empty($X) || empty($Y)) return false;
 
  $regres = array();
  $n = count($X);
  $mx = array_sum($X)/$n; // media delle x
  $my = array_sum($Y)/$n; // media delle y
  $sxy = 0;
  $sxsqr = 0;
 
  for ($i=0;$i&lt;$n;$i++){
    $sxy += ($X[$i] - $mx) * ($Y[$i] - $my);
    $sxsqr += pow(($X[$i] - $mx),2); // somma degli scarti quadratici medi
  }
 
  $m = $sxy / $sxsqr; // coefficiente angolare
  $q = $my - $m * $mx; // termine noto
 
  for ($i=0;$i&lt;$n;$i++){
    $regres[$i] = $m * $X[$i] + $q;
  }
 
  return $regres;
}

La funzione restituisce l’array delle ordinate della retta di regressione. I dati campione si riferiscono al solito rapporto peso / altezza di alcune persone. Per una più chiara rappresentazione dei dati, è necessario realizzare un grafico con il modello “dispersione” per i dati campionari e il modello “retta” per i dati della regressione.

Ho utilizzato il plugin di JQuery: Flot, facendo generare server-side lo script necessario alla rappresentazione del grafico. L’esempio di applicazione di questa funzione e del grafico correlato è visibile in questa demo.

Per completezza occorre dire che bisognerebbe calcolare anche il coefficiente R2 che fornisce indicazioni sulla qualità della correlazione rispetto ai dati. Il coefficiente varia tra 0 e 1 e, tanto più si avvicina a 1, tanto più i dati sono ben correlati.

Conclusioni:

Un breve ripasso di statistica e matematica delle superiori si è reso necessario per sviluppare un algoritmo molto usato, ma non sempre con cognizione di causa!

Riferimenti ed approfondimenti:

PHP: test di algoritmi per generare permutazioni con e senza ricorsione

Benchmarks di algoritmi per le permutazioni
Benchmarks di algoritmi per le permutazioni

Una definizione abbastanza intuitiva delle permutazioni potrebbe essere: “Le permutazioni semplici di n elementi distinti sono tutti i diversi gruppi che si possono formare con gli elementi dati, che rispettino le seguenti clausole:

  1. Ogni gruppo deve essere composto da n elementi.
  2. Un elemento non può essere duplicato in un gruppo.
  3. Due gruppi sono distinti quando differiscono solo per l’ordine con cui sono disposti gli elementi.

La matematica, in particolare il calcolo combinatorio ci insegna che tutte le possibili combinazioni di n elementi sono n!. Per fare un esempio, tutte le possibili permutazioni delle lettere che compongono la parola “mare“, sono 4!, ovvero 4*3*2*1 = 24.
In questo caso, e in tutti i casi in cui tutte le lettere che compongono una certa parola sono distinte, le permutazioni equivalgono agli anagrammi. Nel caso in cui vi siano lettere ripetute, il numero di anagrammi sarà minore. Ad esempio gli anagrammi della parola “olio” sono 4! / 2! = 12

L’implementazione non è banale, ma di algoritmi per la risoluzione del problema “permutazioni” ce ne sono parecchi anche perché l’argomento è quasi sempre presente nei programmi di studio ad indirizzo informatico, quindi è inutile scervellarsi, basta cercarli e cercare di capire la logica con la quale sono stati composti. Cosa più interessante, invece è cercare quello più efficiente.

Per la comparazione ho scelto tre degli algoritmi più noti e comuni, due di essi utilizzano la ricorsione mentre il terzo no. Normalmente il linguaggio con cui vengono presentati questi algoritmi è il C, oppure uno pseudocodice, quindi ho provveduto ad effettuare la traduzione in PHP.

Il primo algoritmo preso in considerazione è quello ricorsivo tradizionale, forse il più conosciuto, tratto da “Appunti di informatica libera” capitolo 595.4 (Algoritmi tradizionali) Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Funzione ricorsiva
function Perm($lista, $k, $m) {
  if ($k == $m){
    $parola = "";
    for ($i=0; $i&lt;=$m; $i++){
      $parola .= $lista[$i];
    }
  echo ($parola."
");
  }
  else{
    for ($i=$k; $i&lt;=$m; $i++){
      $tmp = $lista[$k];
      $lista[$k] = $lista[$i];
      $lista[$i] = $tmp;
      Perm($lista, $k+1, $m);          
      $tmp = $lista[$k];
      $lista[$k] = $lista[$i];
      $lista[$i] = $tmp;
    }
  }   
}

Il secondo preso in esame, sempre ricorsivo, è pubblicato negli “user contribs” del manuale PHP. Si tratta di una versione modificata da alejandro dot garza at itesm dot mx di un algoritmo presentato su uno dei libri del noto editore O’Reilly. Sebbene non sia efficientissimo in termini di prestazioni, si tratta comunque di un esempio interessante per chi programma in PHP, in quanto utilizza alcune funzioni native del linguaggio. Ho commentato le istruzioni per la restituzione del risultato in un array, perché sebbene comodo, lo avrebbe penalizzato eccessivamente.
Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function array_2D_permute($items, $perms = array( )) {
//static $permuted_array;
    if (empty($items)) {
        //$permuted_array[]=$perms;
        //print_r($new);
      print join('', $perms) . "
";
    }  else {
        for ($i = count($items) - 1; $i &gt;= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             array_2D_permute($newitems, $newperms);
         }
         //return $permuted_array;
    }
}

Infine un algoritmo non ricorsivo ideato da Phillip Paul Fuchs, il riferimento è: Scalable Permutations, in particolare ho tradotto in PHP l’esempio descritto in The Counting QuickPerm Algorithm. Phillip Paul Fuchs è un vero esperto di queste tematiche e ha scritto anche un libro sull’argomento. Non a caso, dunque, il suo algoritmo risulta il più efficiente!
Ecco il codice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function Fuchs_perm($buf){
  $res = implode("",$buf);
  echo("$res
");
  $string_length = count($buf);
  for($i=0;$i&lt;$string_length;$i++){
    $p[$i]=0;
  }
  $i=1;
  while($i &lt; $string_length){
   if ($p[$i] &lt; $i) {
      $j = $i % 2 * $p[$i];
      $tmp=$buf[$j];
      $buf[$j]=$buf[$i];
      $buf[$i]=$tmp;
      $res = implode("",$buf);
      echo("$res
");
      $p[$i]++;
      $i=1;
   } else {
      $p[$i] = 0;
      $i++;
   }
  }
}

Per testare la velocità di esecuzione ho utilizzato questa interessante classe PHP realizzata da Ioannis Cherouvim: A time measuring and performance benchmarking class, eliminando tutte le istruzioni di stampa dell’output. I risultati sono visibili nella seguente tabella e nel grafico all’inizio dell’articolo.

Benchmarks di algoritmi per le permutazioni:
Algoritmo2 lett.3 lett.4 lett.5 lett.6 lett.7 lett.8 lett.
Algoritmo non ricorsivo Fuchs0,11010,11790,14210,27781,22007,237158,1750
Algoritmo ricorsivo tradizionale0,11690,15410,31301,19787,174158,0190440,7771
Algoritmo ricorsivo O’Reilly0,19700,28980,53612,301013,8372106,2979854,8127

Se volete fare qualche test con questi 3 algoritmi potete scaricare questo pacchetto
E’ richiesto PHP versione 5.3.x o superiore!

Conclusioni:

I risultati parlano da soli e rispecchiano le mie aspettative. L’algoritmo di Fuchs, è nettamente migliore degli altri, altamente ottimizzato e non ricorsivo. Quelli ricorsivi soffrono degli svantaggi tipici di questa tecnica: ogni chiamata ricorsiva consuma memoria ed utilizza un salto ad una funzione che produce un inevitabile rallentamento.