3

Esta pregunta más que de código se trata sobre algo más concreto: saber la complejidad de las funciones nativas de Php, lo cuál afecta a todo nuestro código.

Con esto me refiero a por ejemplo, ¿Cómo saber la complejidad de la función "implode", "explode", etc?

He buscando en php.net sin resultados.

7
  • Quizás sea algo que todavía nadie haya analizado, aunque revisando el código fuente se puede llegar a calcular. A ojo, yo diría que la complejidad de implode, como mínimo, es O(n), aunque dependerá de como están implementadas las cadenas en php
    – Luis
    el 30 ago. 2017 a las 16:58
  • Ya veo, quizá suene a novatada pero ¿cómo puedo ver el código fuente de php? :p
    – J.Correa
    el 30 ago. 2017 a las 17:17
  • 3
    Creo recordar que desde el propio sitio de php puedes descargar un zip con el código fuente. También he encontrado en github el codigo. Te pego un enlace al fichero donde está definida la función implode: github.com/php/php-src/blob/master/ext/standard/string.c
    – Luis
    el 30 ago. 2017 a las 17:21
  • Por cierto, el código está en c++, creo. Lo he mirado por encima y creo que la complejidad es O(n), aunque habría que revisar el código más a fondo
    – Luis
    el 30 ago. 2017 a las 17:23
  • @Luis creo que deberías colocar tus comentarios como respuesta, hay una de Kenny que me parece acertada pero prácticamente es la misma que la tuya, así que ahora no sé bajo qué criterio determinar como la aceptable, aún así me gustaría que lo coloques como respuesta para darle flechita arriba (marcar como útil)
    – J.Correa
    el 30 ago. 2017 a las 17:29

2 respuestas 2

4

Respuesta rápida: Revisando el código fuente. :)

Respuesta larga:

Tal como ponía en los comentarios a tu pregunta, la complejidad de las funciones propias de PHP no es algo que se hayan parado a estudiar detenidamente, al menos es lo que deduzco de una búsqueda rápida en Google. Lo que si he encontrado son otras preguntas en Stack Overflow (en inglés) en las que se preguntan algo parecido, pero más orientado a los arrays: https://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions, https://stackoverflow.com/questions/4566314/php-what-is-the-complexity-i-e-o1-on-of-the-function-count y https://stackoverflow.com/questions/32100086/php-built-in-functions-complexity-isanagramofpalindrome-function. De estas tres preguntas, la primera es la más completa. Aparte de eso, la otra opción que nos queda es revisar el código fuente de PHP para estudiar la complejidad de las funciones que nos interesen.

En la respuesta de Kenny ya hay una explicación de la complejidad, y de porque nos hace falta conocerla, así que no me extenderé por ese lado.

Revisando el código fuente de PHP (que puedes encontrar en Github, o en Php.net) podemos ver el código de la función implode (en este caso es el código correspondiente al PHP 5.6.31), en el archivo string.c:

PHPAPI void php_implode(zval *delim, zval *arr, zval *return_value TSRMLS_DC)
{
    zval         **tmp;
    HashPosition   pos;
    smart_str      implstr = {0};
    int            numelems, i = 0;
    zval tmp_val;
    int str_len;

    numelems = zend_hash_num_elements(Z_ARRVAL_P(arr));

    if (numelems == 0) {
        RETURN_EMPTY_STRING();
    }

    zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(arr), &pos);

    while (zend_hash_get_current_data_ex(Z_ARRVAL_P(arr), (void **) &tmp, &pos) == SUCCESS) {
        switch ((*tmp)->type) {
            case IS_STRING:
                smart_str_appendl(&implstr, Z_STRVAL_PP(tmp), Z_STRLEN_PP(tmp));
                break;

            case IS_LONG: {
                char stmp[MAX_LENGTH_OF_LONG + 1];
                str_len = slprintf(stmp, sizeof(stmp), "%ld", Z_LVAL_PP(tmp));
                smart_str_appendl(&implstr, stmp, str_len);
            }
                break;

            case IS_BOOL:
                if (Z_LVAL_PP(tmp) == 1) {
                    smart_str_appendl(&implstr, "1", sizeof("1")-1);
                }
                break;

            case IS_NULL:
                break;

            case IS_DOUBLE: {
                char *stmp;
                str_len = spprintf(&stmp, 0, "%.*G", (int) EG(precision), Z_DVAL_PP(tmp));
                smart_str_appendl(&implstr, stmp, str_len);
                efree(stmp);
            }
                break;

            case IS_OBJECT: {
                int copy;
                zval expr;
                zend_make_printable_zval(*tmp, &expr, &copy);
                smart_str_appendl(&implstr, Z_STRVAL(expr), Z_STRLEN(expr));
                if (copy) {
                    zval_dtor(&expr);
                }
            }
                break;

            default:
                tmp_val = **tmp;
                zval_copy_ctor(&tmp_val);
                convert_to_string(&tmp_val);
                smart_str_appendl(&implstr, Z_STRVAL(tmp_val), Z_STRLEN(tmp_val));
                zval_dtor(&tmp_val);
                break;

        }

        if (++i != numelems) {
            smart_str_appendl(&implstr, Z_STRVAL_P(delim), Z_STRLEN_P(delim));
        }
        zend_hash_move_forward_ex(Z_ARRVAL_P(arr), &pos);
    }
    smart_str_0(&implstr);

    if (implstr.len) {
        RETURN_STRINGL(implstr.c, implstr.len, 0);
    } else {
        smart_str_free(&implstr);
        RETURN_EMPTY_STRING();
    }
}
/* }}} */

Nota: hace mucho tiempo que no calculo la complejidad de una función, así que seguramente habré metido la pata en algún sitio. Se aceptan correcciones.

