Optimización del código

Una de las optimizaciones relativamente fáciles y disponibles siempre, es utilizar una versión actualizada de R. En general, R es muy conservador, por lo que el actualizar la versión no daña el código existente. Sin embargo, una nueva versión proporcionará a menudo aumentos de velocidad para funciones clave.

# Print the R version details using version
version
               _                           
platform       x86_64-apple-darwin15.6.0   
arch           x86_64                      
os             darwin15.6.0                
system         x86_64, darwin15.6.0        
status                                     
major          3                           
minor          5.1                         
year           2018                        
month          07                          
day            02                          
svn rev        74947                       
language       R                           
version.string R version 3.5.1 (2018-07-02)
nickname       Feather Spray               
# Assign the variable major to the major component
major <- version$major
major
[1] "3"
# Assign the variable minor to the minor component
minor <- version$minor
minor
[1] "5.1"

Tiempos de ejecución

Una de las tareas más comunes que realizamos es leer datos de archivos CSV. Sin embargo, para archivos CSV grandes, esto puede ser una tarea lenta. Un buen truco es leer los datos y guardarlos como un archivo binario R (rds) usando saveRDS(). Para leer en el archivo rds, usamos readRDS().

# How long does it take to read movies from CSV?
system.time(read.csv("movies.csv"))
   user  system elapsed 
  0.549   0.015   0.564 
# How long does it take to read movies from RDS?
system.time(readRDS("movies.rds"))
   user  system elapsed 
  0.080   0.002   0.082

Usar system.time () es conveniente, pero tiene sus desventajas cuando se comparan llamadas de múltiples funciones. El paquete microbenchmark resuelve este problema con la función microbenchmark().

# Load the microbenchmark package
library(microbenchmark)

# Compare the two functions
compare <- microbenchmark(read.csv("movies.csv"), 
                          readRDS("movies.rds"), 
                          times = 10)

# Print compare
compare
Unit: milliseconds

Depende de la maquina …

Para muchos problemas, el tiempo es la parte cara. Si tener una computadora más rápida lo hace más productivo, puede ser rentable comprar uno. Sin embargo, antes de gastar nuevos juguetes para usted, su jefe/compañero puede querer ver algunos números para justificar el gasto. Medir el rendimiento de su computadora se llama evaluación comparativa, y puede hacerlo con el paquete benchmarkme.

# Load the benchmarkme package
library(benchmarkme)

# Assign the variable ram to the amount of RAM on this machine
ram <- get_ram()
ram
4.29 GB
# Assign the variable cpu to the cpu specs
cpu <- get_cpu()
cpu
$vendor_id
[1] "GenuineIntel"

$model_name
[1] "Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz"

$no_of_cores
[1] 4

El paquete benchmarkme le permite ejecutar un conjunto de puntos de referencia estandarizados y comparar sus resultados con otros usuarios. Un conjunto de pruebas de puntos de referencia es la velocidad de lectura y escritura.

# Load the package
library(benchmarkme)
See https://jumpingrivers.shinyapps.io/benchmarkme/ for a Shiny
interface to the benchmark data.
# Run the io benchmark
res <- benchmark_io(runs = 1, size = 5)
# IO benchmarks (2 tests) for size 5 MB:
     Reading a csv with 625000 values: 0.912 (sec).
     Writing a csv with 625000 values: 0.886 (sec).
# Plot the results
# plot(res)

Asignación de memoria

Si usted está programando en R, tenga en cuenta lo siguiente:

Considere el ejemplo1:

Welcome to R club!

Importancia de vectorizar tu código

El siguiente fragmento de código está escrito como el código tradicional C o Fortran. En lugar de usar la versión vectorizada de la multiplicación, usa un ciclo for.

x <- rnorm(10)
x2 <- numeric(length(x))
for(i in 1:10)
    x2[i] <- x[i] * x[i]

La idea es evitar el uso extensivo de los ciclos for, debido a que R implementa la vectorización.

x <- rnorm(10)
x2 <- numeric(length(x))
x2_imp <- x^2 
x2_imp
 [1] 0.02951567 0.15724065 0.17687795 3.12364545 0.09472666 0.24533842
 [7] 0.09361045 0.12474215 0.35690963 1.18789281

