Overblog
Suivre ce blog Administration + Créer mon blog
22 janvier 2012 7 22 /01 /janvier /2012 14:23

NTILE is good for you

Connaître la répartition des valeurs, c'est la clef pour briller en société et réussir ses projets.

 

Genre vous avez une ressource payante, et un résultat qui sera fonction croissante de la quantité de ressource que vous allouez. Ce qui vous intéresse, c'est bien entendu la gueule de la courbe de cette fonction, son côté linéaire, logarithmique ou exponentiel, ...

"En investissant 2M dans votre campagne, vous aurez un taux de conversion de 90%. En investissant 3M, vous atteindrez 91%"

 

Pour ce genre de problèmatique, on se tape un peu de connaître la moyenne ou l'écart type d'une population.

Moi ce qui m'excite, ce sont les "n-tile" !

 

En français, on appelle ça des quantiles, avec les exemples les plus connus : quartiles, déciles, centiles, ...

http://fr.wikipedia.org/wiki/Quantile

 

Exemple concret : en ces temps de crise, un pote partageait le lien suivant qui propose un certain nombre de statistiques sur l'assiduité des députés :

http://www.nosdeputes.fr/synthesetri/1

 

On intègre juste les données qui nous intéressent : les semaines d'activité

 

CREATE TABLE t (n number);

 

INSERT INTO t(n)
SELECT to_number(substr(lstval, case level when 1 then 0 else instr(lstval, ';', 1, level - 1) + 1 end, instr(lstval, ';',1 , level) - case level when 1 then 0 else instr(lstval, ';', 1, level - 1) end -1)) ext
FROM (
  SELECT
'42;40;40;39;39;39;39;39;39;39;39;39;38;38;38;38;38;38;38;38;38;38;38;37;37;37;37;37;37;37;37;37;37;37;37;37;37;36;'||
'36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;36;35;35;35;35;35;35;35;35;35;35;35;35;35;35;35;'||
'35;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;34;33;33;33;'||
'33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;33;32;32;32;32;32;32;'||
'32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;32;31;'||
'31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;31;30;30;30;30;30;30;'||
'30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;30;29;29;29;29;29;29;29;29;29;29;29;29;'||
'29;29;29;29;29;29;29;29;29;29;29;29;29;29;29;29;29;29;29;29;29;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;'||
'28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;28;27;27;27;27;27;27;27;27;27;27;27;27;'||
'27;27;27;27;27;27;27;27;27;27;27;27;27;27;27;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;26;'||
'26;26;26;26;26;26;26;26;26;25;25;25;25;25;25;25;25;25;25;25;25;25;25;25;25;25;25;25;24;24;24;24;24;24;24;24;24;24;'||
'24;24;24;24;24;24;24;24;24;23;23;23;23;23;23;23;23;23;23;23;23;23;23;23;22;22;22;22;22;22;22;22;22;22;22;22;22;22;'||
'22;21;21;21;21;21;21;21;21;21;21;21;21;21;21;21;21;21;21;20;20;20;20;20;20;20;20;19;19;19;19;19;19;19;18;18;18;18;'||
'18;18;18;17;17;17;17;17;17;17;16;16;16;16;16;15;15;15;15;15;15;15;15;15;14;14;13;13;12;12;12;11;11;11;11;11;11;10;'||
'10;10;9;9;8;8;8;5;5;5;4;3;3;2;1;0;0;' lstval
FROM DUAL
)
CONNECT BY level <= length(lstval) - length(replace(lstval,';',''))

 

Puis découper en déciles :

 

SQL> SELECT buk * 10 as pct, min(n) as nlow, max(n) as nhigh
  2  FROM (
  3     SELECT n, NTILE(10) OVER(ORDER BY n) buk
  4     FROM t
  5  )
  6  GROUP BY buk
  7  ORDER BY buk;

       PCT       NLOW      NHIGH
---------- ---------- ----------
        10          0         18
        20         18         23
        30         23         26
        40         26         28
        50         28         29
        60         29         31
        70         31         32
        80         32         34
        90         34         36
       100         36         42

 

=> NTILE(x) OVER (ORDER BY cols) est une fonction analytique qui pour chaque ligne, donne le x-quantile auquel la ligne appartient, la population étant partitionnée sur les critères "cols"

=> On regroupe les valeurs par quantile pour obtenir les bornes, car c'est ce qui donne de la visibilité sur la répartition.

 

