suena - Número de crujidos en Ruby(optimización necesaria)

el compresor del aire acondicionado hace mucho ruido

Question

Puede que Ruby no sea el lenguaje óptimo para esto, pero me siento cómodo trabajando con esto en mi terminal, así que eso es lo que voy a hacer.

Necesito procesar los números del 1 al 666666, así que elimino todos los números que contienen 6 pero no contiene 7, 8 o 9. El primer número será 6 , los siguientes 16 , luego 26 y así sucesivamente. Entonces lo necesitaba impreso así (6=6) (16=6) (26=6) y cuando tengo rangos como 60 a 66 lo necesito impreso como (60 THRU 66=6) (sintaxis de SPSS).

Tengo este código y funciona, pero no es bonito ni muy eficiente, así que ¿cómo podría optimizarlo?

(código tonto puede seguir)

class Array
  def to_ranges
    array = self.compact.uniq.sort
    ranges = []
    if !array.empty?
      # Initialize the left and right endpoints of the range
      left, right = array.first, nil
      array.each do |obj|
        # If the right endpoint is set and obj is not equal to right''s successor 
        # then we need to create a range.
        if right && obj != right.succ
          ranges << Range.new(left,right)
          left = obj
        end
        right = obj
      end
      ranges << Range.new(left,right) unless left == right
    end
    ranges
  end
end

write = ""
numbers = (1..666666).to_a

