python - una - Multiplicación de matrices en Clojure vs Numpy

numpy tutorial español pdf

Question

Estoy trabajando en una aplicación en Clojure que necesita multiplicar matrices grandes y me encuentro con problemas de rendimiento grandes en comparación con una versión idéntica de Numpy. Numpy parece ser capaz de multiplicar una matriz de 1,000,000x23 por su transposición en menos de un segundo, mientras que el código clojure equivalente toma más de seis minutos. (Puedo imprimir la matriz resultante de Numpy, así que definitivamente está evaluando todo).

¿Estoy haciendo algo terriblemente mal en este código de Clojure? ¿Hay algún truco de Numpy que pueda intentar imitar?

Aquí está la pitón:

import numpy as np

def test_my_mult(n):
    A = np.random.rand(n*23).reshape(n,23)
    At = A.T

    t0 = time.time()
    res = np.dot(A.T, A)
    print time.time() - t0
    print np.shape(res)

    return res

# Example (returns a 23x23 matrix):
# >>> results = test_my_mult(1000000)
# 
# 0.906938076019
# (23, 23)

Y el clojure:

(defn feature-vec [n]
  (map (partial cons 1)
       (for [x (range n)]
         (take 22 (repeatedly rand)))))

(defn dot-product [x y]
  (reduce + (map * x y)))

(defn transpose
  "returns the transposition of a `coll` of vectors"
  [coll]
  (apply map vector coll))

(defn matrix-mult
  [mat1 mat2]
  (let [row-mult (fn [mat row]
                   (map (partial dot-product row)
                        (transpose mat)))]
    (map (partial row-mult mat2)
         mat1)))

(defn test-my-mult
  [n afn]
  (let [xs  (feature-vec n)
        xst (transpose xs)]
    (time (dorun (afn xst xs)))))

;; Example (yields a 23x23 matrix):
;; (test-my-mult 1000 i/mmult) => "Elapsed time: 32.626 msecs"
;; (test-my-mult 10000 i/mmult) => "Elapsed time: 628.841 msecs"

;; (test-my-mult 1000 matrix-mult) => "Elapsed time: 14.748 msecs"
;; (test-my-mult 10000 matrix-mult) => "Elapsed time: 434.128 msecs"
;; (test-my-mult 1000000 matrix-mult) => "Elapsed time: 375751.999 msecs"


;; Test from wikipedia
;; (def A [[14 9 3] [2 11 15] [0 12 17] [5 2 3]])
;; (def B [[12 25] [9 10] [8 5]])

;; user> (matrix-mult A B)
;; ((273 455) (243 235) (244 205) (102 160))

ACTUALIZACIÓN: Implementé el mismo punto de referencia utilizando la biblioteca JBLAS y encontré mejoras de velocidad masivas y masivas. Gracias a todos por su aporte! Es hora de envolver a este imbécil en Clojure. Aquí está el nuevo código:

(import ''[org.jblas FloatMatrix])

(defn feature-vec [n]
  (FloatMatrix.
   (into-array (for [x (range n)]
                 (float-array (cons 1 (take 22 (repeatedly rand))))))))

(defn test-mult [n]
  (let [xs  (feature-vec n)
        xst (.transpose xs)]
    (time (let [result (.mmul xst xs)]
            [(.rows result)
             (.columns result)]))))

;; user> (test-mult 10000)
;; "Elapsed time: 6.99 msecs"
;; [23 23]

;; user> (test-mult 100000)
;; "Elapsed time: 43.88 msecs"
;; [23 23]

;; user> (test-mult 1000000)
;; "Elapsed time: 383.439 msecs"
;; [23 23]

