(blog ‘lucindo)

Para quem ainda não sabe, o Netflix Prize é uma competição que começou no final do 2006 cujo objetivo é melhorar em 10% o algoritmo de sugestão de filmes da Netflix. Quem conseguir fazer isso recebe o prêmio de U$ 1.000.000.

Bom, fiz um pequeno código esses dias que joga os dados do Netflix Prize no Postgres para depois poder brincar um pouco com isso e quem sabe ganhar uma graninha

Usei basicamente o Postmodern e a nova versão do Postmodern-utils. Ainda preciso fazer uma página com a documentação do pacote. Nessa versão entraram algumas funções novas: set-connection-spec, create-tables, map-dao e for-each-dao.

Seguindo a sugestão do Leonardo Varuzza, agora o Postmodern-utils poder ser instalado assim:

* (asdf-install:install :postmodern-utils)

Vamos ao código. Primeiro a definição do pacote:

(eval-when (:load-toplevel :compile-toplevel :execute)
  (require :postmodern)
  (require :postmodern-utils)
  (require :cl-fad)
  (require :split-sequence))

(defpackage :netflix
  (:use :common-lisp :postmodern :postmodern-utils)
  (:export #:setup-database
           #:load-data
           #:predict-ratings
           #:movies #:id-of #:year-of #:title-of #:get-movie
           #:ratings #:user-of #:movie-of #:rating-of #:date-of
           #:get-ratings-of-user #:get-ratings-of-movie))

(in-package :netflix)

Agora alguns dados globais (mude o parametro *netflix-data-dir*):

(defparameter *netflix-data-dir* “/path/to/netflix/download”)
(defparameter *movies-file*
  (concatenate ’string *netflix-data-dir* “/movie_titles.txt”))
(defparameter *ratings-dir*
  (concatenate ’string *netflix-data-dir* “/training_set/”))

(eval-when (:load-toplevel :compile-toplevel :execute)
  (set-connection-spec :username “netflix”
                       :password “”
                       :database “netflix”
                       :hostname “localhost”))

Agora a definição da tabela movies e funções para criar e acessar daos desse tipo:

(deftable movies ()
  ((movie-id :type integer
             :accessor id-of
             :initarg :movie-id)
   (year :type string ;; may be “NULL”
         :accessor year-of
         :initarg :year)
   (title :type string
          :accessor title-of
          :initarg :title))
  (:indices movie-id)
  (:class-name movies))

(defun make-movie (movie-id year title)
  (with-pooled-connection
      (save-dao (make-instance ‘movies
                               :movie-id movie-id
                               :year year
                               :title title))))

(defun get-movie (movie-id)
  (with-pooled-connection
      (get-dao ‘movies movie-id)))

Para ler e parsear os arquivos vamos usar a seguinte função auxiliar:

(defun process-file-by-line (file-name fn)
  (with-open-file (stream file-name :external-format :iso-8859-1)
    (do ((line (read-line stream nil)
               (read-line stream nil)))
        ((null line))
      (funcall fn line))))

Com ela podemos parsear o arquivo movie_titles.txt assim:

(defun load-movies (movies-file)
  (process-file-by-line
   movies-file
   #’(lambda (line)
       (let* ((splitted-line (split-sequence:split-sequence #\, line))
              (movie-id (parse-integer (first splitted-line)))
              (year (second splitted-line))
              (title (third splitted-line)))
         (make-movie movie-id year title)))))

Depois definimos a tabela ratings e uma função para criar os daos desse tipo:

(deftable ratings ()
  ((user-id :type integer
            :accessor user-of
            :initarg :user-id)
   (movie-id :type integer
             :accessor movie-of
             :initarg :movie-id)
   (rating :type integer
           :accessor rating-of
           :initarg :rating)
   (date :type string
         :accessor date-of
         :initarg :date))
  (:indices (user-id movie-id) rating)
  (:class-name ratings))

(defun make-rating (user-id movie-id rating date)
  (with-pooled-connection
      (save-dao (make-instance ‘ratings
                               :user-id user-id
                               :movie-id movie-id
                               :rating rating
                               :date date))))

Podemos fazer algumas funções para selecionar listas de ratings, como por exemplo:

(defun get-ratings-of-user (user-id)
  (with-pooled-connection
    (select-daos ‘ratings :test `(:= user-id ,user-id))))

(defun get-ratings-of-movie (movie-id)
  (with-pooled-connection
    (select-daos ‘ratings :test `(:= movie-id ,movie-id))))

O parse dos arquivos com ratings é feito pelas seguintes funções:

(defun load-ratings-file (file)
  (let ((movie-id 0))
    (process-file-by-line
     file
     #’(lambda (line)
         (if (search “:” line)
             (setq movie-id (parse-integer line :junk-allowed t))
             (let* ((splitted-line (split-sequence:split-sequence #\, line))
                    (user-id (parse-integer (first splitted-line)))
                    (rating (parse-integer (second splitted-line)))
                    (date (third splitted-line)))
               (make-rating user-id movie-id rating date)))))
    (format t “processed: ~a~%” file)))

(defun load-ratings (ratings-dir)
  (cl-fad:walk-directory
   ratings-dir
   #’(lambda (file)
       (load-ratings-file file))))

Agora as funções para carregar todos os dados no Postgres:

(defun load-data ()
  (load-movies *movies-file*)
  (load-ratings *ratings-dir*))

(defun setup-database (&optional (first-drop nil))
  (with-pooled-connection
    (create-tables ‘(movies ratings) :first-drop first-drop)))

Por fim a função para processar os arquivos de entradas e gerar o arquivo com as previsões dada uma função de previsão que recebe três parêmetros: id do usuário, id do filme e a data da votação.

(defun predict-ratings (query-file predict-file predict-fn)
  (with-open-file (stream predict-file :direction :output)
    (let ((movie-id 0))
      (process-file-by-line
       query-file
       #’(lambda (line)
           (if (search “:” line)
               (progn
                 (setq movie-id (parse-integer line :junk-allowed t))
                 (format stream “~a:~%” movie-id))
               (let* ((splitted-line (split-sequence:split-sequence #\, line))
                      (user-id (parse-integer (first splitted-line)))
                      (date (second splitted-line)))
                 (format stream “~1$~%”
                         (funcall predict-fn user-id movie-id date)))))))))

Agora tenho todos os dados e funções para fazer a manipulação. Só falta a função de 1 milhão de dólares e rodar:

(predict-ratings “qualifying.txt” “winner.txt” #’million-dollar-function)

Download: netflix.lisp

Observação 1: carregar todos os dados no Postgres dessa maneira demora (poucos dias), pois faço um insert para cada rating, e são 100 milhões deles.

Observação 2: vale a pena ver também o excelente post do Juho Snellman sobre como processar os dados do Netflix Prize usando Common Lisp.

A submissão campeã do prêmio Best of show do IOCCC de 1989 foi o seguinte interpretador Lisp (aqui modificado para compilar no gcc de hoje):

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define p char*
#define P ,(p)
#define T(E) !strcmp(E,“()”)
#define U return
#define W while
#define X sbrk(199)
#define z atof
#define e isspace
#define D A(_)
#define E S(C(_))
#define B(y) p y(_)p _;{
#define G(y,V) B(y)p i;U sprintf(i=X,“%lf”,z(E)V z(S(C(D)))),i;}

        p sbrk(),*S(),*j(),*O,*H;K,Y,M=14;double
      z();Q(_)p _;{int V=0;W(e(*_))_++;H=_;W(V|!(e
    (*H)|*H==‘)’||(*H==‘(’&&H-_)))V+=(*H==‘(’)-(*H==
      ‘)’),H++;U H-_;}B(C)U _++,Y=Q(_),_=strncpy(X,_,Y),_[
    Y]=0,_;}B(A)_++,_+=Q(_);W(e(*_))_++;U O=X,*O=‘(’,strcpy(
  O+1,_),O;}B(Z)U _;}B(c)U C(E);}B(q)U A(E);}B(t)p i=E;U H=S(C
(D)),sprintf(O=X,T(H                 )?“(%s)”:“(%s %s”,i,H+1)

         ,O;}B(F)U S(C(A(T(E)?D:_)));}L(i,s)p

