php - tag - the title wordpress

PHP integrado en funciones de complejidad(función isAnagramOfPalindrome)

Question

He estado buscando en Google durante las últimas 2 horas, y no puedo encontrar una lista de funciones de php integradas en tiempo y complejidad de espacio. Tengo el problema isAnagramOfPalindrome para resolver con la siguiente complejidad máxima permitida:

expected worst-case time complexity is O(N)
expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

donde N es la longitud de la cadena de entrada. Aquí está mi solución más simple, pero no sé si está dentro de los límites de complejidad.

class Solution {
// Function to determine if the input string can make a palindrome by rearranging it
static public function isAnagramOfPalindrome($S) {
// here I am counting how many characters have odd number of occurrences
$odds = count(array_filter(count_chars($S, 1), function($var) {
return($var & 1);
}));
// If the string length is odd, then a palindrome would have 1 character with odd number occurrences
// If the string length is even, all characters should have even number of occurrences
return (int)($odds == (strlen($S) & 1));
}
}
echo Solution :: isAnagramOfPalindrome($_POST[''input'']);

¿Alguien tiene una idea de dónde encontrar este tipo de información?

EDITAR

Descubrí que array_filter tiene array_filter O (N) y el count tiene complejidad O (1). Ahora necesito encontrar información sobre count_chars , pero una lista completa sería muy conveniente para futuros problemas.

Editar 2

Después de algunas investigaciones sobre la complejidad del espacio y el tiempo en general, descubrí que este código tiene complejidad de tiempo O (N) y complejidad del espacio O (1) porque:

Los count_chars formarán un bucle N veces (longitud completa de la cadena de entrada, lo que le da una complejidad de inicio de O (N)). Esto está generando una matriz con un número máximo de campos limitado (26 precisamente, la cantidad de caracteres diferentes), y luego está aplicando un filtro en esta matriz, lo que significa que el filtro tendrá un bucle de 26 veces como máximo. Cuando se empuja la longitud de entrada hacia el infinito, este bucle es insignificante y se ve como una constante. Count también se aplica a esta matriz constante generada, y además, es insignificante porque la complejidad de la función de count es O (1). Por lo tanto, la complejidad del tiempo del algoritmo es O (N).

Lo mismo ocurre con la complejidad del espacio. Al calcular la complejidad del espacio, no contamos la entrada, solo los objetos generados en el proceso. Estos objetos son la matriz de 26 elementos y la variable de conteo, y ambos se tratan como constantes porque su tamaño no puede aumentar en este punto, sin importar qué tan grande sea la entrada. Entonces podemos decir que el algoritmo tiene una complejidad de espacio de O (1).

De todos modos, esa lista aún sería valiosa, por lo que no tenemos que buscar en el código fuente de php. :)

Answer 1

Una razón probable para no incluir esta información es que es probable que cambie por versión , ya que se realizan mejoras / optimizaciones para un caso general.

PHP se basa en C, algunas de las funciones son simplemente envoltorios alrededor de las contrapartes de c, por ejemplo, hypot una búsqueda de google, una mirada al man hypot , en los documentos para él math lib http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms

La fuente en realidad no proporciona mejor información https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c (no oficial, simplemente fácil de vincular a)

Sin mencionar, esto es solo glibc, Windows tendrá una implementación diferente. Por lo tanto, PUEDE haber incluso una gran O diferente por sistema operativo en la que se compila PHP

Otra razón podría ser porque confundiría a la mayoría de los desarrolladores . La mayoría de los desarrolladores que conozco simplemente elegirían una función con la "mejor" gran O

un máximo no siempre significa que es más lento

http://www.sorting-algorithms.com/

Tiene un buen soporte visual de lo que está sucediendo con algunas funciones, es decir, la clasificación de burbuja es una clasificación "lenta", sin embargo, es una de las más rápidas para datos casi ordenados. La clasificación rápida es lo que muchos usarán, que en realidad es muy lento para los datos casi ordenados. Big O es el peor de los casos: PHP puede decidir entre una versión que deben optimizar para una determinada condición y eso cambiará la gran O de la función y no hay una manera fácil de documentar eso.

Aquí hay una lista parcial (que supongo que has visto)

Lista de Big-O para funciones PHP

Que hace una lista de algunas de las funciones más comunes de PHP.

Para este ejemplo particular ...

Es bastante fácil de resolver sin usar las funciones integradas.

Código de ejemplo

function isPalAnagram($string) {
$string = str_replace(" ", "", $string);
$len = strlen($string);
$oddCount = $len & 1;
$string = str_split($string);
while ($len > 0 && $oddCount >= 0) {
$current = reset($string);
$replace_count = 0;
foreach($string as $key => &$char) {
if ($char === $current){
unset($string[$key]);
$len--;
$replace_count++;
continue;
}
}
$oddCount -= ($replace_count & 1);
}
return ($len - $oddCount) === 0;
}

Usando el hecho de que no puede haber más de 1 cuenta impar, puede regresar temprano de la matriz.

Creo que el mío también es O (N) porque su peor caso es O (N), por lo que puedo decir.

Prueba

$a = microtime(true);
for($i=1; $i<100000; $i++) {
testMethod("the quick brown fox jumped over the lazy dog");
testMethod("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
testMethod("testest");
}
printf("Took %s seconds, %s memory", microtime(true) - $a, memory_get_peak_usage(true));

Las pruebas se ejecutan con hardware muy antiguo a mi manera

Took 64.125452041626 seconds, 262144 memory

A tu manera

Took 112.96145009995 seconds, 262144 memory

Estoy bastante seguro de que mi camino tampoco es el más rápido.

En realidad, no puedo ver mucha información para otros lenguajes que no sean PHP (Java, por ejemplo).

Sé que gran parte de esta publicación es especular sobre por qué no está allí y no hay mucho de fuentes creíbles, espero que se explique en parte por qué la gran O no aparece en la página de documentación, aunque