(defn matrix-stream [rows cols]
  (repeatedly #(FloatMatrix/randn rows cols)))

(defn square-benchmark
  "Times the multiplication of a square matrix."
  [n]
  (let [[a b c] (matrix-stream n n)]
    (time (.mmuli a b c))
    nil))

;; forma.matrix.jblas> (square-benchmark 10)
;; "Elapsed time: 0.113 msecs"
;; nil
;; forma.matrix.jblas> (square-benchmark 100)
;; "Elapsed time: 0.548 msecs"
;; nil
;; forma.matrix.jblas> (square-benchmark 1000)
;; "Elapsed time: 107.555 msecs"
;; nil
;; forma.matrix.jblas> (square-benchmark 2000)
;; "Elapsed time: 793.022 msecs"
;; nil

Answer 1

Acabo de organizar un pequeño tiroteo entre Incanter 1.3 y JBLAS 1.2.1. Aquí está el código:

(ns ml-class.experiments.mmult
  [:use [incanter core]]
  [:import [org.jblas DoubleMatrix]])

(defn -main [m]
  (let [n 23 m (Integer/parseInt m)
        ai (matrix (vec (double-array (* m n) (repeatedly rand))) n)
        ab (DoubleMatrix/rand m n)
        ti (copy (trans ai))
        tb (.transpose ab)]
    (dotimes [i 20]
      (print "Incanter: ") (time (mmult ti ai))
      (print "   jBLAS: ") (time (.mmul tb ab)))))

En mi prueba, Incanter es consistentemente más lento que jBLAS en aproximadamente 45% en la multiplicación de matriz simple. Sin embargo, la función trans Incanter no crea una nueva copia de una matriz, y por lo tanto (.mmul (.transpose ab) ab) en jBLAS toma el doble de memoria y es solo un 15% más rápido que (mmult (trans ai) ai) en Incanter.

Dado el gran conjunto de características de Incanter (especialmente el trazado de la biblioteca), no creo que cambie a jBLAS en el corto plazo. Aún así, me encantaría ver otro tiroteo entre jBLAS y Parallel Colt, y tal vez vale la pena considerar reemplazar Parallel Colt con jBLAS en Incanter. :-)

EDITAR: Aquí están los números absolutos (en mseg.) Que obtuve en mi (bastante lenta) PC:

Incanter: 665.362452
   jBLAS: 459.311598
   numpy: 353.777885

Para cada biblioteca, elegí el mejor tiempo de 20 ejecuciones, tamaño de matriz 23x400000.

PD. Los resultados de Haskell hmatrix están cerca del numpy, pero no estoy seguro de cómo compararlos correctamente.

Answer 2

Como @littleidea y otros han señalado que su versión numpy está usando LAPACK / BLAS / ATLAS, que será mucho más rápido que cualquier cosa que haga en clojure, ya que ha sido afinado durante años. :)

Dicho esto, el mayor problema con el código de Clojure es que está usando dobles, como en dobles en caja. Yo llamo a esto el problema del "doble perezoso" y me he topado con él en el trabajo varias veces. A partir de ahora, incluso con 1.3, las colecciones de clojure no son primitivas. (Puedes crear un vector de primitivas pero no te servirá de nada, ya que todas las funciones secundarias terminarán encajándolas!) También debo decir que las mejoras primitivas en 1.3 son bastante buenas y terminan ayudando ... simplemente no hay un 100% de compatibilidad primitiva WRT en colecciones).

Al hacer cualquier tipo de matemática matricial en Clojure, realmente necesita usar matrices Java o, mejor aún, bibliotecas matriciales. Incanter usa parrelcolt, pero debes tener cuidado con las funciones de incanter que usas ... ya que muchas de ellas hacen que las matrices sean seguras, lo que termina encajonando los dobles, dándote un rendimiento similar al que estás viendo actualmente. (Por cierto, tengo mis propios contenedores de parrelcolt que podría lanzar si crees que serían útiles.)

Para usar las bibliotecas BLAS tienes un par de opciones en java-land. Con todas estas opciones, debe pagar un impuesto JNA ... todos sus datos deben copiarse para poder procesarlos. Este impuesto tiene sentido cuando se realizan operaciones vinculadas a la CPU, como las descomposiciones de la matriz, y cuyo tiempo de procesamiento lleva más tiempo que el que se tarda en copiar los datos. Para operaciones más simples con matrices pequeñas, entonces permanecer en Java será probablemente más rápido. Solo necesita hacer algunas pruebas como lo ha hecho anteriormente para ver qué funciona mejor para usted.

Aquí están sus opciones para usar BLAS de java:

JBLAS

http://code.google.com/p/netlib-java/

• API para arriba: http://code.google.com/p/matrix-toolkits-java/

Debo señalar que parrelcolt usa el proyecto netlib-java. Lo que significa, creo, si lo configura correctamente, usará BLAS. Sin embargo, no he verificado esto. Para una explicación sobre las diferencias entre jblas y netlib-java, mire este hilo que comencé sobre la lista de correo de jblas:

http://groups.google.com/group/jblas-users/browse_thread/thread/c9b3867572331aa5

También debería señalar la biblioteca de Universal Java Matrix Package:

http://sourceforge.net/projects/ujmp/

