Secuencia de Collatz más larga en Scala -- time-limit-exceeded campo con comparative-review campo con scala campo con memoization campo con collatz-sequence camp codereview Relacionados El problema

Longest Collatz sequence in Scala


1
vote

problema

Español

Estoy intentando Encuentre la secuencia de Collatz más larga : < / p>

¿Qué número de inicio, ≤ n , produce la cadena más larga? Si muchos posibles tales números están imprimen el máximo. (1 ≤ n ≤ 5 × 10 6 )

Intenté optimizar el código para incluir la memoización que aún se excede el límite de tiempo, para estas soluciones. Quería algo de ayuda para entender dónde está el método que consume tiempo.

Implementación usando HashMap como caché memorizado:

  object CollatzSeq {   private final val mapOfCollatzSequence =      scala.collection.mutable.HashMap[BigInt, BigInt]()       .withDefaultValue(0)    def longestCollatzSeq(n: BigInt): BigInt = {     def longestCollatzSeqHelper(n: BigInt, count: BigInt = 0): BigInt = {       val mapValueOfN = mapOfCollatzSequence(n)       n match {         case n if n == 1 => count         case _ if mapValueOfN != 0 =>           count + mapValueOfN         case n if n % 2 == 0 =>           val updateForEven = longestCollatzSeqHelper(n/2, count + 1)           mapOfCollatzSequence.update(n, updateForEven - count)           updateForEven         case n if n % 2 != 0 =>           val c = longestCollatzSeqHelper(3 * n + 1 , count + 1)           mapOfCollatzSequence.update(n, c - count)           c       }     }     longestCollatzSeqHelper(n)   } }   