Pensez-y en payant votre soda surtaxé !

Partager cet article
Repost0
Published by Pacman - dans SQL
commenter cet article …
23 décembre 2011 5 23 /12 /décembre /2011 11:48

Rebuild index does definitely not improve clustering factor

A mes débuts dans Oracle, je lisais plein de conneries sur l'optimisation.
Parmi les gros mythes, il y avait : "rebuild un index améliore le clustering factor".

C'est bien entendu absurde :
- Le clustering factor se calcule comme le nombre de changement de bloc sur les lignes de la table que tu effectues en parcourant séquentiellement les feuilles de l'index.
- Les feuilles sont triées par valeur de la clef, donc le fait de le recontruire ne change pas l'ordre des feuilles

Puis je me disais : peut-être que pour les valeurs de clef ex-aequo l'ordre d'insertion pourrait augmenter artificiellement le nombre de changement de blocs, permettant ainsi au rebuild de faire décroître le clustering factor.

Essayons !

CREATE TABLE t (i NUMBER, j NUMBER);

CREATE INDEX idxt ON t(i);

INSERT INTO t
SELECT level, level
FROM DUAL
CONNECT BY level <= 1000;

commit;

SELECT dbms_rowid.rowid_block_number(rowid) blk, count(*) cnt, min(i) mini, max(i) maxi
FROM t
GROUP BY dbms_rowid.rowid_block_number(rowid);

       BLK        CNT       MINI       MAXI
---------- ---------- ---------- ----------
   1452237        574          1        574
   1452238        426        575       1000

De i = 1 à 574, on est dans le premier bloc. Les autres sont dans le deuxième bloc.

Un petit coup de stats...

exec dbms_stats.gather_table_stats(null, 'T', cascade => true)

SELECT clustering_factor
FROM dba_indexes
WHERE index_name = 'IDXT';

CLUSTERING_FACTOR
-----------------
                2

... et ça fait bien 2, qui correspond au passage de i=574 à 575 où on passe au deuxième bloc.

Maintenant, on va séquentiellement updater i = 1 dans un bloc, puis dans l'autre.

UPDATE t
SET i = 1
WHERE i = 575;

commit;

exec dbms_stats.gather_table_stats(null, 'T', cascade => true)

SELECT clustering_factor
FROM dba_indexes
WHERE index_name = 'IDXT';

CLUSTERING_FACTOR
-----------------
                4
 

 

=> Lors du parcours de l'index, pour i = 1, on switche sur le deuxième bloc, puis on revient au premier bloc pour i = 2 : ça augmente donc le clustering factor de 2
Jusque là, pas de surprise :)

UPDATE t
SET i = 1
WHERE i = 2;

commit;

exec dbms_stats.gather_table_stats(null, 'T', cascade => true)

SELECT clustering_factor
FROM dba_indexes
WHERE index_name = 'IDXT';

CLUSTERING_FACTOR
-----------------
                4

Cette fois, je me serais dit que j'insère une feuille i = 1 après celles qui existent, et donc je devrais ajouter 2 au clustering factor... mais non !

SELECT /*+INDEX(t idxt)*/ i, dbms_rowid.rowid_block_number(rowid)
FROM t
WHERE i = 1;

        I DBMS_ROWID.ROWID_BLOCK_NUMBER(ROWID)
--------- ------------------------------------
        1                              1452237
        1                              1452237
        1                              1452238
        1                              1452238

En parcourant l'index, on voit (même si cette requête n'est pas vraiment une preuve fiable) que les blocs sont bien lus "ensemble", et non pèle-mêle !

Ah ben ouais, les feuilles sont triées sur le "couple" (clefs, rowid) !

http://docs.oracle.com/cd/B19306_01/server.102/b14220/schema.htm#i5671

Leaf Blocks
All leaf blocks are at the same depth from the root branch block. Leaf blocks store the following:
    *      The complete key value for every row
    *      ROWIDs of the table rows
All key and ROWID pairs are linked to their left and right siblings. They are sorted by (key, ROWID).

La vie est belle... Bonne dinde à tous !

Partager cet article
Repost0
Published by Pacman - dans SGBD
commenter cet article …
28 octobre 2011 5 28 /10 /octobre /2011 16:23

LOG ERRORS Oracle 10gR2 : don't rollback just for 1 single exception !

Die Softwareentwickler mögen Schleife und Cursors über alles, und finden desshalb die unwahrscheinlichsten Rechtfertigungen um die globale DML query zu vermeiden.