# split each number in an array containing it''s ciphers
numbers = numbers.map { |i| i.to_s.split(//) }

# delete the arrays that doesn''t contain 6 and the ones that contains 6 but also 8, 7 and 9
numbers = numbers.delete_if { |i| !i.include?(''6'') }
numbers = numbers.delete_if { |i| i.include?(''7'') }
numbers = numbers.delete_if { |i| i.include?(''8'') }
numbers = numbers.delete_if { |i| i.include?(''9'') }

# join the ciphers back into the original numbers
numbers = numbers.map { |i| i.join }

numbers = numbers.map { |i| i = Integer(i) }

# rangify consecutive numbers
numbers = numbers.to_ranges

# edit the ranges that go from 1..1 into just 1
numbers = numbers.map do |i|
  if i.first == i.last
    i = i.first
  else
    i = i
  end
end

# string stuff
numbers = numbers.map { |i| i.to_s.gsub(".."," thru ") }

numbers = numbers.map { |i| "(" + i.to_s + "=6)"}

numbers.each { |i| write << " " + i }

File.open(''numbers.txt'',''w'') { |f| f.write(write) }

Como dije, funciona para números incluso en millones, pero me gustaría algunos consejos sobre cómo hacer más bonita y más eficiente.

Answer 1

Explotando patrones en los números, puede cortocircuitar muchos de los bucles, como este:

Si define un prefix como el lugar 100s y todo lo anterior, y defina el suffix como todo en el lugar 10s y 1s, entonces, recorriendo cada posible prefijo:

• Si el prefijo está en blanco (es decir, está probando 0-99), entonces hay 13 posibles coincidencias
• si el prefijo contiene un 7, 8 o 9, no hay coincidencias posibles.
• elsif el prefijo contiene un 6, hay 49 posibles coincidencias (una cuadrícula de 7x7)
• de lo contrario, hay 13 posibles coincidencias. (ver la imagen a continuación)

(el código aún no excluye los números que no están específicamente en el rango, pero está bastante cerca)

number_range = (1..666_666)
prefix_range = ((number_range.first / 100)..(number_range.last / 100))

for p in prefix_range
  ps = p.to_s

  # TODO: if p == prefix_range.last or p == prefix_range.first,
  # TODO: test to see if number_range.include?("#{ps}6".to_i), etc...

  if ps == ''0''
    puts "(6=6) (16=6) (26=6) (36=6) (46=6) (56=6) (60 thru 66) "

  elsif ps =~ /7|8|9/
    # there are no candidate suffixes if the prefix contains 7, 8, or 9.

  elsif ps =~ /6/
    # If the prefix contains a 6, then there are 49 candidate suffixes
    for i in (0..6)
      print "(#{ps}#{i}0 thru #{ps}#{i}6) "
    end
    puts

  else
    # If the prefix doesn''t contain 6, 7, 8, or 9, then there are only 13 candidate suffixes.
    puts "(#{ps}06=6) (#{ps}16=6) (#{ps}26=6) (#{ps}36=6) (#{ps}46=6) (#{ps}56=6) (#{ps}60 thru #{ps}66) "

  end
end

Que imprime lo siguiente:

(6=6) (16=6) (26=6) (36=6) (46=6) (56=6) (60 thru 66) 
(106=6) (116=6) (126=6) (136=6) (146=6) (156=6) (160 thru 166) 
(206=6) (216=6) (226=6) (236=6) (246=6) (256=6) (260 thru 266) 
(306=6) (316=6) (326=6) (336=6) (346=6) (356=6) (360 thru 366) 
(406=6) (416=6) (426=6) (436=6) (446=6) (456=6) (460 thru 466) 
(506=6) (516=6) (526=6) (536=6) (546=6) (556=6) (560 thru 566) 
(600 thru 606) (610 thru 616) (620 thru 626) (630 thru 636) (640 thru 646) (650 thru 656) (660 thru 666) 
(1006=6) (1016=6) (1026=6) (1036=6) (1046=6) (1056=6) (1060 thru 1066) 
(1106=6) (1116=6) (1126=6) (1136=6) (1146=6) (1156=6) (1160 thru 1166) 
(1206=6) (1216=6) (1226=6) (1236=6) (1246=6) (1256=6) (1260 thru 1266) 
(1306=6) (1316=6) (1326=6) (1336=6) (1346=6) (1356=6) (1360 thru 1366) 
(1406=6) (1416=6) (1426=6) (1436=6) (1446=6) (1456=6) (1460 thru 1466) 
(1506=6) (1516=6) (1526=6) (1536=6) (1546=6) (1556=6) (1560 thru 1566) 
(1600 thru 1606) (1610 thru 1616) (1620 thru 1626) (1630 thru 1636) (1640 thru 1646) (1650 thru 1656) (1660 thru 1666) 

etc ...

Answer 2

Mi primera respuesta fue tratar de ser demasiado inteligente. Aquí hay una versión mucho más simple

class MutablePrintingCandidateRange < Struct.new(:first, :last)
  def to_s
    if self.first == nil and self.last == nil
      ''''
    elsif self.first == self.last
      "(#{self.first}=6)"
    else
      "(#{self.first} thru #{self.last})"
    end
  end

  def <<(x)
    if self.first == nil and self.last == nil
      self.first = self.last = x
    elsif self.last == x - 1
      self.last = x
    else
      puts(self) # print the candidates
      self.first = self.last = x # reset the range
    end
  end

end

Y cómo usarlo:

numer_range = (1..666_666)
current_range = MutablePrintingCandidateRange.new

for i in numer_range
  candidate = i.to_s

  if candidate =~ /6/ and candidate !~ /7|8|9/
    # number contains a 6, but not a 7, 8, or 9
    current_range << i
  end
end
puts current_range

Answer 3

Observación básica: si el número actual es (digamos) 1900 usted sabe que puede saltar de manera segura hasta al menos 2000 ...

Answer 4

Se me ocurrió esta pieza de código, que traté de mantener más o menos en el estilo FP. Probablemente no sea mucho más eficiente (como se ha dicho, con la lógica numérica básica podrá aumentar el rendimiento, por ejemplo saltando de 19xx a 2000 directamente, pero eso lo dejaré en sus manos :)

def check(n)
    n = n.to_s
    n.include?(''6'') and
    not n.include?(''7'') and
    not n.include?(''8'') and
    not n.include?(''9'')
end

def spss(ranges)
  ranges.each do |range|
    if range.first === range.last
      puts "(" + range.first.to_s + "=6)"
    else
      puts "(" + range.first.to_s + " THRU " + range.last.to_s + "=6)"
    end
  end
end

range = (1..666666)

range = range.select { |n| check(n) }

range = range.inject([0..0]) do |ranges, n|
  temp = ranges.last
  if temp.last + 1 === n
    ranges.pop
    ranges.push(temp.first..n)
  else
    ranges.push(n..n)
  end
end

spss(range)

Answer 5

$range_start = -1 $range_end = -1 $f = File.open(''numbers.txt'',''w'') def output_number(i) if $range_end == i-1 $range_end = i elsif $range_start < $range_end $f.puts "(#{$range_start} thru #{$range_end})" $range_start = $range_end = i else $f.puts "(#{$range_start}=6)" if $range_start > 0 # no range, print out previous number $range_start = $range_end = i end end ''1''.upto(''666'') do |n| next unless n =~ /6/ # keep only numbers that contain 6 next if n =~ /[789]/ # remove nubmers that contain 7, 8 or 9 output_number n.to_i end if $range_start < $range_end $f.puts "(#{$range_start} thru #{$range_end})" end $f.close puts "Ruby is beautiful :)"

Answer 6

El asesino aquí es

numbers = (1..666666).to_a

El rango admite iteraciones, por lo que le irá mejor revisando todo el rango y acumulando números que incluyen sus segmentos en bloques. Cuando un bloque es terminado y suplantado por otro, puedes escribirlo.

Answer 7

Mi respuesta a continuación no está completa, solo para mostrar un camino (podría volver y continuar la respuesta):

Solo hay dos casos:

1) Todos los dígitos además del más bajo están ausentes o no 6

6, 16, ...

2) Al menos un dígito además del más bajo incluye 6

60--66, 160--166, 600--606, ...

Los casos en (1) no incluyen ningún número continuo porque todos tienen 6 en el dígito más bajo y son diferentes el uno del otro. Los casos en (2) aparecen como intervalos continuos donde el dígito más bajo continúa de 0 a 6. Cualquier continuación simple en (2) no es continua con otra en (2) o con algo de (1) porque un número uno menor que xxxxx0 será xxxxy9, y un número uno más que xxxxxx6 será xxxxxx7, y por lo tanto se excluirá.

Por lo tanto, la pregunta se reduce a lo siguiente:

3)

Obtenga todas las cadenas entre "" y "66666" que no incluyen "6"
Para cada uno de ellos ("xxx"), imprima la cadena "(xxx6 = 6)"

4)

Obtenga todas las cadenas entre "" y "66666" que incluyen al menos un "6"
Para cada uno de ellos ("xxx"), envíe la cadena "(xxx0 THRU xxx6 = 6)"

Answer 8

¿Eliminé mi intento anterior de parlez-vous-ruby? y compensado por eso. Sé que tengo una versión optimizada del excelente ejemplo de x3ro .

$,="/n"
puts ["(0=6)", "(6=6)", *(1.."66666".to_i(7)).collect {|i| i.to_s 7}.collect do |s|
    s.include?(''6'')? "(#{s}0 THRU #{s}6=6)" : "(#{s}6=6)"
end ]

Comparado con la versión de x3ro

... Se trata de tres líneas

... 204.2 x más rápido (hasta 66666666)

... tiene salida byte-idéntica

Utiliza todas mis ideas para la optimización

• Números de gen basados ​​en dígitos del módulo 7 (por lo tanto, números de base 7)
• generar el último dígito ''inteligente'': esto es lo que comprime los rangos

Entonces ... ¿cuáles son los tiempos? Esto estaba probando con 8 dígitos (hasta 66666666, o 823544 líneas de salida):

$ time ./x3ro.rb >  /dev/null

real    8m37.749s
user    8m36.700s
sys 0m0.976s

$ time ./my.rb >  /dev/null

real    0m2.535s
user    0m2.460s
sys 0m0.072s

Aunque el rendimiento es realmente bueno, ni siquiera está cerca de la versión optimizada C que publiqué antes: No pude ejecutar my.rb a 6666666666 (6x10) debido a OutOfMemory . Cuando se ejecuta en 9 dígitos, este es el resultado comparativo:

sehe@meerkat:/tmp$ time ./my.rb >  /dev/null

real    0m21.764s
user    0m21.289s
sys 0m0.476s

sehe@meerkat:/tmp$ time ./t2 > /dev/null

real    0m1.424s
user    0m1.408s
sys 0m0.012s

La versión C todavía es 15 veces más rápida ... lo cual es justo teniendo en cuenta que funciona en el metal desnudo.

Espero que lo hayas disfrutado, y puedo por favor tener tus votos solo para aprender a Ruby para este propósito :)

( ¿Puedes decir que estoy orgulloso? Este es mi primer encuentro con ruby, comencé los ruby ​​koans hace 2 horas ... )

Edite por @johndouthat :

¡Muy agradable! El uso de base7 es muy inteligente y es un excelente trabajo para tu primera prueba de ruby ​​:)

Aquí hay una pequeña modificación de su fragmento que le permitirá probar más de 10 dígitos sin obtener un error de OutOfMemory:

puts ["(0=6)", "(6=6)"]
(1.."66666666".to_i(7)).each do |i| 
  s = i.to_s(7)
  puts s.include?(''6'') ? "(#{s}0 THRU #{s}6=6)" : "(#{s}6=6)"
end

# before:
real    0m26.714s
user    0m23.368s
sys 0m2.865s
# after
real    0m15.894s
user    0m13.258s
sys 0m1.724s

Answer 9

( No me molesté en actualizar mi solución C para formatear. En cambio , opté por la excelente versión ruby ​​de x3ro y optimicé eso )

Sin eliminar:

Todavía no estoy seguro de si el comportamiento de notación de rango cambiado no es realmente lo que el OP quiere: esta versión cambia el comportamiento de los rangos de interrupción que son realmente contiguos módulo 6; No me sorprendería que OP esperara realmente .

....
(555536=6)
(555546=6)
(555556 THRU 666666=6)

en lugar de

....
(666640 THRU 666646=6)
(666650 THRU 666656=6)
(666660 THRU 666666=6)

Dejaré que el OP decida, y aquí está la versión modificada, que se ejecuta en el 18% del tiempo como la versión de x3ro (3.2s en lugar de 17.0s al generar hasta 6666666 (7x6)).

def check(n)
    n.to_s(7).include?(''6'')
end

def spss(ranges)
  ranges.each do |range|
    if range.first === range.last
      puts "(" + range.first.to_s(7) + "=6)"
    else
      puts "(" + range.first.to_s(7) + " THRU " + range.last.to_s(7) + "=6)"
    end
  end
end

range = (1..117648)

range = range.select { |n| check(n) }

range = range.inject([0..0]) do |ranges, n|
  temp = ranges.last
  if temp.last + 1 === n
    ranges.pop
    ranges.push(temp.first..n)
  else
    ranges.push(n..n)
  end
end

spss(range)

Answer 10

Tenga en cuenta que no hablo ruby, pero tengo la intención de hacer una versión de ruby ​​más tarde solo para la comparación de velocidad :)

Si solo itera todos los números de 0 a 117648 ( ruby <<< ''print "666666".to_i(7)'' ) e imprime en notación base-7, al menos habrá descartado cualquier número que contenga 7,8, 9. Esto incluye la sugerencia de optimización de MrE, además de resolver el problema con aritmética simple en lugar de manipulaciones de secuencia de char.

Lo único que queda es comprobar la presencia de al menos un 6. Esto haría que el algoritmo omita como máximo 6 elementos en una fila, por lo que considero que es menos importante (el número promedio de elementos saltables en el rango total es del 40% )

Referencia simple para 6666666666

(Tenga en cuenta que esto significa dar salida a 222,009,073 (222M) líneas de números 6-y)

Manteniéndome cerca de esta idea, escribí este código C bastante optimizado (no hablo ruby) para demostrar la idea. Lo ejecuté a 282475248 (congruente con 6666666666 (mod 7)) por lo que era más un punto de referencia para medir: 0m26.5s

#include <stdio.h>

static char buf[11]; 
char* const bufend = buf+10;

char* genbase7(int n)
{
    char* it = bufend; int has6 = 0;
    do
    { 
        has6 |= 6 == (*--it = n%7); 
        n/=7; 
    } while(n);

    return has6? it : 0;
}

void asciify(char* rawdigits)
{
    do { *rawdigits += ''0''; } 
    while (++rawdigits != bufend);
}

int main()
{
    *bufend = 0; // init

    long i;
    for (i=6; i<=282475248; i++)
    {
        char* b7 = genbase7(i);
        if (b7)
        {
            asciify(b7);
            puts(b7);
        }
    }
}

También comparé otro enfoque que, como era de esperar, funcionó en menos de la mitad de las veces porque

• esta versión manipula directamente los resultados en forma de cadena ascii, lista para mostrar
• esta versión has6 bandera has6 para niveles de recursión más profundos
• esta versión también optimiza el ''twiddling'' del último dígito cuando se requiere que sea ''6''
• el código es simplemente más corto ...

Tiempo de ejecución: 0m12.8s

#include <stdio.h>
#include <string.h>

inline void recursive_permute2(char* const b, char* const m, char* const e, int has6)
{
    if (m<e)
        for (*m = ''0''; *m<''7''; (*m)++)
            recursive_permute2(b, m+1, e, has6 || (*m==''6''));
    else
        if (has6)
            for (*e = ''0''; *e<''7''; (*e)++)
                puts(b);
        else /* optimize for last digit must be 6 */
            puts((*e=''6'', b));
}

inline void recursive_permute(char* const b, char* const e)
{
    recursive_permute2(b, b, e-1, 0);
}

int main()
{
    char buf[] = "0000000000"; 
    recursive_permute(buf, buf+sizeof(buf)/sizeof(*buf)-1);
}

Puntos de referencia medidos con:

gcc -O4 t6.c -o t6
time ./t6 > /dev/null