¿Cuál es más rápido y por qué?

Question

(n >= 3) && (n <= 99) 

O

n `elem` [3..99] 

Cuál es más rápido y por qué?

Answer 1

El primero es más rápido

(n >= 3) && (n <= 99) 

que está haciendo 3 operaciones

n >= 3 
n <= 99 
and 

Donde como la elem está mirando hacia arriba del elemento de la matriz, por lo que está haciendo hasta (99 - 3) * 2 operaciones.

index = 0 
isFound = false 
array[] = { 3, 4, 5, 6, ... 98, 99 } 

while isFound == false 
    isFound = (n == array[index++]) 

Answer 2

(n> = 3) & & (n = < 99) es más rápido, ya que implica sólo dos comparaciones triviales. Si el compilador/intérprete no hace ningún tipo de optimización real de magia negra, tiene que construir la lista ([3.99]) porque la evaluación diferida no se puede usar (normalmente "tirando" el siguiente valor hasta que hayas terminado, tendría una complejidad de O (n/2) en este caso).

Answer 3

Estas dos expresiones no significan lo mismo. Una sutil diferencia es que uno se basa en Ord y el otro en Enum:

> :t \n -> (n >= 3) && (n <= 99) 
\n -> (n >= 3) && (n <= 99) :: (Num a, Ord a) => a -> Bool 

> :t \n -> n `elem` [3..99] 
\n -> n `elem` [3..99] :: (Num a, Enum a) => a -> Bool 

Así, por ejemplo, si n es 3,14159, a continuación, se pasa la primera prueba, pero el segundo no:

> (pi >= 3) && (pi <= 99) 
True 

> pi `elem` [3..99] 
False 

Además, aunque las cuatro Prelude Num instancias (Int, Integer, Float, y Double) son todas las instancias de ambos Ord y Enum, es posible imaginar un tipo numérico que es una instancia de Ord pero no Enum. En tal caso, entonces la segunda prueba ni siquiera sería legal.

Por lo tanto, en general, el compilador no puede optomize el segundo para ser tan rápido como el primero a menos que sepa para un tipo dado, que es Ord y que todos los valores ordenados en el rango también están en la lista enumeración creado por enumFromTo. Para Float y Double esto no es cierto, y para Int y Integer no hay forma de que el compilador lo obtenga, el compilador y los programadores de la biblioteca tendrían que codificarlo a mano y garantizar que se mantenga en todos los casos.

Answer 4

Depende de la máquina y el compilador (o intérprete).