Unter denen gibt's die Handlung der Fehlerfällen :

"Neee, die ganze Anfrage darf nicht Rollbacked werden, nur wegen einer verdammten Zeile"

 

Aber seit 10gR2 gilt dieses Argument (fast) nicht mehr, denn es gibt jetzt die ERROR LOGGING !

 

Versuchen wir's mal mit verschiedenen Fehler Gründen...

 

1) Die Testtabelle :


 CREATE TABLE testlog (

 id NUMBER UNIQUE,

 n NUMBER CHECK(n > 0),

 c VARCHAR2(10) NOT NULL);

 

2) Die Errorlogtabelle :

 

EXEC dbms_errlog.create_error_log('TESTLOG', 'TESTERR')

 

3) Einfügen

 

SQL> INSERT INTO testlog

  2  SELECT CASE level WHEN 2 THEN 1 ELSE level END, --die zweite Zeile wird unique contraint verletzen

  3         CASE level WHEN 4 THEN -1 ELSE level END, --die vierte verletzt die positiv check bedingung

  4         CASE level WHEN 6 THEN null WHEN 8 THEN lpad('x', 12, 'x') ELSE 'd' END --die sechte die NOT NULL bedingung und die achte überschreitet die maximale Länge

  5  FROM DUAL

  6  CONNECT BY level <= 12

  7  LOG ERRORS INTO TESTERR ('instest') REJECT LIMIT UNLIMITED;

 

8 ligne(s) créée(s).

 

SQL> SELECT *

  2  FROM testlog

  3  /

 

  ID    N C

---- ---- --------------------

   1    1 d

   3    3 d

   5    5 d

   7    7 d

   9    9 d

  10   10 d

  11   11 d

  12   12 d

 

=> 8 der 12 zeilen sind erfolgreich hinzufügen worden !

 

SQL> SELECT * FROM testerr;


  PrtScr capture 3(1)

 

Und natürlich klappt  es auch mit UPDATE, MERGE UND DELETE !

 

SQL> MERGE INTO testlog a

  2  USING (SELECT level l,

  3             CASE level WHEN 4 THEN -1 ELSE level + 1 END n,

  4             CASE level WHEN 5 THEN null ELSE 'c' END c

  5         FROM DUAL CONNECT BY LEVEL <= 13) t

  6  ON (a.id = t.l)

  7  WHEN MATCHED THEN UPDATE SET a.n = t.n, a.c = t.c

  8  WHEN NOT MATCHED THEN INSERT (a.id, a.n, a.c) VALUES(t.l, t.n, t.c)

  9  LOG ERRORS INTO TESTERR('testmerge') REJECT LIMIT UNLIMITED;

 

11 lignes fusionnées.

 

SQL> SELECT * FROM testlog;

 

  ID    N C

---- ---- --------------------

   1    2 c

   3    4 c

   5    5 d

   7    8 c

   9   10 c

  10   11 c

  11   12 c

  12   13 c

   2    3 c

   6    7 c

   8    9 c

  13   14 c

 

SQL> SELECT ORA_ERR_MESG$, ORA_ERR_ROWID$, ORA_ERR_TAG$

  2  FROM testerr;

 

PrtScr-capture_3-1--copie-1.jpg

 

 

4) Trotzdem ein Paar Schertze

 

Manchmal werden die unique contraints nur "am Ende" überprüft : in diese Fälle scheitert die ganze Anfrage.

Zum beispiel den direct path load :

 

SQL> INSERT INTO testlog

  2  SELECT /*+APPEND*/ CASE level WHEN 10 THEN 1 ELSE level END, level, 'c'

  3  FROM DUAL

  4  CONNECT BY level <= 10

  5  LOG ERRORS INTO testerr ('rarghl') REJECT LIMIT UNLIMITED;

INSERT INTO testlog

*

ERREUR à la ligne 1 :

ORA-00001: unique constraint (EDGE_ADM.SYS_C00356572) violated

 

Ohne den append hint klappt's prima :

 

SQL> INSERT INTO testlog

  2  SELECT CASE level WHEN 10 THEN 1 ELSE level END, level, 'c'

  3  FROM DUAL

  4  CONNECT BY level <= 10

  5  LOG ERRORS INTO testerr ('rarghl') REJECT LIMIT UNLIMITED;

 

1 ligne créée.