¡Envuelve todas las bibliotecas que he mencionado, y algo más! Sin embargo, no he analizado demasiado la API para saber qué tan permeable es su abstracción. Parece un buen proyecto. Terminé usando mis propios envoltorios de clojure de parrelcolt, ya que eran lo suficientemente rápidos y realmente me gustó bastante la API Colt. (Colt usa objetos de función, ¡lo que significa que pude pasar las funciones de clojure sin problemas!)

Answer 3

El código Numpy utiliza bibliotecas integradas, escritas en Fortran en las últimas décadas y optimizadas por los autores, su proveedor de CPU y su distribuidor de sistema operativo (así como las personas Numpy) para un rendimiento máximo. Acabas de hacer el enfoque completamente directo y obvio de la multiplicación de matrices. No es sorprendente, realmente, que el rendimiento sea diferente.

Pero si eres insistente al hacerlo en Clojure, considera buscar mejores algoritmos , utilizando bucles directos en lugar de funciones de orden superior como reduce , o encontrar una biblioteca de álgebra matricial adecuada para Java (dudo que haya buenos en Clojure, pero realmente no lo sé) escrito por un matemático competente.

Finalmente, busca cómo escribir correctamente Clojure rápido. Utilice sugerencias de tipo, ejecute un generador de perfiles en su código (¡sorpresa! La función de producto de punto está consumiendo la mayor cantidad de tiempo), y suelte las características de alto nivel dentro de sus bucles ajustados.

Answer 4

La versión de Python se está compilando en un bucle en C, mientras que la versión de Clojure está creando una nueva secuencia intermedia para cada una de las llamadas a mapear en este código. Es probable que la diferencia de rendimiento que vea provenga de la diferencia de las estructuras de datos.

Para mejorar, puedes jugar con una biblioteca como Incanter o escribir tu propia versión como se explica en esta pregunta SO . ver también este , neanderthal o nd4j . Si realmente desea permanecer con las secuencias para mantener las propiedades de evaluación diferida, etc., puede obtener un impulso real al observar los transients para los cálculos internos de la matriz.

EDITAR: se olvidó de agregar el primer paso para ajustar clojure, activar "advertir al reflexionar"

Answer 5

No tengo ninguna respuesta específica para ti; solo algunas sugerencias

1. Use un generador de perfiles para averiguar dónde se está gastando el tiempo
2. establezca warn-on-reflection y use sugerencias tipo cuando sea necesario
3. Puede que tenga que renunciar a algunas construcciones de alto nivel e ir con bucle-recurrir a sqeeze a cabo esa última onza de rendimiento

IME, el código de Clojure debería funcionar bastante cerca de Java (2 o 3X). Pero tienes que trabajar en eso.

Answer 6

Numpy enlaza las rutinas BLAS / Lapack que se han optimizado durante décadas en el nivel de la arquitectura de la máquina, mientras que Clojure implementa la multiplicación de la manera más directa e ingenua.

Cada vez que tenga operaciones de matrices / vectores no triviales para realizar, probablemente debería vincularse a BLAS / LAPACK.

El único momento en que esto no será más rápido es para matrices pequeñas de idiomas en los que la sobrecarga de traducir la representación de datos entre el tiempo de ejecución del idioma y el LAPACK supera el tiempo dedicado al cálculo.

Answer 7

Numpy está altamente optimizado para el álgebra lineal. Ciertamente para matrices grandes, donde la mayor parte del procesamiento está en el código C nativo.

Para que coincida con este rendimiento (suponiendo que sea posible en Java) tendría que quitar la mayoría de las abstracciones de Clojure: no utilice mapas con funciones anónimas cuando itere sobre matrices grandes, agregue sugerencias de tipo para permitir el uso de matrices en bruto de Java, etc. .

Probablemente, la mejor opción sea utilizar una biblioteca Java preparada y optimizada para computación numérica (http://math.nist.gov/javanumerics/ o similar).

Answer 8

Si quieres hacer numerics en Clojure, te recomiendo utilizar Incanter lugar de intentar rodar tus propias funciones de matriz y cosas por el estilo.

Incanter usa Parallel Colt debajo del capó, que es bastante rápido.

EDITAR:

A principios de 2013, si desea hacer números en Clojure, le recomiendo visitar core.matrix

Answer 9

Solo usa map () si tiene sentido. Lo que significa que si tiene un problema específico como multiplicar dos matrices, no intente asignarlo (), solo multiplique las matrices.

Tiendo a usar map () solo cuando tiene sentido lingüístico (es decir, si el programa es realmente más legible que sin él). La multiplicación de matrices es un bucle tan obvio que su cartografía no tiene sentido.

Tuya.

Pedro Fortuny.