Как мы можем эффективно проверить, является ли строка шестнадцатеричной в Python - PullRequest
Новая
       55

Как мы можем эффективно проверить, является ли строка шестнадцатеричной в Python

0 голосов
/ 17 октября 2019

Мне нужно проверить, является ли строка шестнадцатеричной. Я изучил 2 подхода -

1.) Цикл по каждому символу 

all(c in string.hexdigits for c in s) # Straight forward with no optimizations

2.) Используйте функцию int () для проверки на ошибку 

try:
    int(s, 16)
    return True
except ValueError:
    return False

В 1-м случае я знаю, что сложность O (n). Но как насчет второго? Какая там временная сложность?

1 Ответ

4 голосов
/ 17 октября 2019

int(s, 16) будет по-прежнему иметь сложность O (n), где n == len(s), но эти два значения не сопоставимы напрямую. int будет перебирать данные на более низком уровне, чем all, что быстрее, но int также выполняет больше работы (на самом деле нужно вычислить целое значение s).

Так что быстрее? Вы должны профилировать оба. 

In [1]: s = "783c"

In [2]: import string

In [3]: %timeit all(c in string.hexdigits for c in s)
800 ns ± 3.23 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [4]: %%timeit
   ...: try:
   ...:   int(s, 16)
   ...: except ValueError:
   ...:   pass
   ...:
223 ns ± 1.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Похоже, выигрывает внутренняя итерация. Я также протестировал 9-значную строку, и int был примерно в 4 раза быстрее.

Но как насчет неверных строк? 

In [8]: s = 'g'

In [9]: %%timeit
   ...: try:
   ...:   int(s, 16)
   ...: except ValueError:
   ...:   pass
   ...:
1.09 µs ± 2.62 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [10]: %timeit all(c in string.hexdigits for c in s)
580 ns ± 6.55 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Теперь мы в основном проверяем преимущество короткого замыкания по сравнению со стоимостью перехвата исключения. Что произойдет, если ошибка возникнет позже в строке? 

In [11]: s = "738ab89ffg"

In [12]: %timeit all(c in string.hexdigits for c in s)
1.59 µs ± 19.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [13]: %%timeit
    ...: try:
    ...:   int(s, 16)
    ...: except ValueError:
    ...:   pass
    ...:
1.25 µs ± 19.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Теперь мы снова видим преимущество от внутренней итерации.

...