Una operación común en estadística es calcular la suma de los logaritmos de las probabilidades. El siguiente código calcula el log-sum (la suma de los logaritmos).

# Initial code
n <- 100
total <- 0
x <- runif(n)
for(i in 1:n) 
    total <- total + log(x[i])
total
[1] -108.7323
# Rewrite in a single line. Store the result in log_sum
log_sum <- sum(log(x))
log_sum
[1] -108.7323

Welcome to R club!

    - La segunda regla del club R: use una solución vectorizada siempre que sea posible.

Matrices y Data Frame

Data Frame

  • Estructura de datos clave en R

  • Copiado en otros lenguajes

      - Python: pandas data frame

Matrices

  • Es una estructura de datos rectangular.

  • Puede realizar operaciones de subconjunto y extracción habituales.

Ver Ejemplo 2.

Welcome to R club!

    - La tercera regla del club R: use una matriz cuando sea apropiado.

Code profiling

profiling le ayuda a localizar los cuellos de botella en su código. Este apartado le enseña a visualizar los cuellos de botella utilizando el paquete profis.

La idea general es:

Pararrel Programing

get_cpu()

$vendor_id
[1] "GenuineIntel"

$model_name
[1] "Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz"

$no_of_cores
[1] 4

Corriendo en paralelo

¿Qué tipo de problemas se benefician de la informática paralela?

La siguiente pieza de código implementa un simple juego de dados. El juego es el siguiente:

total <- no_of_rolls <- 0 # Initialise
while(total < 10) {
        total <- total + sample(1:6, 1)
        
        if(total %% 2 == 0) total <- 0  # If even. Reset to 0
        
        no_of_rolls <- no_of_rolls + 1
}
no_of_rolls

¿Crees que este algoritmo se puede (fácilmente) ejecutar en paralelo?

  • No: es un algoritmo secuencial. El i-ésimo valor depende del valor anterior.

Has disfrutado tanto del juego de dados anterior, ¡quieres jugarlo muchas veces!. Vuelve el código original en una función

play <- function() {
  total <- no_of_rolls <- 0
  while(total < 10) {
    total <- total + sample(1:6, 1)

    # If even. Reset to 0
    if(total %% 2 == 0) total <- 0 
    no_of_rolls <- no_of_rolls + 1
  }
  no_of_rolls
}

y construye un ciclo para jugar el juego:

results <- numeric(100)
for(i in seq_along(results)) 
    results[i] <- play()

¿Crees que este ciclo for se puede ejecutar (fácilmente) en paralelo?

Sí, esto es embarrassingly parallel. Podemos simular los juegos en cualquier orden

Convertir a paralelo