Partager cet article
Repost0
Published by Pacman - dans SQL
commenter cet article …
20 juillet 2011 3 20 /07 /juillet /2011 13:03

Do not rely on any technical sort [...] part 2

C'est l'anniversaire du PacBlog ! (en fait c'était il y a deux jours)

 

Pour ses deux ans, son "Blog Rank" est retombé à 2.

(C'est en gros un indicateur qui dit que quand il est proche de 0, le blog est à chier)

 

Voilà, pour ne pas s'arrêter sur ce caca d'anniversaire, je vais quand même ajouter un complément sans aucune valeur ajoutée sur l'article précédent.

 

Donc, pour garantir l'ordre sur le résultat d'un ORDER BY, définissez un champ fictif sur chacune des requêtes composant le UNION ALL :

 

SQL> SELECT *
  2  FROM (
  3     SELECT a.*, 1 o
  4     FROM paral1 a
  5     UNION ALL
  6     SELECT b.*, 2 o
  7     FROM paral2 b)
  8  ORDER BY o
  9  /

 

Ah là là, c'est pas ça qui va faire remonter mon BlogRank...

Partager cet article
Repost0
Published by Pacman - dans SQL
commenter cet article …
7 juillet 2011 4 07 /07 /juillet /2011 13:49

Do not rely on any technical sort : always use ORDER BY clause !

Tiens aujourd'hui, mon jeune Padawan me demandait :
"Maître, quand on fait un UNION ALL, est-ce que cela garantit que le resultset comportera en premier la première requête ?"

 

On dit toujours a fort juste titre que si on veut qu'un résultat soit trié, il faut un ORDER BY.
Par exemple :
- Le GROUP BY (ne serait-ce que parce que le HASH GROUP BY est venu remplacer le SORT GROUP BY)
- Le DISTINCT (ne serait-ce que parce que le HASH UNIQUE est venu remplacer le SORT UNIQUE)
... et :
- Le UNION ALL (ne serait-ce qu'à cause du parallèle)

 

Allez, juste un petit test :

 

Dans une première table, que des "1" :

 

SQL> CREATE TABLE paral1 PARALLEL 4 AS 
 SELECT 1 n 
 FROM DUAL 
 CONNECT BY LEVEL <= 100;

 

Table crÚÚe.

 

Dans deuxième table, que des "2" :

 

SQL> CREATE TABLE paral2 PARALLEL 4 AS 
 SELECT 2 n 
 FROM DUAL 
 CONNECT BY LEVEL <= 100;

 

Table crÚÚe.

 

Et là :

SQL> SELECT * 
 FROM paral1 
 UNION ALL 
 SELECT * 
 FROM paral2;

 

... droumdroumdroumdroumdroum ... (si vous avez une meilleure version phonétique de l'onomatopée du tambour, n'hésitez pas) :

 

Tadaaam ! (c'est mélangé, hoho)

 

         N
----------
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         1
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2
         2

200 ligne(s) sÚlectionnÚe(s).

 

Partager cet article
Repost0
Published by Pacman - dans SGBD
commenter cet article …
20 juin 2011 1 20 /06 /juin /2011 13:43

Euler Challenge 3: the greatest prime factor

Ouais, on revient aux choses sérieuses : EULER CHALLENGE N°3 !

http://projecteuler.net/index.php?section=problems

 

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

 

DISCLAIMER :

J'ai la flemme de m'inscrire sur le site, donc je ne prendrais même pas la peine de vérifier mes résultats


Ah, la décomposition en facteurs premiers... il n'y a pas grand chose de plus beau en ce monde !

 

1) La méthode brutale

 

Sous forme de questions successives :
Mon entier donné est-il divisible par un nombre entre 2 et lui-même ?
Ce diviseur est-il non divisible par un nombre entre 2 et lui-même (moins un) ?

 

=> Le plus grand de ceux-là, c'est le gagnant.

 

Allez :

 

SQL> WITH t AS (
  2  SELECT level n
  3  FROM DUAL
  4  CONNECT BY level <= round(sqrt(600851475143))
  5  )
  6  SELECT case max(n) when 1 then 600851475143 else max(n) end
  7  FROM t t1
  8  WHERE mod(600851475143, n) = 0
  9    AND NOT EXISTS (SELECT null
 10                    FROM t t2
 11                    WHERE mod(t1.n, t2.n) = 0
 12                      AND t2.n < round(sqrt(t1.n))
 13                      AND t2.n > 1
 14                      );

 

CASEMAX(N)WHEN1THEN600851475143ELSEMAX(N)END
--------------------------------------------
                                        6857

 

2) La méthode pas géniale mais très légèrement moins naze

 

Ce qui est bien avec les diviseurs, c'est qu'ils s'emboîtent :
Si :
a = b * q
Et
b = c * q2

 

Alors d'une part c est un diviseur de a :
a = (c * q2) * q
Avec c < b

 

D'autre part, si a n'est pas divisible par n < b, alors b ne l'est pas non plus (ni c d'ailleurs).

 

Donc pour limiter la complexité moyenne de la décomposition, on peut travailler itérativement sur le quotient.
La démarche :
- On prend n = 600851475143
- On cherche le premier diviseur de n entre 2 et racine carrée de n
- Dès qu'on trouve un diviseur p, il est premier par construction (sinon, un autre aurait été diviseur avant lui)

 

- On prend le quotient n1 = n / p
- On recherche le premier diviseur de n1 entre p et racine carrée de n1
- Dès qu'on trouve un diviseur p1, il est premier par construction (sinon, un autre aurait été diviseur avant lui)

 

... on itère jusqu'à ce que le diviseur à tester soit supérieur à la racine du quotient.

A la fin, le quotient qu'on n'a pas réussi à diviser est le plus grand facteur premier !

 

SQL> SELECT n, p, m, n / p
  2  FROM (
  3      SELECT 600851475143 n, 2 p, round(sqrt(13195)) m
  4      FROM DUAL
  5      ) t
  6  MODEL
  7  DIMENSION BY (0 l)
  8  MEASURES (n, p, m)
  9  RULES
 10  ITERATE(1000000) UNTIL (p[0] > m[0])
 11  (
 12      n[0] = CASE mod(n[0], p[0]) WHEN 0 THEN n[0] / p[0] ELSE n[0] END,
 13      p[0] = CASE mod(n[0], p[0]) WHEN 0 THEN p[0] ELSE p[0] + 1 END,
 14      m[0] = CASE mod(n[0], p[0]) WHEN 0 THEN round(sqrt(n[0] / p[0])) ELSE m[0] END
 15      );

         N          P          M        N/P
---------- ---------- ---------- ----------
  10086647       1471         83       6857

 

Tain, on dirait un exo de terminale...
Mais bon, j'ai vraiment pas trouvé plus joli pour chopper le plus grand facteur premier.

(Triste journée, en plus le temps est à chier...)

 

Partager cet article
Repost0
Published by Pacman - dans Journal intime
commenter cet article …
11 juin 2011 6 11 /06 /juin /2011 12:19

Reversing a string

Bon, l'autre jour, mon chef me demandait : sais tu pallindromer une chaîne de caractères sans fonction PL ?

 

... merci google, il y a une built-in fonction :)

 

