SWIFT - Encontrar una brecha binaria más larga de un entero dado -- performance campo con algorithm campo con array campo con swift campo con complexity camp codereview Relacionados El problema

Swift - Finding longest binary gap of a given integer


3
vote

problema

Español

Recientemente tuve la oportunidad de probar la capacitación del algoritmo de la Codilidad, y la primera en la lista es encontrar la brecha binaria más larga de un entero dado .

Intenté implementar esto en Swift, y después de terminarlo, miré las respuestas en todo Internet. Mi enfoque es un poco diferente de lo que he visto de los demás.


¿Qué es una brecha binaria?

Una brecha binaria dentro de un entero positivo N es cualquier secuencia máxima de ceros consecutivos que está rodeada de unos en ambos extremos en la representación binaria de n.

Por ejemplo, número 9 tiene representación binaria 1001 y contiene un espacio binario de longitud 2 . El número 529 tiene una representación binaria 1000010001 y contiene dos huecos binarios: uno de la longitud 4 y una de longitud 3 . El número 20 tiene representación binaria 10100 y contiene un espacio binario de longitud 1 . El número 15 tiene representación binaria 1111 y no tiene brechas binarias. El número 32 tiene representación binaria 100000 y no tiene brechas binarias.


La siguiente es de la consola, lo que facilita la comprensión de la implementación.

  Binary String of "1041" is: "10000010001" Position of 1's: [0, 6, 10] The longest binary gap is 5   

básicamente lo que estoy haciendo es:

  1. iterando cada carácter binario, y almacena la posición / índice de 1 en una matriz.
  2. A medida que estoy en bucle, encuentro la brecha binaria entre dos 1, restando el índice actual de 1 con el índice anterior de 1 , para que me dé como Muchos 0 están presentes entre ellos. Luego disminuyo cualquier valor que obtenga por 1 ('causa matrices ...).
  3. A medida que estoy pasando por la vuelta, realizo un seguimiento de la brecha binaria más larga en una variable.

La complejidad es o (n) , y me gustaría saber si este enfoque es de alguna manera eficiente en términos de memoria, o cualquier alcance de mejoras con esto? Gracias por tu tiempo.


Código:

  public func getLongestBinaryGapFor(_ N : Int) -> Int {          var arrayOfIndexes:[Int] = []     let binaryString = String(N, radix:2)          print("Binary String of "(N)" is: "(binaryString)"")          var longestBinaryGap:Int = 0     var index = 0          for char in binaryString {         if char == "1" {             arrayOfIndexes.append(index)             let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes)             if arrayOfIndexes.count == 2 {                 longestBinaryGap = currentBinaryGap             } else if index > 2 {                 if currentBinaryGap > longestBinaryGap {                     longestBinaryGap = currentBinaryGap                 }             }         }         index += 1     }          print("Position of 1's: (arrayOfIndexes)")     return longestBinaryGap }  func getCurrentBinaryGapFor(_ array:[Int]) -> Int {     var currentBinaryGap = 0     if array.count >= 2 {         let currentPosition = array.count - 1         let previousPosition = currentPosition - 1         currentBinaryGap = array[currentPosition] - array[previousPosition] - 1         return currentBinaryGap     } else {         return currentBinaryGap     } }   
Original en ingles

I recently had the chance to try Codility's algorithm training, and the very first one in the list is finding the longest binary gap of a given integer.

I tried to implement this in Swift, and after finishing it up, I looked at answers all over the internet. My approach is a bit different from what I have seen from others.


What is a Binary Gap?

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.


The following is from the console which makes it easy to understand the implementation.

Binary String of "1041" is: "10000010001" Position of 1's: [0, 6, 10] The longest binary gap is 5 

