Para todos los índices, debo eliminar el dígito de ese lugar. Un número entero a, convirtiéndolo en Cadena, es decir, S. Y allí después de iterar a lo largo de la cadena,

for i in range(len(S)):
    new =S[:i]+S[i+1:]

¿Hay alguna forma más eficiente de eliminar el dígito del entero?

0
Devendra Sharma 28 oct. 2017 a las 19:35

3 respuestas

La mejor respuesta

ACTUALIZACIÓN: Parece ser contradictorio, pero la solución basada en cadenas es mucho más rápida que la basada en int. Aquí está mi código y resultados en segundos para números de 103, 226 dígitos y 472 dígitos. Decidí no probar el número de 102139 dígitos en mi computadora portátil :)

import timeit, math

digits = [100, 200, 500, 1_000, 2_000, 5_000, 10_000, 50_000, 100_000]

def print_str(n):
  s = str(n)
  for i in range(len(s)):
    #print(i)
    n2 = int(s[:i] + s[i+1:])


def print_int(a):
  p = 1
  while p <= a:
        n2 = a//p//10*p + a%p
        p *= 10

if __name__ == '__main__':
  number = 1
  for i in digits:
    n = 17**math.ceil(math.log(10**i, 17))
    str_ = timeit.timeit('print_str(n)', setup='from __main__ import print_str, n', number=number)
    int_ = timeit.timeit('print_int(n)', setup='from __main__ import print_int, n', number=number)
    print("{:8d}\t{:15.6f}\t{:15.6f}".format(len(str(n)), str_/number*1000, int_/number*1000))

Resultados (en milisegundos para una longitud numérica particular):

$ time python3 main.py
     101           0.169280        0.185082
     201           0.502591        0.537000
     501           3.917680        3.195815
    1001          13.768999       22.781801
    2001         114.404890      120.546628
    5001        1066.541904     1625.172070
   10002        8033.144731     8802.031382
   50001      937385.167088  1045865.986814
  100002     7800950.456252  8189620.010314

Primera columna: número de dígitos, segunda una vez en milisegundos para la solución basada en str y tercera para la basada en int.

¿Pero cómo es posible?

Podría entenderse si recordamos cómo se construyen números enteros sin fin en Python. Debajo del capó hay una matriz de enteros de 15 o 30 bits que al unirse produce el número de resultado. Entonces, cuando divide este número, debe recorrer toda la matriz y modificar cada dígito. También tenga en cuenta la complejidad: a veces tiene que sumar o restar dígitos más significativos, lo que complica el proceso.

Cuando usa cadenas, solo copia bytes de un lugar a otro. Es un procedimiento extremadamente rápido hecho con instrucciones internas de la CPU.

Pero, ¿y si no necesitamos conversión a int? Por ejemplo, queremos imprimir un número, ¿es mejor tenerlo en forma de cadena? ¿Cómo enfatizará el proceso?

Aquí están los resultados, también en ms para diferentes longitudes

 $ time python3 main.py
     101           0.051510        0.124668
     201           0.091741        0.442547
     501           0.357862        2.562110
    1001           0.787016       15.229156
    2001           2.545076      111.917518
    5001           4.993472     1334.944235

UPD: Bencharks de versiones actualizadas:

$ time python3 main2.py

digits        str1        str2        int1        int2
   101       0.047       0.101       0.110       0.073
   201       0.091       0.315       0.380       0.145
   501       0.338       2.049       2.540       0.778
  1001       1.342      16.878      16.032       1.621
  2001       1.626      85.277      97.809       5.553
  5001       4.903    1039.889    1326.481      32.490
 10002      15.987    7856.753    9512.209     129.280
 20001      72.205   60363.860   68219.334     487.088

real    2m29.403s
user    2m27.902s
sys 0m0.577s
2
Eugene Lisitsky 1 nov. 2017 a las 06:43

Otra respuesta produce enteros, mucho más rápido que mi otra respuesta y la solución de cadena del OP:

>>> a = 12345

>>> digits = [0] + list(map(int, str(a)))
>>> p = 10**(len(digits) - 2)
>>> for x, y in zip(digits, digits[1:]):
        a += (x - y) * p
        p //= 10
        print(a)

2345
1345
1245
1235
1234

Esto va de 2345 a 1345 reemplazando el 2 con el 1, lo que hace restando 2⋅1000 y sumando 1⋅1000. O en resumen, agregando (1-2) ⋅1000. Luego va de 1345 a 1245 agregando (2-3) ⋅100. Y así.

Resultados de referencia, utilizando una versión modificada del programa de Eugene:

digits        str1        str2        int1        int2
   101       0.085       0.255       0.376       0.157
   201       0.161       0.943       1.569       0.389
   501       0.514       9.180       9.932       0.983
  1001       0.699      30.544      39.796       2.218
  2001       1.402     203.429     291.006       8.435
  5001       4.852    2691.292    3983.420      50.616
 10002      16.080   21139.318   29114.274     197.343
 20001      54.884  167641.593  222848.841     789.182

Str1 es el momento de la solución de cadena del OP, que produce cadenas.

Str2 es el momento para la solución de cadena del OP, convirtiendo las cadenas en ints.
int1 es mi otra solución para producir ints.
int2 es mi nueva solución para producir ints.

No sorprende que la solución de cadena del OP sea la más rápida en general. Su complejidad de tiempo de ejecución es cuadrática en el número de dígitos. Cuál es el tamaño de salida total, por lo que es óptimo. Mi nueva solución también es cuadrática, pero hacer cálculos es, por supuesto, más trabajo que una copia pura.

Para producir ints, mi nueva solución es, con mucho, la más rápida. Mi anterior y los OP tienen un tiempo de ejecución cúbico para eso (con los OP aparentemente alrededor de 1,4 veces más rápido que el anterior).

El programa de referencia (versión modificada de Eugene):

import timeit, math

digits = [100, 200, 500, 1_000, 2_000, 5_000, 10_000, 20_000]

def print_str_1(n):
  s = str(n)
  for i in range(len(s)):
    #print(i)
    n2 = s[:i] + s[i+1:]

def print_str_2(n):
  s = str(n)
  for i in range(len(s)):
    #print(i)
    n2 = int(s[:i] + s[i+1:])

def print_int_1(a):
  p = 1
  while p <= a:
        n2 = a//p//10*p + a%p
        p *= 10

def print_int_2(a):
    digits = [0] + list(map(int, str(a)))
    p = 10**(len(digits) - 2)
    for x, y in zip(digits, digits[1:]):
        a += (x - y) * p
        p //= 10
        #print(a)

if __name__ == '__main__':
  print(("{:>6}" + 4 * "{:>12}").format('digits', 'str1', 'str2', 'int1', 'int2'))
  number = 1
  for i in digits:
    n = 17**math.ceil(math.log(10**i, 17))
    str1 = timeit.timeit('print_str_1(n)', setup='from __main__ import print_str_1, n', number=number)
    str2 = timeit.timeit('print_str_2(n)', setup='from __main__ import print_str_2, n', number=number)
    int1 = timeit.timeit('print_int_1(n)', setup='from __main__ import print_int_1, n', number=number)
    int2 = timeit.timeit('print_int_2(n)', setup='from __main__ import print_int_2, n', number=number)
    print(("{:6d}" + 4 * "{:12.3f}").format(len(str(n)), *(x/number*1000 for x in (str1, str2, int1, int2))))
2
Stefan Pochmann 31 oct. 2017 a las 20:48

También puedes hacerlo sin condiciones:

>>> a = 12345
>>> p = 1
>>> while p <= a:
        print a/p/10*p + a%p
        p *= 10

1234
1235
1245
1345
2345
0
Stefan Pochmann 28 oct. 2017 a las 17:47