Implementación mediante matriz como caché memorizado:

  object CollatzSeq {    // Using Array As Performance Is Better Than Map   private final val collatzSeq = Array.fill[BigInt](5* 1000 * 1000)(0)   def longestCollatzSeq(n: BigInt): BigInt = {     def longestCollatzSeqHelper(n: BigInt, count: BigInt = 0): BigInt = {       val countOfN = collatzSeq((n - 1).toInt)       n match {         case n if n == 1 => count         case _ if countOfN != 0 =>           count + countOfN         case n if n % 2 == 0 =>           val updateForEven = longestCollatzSeqHelper(n/2, count + 1)           collatzSeq.update((n-1).toInt, updateForEven - count)           updateForEven         case n if n % 2 != 0 =>           val updateForOdd = longestCollatzSeqHelper(3 * n + 1 , count + 1)           collatzSeq.update((n-1).toInt, updateForOdd - count)           updateForOdd       }     }     longestCollatzSeqHelper(n)   } }   

Referencia de rendimiento

Original en ingles

I am trying to find the longest Collatz Sequence:

Which starting number, xe2x89xa4xc2xa0N, produces the longest chain? If many possible such numbers are there print the maximum one. (1xc2xa0xe2x89xa4xc2xa0Nxc2xa0xe2x89xa4xc2xa05xc3x97106)

I tried optimizing the code to include memoization still getting Time Limit Exceeded, for these solutions. Wanted some help to understand where the method is consuming time.

Implementation Using HashMap As Memoized Cache:

object CollatzSeq {   private final val mapOfCollatzSequence =      scala.collection.mutable.HashMap[BigInt, BigInt]()       .withDefaultValue(0)    def longestCollatzSeq(n: BigInt): BigInt = {     def longestCollatzSeqHelper(n: BigInt, count: BigInt = 0): BigInt = {       val mapValueOfN = mapOfCollatzSequence(n)       n match {         case n if n == 1 => count         case _ if mapValueOfN != 0 =>           count + mapValueOfN         case n if n % 2 == 0 =>           val updateForEven = longestCollatzSeqHelper(n/2, count + 1)           mapOfCollatzSequence.update(n, updateForEven - count)           updateForEven         case n if n % 2 != 0 =>           val c = longestCollatzSeqHelper(3 * n + 1 , count + 1)           mapOfCollatzSequence.update(n, c - count)           c       }     }     longestCollatzSeqHelper(n)   } } 

Implementation Using Array As Memoized Cache:

object CollatzSeq {    // Using Array As Performance Is Better Than Map   private final val collatzSeq = Array.fill[BigInt](5* 1000 * 1000)(0)   def longestCollatzSeq(n: BigInt): BigInt = {     def longestCollatzSeqHelper(n: BigInt, count: BigInt = 0): BigInt = {       val countOfN = collatzSeq((n - 1).toInt)       n match {         case n if n == 1 => count         case _ if countOfN != 0 =>           count + countOfN         case n if n % 2 == 0 =>           val updateForEven = longestCollatzSeqHelper(n/2, count + 1)           collatzSeq.update((n-1).toInt, updateForEven - count)           updateForEven         case n if n % 2 != 0 =>           val updateForOdd = longestCollatzSeqHelper(3 * n + 1 , count + 1)           collatzSeq.update((n-1).toInt, updateForOdd - count)           updateForOdd       }     }     longestCollatzSeqHelper(n)   } } 

Performance Reference

              
   
   

Lista de respuestas

1
 
vote

Hay algunas cosas que podrías hacer para hacer lo que tienes un poco más rápido:

  1. Los números se vuelven bastante grandes, pero 9988776655544330 es Overkill (y lento). El método longestCollatzSeqHelper()1 tendrá que lidiar con los valores en el dominio 9988776665544332 , pero el conjunto de problemas y los resultados, están bien dentro del rango 99887776665544333 , que será más rápido.
  2. debido a los grandes números, eres caché podría crecer enormemente. Tal vez más allá de los recursos del sistema.
  3. Estás probando n hasta 4 veces por iteración. Que se puede reducir a 2.

Pero este es el mero aderezo de ventanas. Cuando se encuentra con los límites de tiempo de espera de Hackerrank, la optimización del código generalmente no lo lleva muy lejos. 9 veces de cada 10 necesita volver, volver a examinar la declaración del problema y repensar su enfoque.

Cuando abordé este problema, comencé por los cálculos de almacenamiento en caché, pero finalmente le di la información y comenzé a centrarse en el otro extremo:

  1. para encontrar la longitud de cola más larga para los números & lt; = n, no tengo que contar la longitud de Collatz para cada número debajo de N. Hay un umbral por debajo de lo cual es imposible para el C -La longitud para superar las longitudes para los números por encima de ese umbral.
  2. Algunos números no necesitan tener su longitud de Collatz calculada en absoluto. Debido a una propiedad matemática simple, es imposible que su longitud C supere a sus vecinos.

Con esto en mente, y el almacenamiento en caché solo para reutilizar los resultados individuales dentro de un conjunto de problemas, debería poder pasar este desafío.

 

There are a few things you could do to make what you've got a bit faster:

  1. The numbers get quite big but BigInt is overkill (and slow). The longestCollatzSeqHelper() method will have to deal with values in the Long domain, but the problem set, and results, are well within the Int range, which will be faster.
  2. Because of the large numbers, you're cache could grow immensely. Perhaps beyond system resources.
  3. You're testing n as many as 4 times per iteration. That can be reduced to 2.

But this is mere window dressing. When you encounter HackerRank timeout limits, code optimization usually doesn't get you very far. 9 times out of 10 you need to go back, re-examine the problem statement, and rethink your approach to it.

When I tackled this problem I started by caching calculations, but eventually I gave that up and started focusing on the other end:

  1. To find the longest Collatz length for numbers <= N, I don't have to count the Collatz length for every number below N. There's a threshold below which it is impossible for the C-length to surpass the lengths for numbers above that threshold.
  2. Some numbers don't need to have their Collatz length calculated at all. Due to a simple mathematical property it is impossible for its C-length to surpass its neighbors.

With this in mind, and caching for reuse only individual results within a problem set, you should be able to pass this challenge.

 
 

Relacionados problema

4  Verificación computacional de la conjetura de Collatz utilizando OpenCl  ( Computational verification of collatz conjecture using opencl ) 
Esta solicitud de revisión de código sigue mi solicitud anterior Verificación computacional de Collatz Conyecture . A diferencia del programa anterior (que ...

3  Secuencia Collatz más larga con programación dinámica en Java  ( Longest collatz sequence using dynamic programming in java ) 
No estoy obteniendo dónde más debería optimizarlo. ¿Hay alguna manera de optimizar este código? Solo dame sugerencias. import java.io.*; import java.util.*...

4  Proyecto EULER # 14 en Clojure (encontrando cadena de secuencia de cola larga)  ( Project euler 14 in clojure finding long collatz sequence chain ) 
Estoy trabajando en una implementación de Clojure para Project Euler # 14 , que pregunta por el elemento inicial , menores de 10 años 6 , que produce la Co...

9  Desafío de programación 3n + 1 en Python  ( 3n 1 programming challenge in python ) 
Estoy tratando de encontrar una solución eficiente para 3N + 1 problema en UvaOnlineJudge . El código que tengo usa la memorización utilizando un diccionario...

4  Proyecto EULER # 14 en Clojure (encontrando cadena de secuencia de cola larga)  ( Project euler 14 in clojure finding long collatz sequence chain ) 
Estoy trabajando en una implementación de Clojure para Project Euler # 14 , que pregunta por el elemento inicial , menores de 10 años 6 , que produce la Co...

6  UVA 100: "El problema 3n + 1"  ( Uva 100 the 3n 1 problem ) 
He resuelto el problema de la UVA 100: el problema 3n + 1 . En resumen, la tarea era escribir un programa que calcula un máximo de longitudes de secuencia de...

2  Determine la longitud de la secuencia de Collatz para los valores de inicio dados  ( Determine collatz sequence length for given starting values ) 
Estoy tratando de meterme en el hábito de resolver los rompecabezas de programación en mi tiempo libre, pero estoy atascado en el primero (lo que sé puede ser...

4  Secuencia de colatz más larga optimizada  ( Optimized longest collatz sequence ) 
Estoy escribiendo un programa para calcular la secuencia de Collatz más larga para enteros positivos por debajo de algunos N. Lo he optimizado todo lo que pue...

0  Encontrar la secuencia de Collatz más larga usando Go, simultáneamente  ( Finding the longest collatz sequence using go concurrently ) 
Estoy trabajando a través de este problema en el proyecto Euler. Propósito básico del código: /* if n is even n -> n/2 if n is odd n -> 3n + 1 which st...

1  Proyecto EULER 14 Secuencia más larga de Collatz [CERRADO]  ( Euler project 14 longest collatz sequence ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos