Какая функция лучше для удаления символов из строк - сложность времени - PullRequest
Новая
       5

Какая функция лучше для удаления символов из строк - сложность времени

0 голосов
/ 19 апреля 2020

Мне нужно создать функцию, которая удаляет все цифры из строки в Python, однако мой вопрос не о том, как это сделать (потому что я знаю из предыдущих сообщений здесь)

У меня есть вопрос о сложности этих двух функций: одна использует фильтр и лямбда-функцию для удаления цифр, а другая - регулярное выражение из базовых c тестов с очень длинными строками (~ 67 912 000 символов +)
Я пришел к выводу это регулярное выражение быстрее, однако я не знаю реальной сложности, и поэтому мои «расчеты» не верны / смещены по спецификациям компьютера (возможно, мой компьютер работает быстро, а другие будут медленными или наоборот ...)
Чтение из целого rnet о сложности функции фильтра и сложности регулярного выражения Я понял, что они оба O (n) ..

Итак, что Один из них «перебор» в сложности памяти / времени, а другой нет. Какой из них вы должны использовать (как лучшую практику) ?: 

import time
import re

def dwf(word):
    start = time.time()
    word = ''.join((filter(lambda x: x.isalpha(), word)))
    end = time.time()
    return end - start



def dwr(word):
    start = time.time()
    word = re.sub(r"\d+", '', word)
    end = time.time()
    return end-start

Например, для меня:
, если слово составляет 67 миллионов ~ символов, разница во времени была близка к 7 секундам! (когда фильтр длиннее, а регулярное выражение быстрее)

Ответы [ 2 ]

0 голосов
/ 19 апреля 2020

Различные методы - это O (n), но некоторые методы намного быстрее из-за разного коэффициента масштабирования.

Например, проверка времени показывает, что maketrans намного быстрее, чем методы OP.

Метод 

def dwf(word):
    " Filter method "
    return ''.join((filter(lambda x: x.isalpha(), word)))


def dwr(word):
    " Regex method "
    return  re.sub(r"\d+", '', word)

def trans(word):
    " Maketrans method "
    translation = str.maketrans("", "", string.digits)
    return word.translate(translation)

Тестирование

Используйте timeit для измерения времени, так как оно самое надежное.

Настройка

Случайная строка в верхнем / нижнем регистре + цифры 

import string
import random

N = 1000000  # Million characters
word = ''.join(random.choice(string.ascii_uppercase + string.ascii_lowercase + string.digits) for _ in range(N))

Результаты 

import timeit

Фильтр 

%timeit dwf(word)
 N = 1000 -> timeit: 280 us
 N = 1 M -> timeit:  241 ms

Regex 

%timeit dwr(word)
N = 1000 -> timeit: 84.6 us
N = 1 M  -> timeit: 87.5 ms

Макетранс 

%timeit trans(word)
N = 1000 -> timeit: 11.4 us
N = 1 M -> timeit:   3.78 ms

Заключение

При увеличении количества точек с 1К до 1М время фильтра и регулярных выражений увеличилось на ~ 1000 (линейное)

Макетранс увеличился всего на ~ 300, что означает, что он более эффективен при обработке больших строк .

С N = 1000 

  Maketrans is 24X filter

  Maketrans is 7X Regex

С N = 1 М 

  Maketrans is 63X filter

  Maketrans is 23X regex
0 голосов
/ 19 апреля 2020

Поскольку вы уже знаете, что для этого требуется O (n), я бы сказал, что вам необходимо выяснить свои входные данные (здесь это word), т. Е. Лучшие и худшие случаи, чтобы увидеть, если вы получаете одинаковую сложность времени O (n) для подходов, которые вы пробуете.

Для сложности пространства я вижу, что оба метода дают вам в среднем O (1).

...