1) Fonction REVERSE

 

Attendez, un petit jeu de test d'abord :

 

SQL> CREATE TABLE testrev(txt VARCHAR2(255));

Table crÚÚe.

SQL> INSERT INTO testrev VALUES ('marcel');

1 ligne crÚÚe.

SQL> INSERT INTO testrev VALUES ('robert');

1 ligne crÚÚe.

SQL> INSERT INTO testrev VALUES ('cosmetic sql is good for you');

1 ligne crÚÚe.

SQL> commit;

Validation effectuÚe.

 

Et hop :

 

SQL> SELECT txt, reverse(txt) rev
  2  FROM testrev;

TXT                                                REV

marcel                                             lecram
robert                                             trebor
cosmetic sql is good for you                       uoy rof doog si lqs citemsoc

 

Surprise, ça marche !

Mais bon, c'est pas très drôle, disons le.

EDIT :  et en plus la fonction n'est pas supportée, et elle est limitée dans un certain nombre de cas (Cf. le commentaire de Laurent)

 

Ben on va essayer de le faire à la main quand même !

 

2) Encore de la clause MODEL !

 

Alors, dans la mesure où on est capable de faire de l'itératif avec la clause MODEL, on devrait y arriver :

Il suffit d'itérer, pour chaque ligne, sur la longueur de la chaine, et construire le résultat.

 

