Действительно ли временная сложность итеративного добавления строки O (n ^ 2) или O (n)?

89

Я работаю над проблемой вне CTCI.

Третья задача главы 1 - взять строку, например

'Mr John Smith '

и просит вас заменить промежуточные пробелы на %20:

'Mr%20John%20Smith'

Автор предлагает это решение на Python, назвав его O (n):

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    counter = 0
    output = ''
    for char in string:
        counter += 1
        if counter > length:
            return output
        elif char == ' ':
            output = output + '%20'
        elif char != ' ':
            output = output + char
    return output

Мой вопрос:

Я понимаю, что это O (n) с точки зрения сканирования фактической строки слева направо. Но разве строки в Python не неизменны? Если у меня есть строка, и я добавляю к ней еще одну строку с помощью +оператора, разве он не выделяет необходимое пространство, не копирует оригинал, а затем копирует добавляемую строку?

Если у меня есть набор nстрок длиной 1, для этого потребуется:

1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

или время O (n ^ 2) , да? Или я ошибаюсь в том, как Python обрабатывает добавление?

В качестве альтернативы, если вы захотите научить меня ловить рыбу: как бы я узнал это для себя? Я безуспешно пытался найти официальный источник в Google. Я нашел https://wiki.python.org/moin/TimeComplexity, но там ничего не сказано о строках.

user5622964
источник
17
Кто-то должен рассказать автору оurllib.urlencode
wim
11
@wim Это практическая проблема с массивами и строками
user5622964
3
Цель книги - научить задавать вопросы на собеседовании, которые обычно просят вас заново изобрести колесо, чтобы увидеть мыслительный процесс интервьюируемого.
Джеймс Вежба
1
Поскольку это Python, я думаю, что использование rtrimи replaceбыло бы более предпочтительным и примерно равным O(n). Копирование строк кажется наименее эффективным способом.
OneCricketeer
2
@RNar Вы можете объяснить, как копия может занимать постоянное время?
Джеймс Вежба

Ответы:

83

В CPython, стандартной реализации Python, есть деталь реализации, которая делает это обычно O (n), реализованным в коде, который вызывает цикл оценки байт-кода, +или +=с двумя строковыми операндами . Если Python обнаруживает, что левый аргумент не имеет других ссылок, он reallocпытается избежать копирования, изменяя размер строки на месте. Это не то, на что вы должны когда-либо полагаться, потому что это деталь реализации, и потому что, если в reallocконечном итоге возникает необходимость часто перемещать строку, производительность в любом случае снижается до O (n ^ 2).

Без странных деталей реализации алгоритм равен O (n ^ 2) из-за квадратичного количества задействованного копирования. Такой код имел бы смысл только на языке с изменяемыми строками, таком как C ++, и даже в C ++, который вы хотите использовать +=.

user2357112 поддерживает Монику
источник
2
Я смотрю на код, который вы связали ... похоже, что большая часть этого кода очищает / удаляет указатели / ссылки на добавляемую строку, правильно? А затем ближе к концу он выполняет _PyString_Resize(&v, new_len)выделение памяти для объединенной строки, а затем memcpy(PyString_AS_STRING(v) + v_len, PyString_AS_STRING(w), w_len);делает копию. Если изменение размера на месте не удается, это происходит PyString_Concat(&v, w);(я предполагаю, что это означает, что непрерывная память в конце исходного строкового адреса не свободна). Как это показывает ускорение?
user5622964
В моем предыдущем комментарии мне не хватило места, но мой вопрос в том, правильно ли я понимаю этот код и как интерпретировать использование памяти / время выполнения этих частей.
user5622964
1
@ user5622964: Упс, неправильно запомнил странную деталь реализации. Нет эффективной политики изменения размера; он просто зовет reallocи надеется на лучшее.
user2357112 поддерживает Монику
Как memcpy(PyString_AS_STRING(v) + v_len, PyString_AS_STRING(w), w_len);работает? Согласно cplusplus.com/reference/cstring/memcpy, у него есть определение void * memcpy ( void * destination, const void * source, size_t num );и описание: "Copies the values of num bytes from the location pointed to by source directly to the memory block pointed to by destination."число в этом случае - это размер добавляемой строки, а источник - это адрес второй строки, я полагаю? Но тогда почему назначение (первая строка) + len (первая строка)? Двойная память?
user5622964
7
@ user5622964: Это арифметика указателя. Если вы хотите разобраться в исходном коде CPython вплоть до странных деталей реализации, вам необходимо знать C. Сверхконденсированная версия - это PyString_AS_STRING(v)адрес данных первой строки, и добавление v_lenдает вам адрес сразу после строки данные заканчиваются.
user2357112 поддерживает Монику
40

Автор полагается на оптимизацию, которая здесь присутствует, но явно не заслуживает доверия. strA = strB + strCобычно O(n)делает функцию O(n^2). Тем не менее, довольно легко убедиться, что это весь процесс O(n), используя массив:

output = []
    # ... loop thing
    output.append('%20')
    # ...
    output.append(char)
# ...
return ''.join(output)

Вкратце, appendоперация амортизируется O(1) (хотя вы можете сделать ее сильной O(1), предварительно выделив массив до нужного размера), создавая цикл O(n).

И тогда joinтоже O(n), но это нормально, потому что он находится вне цикла.

njzk2
источник
Этот ответ хорош, потому что в нем рассказывается, как объединять строки.
user877329 01
точный ответ в контексте расчета времени выполнения.
Интесар Хайдер,
25

Я нашел этот фрагмент текста на Python Speed> Используйте лучшие алгоритмы и самые быстрые инструменты :

Конкатенацию строк лучше всего выполнять с ''.join(seq)помощью O(n)процесса. Напротив, использование операторов '+'или '+='может привести к O(n^2)процессу, потому что для каждого промежуточного шага могут быть построены новые строки. Интерпретатор CPython 2.4 несколько смягчает эту проблему; однако ''.join(seq)остается лучшей практикой

OneCricketeer
источник
3

Для будущих посетителей: поскольку это вопрос CTCI , здесь не требуется никаких ссылок на изучение пакета urllib , особенно в соответствии с OP и книгой, этот вопрос касается массивов и строк.

Вот более полное решение, вдохновленное псевдонимом @ njzk2:

text = 'Mr John Smith'#13 
special_str = '%20'
def URLify(text, text_len, special_str):
    url = [] 
    for i in range(text_len): # O(n)
        if text[i] == ' ': # n-s
            url.append(special_str) # append() is O(1)
        else:
            url.append(text[i]) # O(1)

    print(url)
    return ''.join(url) #O(n)


print(URLify(text, 13, '%20'))
geekidharsh
источник