Какова вычислительная стоимость операции подсчета по строкам Python?

Например:Какова вычислительная стоимость операции подсчета по строкам Python?

'hello'.count('e')

ли это O (п)? Я предполагаю, что он работает, он сканирует 'hello' и увеличивает счетчик каждый раз, когда видно письмо 'e'. Как я могу знать это, не догадываясь? Я попробовал чтение исходного кода here, но застрял на поиске этого:

def count(s, *args): 
    """count(s, sub[, start[,end]]) -> int 

    Return the number of occurrences of substring sub in string 
    s[start:end]. Optional arguments start and end are 
    interpreted as in slice notation. 

    """ 
    return s.count(*args)

Где можно прочитать о том, что выполняется в s.count(*args)?

Редактировать: Я понимаю, что делает *args в контексте функций Python.

источник

2016-03-07 nacho

@ cricket_007: Почему вы думаете, что это * соответствующая цель обмана? «*», Похоже, не имеет ничего общего с путаницей опроса. – user2357112

http://stackoverflow.com/questions/16806972/algorithm-used-to-implement-the-python-str-count-function –

str.count реализован в родном коде, в файле stringobject.c, что делегаты либо stringlib_count, либо PyUnicode_Count, который сам делегирует stringlib_count. stringlib_count в конечном счете использует fastsearch для поиска вхождений подстроки в строке и подсчета их.

Для строк один-символов (например, ваш 'e'), это короткое замыкание по следующему пути кода:

for (i = 0; i < n; i++) 
    if (s[i] == p[0]) { 
     count++; 
     if (count == maxcount) 
      return maxcount; 
    } 
return count;

Так что да, это именно так, как вы приобрели простой итерации по последовательности строки и считая вхождения подстроки.

Для строк поиска длиннее одного символа это становится немного сложнее из-за обработки перекрытий и т. Д., А логика глубже погружается в реализацию fastsearch. Но это по сути то же самое: линейный поиск по строке.

Да, str.count находится в линейном времени, O (n). И если вы думаете об этом, это имеет большой смысл: для того, чтобы знать, как часто подстрока появляется в строке, вам нужно посмотреть на каждую возможную подстроку той же длины. Таким образом, для длины подстроки 1 вам нужно посмотреть на каждый символ в строке, что дает вам линейную сложность.

КПП. для получения дополнительной информации о базовом алгоритме fastsearch см. this article on effbot.org.

Для Python 3, который имеет только один Unicode типа строки, ссылки на реализации являются: unicode_count, который использует stringlib_count который использует fastsearch.

источник

2016-03-07 23:08:52 poke

Сложность для строки '' '' '' '' 'O ((nk) k) '. Наихудший сценарий - поиск строки типа '000000' для строки типа' 001'. Цикл проходит через первые символы «n-k» и сравнивает первый элемент (для сравнения «n-k»). Затем он проходит через следующие элементы 'k-1' (для сравнений' (n-k) (k-1) '). Это достигает максимума при 'k = n/2' со сложностью« O (0.25n^2) ». –

@JaredGoguen: для наивного поиска строк это будет правильный анализ. Однако поиск Python намного сложнее, чем это. Я думаю, что он по-прежнему имеет ту же самую наихудшую асимметрию, что и наивный алгоритм, но есть способы получить наихудший случай до O (n). Я думаю, что Python жертвует наихудшими результатами для лучшей производительности в обычном режиме. – user2357112

@ user2357112 Этот анализ основывался на коде в источнике fastsearch. Вложенный цикл можно четко увидеть в 'for (i = 0; i <= w; i ++) {... for (j = 0; j

Большая часть кода библиотеки питона написан на C. Код, который вы ищете здесь:

http://svn.python.org/view/python/trunk/Objects/stringobject.c?view=markup

static PyMethodDef 
string_methods[] = { 
    // ... 
    {"count", (PyCFunction)string_count, METH_VARARGS, count__doc__}, 
    // ... 
    {NULL,  NULL}       /* sentinel */ 
}; 

static PyObject * 
string_count(PyStringObject *self, PyObject *args) { 
    ... 
}

источник

2016-03-07 22:59:11 AJNeufeld

Если вы преследуете ответ @ AJNeufeld, вы в конце концов столкнетесь с этой ссылкой, что объясняет, как работает (then-) новая логика поиска. Это комбинация нескольких подходов к поиску строк, с целью использования некоторой логики, но при этом избегая расходов на настройку начальной таблицы для поиска: http://effbot.org/zone/stringlib.htm

Boyer-Moore - это известный алгоритм поиска строк. BM-Horspool и BM-Sunday - это варианты, которые улучшают оригинал определенным образом.Google найдет вас больше, чем вы когда-либо хотели узнать об этом.

источник

2016-03-07 23:18:33

Какова вычислительная стоимость операции подсчета по строкам Python?

ответ

Смежные вопросы