Sin entrar en muchos detalles, vemos que el código está en C (no en C++ como puse en los comentarios), y en el caso concreto (implode) hay una función C, llamada implode (no la he copiado), que realiza la función de extraer los parámetros de la llamada a implode desde el código PHP, verificar que estos sean correctos, realizar alguna conversión, y por último llamar a php_implode, que es la función que realiza el trabajo. Para este ejemplo voy a ignorar la complejidad de la función que realiza las comprobaciones, ya que dependerá de como trabaja internamente el intérprete de PHP (haciendo una apuesta, podría estar entre O(log n) y O(n)... quizás un poco más pero no creo que llegue a O(n*n)...).

Revisando ya la función php_implode (la que hace el trabajo de verdad), vemos que hay un par de llamadas a funciones internas, una que obtiene el total de elementos del array y otra que un puntero al primer elemento válido del array. La complejidad de la primera es O(1) y y la de la segunda es O(n) en el peor de los casos. Después tenemos un bucle que recorre cada uno de los elementos del array -O(n)-, obteniendo cada uno de los valores almacenados en este -O(1)-. Dependiendo del tipo de dato guardado lo convierte a una cadena y lo concatena con el resultado actual. La complejidad de la concatenación es O(m) (depende de la longitud de la cadena a concatenar), pero en nuestro caso la podemos considerar un valor constante O(1). La conversión, aunque variará dependiendo del tipo de datos, vamos a considerarla O(2m), ya que en el peor de los casos tiene que copiar cadenas un par de veces. Todo esto es mucho rollo buscando la complejidad de cada función que utiliza implode, pero al final nos quedará una fórmula como esta: O(1)+O(n)+O(n)*(O(1)+O(2m)+O(1))... Simplificando la fórmula nos quedaría

  • O(n) en el mejor de los casos (todos los elementos del array son cadenas, y el array no tiene elementos borrados al principio),
  • O(n)+O(2n*2m) en el peor (el array tiene un montón de elementos borrados al principio y los elementos son todos de tipos complejos que hay que convertir a cadena)

Trabajando en web, que es lo más habitual, la mayoría de las veces que utilicemos esta función seguramente solo contendrá cadenas, por lo que normalmente su complejidad será O(n).

Conclusión

Calcular la complejidad de una función interna de un proceso es una tarea simple pero tediosa, ya que exige tiempo (hacer este cálculo me ha llevado más de media hora, revisando ficheros de código que no había visto hasta el día de hoy para buscar las funciones e intentando comprender que hace cada una de ellas). A grandes rasgos podemos llegar a calcularla, aunque como dice Kenny, normalmente los problemas de rendimiento que podemos encontrarnos no son por culpa del lenguaje de programación utilizado, sino porque no le estamos dando la mejor solución al problema que queremos resolver, o no estamos utilizando la herramienta adecuada dentro del lenguaje. Enlazo un artículo de 2005 de Joel Spolsky: De vuelta a las bases en el que el autor viene a decir que con los lenguajes actuales, muchas veces se desconoce como funcionan estos por debajo y se terminan desarrollando soluciones que son ineficaces.

1
  • Gracias Luis por tomarte el tiempo para esto :) tu respuesta y la de Kenny son correctas, si pudiese elegir a ambas lo haría
    – J.Correa
    el 31 ago. 2017 a las 14:10
4

Esto es masomenos un comentario largo, aunque pienso que puede ser considerada como respuesta, porque responder a tu pregunta, básicamente, es responder como saber la complejidad algorítmica de un algoritmo. (solo que en tu caso específico, necesitas esta información de los algoritmos implementados para construir las funciones implode y explode de PHP, pero por supuesto, la forma de obtener esta complejidad no cambiaría para cualquier otro algoritmo)

Entendemos por complejidad algoritmica la cantidad de instrucciones necesarias para resolver un problema, las cuales son directamente dependientes del conjunto de valores que ese algoritmo recibe como entrada, mas conocido como la talla del problema. Esto siempre es modelado por una función, ya sea linea, exponencial, logaritmica, etc.

Llegado a este punto, ya que tu pregunta es como obtener dicha función, esto es lo que tendrias que hacer. Puedes ir al código fuente de PHP, especificamente hay paquete de librerias que se llama standar y aqui hay un archivo que se llama string.c, el cual (si, adivinaste) es un archivo escrito en c que tiene las definiciones de las funciones implode y explode, ademas de muchas otras.

Aqui deberias analizar el algoritmo y poder determinar la función que modela su complejidad algoritmica. Como lo que mencionaba Luis, con un rápido vistazo a la función, y echando un vistazo a las funciones dentro, veo que quizas si podría ser del orden O(n).

Ahora que llegamos a este punto, ¿por qué quieres saber esto? La principal razón para analizar la complejidad algorítmica es hacer comparaciones para determinar cual es la manera mas eficiente de resolver un problema. Realmente dudo mucho que quieras implementar una función que reemplaze a alguna de estas y recompilar todo el código de PHP para poder usarla en tus implementaciones. Ahora bien, si tienes algun problema con el tiempo que se esta tomando tu solución en resolver determinado problema, quizas lo estas viendo del lado equivocado y podrias plantearte re analizar el problema para encontrar la solución optima, y quizas esta solución no incluya usar las funciones implode o explode.

1
  • Me parece acertada, entonces el único modo de saber la complejidad de funciones nativas de php es viendo el código fuente en c++. Creí que habría una sección en php.net o así con esa info. Lo que preguntas, es para decidir qué función usar entre las opciones de Php y cómo pueden impactar en mi código, no para crear mis propias funciones que hagan lo mismo que las de php. Implode y explode fueron sólo ejemplos
    – J.Correa
    el 30 ago. 2017 a las 17:31

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.