Basically what I am doing is:

  1. Iterating each binary character, and store the position/index of 1's in an array.
  2. As I am looping through, I find the binary gap between two 1's by subtracting the current index of 1 with previous index of 1, so that it gives me how many 0's are present in between them. I then decrement whatever value I get by 1 ('cause arrays...).
  3. As I am looping through, I keep track of the longest binary gap in a variable.

The complexity is O(n), and I'd like to know if this approach is in any way efficient in terms of memory, or any scope of improvements with this? Thanks for your time.


Code:

public func getLongestBinaryGapFor(_ N : Int) -> Int {          var arrayOfIndexes:[Int] = []     let binaryString = String(N, radix:2)          print("Binary String of \"\(N)\" is: \"\(binaryString)\"")          var longestBinaryGap:Int = 0     var index = 0          for char in binaryString {         if char == "1" {             arrayOfIndexes.append(index)             let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes)             if arrayOfIndexes.count == 2 {                 longestBinaryGap = currentBinaryGap             } else if index > 2 {                 if currentBinaryGap > longestBinaryGap {                     longestBinaryGap = currentBinaryGap                 }             }         }         index += 1     }          print("Position of 1's: \(arrayOfIndexes)")     return longestBinaryGap }  func getCurrentBinaryGapFor(_ array:[Int]) -> Int {     var currentBinaryGap = 0     if array.count >= 2 {         let currentPosition = array.count - 1         let previousPosition = currentPosition - 1         currentBinaryGap = array[currentPosition] - array[previousPosition] - 1         return currentBinaryGap     } else {         return currentBinaryGap     } } 
              

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

Naming

de acuerdo con el Directrices de diseño de API , Se debe omitir la palabra innecesar, y se deben hacer frases preposicionales. Etiquetas de argumento. También los nombres variables generalmente deben ser un caso más bajo (camello).

Por lo tanto, un mejor nombre de función sería

  public func longestBinaryGap(for n: Int) -> Int    

Los nombres de las variables no deben contener información de tipo, que se aplica por ejemplo a

  var arrayOfIndexes: [Int]   

Simplificación de su enfoque

Vamos a empezar con func getCurrentBinaryGapFor() , que parece innecesario Complicado. Sin variables locales adicionales, se puede escribir como

  func getCurrentBinaryGapFor(_ array:[Int]) -> Int {     if array.count >= 2 {         return array[array.count - 1] - array[array.count - 2] - 1     } else {         return 0     } }   

en la función principal,

  let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes) if arrayOfIndexes.count == 2 {     longestBinaryGap = currentBinaryGap } else if index > 2 {     if currentBinaryGap > longestBinaryGap {         longestBinaryGap = currentBinaryGap     } }   

se puede simplificar a

  let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes) if currentBinaryGap > longestBinaryGap {     longestBinaryGap = currentBinaryGap }   