SQL>  SELECT txt, rev
  2   FROM (
  3      SELECT txt, length(txt) lng, length(txt) cnt
  4      FROM testrev
  5   ) t
  6   MODEL
  7   PARTITION BY (ROWID)
  8   DIMENSION BY (0 n)
  9   MEASURES (txt, lpad(' ', lng) rev, lng, cnt)
 10   RULES
 11   ITERATE(1000000) UNTIL (cnt[0] = 0)
 12   (
 13      rev[0] = substr(rev[0], 1, iteration_number) || substr(txt[0], lng[0] - iteration_number, 1)
 14      , cnt[0] = cnt[0] -1)
 15   /

TXT                                                REV

cosmetic sql is good for you                       uoy rof doog si lqs citemsoc
marcel                                             lecram
robert                                             trebor

 

La question que je me pose encore cela dit : mais à quoi ça sert de pallindromer ?

Pfiou, heureusement que ce blog ne sert à rien...

 

Partager cet article
Repost0
Published by Pacman - dans SQL cosmétique
commenter cet article …
25 mai 2011 3 25 /05 /mai /2011 07:25

Euler challenge 2

Salut les gars, moi c'est Robert, et je n'aime pas les mouches.

(Il me fallait une phrase d'intro, j'ai pas trouvé mieux...)

 

Bon aujourd'hui, c'est le deuxième exo de l'Euler challenge !

 

 http://projecteuler.net/index.php?section=problems


DISCLAIMER :

J'ai la flemme de m'inscrire sur le site, donc je ne prendrais même pas la peine de vérifier mes résultats


  By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

 

1) La méthode brutale

 

Il y a quelques temps, je découvrais la clause MODEL qui permet de faire de l'itératif à partir de 10g... et donc facilement des suites récurrentes.

 

Donc du coup, c'est tout simple :

 

SQL> SELECT sum(u)
  2  FROM (
  3       SELECT n, u
  4       FROM (
  5         SELECT 0 n, 0 U FROM DUAL
  6         UNION ALL SELECT 1 n, 1 U FROM DUAL
  7         ) t
  8       MODEL
  9        dimension by (n)
 10        measures (u)
 11        rules upsert
 12        iterate(33)
 13        (u[2+iteration_number] = u[1+iteration_number] + u[iteration_number])
 14  )
 15  WHERE mod(u, 2) = 0
 16  /

    SUM(U)
----------
  4613732

 

Passionnant, n'est ce pas... allez, on va rigoler un peu plus !

 

2) La méthode mathématique

 

Bon, faire la somme de trucs qui sont déjà définis en se sommant les uns les autres, ça sent l'astuce à plein nez, non ?

(J'ai toujours fait les maths à l'intuition, ce qui explique surement mon destin pitoyable...)

 

Première remarque :

Un+2 = Un+1 + Un

Pour que Un+2 soit pair, il faut que Un+1 et Un soient soit tous les deux pairs, soit tous les deux impairs.

Mais s'ils sont tous les deux pairs, tous les autres termes le sont... et ce n'est pas le cas.

 

Bref, regardez bien les termes de la suite :

0 1 1 2 3 5 8 13 21 34 ...

Un terme sur 3 est pair, et bien sûr il est la somme des deux termes impairs précédents.

 

=> Si on s'arrête au bon endroit, la somme des termes pairs est égale à la somme des termes impairs !

 

La proposition formelle P(p) :

Quel que soit p, somme(U3i, 0<= i <= p) = somme(Ui impairs, 0<=i<=3p)

 

La preuve :

P(0) vraie, disons-le (ça c'est de l'argument !)

 

Supposons p(n) vraie, qu'en est-il de p(n+1) ?

 

somme(U3i, 0<= i <= n+1) = somme(U3i, 0<= i <= n)  + U3(n+1)

                                                 = somme(U3i, 0<= i <= n)  + U3n+1 + U3n+2

                                                 = somme(Ui impairs, 0<= i <= 3n)  + U3n+1 + U3n+2

                                                 = somme(Ui impairs, 0<= i <= 3(n+1))

 

Ca, c'est fait... 

 

somme(U3i, 0<= i <= n) = somme(Ui, 0<= i <= 3n) / 2

 

Il ne reste plus qu'à calculer la "série" de Fibonacci !

Pour cela, deuxième remarque :

quand on somme des termes qui justement se définissent comme la somme des deux précédents, on doit avoir des chances de retomber sur un de ces termes, non ?

 

Fibo 0 1 1 2 3 5 8 13 21
Série 0 1 2 4 7 12 20 33 54

 

Ben on retombe pas tout à fait dessus, mais à un près...

Somme(Ui, 0<=i<=n) = Un+2 - 1

 

(La démo par récurrence est triviale, vous la ferez vous-même !)

 

Et du coup, le résultat (en utilisant la forme analytique de Fibonacci) : 

 

somme(U3i, 0<= i <= n) = (U3n+2 - 1) / 2 = ((((1 + sqrt(5)) / 2) ^ (3n+2) - ((1 - sqrt(5)) / 2) ^ (3n+2)) / sqrt(5) - 1) / 2

 

(Ok, c'est illisible...)

 

SQL> SELECT ((power((1+sqrt(5))/2, 35) - power((1-sqrt(5))/2, 35)) / sqrt(5) - 1) / 2 res
  2  FROM dual
  3  /

       RES
----------
   4613732

 

Bon ok, le U33, je l'ai cherché à tâtons et c'est laid, mais bon !

Partager cet article
Repost0
Published by Pacman - dans SQL cosmétique
commenter cet article …
19 mai 2011 4 19 /05 /mai /2011 20:04

Euler challenge 1

Bon début, d'une longue, longue série...

 

Le challenge Nr. 1 :

 

Add all the natural numbers below one thousand that are multiples of 3 or 5.
 
Ho, facile !
 
1) La méthode brute

Ben en SQL il faut :
- générer les 1000 premier entiers
(
  - filtrer les non multiples de 3 et / ou de 5 et sommer
OU
  - sommer en annulant les non multiples de 3 et / ou de 5
)
Sans discussion, la deuxième solution est la plus proche de la philosophie du PacBlog !
 
SQL> SELECT sum(level * greatest(0, 1 - mod(level, 3) * mod(level, 5)))
  2  FROM DUAL
  3  CONNECT BY level <= 1000
  4  /

SUM(LEVEL*GREATEST(0,1-MOD(LEVEL,3)*MOD(LEVEL,5)))
--------------------------------------------------
                                            234168

- On génère les 1000 premiers entiers
- On les aditionne... avec une astuce :
  - s'ils sont multiples, le reste est 0 et le facteur est neutre
 - s'il ne sont pas multiple,1 - le produit des mods est strictement négatif, et on multiplie par 0... 
 
2) La méthode mathématique

Ben on sait additionner les nombre de 1 à N : N (N+1) / 2
(la piste de démo est : en les couplant deux à deux symétriquement par rapport au milieu, c'est comme multiplier le terme du milieu par 2)
 
Sachant que sommer des multiples de 3 (resp. 5)... c'est comme sommer des entiers consécutifs puis les multiplier par 3 (resp. 5) (vive la distributivité !), il suffit de :
- sommer les multiples de 3
- sommer les multiples de 5
- ah zut il y en a qu'on a ajoutés deux fois... ce sont les multiples de 3 et de 5 : on retranche les multiples de 3 et de 5 (ça vous rappelle pas une formule de patates ?)  
Ce qui donne :
 
SQL> SELECT
  2      trunc (1000/3) * (trunc (1000/3) + 1) / 2 * 3
  3     + trunc (1000/5) * (trunc (1000/5) + 1) / 2 * 5
  4     - trunc (1000/15) * (trunc(1000/15) + 1) /2 * 15 as res
  5  FROM DUAL
  6  /

       RES
----------
    234168

Attendez, je cherche une conclusion à tout cela...
Ho !
 
La mort, n'est qu'une étape de la vie !
EDIT : merci Keeh pour ta vigilance !
Partager cet article
Repost0
Published by Pacman - dans SQL cosmétique
commenter cet article …
19 mai 2011 4 19 /05 /mai /2011 20:02

SQL Geek loves mathematics challenges

Cher journal intime,

 

Un jour, j'ai commencé à te raconter mes fantasmes arithmétiques.

Et ce jour là, l'ami Keeh les a sur-alimentés avec son lien vers le Euler Project :

http://projecteuler.net/index.php?section=problems

 

Donc voilà, à partir d'aujourd'hui et autant que faire se peut, nous allons résoudre des défis de ce projet en SQL.

(Et si possible, avec du pur calcul)

 

Et puis tiens, je vais en faire un sur deux en allemand (l'anglais on me force à en faire au boulot, j'en vomis...)

 

DISCLAIMER :

J'ai la flemme de m'inscrire sur le site, donc je ne prendrais même pas la peine de vérifier mes résultats

Partager cet article
Repost0
Published by Pacman - dans Journal intime
commenter cet article …