Pregunta Rendimiento de matriz de PHP


Estoy probando un algoritmo para 2d bin packing y he elegido PHP para simularlo, ya que es mi lenguaje pan y mantequilla en la actualidad.

Como puedes ver en http://themworks.com/pack_v0.2/oopack.php?ol=1 funciona bastante bien, pero debe esperar entre 10 y 20 segundos para que quepan 100 rectángulos. Para algunos conjuntos difíciles de manejar, alcanzaría el límite de tiempo de ejecución de 30 php.

Hice algunos perfiles y muestra que la mayoría de las veces mi script pasa por diferentes partes de una pequeña matriz 2d con 0 y 1 en ella. Comprueba si cierta celda es igual a 0/1 o la establece en 0/1. Puede hacer tales operaciones millones de veces y cada vez lleva pocos microsegundos.

Creo que podría usar una matriz de booleanos en un lenguaje estáticamente tipado y las cosas serían más rápidas. O incluso hacer una matriz de valores de 1 bit. Estoy pensando en convertir todo en un lenguaje compilado. ¿PHP no es bueno para eso?

Si necesito convertirlo a C ++, ¿qué tan buenos son los convertidores automáticos? Mi script es solo un montón de bucles con matrices básicas y manipulaciones de objetos.

Editar. Esta función se llama más que cualquier otra. Lee pocas propiedades de un objeto muy simple y pasa por una pequeña parte de una matriz pequeña para comprobar si hay algún elemento que no sea igual a 0.

function fits($bin, $w, $h, $x, $y) {

    $w += $x;
    $h += $y;

    for ($i = $x; $i < $w; $i++) {

        for ($j = $y; $j < $h; $j++) {

            if ($bin[$i][$j] !== 0) {
                return false;
            }
        }
    }

    return true;    
}

Actualización: He intentado usar 1d array en lugar de 2d como una de las respuestas sugeridas. Como necesitaba tener siempre disponible el ancho actual de la papelera, decidí ajustar todo en el objeto. Además, ahora en cada bucle, el índice debe calcularse. Ahora el script tarda aún más tiempo en ejecutarse. Otras técnicas no aportaron mucho impulso al rendimiento, sino que hicieron que el código fuera menos legible. Es hora de HipHop, supongo.

Actualización: ya que hiphop php solo se ejecuta en Linux, y no tengo uno, he decidido volver a escribir todo en C ++. Es bueno refrescar las viejas habilidades. Además, si encuentro una forma de usar hiphop, será interesante comparar el código de C ++ escrito a mano y el que hiphop generaría.

Actualización: reescribí esta cosa en c ++, en promedio funciona 20 veces más rápido y usa mucha menos memoria. Déjame ver si puedo hacerlo aún más rápido.


32
2018-02-04 23:50


origen


Respuestas:


El acceso de matriz en PHP puede ser lento. PHP utiliza tablas hash para implementar matrices, es decir, para acceder a un elemento en una matriz, debe calcular un hash y atravesar una lista vinculada. El uso de un lenguaje compilado con matrices reales definitivamente mejorará el rendimiento, ya que se realiza un acceso directo a la memoria. Para el interesado: Código para acceso hash con cadena y con un entero.

En cuanto a su código, hay varios puntos que optimizaría:

  • return directamente, no lo hagas break dos veces.
  • poner $file->get_width() y $file->get_height en variables simples. Supongo que la altura o el ancho no cambia a lo largo del proceso. Recuerde: las funciones en PHP son lentas.
  • Use una matriz unidimensional, en lugar de matrices anidadas. Guarda una búsqueda de hash por iteración de esa manera.En realidad, una matriz unidimensional es solo marginalmente más rápida o incluso ligeramente más lenta. Comparación de varias formas de guardar los datos relacionados con el rendimiento y el uso de la memoria.

.

function fits($bin, $x, $y, $w, $h) {
    $w += $x;
    $h += $y;

    for ($i = $x; $i < $w; ++$i) {
        for ($j = $y; $j < $h; ++$j) {
            if ($bin[$i][$j] !== 0) {
                return false;
            }
        } 
    }

    return true;   
}

Aunque no estoy seguro, ¿por qué agregar $x al $width / $y al $height. ¿No quieres iterar desde las coordenadas actuales hasta los límites de la imagen?


