Использует `str` правильную идиому для работы с цифрами в Python

Question

Я понимаю, что одним из способов работы с цифрами числа в Python является преобразование числа в строку, а затем использование строковых методов для срезания результирующего «число» в группы «цифр». Например, предположим, у меня есть функция prime, которая проверяет простоты, я могу подтвердить, что целое число п является одновременно левым и правым truncatable prime с

all(prime(int(str(n)[:-i])) and prime(int(str(n)[i:])) for i in range(1, len(str(n)))) 

Этот метод включает первый преобразование н в строку так, чтобы его можно нарезать и преобразовать этот срез обратно в целое число, чтобы можно было проверить его примитивность. Возможно, это моя история со статически типизированными языками или смутная идея о том, что строки являются «дорогими» или опытными языками, которые включают встроенные функции для подобных манипуляций (например, Mathematica'sIntegerDigits и FromDigits); но мне осталось интересно, правильно ли это решать такие задачи.

Является конверсией между укусами и цифрами правильный или даже единственный подход для доступа к цифрам в Python. Существуют ли более эффективные подходы?

Answer 1

Это всегда был мой подход, и он отлично работал, хотя я никогда не проводил много испытаний на скорость. Он работает особенно хорошо, когда требуется перебирать перестановки/комбинации цифр, поскольку вы можете создавать такие строки с функциями в пакете itertools.

Существуют, конечно, другие методы, которые включают в себя менее простые математические операции, но если скорость абсолютно невелика, я чувствую, что строковый метод является самым Pythonic.

---

Вот, к примеру, является более математический подход, где а и Ь индексируются с правой стороны (то есть те, место 0, десятки место 1, и т.д.):

def getSubdigits(n, a, b): 
    n %= 10 ** a 
    n //= 10 ** b 
    return n 

Для это работать с той же индексацией, как строки нарезка, вам нужно найти общее количество цифр первого и функция становится:

def getSubdigits2(n, a, b): 
    l = int(math.ceil(math.log10(n))) 
    n %= 10 ** (l - a) 
    n //= 10 ** (l - b) 
    return n 

и строка нарезка эквивалент:

def subDigits3(n, a, b): 
    return int(str(n)[a:n]) 

Вот временные результаты:

• subDigits: 0,293327726114
• subDigits2: 0,850861833337
• subDigits3: 0,990543234267

Мой вынос из этого результата состоит в том, что метод нарезки прекрасно, если вы действительно заботитесь о скорости, и в этом случае вам нужно использовать первый m этод и подумать об индексах в другом направлении.

Answer 2

Как насчет этого?

def digits(n): 
    if n == 0: 
     yield 0 
    else: 
     while n: 
      yield n % 10 
      n //= 10 

for digit in digits(123): 
    # do something with digit 

Это должно быть как более удобным, так и более эффективным, чем пример, который вы показали.

EDIT: Я хочу добавить еще две вещи.

0) Вы можете расширить технику по мере необходимости. Предположим, вы хотите проверить правильные штрихи. Если у вас есть функция is_prime():

def right_trunc_int_values(n): 
    if n == 0: 
     yield 0 
    else: 
     while n: 
      yield n 
      n //= 10 

assert(all(is_prime(n) for n in right_trunc_int_values(317)) 

1) Для того, чтобы решить общую проблему удобно работать с цифрами, вы можете быть в состоянии использовать decimal модуль. Я рассмотрю это больше. Но между тем, вы можете использовать мою digits() функции, чтобы индексируемый список цифр:

d = list(digits(123)) 
print(d[2]) # prints 2 

EDIT: Это довольно легко конвертировать ряд цифр до целого значения.

def int_from_digits(digits): 
    result = 0 
    found_a_digit = False 
    for digit in reversed(digits): 
     result = result * 10 + digit 
    return result 

def is_right_trunc_prime(n): 
    d = list(digits(n)) 
    return all(is_prime(int_from_digits(d[:i]) for i in range(len(d), -1, -1))) 

# example from question of left and right truncatable check 
d = list(digits(n)) 
all(prime(int_from_digits(d[:-i])) and prime(int_from_digits(d[i:])) for i in range(1, len(d))) 

Answer 3

В вашем примере кода, вы могли бы уйти с использованием divmod, а не строка нарезка цифр. divmod(x, y) возвращает кортеж x//y, x%y, который для y значений 10**i - это именно то, что вы хотите для левой и правой частей вашего номера. Это не обязательно больше Pythonic, хотя это может быть немного быстрее.

sn = str(n) 
all(prime(int(sn[:i])) and prime(int(sn[i:])) for i in range(1, len(sn))) # original 
all(all(map(prime, divmod(n, 10**i))) for i in range(1, len(sn))) # variant using divmod 

Я думаю, что для более общих цифр операций, используя str, вероятно, довольно разумно, как делать много математики по степеням вашей числовой базы, вероятно, будет труднее понять, чем делать вещи прямо на цифры в строке ,

Напишите код для чтения, если только он не чувствителен к производительности.

Answer 4

Тестирование осталось truncatable простых чисел без str() и нарезки:

def is_prime(n): 
    if n < 2: 
     return False 
    elif n == 2: 
     return True 
    elif n % 2 == 0: 
     return False 
    return all(n % x for x in xrange(3,int(pow(n,0.5))+1,2)) 

def is_left_truncatable_prime(n): 
    largest_power_of_ten = 1 
    while largest_power_of_ten < n: 
     largest_power_of_ten *= 10 
    while True: 
     largest_power_of_ten /= 10 # Use // in Python 3 
     if is_prime(n): 
      n %= largest_power_of_ten 
      if n == 0: 
       return True 
     else: 
      return False 

print is_left_truncatable_prime(167) # True 
print is_left_truncatable_prime(173) # True 
print is_left_truncatable_prime(171) # False 

Я не экстенсивно проверил это очень жаль, если есть какая-либо ошибка. Дайте мне знать, если есть, и я их исправлю.

EDIT: исправлен код.

Answer 5

Нативные целые числа на Python хранятся в базе с мощностью-2, поэтому для преобразования их в десятичную нотацию или из десятичной записи требуется реальная работа. Во многих типах «головоломок» ;-) проблем, требующих частого доступа к десятичным разрядам очень больших целых чисел, может сделать мир различий, чтобы вместо этого использовать модуль decimal. Это сохраняет значения в базе с мощностью -10, так что «преобразование» в/из десятичных цифр является тривиальным расходом.

>>> import decimal 
>>> x = decimal.Decimal('1e20') - 1 
>>> x 
Decimal('99999999999999999999') 
>>> x.as_tuple().digits 
(9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9) 

Это занимает время линейное в количестве цифр. Преобразование собственного целого числа в/из десятичного числа занимает квадратичное время в количестве цифр.

Лучшее Я могу догадаться о вашем конкретном приложении здесь, хотя, используя divmod(), действительно лучший подход.