Nuestro equipo de expertos pasados varios días de investigación y recopilación de de información, obtuvimos la solución, esperamos que todo este artículo sea de utilidad en tu plan.
Solución:
Al contrario de lo que otros han dicho aquí, esta función no implementar el true tamiz de Eratóstenes. Sin embargo, devuelve una secuencia inicial de los números primos, y de manera similar, por lo que está bien pensar en él como el tamiz de Eratóstenes.
Estaba a punto de terminar de explicar el código cuando mipadi publicó su respuesta; Podría eliminarlo, pero como le dediqué un tiempo y nuestras respuestas no son completamente idénticas, lo dejo aquí.
Primero que nada, tenga en cuenta que hay algunos errores de sintaxis en el código que publicó. El código correcto es,
let sieve (p:xs) = p : sieve (filter (x -> x `mod` p /= 0) xs) in sieve [2..]
-
let x in ydefinexy permite utilizar su definición eny. El resultado de esta expresión es el resultado dey. Entonces en este caso definimos una funciónsievey devolver el resultado de aplicar[2..]parasieve. -
Ahora echemos un vistazo más de cerca al
letparte de esta expresión:sieve (p:xs) = p : sieve (filter (x -> x `mod` p /= 0) xs)- Esto define una función
sieveque toma una lista como primer argumento. (p:xs)es un patrón que coincidepcon el encabezado de dicha lista yxscon la cola (todo menos la cabeza).- En general,
p : xses una lista cuyo primer elemento esp.xses una lista que contiene los elementos restantes. Por lo tanto,sievedevuelve el primer elemento de la lista que recibe. -
No mire el resto de la lista:
sieve (filter (x -> x `mod` p /= 0) xs)- Podemos ver eso
sievese llama de forma recursiva. Por lo tanto, lafilterexpresión devolverá una lista. filtertoma una función de filtro y una lista. Devuelve solo aquellos elementos de la lista para los que devuelve la función de filtro true.-
En este caso
xses la lista que se filtra y(x -> x `mod` p /= 0)es la función de filtro.
- La función de filtro toma un solo argumento,
xy vuelve true si no es un múltiplo dep.
- Podemos ver eso
- Esto define una función
-
Ahora eso
sieveestá definido, lo pasamos[2 .. ], la lista de todos los números naturales que comienzan en 2. Por lo tanto,- Se devolverá el número 2. Todos los demás números naturales que sean múltiplos de 2 serán descartados.
- Por tanto, el segundo número es 3. Se devolverá. Todos los demás múltiplos de 3 se descartarán.
- Por lo tanto, el siguiente número será 5. Etc.
De hecho, es bastante elegante.
Primero, definimos una función sieve que toma una lista de elementos:
sieve (p:xs) =
En el cuerpo de sieve, tomamos la cabeza de la lista (porque estamos pasando la lista infinita [2..], y 2 se define como primo) y agregarlo (¡perezosamente!) al resultado de aplicar sieve al resto de la lista:
p : sieve (filter ( x -> x 'mod' p /= 0) xs)
Así que veamos el código que hace el trabajo en el resto de la lista:
sieve (filter ( x -> x 'mod' p /= 0) xs)
Estamos aplicando sieve a la lista filtrada. Analicemos lo que hace la parte del filtro:
filter ( x -> x 'mod' p /= 0) xs
filter toma una función y una lista en la que aplicamos esa función, y retiene los elementos que cumplen con los criterios dados por la función. En este caso, filter toma una función anónima:
x -> x 'mod' p /= 0
Esta función anónima toma un argumento, x. Comprueba el módulo de x contra p (la cabeza de la lista, cada vez sieve se llama):
x 'mod' p
Si el módulo no es igual a 0:
x 'mod' p /= 0
Entonces el elemento x se mantiene en la lista. Si es igual a 0, se filtra. Esto tiene sentido: si x es divisible por p, que x es divisible por más de 1 y por sí mismo, por lo que no es primo.
Define un generador – un transformador de corriente llamado “tamiz”,
Sieve s =
while( True ):
p := s.head
s := s.tail
yield p -- produce this
s := Filter (nomultsof p) s -- go next
primes := Sieve (Nums 2)
que utiliza una forma de curry de una función anónima equivalente a
nomultsof p x = (mod x p) /= 0
Ambos Sieve y Filter son operaciones de construcción de datos con estado interno y semántica de paso de argumentos por valor.
Aquí podemos ver que el problema más evidente de este código es no, repetir no que utiliza la división de prueba para filtrar los múltiplos de la secuencia de trabajo, mientras que podría encontrarlos directamente, contando en incrementos de p. Si reemplazáramos el primero por el segundo, el código resultante aún tendría una complejidad de ejecución abismal.
No, su problema más evidente es que pone un Filter además de su secuencia de trabajo demasiado pronto, cuando realmente debería hacer eso Solo después el cuadrado del primo se ve en la entrada. Como resultado, crea una cuadrático número de Filters comparado con lo que realmente se necesita. La cadena de Filters que crea es demasiado largo y la mayoría de ellos ni siquiera son necesarios.
La versión corregida, con la creación del filtro. pospuesto hasta el momento adecuado, es
Sieve ps s =
while( True ):
x := s.head
s := s.tail
yield x -- produce this
p := ps.head
q := p*p
while( (s.head) < q ):
yield (s.head) -- and these
s := s.tail
ps := ps.tail -- go next
s := Filter (nomultsof p) s
primes := Sieve primes (Nums 2)
o en Haskell,
primes = sieve primes [2..]
sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0]
where (p:pt) = ps
(h,t) = span (< p*p) xs
rem se usa aquí en lugar de mod ya que puede ser mucho más rápido en algunos intérpretes, y los números son todos positivos aquí de todos modos.
Medir los órdenes de crecimiento locales de un algoritmo tomando sus tiempos de ejecución t1,t2 en puntos del tamaño del problema n1,n2, como logBase (n2/n1) (t2/t1), obtenemos O(n^2) para el primero, y justo arriba O(n^1.4) por el segundo (en n primos producidos).
Solo para aclararlo, las partes faltantes podrían definirse en este lenguaje (imaginario) simplemente como
Nums x = -- numbers from x
while( True ):
yield x
x := x+1
Filter pred s = -- filter a stream by a predicate
while( True ):
if pred (s.head) then yield (s.head)
s := s.tail
ver también.
actualizar: Curiosamente, la primera instancia de este código en el manual SASL de 1976 de David Turner según el libro Haskell de 1992 de AJT Davie,
primes = sieve [2..]
sieve (p:nos) = p : sieve (remove (multsof p) nos)
realmente admite dospares de implementaciones para remove y multsof yendo juntos: un par para el tamiz de división de prueba como en esta pregunta, y el otro para la eliminación ordenada de los múltiplos de cada primo generados directamente por el conteo, también conocido como el auténtico Tamiz de Eratóstenes (ambos no se aplazarían, por supuesto). En Haskell,
multsof p n = rem n p==0 remove m xs = filter (not . m) xs
multsof p = [p*p, p*p+p..] remove m xs = minus xs m
(Si tan solo hubiera pospuesto eligiendo la implementación real ...)
En cuanto al código pospuesto, en un pseudocódigo con "patrones de lista" podría haber sido
primes = [2, ...sieve primes [3..]]
sieve [p, ...ps] [...h, p*p, ...nos] =
[...h, ...sieve ps (remove (multsof p) nos)]
que en Haskell real, con ViewPatterns, es
-# LANGUAGE ViewPatterns #-
primes = 2 : sieve primes [3..]
sieve (p:ps) (span (< p*p) -> (h, _:nos))
= h ++ sieve ps (remove (multsof p) nos)
pero probablemente todavía no había patrones de visualización en ese entonces, y es un poco menos aparente visualmente de esa manera.
Comentarios y valoraciones
Si eres capaz, eres capaz de dejar un escrito acerca de qué le añadirías a este post.