valor - Rendimiento de matriz de PHP

obtener el valor de un array php

Question

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 puede 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 se empaquen 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.

Answer 1

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

Answer 2

El acceso de matriz en PHP puede ser lento. PHP usa 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 número entero .

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

• return directamente, no break dos veces.
• pon $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é agrega $x al $width / $y a $height . ¿No quieres iterar desde las coordenadas actuales hasta los límites de la imagen?

Answer 3

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, 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).

Answer 4

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í.

Answer 5

RESPUESTA ACTUALIZADA NECESARIA A PARTIR DE 2018.

Esta pregunta es antigua y las respuestas dadas no son completamente ciertas en PHP 7 si usa 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.

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

Answer 6

Sugerir otra alternativa de PHP:

¿Has mirado en 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 obtener una referencia, consulte: http://www.slideshare.net/tobias382/new-spl-features-in-php-53 Diapositiva 15 y 16 (lo siento, no encontré una mejor)

Answer 7

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.

Si bien PHP es un lenguaje excelente para crear aplicaciones web complejas, impone ciertas limitaciones. Escribir código que realiza tareas computacionalmente intensivas de bajo nivel en PHP generalmente 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 Zend y ejecutarlos a través de una máquina virtual tipada estáticamente, QB ofrece una ganancia de orden de magnitud en el rendimiento. La potencia agregada permite a los programadores de PHP hacer cosas que antes no podían hacer, una manipulación de imágenes tan compleja a nivel de píxel.

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