i,*s;{U isdigit(*i)     ?         z(i)!=z(s):strcmp(i,s);}
  B(b)U L(E,S(C(D)))?“()”:“t”;}B(R)U E;}B(o)U z(E)<z(S(C(D)))?
    “t”:“()”;}G(f,+)G(g,-)G(h,*)p r[4][2]={“function”   P R,
      “quote”P C,“lambda”P Z,“defun”P j};B(j)U r[M][1]=D,*
    r[M++]=C(_);}p not[99][2]={“if”P F,“equal”P b,“<”
      P o,“+”P f,“-”P g,“*”P h,“car”P c,“cdr”P q,
        “cons”P t,“t”,“t”};B(S)int Li,s;p u;if(
          isdigit(*_)|T(_))U _;for(Y=M;Y–;)
        if(!strcmp(_,*r[Y]))U r[Y][1]
          ;u=E,_=D;if(*u-‘(’)U(*((p(*)())u)
        )(_);s=Li=M;W(!T(_))r[M][1]=E,*r[M++]
    =“”,_=D;O=C(u);W(!T(O))*r[Li++]=C(O),O=A(O);U O=S
    (C(A(u))),M=s,O;}main(){H=O=X,Y=0;W(Y|!e(K=getchar()))K==
    EOF?exit(0):0,Y+=(K==‘(’)-(K==‘)’),*H++=K;*H=0,puts(S(O))
                ,
        main();{printf(“XLISP 4.0n”);}}

Essa implementação foi feita por Jari Arkko, Ora Lassila e Esko Nuutila da Universidade Tecnológica de Helsinki. Ele implementa as operações:

+	-	*	<	()
car	cdr	cons	defun	equal
function if	lambda	quote	t

Os autores propõe o seguinte teste:

(+ 2.5 3.1)
(defun fib (n)
  (if (< n 2)
      1
      (+ (fib (- n 2)) (fib (- n 1)))))
(fib 10)
(defun ! (x) (if (equal x 0) 1 (* x (! (- x 1)))))
(! 7)
(defun fn1 (fn) (+ (fn 1 2) (fn 3 4)))
(defun fn2 (a b) (+ a b))
(fn1 (function +))
(fn1 (function fn2))
(fn1 (function (lambda (z1 z2) (+ z1 z2))))
(quote a)
(cons (quote (a b)) (quote (c d e)))
(cons (quote (f)) ())
(car (quote (a b c)))
(cdr (cdr (quote (g h i))))

Mais informações aqui.

Download: jar.2.c (versão alterada para gcc 4.x)