Я работаю над проблемой вне 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, но там ничего не сказано о строках.
источник
urllib.urlencode
rtrim
иreplace
было бы более предпочтительным и примерно равнымO(n)
. Копирование строк кажется наименее эффективным способом.Ответы:
В CPython, стандартной реализации Python, есть деталь реализации, которая делает это обычно O (n), реализованным в коде, который вызывает цикл оценки байт-кода,
+
или+=
с двумя строковыми операндами . Если Python обнаруживает, что левый аргумент не имеет других ссылок, онrealloc
пытается избежать копирования, изменяя размер строки на месте. Это не то, на что вы должны когда-либо полагаться, потому что это деталь реализации, и потому что, если вrealloc
конечном итоге возникает необходимость часто перемещать строку, производительность в любом случае снижается до O (n ^ 2).Без странных деталей реализации алгоритм равен O (n ^ 2) из-за квадратичного количества задействованного копирования. Такой код имел бы смысл только на языке с изменяемыми строками, таком как C ++, и даже в C ++, который вы хотите использовать
+=
.источник
_PyString_Resize(&v, new_len)
выделение памяти для объединенной строки, а затемmemcpy(PyString_AS_STRING(v) + v_len, PyString_AS_STRING(w), w_len);
делает копию. Если изменение размера на месте не удается, это происходитPyString_Concat(&v, w);
(я предполагаю, что это означает, что непрерывная память в конце исходного строкового адреса не свободна). Как это показывает ускорение?realloc
и надеется на лучшее.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 (первая строка)? Двойная память?PyString_AS_STRING(v)
адрес данных первой строки, и добавлениеv_len
дает вам адрес сразу после строки данные заканчиваются.Автор полагается на оптимизацию, которая здесь присутствует, но явно не заслуживает доверия.
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)
, но это нормально, потому что он находится вне цикла.источник
Я нашел этот фрагмент текста на Python Speed> Используйте лучшие алгоритмы и самые быстрые инструменты :
источник
Для будущих посетителей: поскольку это вопрос 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'))
источник