y el bucle

  var index = 0 for char in binaryString {     if char == "1" {         // ... do something ...     }     index += 1 }   

se puede escribir como

  for (index, char) in binaryString.enumerated() where char == "1" {     // ... do something ... }   

Solo los dos últimos elementos de arrayOfIndexes se utilizan en el programa. Lo haría

  • almacena todas las posiciones de las en la matriz primero, y luego determine la carrera más larga de esa matriz una vez,
  • o use dos variables para las dos posiciones recientes en lugar de una matriz.

En cualquier caso, una función separada para calcular la brecha actual parece innecesario.

Resumiendo los cambios Hasta ahora, la función se vería así:

  public func longestBinaryGap(for n: Int) -> Int {     var bitPositions: [Int] = [] // Positions of all `1` bits in `n`     let binaryRepr = String(n, radix:2) //      for (index, char) in binaryRepr.enumerated() where char == "1" {         bitPositions.append(index)     }      var longestGap: Int = 0     if bitPositions.count >= 2 {         for i in 0...bitPositions.count - 2 {             let gap = bitPositions[i + 1] - bitPositions[i] - 1             if gap > longestGap {                 longestGap = gap             }         }     }      return longestGap }   

Usando los métodos funcionales de Swift, esto podría escribirse como

  var arrayOfIndexes: [Int] 0  

que se ve elegante, pero en realidad es un poco más lento que la versión anterior.

Aumentar el rendimiento

Su enfoque es $ O (D) $ (en el tiempo y la memoria), donde $ d $ es el Número de dígitos en $ n $. Eso parece muy bueno ya que cualquier solución debe De alguna manera transversales todos los dígitos del número dado.

Como se dijo anteriormente, el uso de la memoria se puede reducir a $ O (1) $ por mantener solo las últimas dos posiciones de bits, en lugar de usar una matriz.

Sin embargo, se puede guardar mucho tiempo por no convertir el entero a una cadena. Los dígitos binarios de un número se pueden determinar de manera eficiente en puro. aritmética entera.

que conduce a la siguiente implementación (esencialmente una versión rápida de Encuentre la brecha binaria de un número N < / a>), que es considerablemente más rápido:

  var arrayOfIndexes: [Int] 1  

y se vuelve aún más rápido si usamos el "Buscar el primer conjunto de bits" Función var arrayOfIndexes: [Int] 2 (que podría aprovechar el compilador intrínseco):

  var arrayOfIndexes: [Int] 3  

Benchmark

MI SIMPLE BENCHMARK:

  var arrayOfIndexes: [Int] 4  

en un 1,2 GHz Intel Core M5 (con el programa compilado en modo de liberación, es decir, con optimizaciones), medí aproximadamente:

  • su código original: 3.3 segundos
  • var arrayOfIndexes: [Int] 5 : 0.08 segundos
  • var arrayOfIndexes: [Int] 6 : 0.04 segundos
 

Naming

According to the API Design Guidelines, needless word should be omitted, and prepositional phrases should be made argument labels. Also variable names should generally be lower (camel) case.

Therefore a better function name would be

public func longestBinaryGap(for n: Int) -> Int  

Also variable names should not contain type information, that applies for example to

var arrayOfIndexes: [Int] 

Simplifying your approach

Let's start with func getCurrentBinaryGapFor(), that looks unnecessary complicated. Without additional local variables it can be written as

func getCurrentBinaryGapFor(_ array:[Int]) -> Int {     if array.count >= 2 {         return array[array.count - 1] - array[array.count - 2] - 1     } else {         return 0     } } 

In the main function,

let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes) if arrayOfIndexes.count == 2 {     longestBinaryGap = currentBinaryGap } else if index > 2 {     if currentBinaryGap > longestBinaryGap {         longestBinaryGap = currentBinaryGap     } } 

can be simplified to

let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes) if currentBinaryGap > longestBinaryGap {     longestBinaryGap = currentBinaryGap } 

and the loop

var index = 0 for char in binaryString {     if char == "1" {         // ... do something ...     }     index += 1 } 

can be written as

for (index, char) in binaryString.enumerated() where char == "1" {     // ... do something ... } 

Only the last two elements of arrayOfIndexes are used in the program. I would

  • either store all positions of ones in the array first, and then determine the longest run from that array once,
  • or use two variables for the recent two positions instead of an array.

In either case, a separate function to compute the current gap seems unnecessary.

Summarizing the changes so far, the function would look like this:

public func longestBinaryGap(for n: Int) -> Int {     var bitPositions: [Int] = [] // Positions of all `1` bits in `n`     let binaryRepr = String(n, radix:2) //      for (index, char) in binaryRepr.enumerated() where char == "1" {         bitPositions.append(index)     }      var longestGap: Int = 0     if bitPositions.count >= 2 {         for i in 0...bitPositions.count - 2 {             let gap = bitPositions[i + 1] - bitPositions[i] - 1             if gap > longestGap {                 longestGap = gap             }         }     }      return longestGap } 

Using Swift's functional methods this could be written as

public func longestBinaryGap(for n: Int) -> Int {     let binaryRepr = String(n, radix: 2) //      let bitPositions = binaryRepr.enumerated()         .filter { $0.element == "1" }         .map { $0.offset }      let longestGap = zip(bitPositions, bitPositions.dropFirst())         .map { $1 - $0 - 1 }         .max() ?? 0      return longestGap } 

which looks elegant, but is actually a bit slower than the previous version.

Boosting the performance

Your approach is \$ O(d) \$ (in time and memory), where \$ d \$ is the number of digits in \$ n \$. That seems very good since any solution must somehow traverse all digits of the given number.

As said above, the memory usage can be reduced to \$ O(1) \$ by keeping only the last two bit positions, instead of using an array.

However, much time can be saved by not converting the integer to a string. The binary digits of a number can be determined efficiently in pure integer arithmetic.

That leads to the following implementation (essentially a Swift version of Find the binary gap of a number N), which is considerably faster:

public func longestBinaryGap1(for n : Int) -> Int {      if n <= 0 {         return 0     }      var n = n // Make a mutable copy     // Remove trailing zeros:     while n % 2 == 0 {         n /= 2     }      var longestGap = 0     var gap = 0     repeat {         n /= 2         if n % 2 == 0 {             // Current bit is `0`: increase gap size.             gap += 1         } else {             // Current bit is `1`: check current gap, then reset.             if gap > longestGap {                 longestGap = gap             }             gap = 0         }     } while n > 0      return longestGap } 

And it gets even faster if we use the xe2x80x9cfind first bit setxe2x80x9d function ffsl() (which might take advantage of compiler intrinsics):

public func longestBinaryGap2(for n : Int) -> Int {      var n = n // Make a mutable copy     let firstPosition = ffsl(n)     if firstPosition == 0 {         return 0     }     n = n >> firstPosition      var longestGap = 0     while n > 0 {         let position = Int(ffsl(n))         if position - 1 > longestGap {             longestGap = position - 1         }         n = n >> position     }      return longestGap } 

Benchmark

My simple benchmark:

let M = 1_000_000  do {     var sum = 0     let start = Date()     for n in 1...M { sum += longestBinaryGap(for: n) }     let end = Date()     print(sum, end.timeIntervalSince(start)) } 

On a 1.2 GHz Intel Core m5 (with the program compiled in Release mode, i.e. with optimizations), I measured approximately:

  • Your original code: 3.3 seconds
  • longestBinaryGap1(): 0.08 seconds
  • longestBinaryGap2(): 0.04 seconds
 
 
 
 

Relacionados problema

2  Tiempo de alta ejecución en el programa de partición numérico en Python 2.7  ( High execution time on number partitioning program in python 2 7 ) 
Estoy escribiendo un programa para contar solo las particiones de un número con distinta partes . Estoy usando un enfoque de abajo hacia arriba para la progr...

7  Encontrar trillizos únicos agregando hasta 0  ( Finding unique triplets adding up to 0 ) 
Estoy trabajando en un problema "3Sum", en el que, dado una matriz var lastName = Request.Params["lastName"] ?? ""0 de var lastName = Request.Params["lastN...

4  Tour de Knights - Algo que estoy haciendo mal  ( Knights tour something i am doing wrong ) 
Tengo una tarea para escribir un programa de backtracking de Knights Tour en Java donde dice el profesor a: Eliminar el tiempo de retroceso por: Find the...

2  HackerRank: Rotación de la matriz izquierda en Python  ( Hackerrank left array rotation in python ) 
Aquí está el problema en Hackerrank . Quiero saber cómo puedo mejorar este código. Estoy tratando principalmente de mejorar las siguientes habilidades: la do...

7  Un algoritmo de partición para enteros positivos  ( A partition algorithm for positive integers ) 
He encontrado el siguiente problema que encontré muy interesante para resolver: Dada una matriz de enteros positivos {A1, A2, ..., A} Se requiere para pa...

5  Números psicosicos y ordinarios  ( Psycho and ordinary numbers ) 
La declaración del problema se puede encontrar aquí . En resumen, aquí es cuál es el problema sobre: ​​ Se le da un conjunto de números y necesita encontra...

4  Python Encuentra todos los subconjuntos adyacentes del conjunto de monedas que tienen una minoría de colas  ( Python find all adjacent subsets of set of coins which have a tails minority ) 
Dada una secuencia de cabezas y colas, quiero encontrar cuántas subsiguientes significativas hay en esta secuencia donde el número de cabezas no es menor que ...

7  Compruebe la consistencia de una lista de declaraciones, con coincidencia de rima difusa  ( Check consistency of a list of statements with fuzzy rhyme matching ) 
Hice un programa hoy que resuelve lo siguiente problema en un sitio de competencia de programación (Open.Kattis.com) : verifique si todas las declaraciones c...

2  Optimización del código para la secuencia A064604  ( Optimizing code for sequence a064604 ) 
Estoy implementando a064604 - oeis para enteros positivos de hasta 10 mil millones. Estoy encontrando a los divisores en $ o ( sqrt n) $. Por lo tanto, ...

-1  Encontrar la distancia desde cada elemento de matriz a la entrada cero más cercana  ( Finding the distance from each array element to the nearest zero entry ) 
Escribí un programa, que obtiene una cierta matriz y reemplaza cada valor en la matriz con la distancia de ella al valor cero más cercano. La complejidad del ...




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