LS0tCnRpdGxlOiAiRXNjcmliaWVuZG8gY8OzZGlnbyBlZmljaWVudGUgZW4gUiIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKCiMjIE9wdGltaXphY2nDs24gZGVsIGPDs2RpZ28gCgpVbmEgZGUgbGFzIG9wdGltaXphY2lvbmVzIHJlbGF0aXZhbWVudGUgZsOhY2lsZXMgeSBkaXNwb25pYmxlcyBzaWVtcHJlLCBlcyB1dGlsaXphciB1bmEgdmVyc2nDs24gYWN0dWFsaXphZGEgZGUgUi4gRW4gZ2VuZXJhbCwgUiBlcyBtdXkgY29uc2VydmFkb3IsIHBvciBsbyBxdWUgZWwgYWN0dWFsaXphciBsYSB2ZXJzacOzbiBubyBkYcOxYSBlbCBjw7NkaWdvIGV4aXN0ZW50ZS4gU2luIGVtYmFyZ28sIHVuYSBudWV2YSB2ZXJzacOzbiBwcm9wb3JjaW9uYXLDoSBhIG1lbnVkbyBhdW1lbnRvcyBkZSB2ZWxvY2lkYWQgcGFyYSBmdW5jaW9uZXMgY2xhdmUuCgpgYGB7cn0KIyBQcmludCB0aGUgUiB2ZXJzaW9uIGRldGFpbHMgdXNpbmcgdmVyc2lvbgp2ZXJzaW9uCgojIEFzc2lnbiB0aGUgdmFyaWFibGUgbWFqb3IgdG8gdGhlIG1ham9yIGNvbXBvbmVudAptYWpvciA8LSB2ZXJzaW9uJG1ham9yCm1ham9yCiMgQXNzaWduIHRoZSB2YXJpYWJsZSBtaW5vciB0byB0aGUgbWlub3IgY29tcG9uZW50Cm1pbm9yIDwtIHZlcnNpb24kbWlub3IKbWlub3IKYGBgCgoKIyMgVGllbXBvcyBkZSBlamVjdWNpw7NuIAoKVW5hIGRlIGxhcyB0YXJlYXMgbcOhcyBjb211bmVzIHF1ZSByZWFsaXphbW9zIGVzIGxlZXIgZGF0b3MgZGUgYXJjaGl2b3MgQ1NWLiBTaW4gZW1iYXJnbywgcGFyYSBhcmNoaXZvcyBDU1YgZ3JhbmRlcywgZXN0byBwdWVkZSBzZXIgdW5hIHRhcmVhIGxlbnRhLiBVbiBidWVuIHRydWNvIGVzIGxlZXIgbG9zIGRhdG9zIHkgZ3VhcmRhcmxvcyBjb21vIHVuIGFyY2hpdm8gYmluYXJpbyBSIChyZHMpIHVzYW5kbyBzYXZlUkRTKCkuIFBhcmEgbGVlciBlbiBlbCBhcmNoaXZvIHJkcywgdXNhbW9zIHJlYWRSRFMoKS4KCgpgYGB7cn0KIyBIb3cgbG9uZyBkb2VzIGl0IHRha2UgdG8gcmVhZCBtb3ZpZXMgZnJvbSBDU1Y/CnN5c3RlbS50aW1lKHJlYWQuY3N2KCJtb3ZpZXMuY3N2IikpCgojIEhvdyBsb25nIGRvZXMgaXQgdGFrZSB0byByZWFkIG1vdmllcyBmcm9tIFJEUz8Kc3lzdGVtLnRpbWUocmVhZFJEUygibW92aWVzLnJkcyIpKQpgYGAKClVzYXIgc3lzdGVtLnRpbWUgKCkgZXMgY29udmVuaWVudGUsIHBlcm8gdGllbmUgc3VzIGRlc3ZlbnRhamFzIGN1YW5kbyBzZSBjb21wYXJhbiBsbGFtYWRhcyBkZSBtw7psdGlwbGVzIGZ1bmNpb25lcy4gRWwgcGFxdWV0ZSBtaWNyb2JlbmNobWFyayByZXN1ZWx2ZSBlc3RlIHByb2JsZW1hIGNvbiBsYSBmdW5jacOzbiBtaWNyb2JlbmNobWFyaygpLgoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CiMgTG9hZCB0aGUgbWljcm9iZW5jaG1hcmsgcGFja2FnZQpsaWJyYXJ5KG1pY3JvYmVuY2htYXJrKQoKIyBDb21wYXJlIHRoZSB0d28gZnVuY3Rpb25zCmNvbXBhcmUgPC0gbWljcm9iZW5jaG1hcmsocmVhZC5jc3YoIm1vdmllcy5jc3YiKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgcmVhZFJEUygibW92aWVzLnJkcyIpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICB0aW1lcyA9IDEwKQoKIyBQcmludCBjb21wYXJlCmNvbXBhcmUKYGBgCgojIyBEZXBlbmRlIGRlIGxhIG1hcXVpbmEgLi4uCgpQYXJhIG11Y2hvcyBwcm9ibGVtYXMsIGVsIHRpZW1wbyBlcyBsYSBwYXJ0ZSBjYXJhLiBTaSB0ZW5lciB1bmEgY29tcHV0YWRvcmEgbcOhcyByw6FwaWRhIGxvIGhhY2UgbcOhcyBwcm9kdWN0aXZvLCBwdWVkZSBzZXIgcmVudGFibGUgY29tcHJhciB1bm8uIFNpbiBlbWJhcmdvLCBhbnRlcyBkZSBnYXN0YXIgbnVldm9zIGp1Z3VldGVzIHBhcmEgdXN0ZWQsIHN1IGplZmUvY29tcGHDsWVybyBwdWVkZSBxdWVyZXIgdmVyIGFsZ3Vub3MgbsO6bWVyb3MgcGFyYSBqdXN0aWZpY2FyIGVsIGdhc3RvLiBNZWRpciBlbCByZW5kaW1pZW50byBkZSBzdSBjb21wdXRhZG9yYSBzZSBsbGFtYSBldmFsdWFjacOzbiBjb21wYXJhdGl2YSwgeSBwdWVkZSBoYWNlcmxvIGNvbiBlbCBwYXF1ZXRlIGJlbmNobWFya21lLgoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CiMgTG9hZCB0aGUgYmVuY2htYXJrbWUgcGFja2FnZQpsaWJyYXJ5KGJlbmNobWFya21lKQoKIyBBc3NpZ24gdGhlIHZhcmlhYmxlIHJhbSB0byB0aGUgYW1vdW50IG9mIFJBTSBvbiB0aGlzIG1hY2hpbmUKcmFtIDwtIGdldF9yYW0oKQpyYW0KCiMgQXNzaWduIHRoZSB2YXJpYWJsZSBjcHUgdG8gdGhlIGNwdSBzcGVjcwpjcHUgPC0gZ2V0X2NwdSgpCmNwdQpgYGAKCkVsIHBhcXVldGUgYmVuY2htYXJrbWUgbGUgcGVybWl0ZSBlamVjdXRhciB1biBjb25qdW50byBkZSBwdW50b3MgZGUgcmVmZXJlbmNpYSBlc3RhbmRhcml6YWRvcyB5IGNvbXBhcmFyIHN1cyByZXN1bHRhZG9zIGNvbiBvdHJvcyB1c3Vhcmlvcy4gVW4gY29uanVudG8gZGUgcHJ1ZWJhcyBkZSBwdW50b3MgZGUgcmVmZXJlbmNpYSBlcyBsYSB2ZWxvY2lkYWQgZGUgbGVjdHVyYSB5IGVzY3JpdHVyYS4KCgpgYGB7cn0KIyBMb2FkIHRoZSBwYWNrYWdlCmxpYnJhcnkoYmVuY2htYXJrbWUpCgojIFJ1biB0aGUgaW8gYmVuY2htYXJrCnJlcyA8LSBiZW5jaG1hcmtfaW8ocnVucyA9IDEsIHNpemUgPSA1KQoKIyBQbG90IHRoZSByZXN1bHRzCiMgcGxvdChyZXMpCmBgYAoKCgojIyBBc2lnbmFjacOzbiBkZSBtZW1vcmlhCgpTaSB1c3RlZCBlc3TDoSBwcm9ncmFtYW5kbyBlbiBSLCB0ZW5nYSBlbiBjdWVudGEgbG8gc2lndWllbnRlOgoKKiBFbiBSLCBsYSBhc2lnbmFjacOzbiBkZSBtZW1vcmlhIG9jdXJyZSBhdXRvbcOhdGljYW1lbnRlCgoqIFIgYXNpZ25hIG1lbW9yaWEgZW4gUkFNIHBhcmEgYWxtYWNlbmFyIHZhcmlhYmxlcwoKKiBNaW5pbWljZSBsYSBhc2lnbmFjacOzbiBkZSB2YXJpYWJsZXMgcGFyYSBsYSB2ZWxvY2lkYWQKCkNvbnNpZGVyZSBlbCBlamVtcGxvMToKCiMjIFdlbGNvbWUgdG8gUiBjbHViIQoKKiBfKipUaGUgZmlyc3QgcnVsZSBvZiBSIGNsdWIgbmV2ZXIsIGV2ZXIgZ3JvdyBhIHZlY3RvcioqXyAoTnVuY2EgaW5jcmVtZW50ZSB1biB2ZWN0b3IpCgoKICAgIAoKIyMgSW1wb3J0YW5jaWEgZGUgdmVjdG9yaXphciB0dSBjw7NkaWdvCgoqIExsYW1hciBhIHVuYSBmdW5jacOzbiBSIGZpbmFsbWVudGUgbGxldmEgYWwgY8OzZGlnbyBDIG8gRk9SVFJBTgoKKiBFc3RlIGPDs2RpZ28gZXN0w6EgbXV5IG9wdGltaXphZG8KCiogXyoqTGEgbWV0YSBlcyoqXzogQWNjZWRhIGFsIGPDs2RpZ28gc3VieWFjZW50ZSBkZSBDIG8gRk9SVFJBTiBsbyBtw6FzIHLDoXBpZG8gcG9zaWJsZTsgY3VhbnRhcyBtZW5vcyBmdW5jaW9uZXMgc2UgbGxhbWFuIG1lam9yLgoKCgpFbCBzaWd1aWVudGUgZnJhZ21lbnRvIGRlIGPDs2RpZ28gZXN0w6EgZXNjcml0byBjb21vIGVsIGPDs2RpZ28gdHJhZGljaW9uYWwgQyBvIEZvcnRyYW4uIEVuIGx1Z2FyIGRlIHVzYXIgbGEgdmVyc2nDs24gdmVjdG9yaXphZGEgZGUgbGEgbXVsdGlwbGljYWNpw7NuLCB1c2EgdW4gY2ljbG8gZm9yLgoKYGBge3J9CnggPC0gcm5vcm0oMTApCngyIDwtIG51bWVyaWMobGVuZ3RoKHgpKQpmb3IoaSBpbiAxOjEwKQogICAgeDJbaV0gPC0geFtpXSAqIHhbaV0KYGBgCgoKTGEgaWRlYSBlcyBldml0YXIgZWwgdXNvIGV4dGVuc2l2byBkZSBsb3MgY2ljbG9zIGZvciwgZGViaWRvIGEgcXVlIFIgaW1wbGVtZW50YSBsYSB2ZWN0b3JpemFjacOzbi4gCgpgYGB7cn0KeCA8LSBybm9ybSgxMCkKeDIgPC0gbnVtZXJpYyhsZW5ndGgoeCkpCngyX2ltcCA8LSB4XjIgCngyX2ltcApgYGAKCgpVbmEgb3BlcmFjacOzbiBjb23Dum4gZW4gZXN0YWTDrXN0aWNhIGVzIGNhbGN1bGFyIGxhIHN1bWEgZGUgbG9zIGxvZ2FyaXRtb3MgZGUgbGFzIHByb2JhYmlsaWRhZGVzLiBFbCBzaWd1aWVudGUgY8OzZGlnbyBjYWxjdWxhIGVsIGxvZy1zdW0gKGxhIHN1bWEgZGUgbG9zIGxvZ2FyaXRtb3MpLgoKYGBge3J9CiMgSW5pdGlhbCBjb2RlCm4gPC0gMTAwCnRvdGFsIDwtIDAKeCA8LSBydW5pZihuKQpmb3IoaSBpbiAxOm4pIAogICAgdG90YWwgPC0gdG90YWwgKyBsb2coeFtpXSkKdG90YWwKCiMgUmV3cml0ZSBpbiBhIHNpbmdsZSBsaW5lLiBTdG9yZSB0aGUgcmVzdWx0IGluIGxvZ19zdW0KbG9nX3N1bSA8LSBzdW0obG9nKHgpKQpsb2dfc3VtCmBgYAoKIyMgV2VsY29tZSB0byBSIGNsdWIhCgogICAgICAgIC0gTGEgc2VndW5kYSByZWdsYSBkZWwgY2x1YiBSOiB1c2UgdW5hIHNvbHVjacOzbiB2ZWN0b3JpemFkYSBzaWVtcHJlIHF1ZSBzZWEgcG9zaWJsZS4KCiMjIE1hdHJpY2VzIHkgRGF0YSBGcmFtZQoKIyMjIERhdGEgRnJhbWUgCgoqIEVzdHJ1Y3R1cmEgZGUgZGF0b3MgY2xhdmUgZW4gUgoKKiBDb3BpYWRvIGVuIG90cm9zIGxlbmd1YWplcyAKCiAgICAgICAgLSBQeXRob246IHBhbmRhcyBkYXRhIGZyYW1lCiAgICAgICAgCgojIyMgTWF0cmljZXMgCgoqIEVzIHVuYSBlc3RydWN0dXJhIGRlIGRhdG9zIHJlY3Rhbmd1bGFyLiAKCiogUHVlZGUgcmVhbGl6YXIgb3BlcmFjaW9uZXMgZGUgc3ViY29uanVudG8geSBleHRyYWNjacOzbiBoYWJpdHVhbGVzLgoKVmVyIEVqZW1wbG8gMi4KCiMjIFdlbGNvbWUgdG8gUiBjbHViIQoKICAgICAgICAtIExhIHRlcmNlcmEgcmVnbGEgZGVsIGNsdWIgUjogdXNlIHVuYSBtYXRyaXogY3VhbmRvIHNlYSBhcHJvcGlhZG8uCgojIyBDb2RlIHByb2ZpbGluZwoKcHJvZmlsaW5nIGxlIGF5dWRhIGEgbG9jYWxpemFyIGxvcyBfY3VlbGxvcyBkZSBib3RlbGxhXyBlbiBzdSBjw7NkaWdvLiBFc3RlIGFwYXJ0YWRvIGxlIGVuc2XDsWEgYSB2aXN1YWxpemFyIGxvcyBjdWVsbG9zIGRlIGJvdGVsbGEgdXRpbGl6YW5kbyBlbCBwYXF1ZXRlIGBwcm9maXNgLgoKCkxhIGlkZWEgZ2VuZXJhbCBlczoKCiogRWplY3V0YSBlbCBjw7NkaWdvCgoqIENhZGEgcG9jb3MgbWlsaXNlZ3VuZG9zLCByZWdpc3RyZSBsbyBxdWUgc2UgZXN0w6EgZWplY3V0YW5kbyBhY3R1YWxtZW50ZQoKKiBScHJvZigpIHZpZW5lIGNvbiBSIHkgaGFjZSBleGFjdGFtZW50ZSBlc3RvLCBEaWbDrWNpbCBkZSB1c2FyCgoqIFVzZSBwcm9mdmlzIGVuIHN1IGx1Z2FyCgoKIyMgUGFyYXJyZWwgUHJvZ3JhbWluZyAKCiogQ1BVOiBjZXJlYnJvcyBkZSBsYSBjb21wdXRhZG9yYQoKKiBMYSB2ZWxvY2lkYWQgc2UgZXN0YWJpbGl6w7MgbGVudGFtZW50ZQoKICAgICAgICBfIExhcyBDUFUgc2UgZXN0YWJhbiBjYWxlbnRhbmRvIGRlbWFzaWFkbwoKKiBNdWx0aS1jb3JlIENQVXMKCiogUGVybyBSIHNvbG8gdXNhIDEgbsO6Y2xlbyA6KAoKKiBObyB0b2RvcyBsb3MgYW7DoWxpc2lzIHB1ZWRlbiBoYWNlciB1c28gZGUgbcO6bHRpcGxlcyBuw7pjbGVvcwoKKiBNdWNob3MgYWxnb3JpdG1vcyBlc3RhZMOtc3RpY29zIHNvbG8gcHVlZGVuIHVzYXIgdW4gc29sbyBuw7pjbGVvCgoKCmBgYHtyfQpsaWJyYXJ5KHBhcmFsbGVsKQpsaWJyYXJ5KGJlbmNobWFya21lKQoKZGV0ZWN0Q29yZXMoKQoKZ2V0X2NwdSgpCgpgYGAKCiMjIENvcnJpZW5kbyBlbiBwYXJhbGVsbwoKIyMjIMK/UXXDqSB0aXBvIGRlIHByb2JsZW1hcyBzZSBiZW5lZmljaWFuIGRlIGxhIGluZm9ybcOhdGljYSBwYXJhbGVsYT8KCkxhIHNpZ3VpZW50ZSBwaWV6YSBkZSBjw7NkaWdvIGltcGxlbWVudGEgdW4gc2ltcGxlIGp1ZWdvIGRlIGRhZG9zLiBFbCBqdWVnbyBlcyBlbCBzaWd1aWVudGU6CgpgYGB7cn0KdG90YWwgPC0gbm9fb2Zfcm9sbHMgPC0gMCAjIEluaXRpYWxpc2UKd2hpbGUodG90YWwgPCAxMCkgewogICAgICAgIHRvdGFsIDwtIHRvdGFsICsgc2FtcGxlKDE6NiwgMSkKICAgICAgICAKICAgICAgICBpZih0b3RhbCAlJSAyID09IDApIHRvdGFsIDwtIDAgICMgSWYgZXZlbi4gUmVzZXQgdG8gMAogICAgICAgIAogICAgICAgIG5vX29mX3JvbGxzIDwtIG5vX29mX3JvbGxzICsgMQp9Cm5vX29mX3JvbGxzCmBgYAoKwr9DcmVlcyBxdWUgZXN0ZSBhbGdvcml0bW8gc2UgcHVlZGUgKGbDoWNpbG1lbnRlKSBlamVjdXRhciBlbiBwYXJhbGVsbz8KCiogTm86IGVzIHVuIGFsZ29yaXRtbyBzZWN1ZW5jaWFsLiBFbCBpLcOpc2ltbyB2YWxvciBkZXBlbmRlIGRlbCB2YWxvciBhbnRlcmlvci4KCkhhcyBkaXNmcnV0YWRvIHRhbnRvIGRlbCBqdWVnbyBkZSBkYWRvcyBhbnRlcmlvciwgwqFxdWllcmVzIGp1Z2FybG8gbXVjaGFzIHZlY2VzIS4gVnVlbHZlIGVsIGPDs2RpZ28gb3JpZ2luYWwgZW4gdW5hIGZ1bmNpw7NuCgpgYGB7cn0KcGxheSA8LSBmdW5jdGlvbigpIHsKICB0b3RhbCA8LSBub19vZl9yb2xscyA8LSAwCiAgd2hpbGUodG90YWwgPCAxMCkgewogICAgdG90YWwgPC0gdG90YWwgKyBzYW1wbGUoMTo2LCAxKQoKICAgICMgSWYgZXZlbi4gUmVzZXQgdG8gMAogICAgaWYodG90YWwgJSUgMiA9PSAwKSB0b3RhbCA8LSAwIAogICAgbm9fb2Zfcm9sbHMgPC0gbm9fb2Zfcm9sbHMgKyAxCiAgfQogIG5vX29mX3JvbGxzCn0KYGBgCgp5IGNvbnN0cnV5ZSB1biBjaWNsbyBwYXJhIGp1Z2FyIGVsIGp1ZWdvOgoKYGBge3J9CnJlc3VsdHMgPC0gbnVtZXJpYygxMDApCmZvcihpIGluIHNlcV9hbG9uZyhyZXN1bHRzKSkgCiAgICByZXN1bHRzW2ldIDwtIHBsYXkoKQpgYGAKCgrCv0NyZWVzIHF1ZSBlc3RlIGNpY2xvIGZvciBzZSBwdWVkZSBlamVjdXRhciAoZsOhY2lsbWVudGUpICBlbiBwYXJhbGVsbz8KClPDrSwgZXN0byBlcyBfZW1iYXJyYXNzaW5nbHkgcGFyYWxsZWxfLiBQb2RlbW9zIHNpbXVsYXIgbG9zIGp1ZWdvcyBlbiBjdWFscXVpZXIgb3JkZW4KCgojIyBDb252ZXJ0aXIgYSBwYXJhbGVsbwoKKiBDYXJndWUgZWwgcGFxdWV0ZQoKKiBFc3BlY2lmaXF1ZSBsYSBjYW50aWRhZCBkZSBuw7pjbGVvcwoKKiBDcmVhciB1biBvYmpldG8gZGUgY2zDunN0ZXIKCiogQ2FtYmlhciBhIHBhckFwcGx5KCkKCiogRGV0ZW5lcgoKCg==