19
2018-02-04 23:54



La solución a su problema podría ser https://github.com/facebook/hiphop-php/wiki/

Como dicen todos los demás, PHP no es el lenguaje óptimo para tareas de cálculo intensivo. Tampoco tiene realmente un tipo de matriz. Lo que se describe como array() en PHP es realmente un mapa de diccionario / hash. Tiene algunas optimizaciones para duplicar como lista, pero como ya has descubierto, no proporciona el mismo comportamiento en tiempo de ejecución que los punteros C y las matrices.

HipHop puede transformar el código PHP en C ++ optimizado. También se dirigió a la manipulación de cadenas, pero podría ofrecer una transformación adecuada de matriz / lista.

Descargo de responsabilidad: nunca lo intenté. Solo quería contribuir con una respuesta de sonido inteligente aquí.


10
2018-02-05 00:11



Sugerir otra alternativa de PHP:

¿Has investigado SplFixedArray ?

Dependiendo de cómo estén estructuradas sus matrices (matrices lineales de 0 a x), esto puede funcionar un poco más rápido

Para un benchmark, vea: http://www.slideshare.net/tobias382/new-spl-features-in-php-53 Diapositiva 15 y 16 (lo siento, no encontré uno mejor)


6
2018-02-05 19:55



Una alternativa más reciente es la extensión de QB a PHP que está específicamente diseñada para ayudar con este tipo de problema.

Mientras que PHP es un lenguaje excelente para construir una web compleja   aplicación, impone ciertas limitaciones. Escribir código que   realiza tareas intensivas computacionalmente de bajo nivel en PHP es   en general, no es práctico; simplemente sería demasiado lento. La extensión QB   aborda esta debilidad particular de PHP. Al traducir los códigos de operación de Zend   y ejecutarlos a través de una máquina virtual estáticamente estática, QB   ofrece una ganancia de orden de magnitud en el rendimiento. La potencia añadida   permite a los programadores de PHP hacer cosas que antes no podían hacer, como   manipulación de imágenes a nivel de píxel complejo.

Ver: http://php-qb.net/


1
2018-06-11 09:53



RESPUESTA ACTUALIZADA NECESARIA A PARTIR DE 2018.

Esta pregunta es antigua y las respuestas dadas no son completamente ciertas en PHP 7 Si Usas matrices empaquetadas. Como la pregunta aparece en Google hit, agrego una nueva respuesta

Si usa números enteros como claves de matriz en PHP 7 y se asegura de que los inserte en la matriz en orden ascendente, puede ver las mejoras de las operaciones de matriz 10 veces más rápidas.

Leer aquí: Blackfire Blog en PHP 7 Mejoras de matriz


1
2018-01-16 19:25



De hecho, las matrices en PHP parecen ser bastante lentas, especialmente en bucles a través de matrices multidimensionales. Otra opción sería intentar Quercus. Es una implementación de PHP en Java. Supongo que usa matrices de Java. No he hecho una comparación sin embargo.


0
2017-09-08 08:01



La pregunta es casi calificable como "principalmente basada en la opinión". Con eso en mente:

"¿PHP no es bueno para eso?"

PHP era originalmente solo un lenguaje de plantillas web, y la simplicidad era una preocupación mayor que el rendimiento cuando se diseñó. Ha evolucionado con el tiempo y se han agregado muchas optimizaciones, pero aún así, el rendimiento de PHP es relativamente pobre para las otras plataformas. Entonces, si su criterio es el rendimiento, entonces PHP no es bueno para eso.

"Estoy pensando en convertir todo en un lenguaje compilado".

Técnicamente, también se puede compilar PHP. Existe un compilador PHP a C ++ por Facebook. Hay un compilador de compilación justo a tiempo por Zend. Solía ​​haber un intérprete de PHP en Java (aunque ya no está activo si no recuerdo mal).

Te recomendaría probar Java, ya que su sintaxis es similar, después de todo, fue una de las inspiraciones de PHP 5. Java bytecode se compila en código nativo desde JDK 1.5. El rendimiento debería surgir cca 4x para la misma estructura de código (suponiendo que utilice la distribución PHP de la comunidad).


-5
2018-02-15 18:51