Рассмотрим питона строку:Как реализовать Python str [:: - 1]?

str[::-1]

Я вижу это очень быстро, и путь более быстрее, чем какой-то O (п) раствора, а также экономии памяти. Какой алгоритм использует Python в этом случае?

2016-07-03 jerrypy

Хм, вы пробовали какие-либо быстрые и грязные тесты? Вот первый проход:

In [1]: import time 

In [2]: def reverse_list_time(my_list): 
    ...:  start = time.time() 
    ...:  reversed = my_list[::-1] 
    ...:  stop = time.time() 
    ...:  return stop - start 
    ...: 

In [3]: reverse_list_time(list(range(1000))) 
Out[3]: 1.33514404296875e-05 

In [4]: testing_lists = (list(range(n)) for n in range(1000,100000,500)) 

In [5]: testing_lists 
Out[5]: <generator object <genexpr> at 0x7f7786bd97d8> 

In [6]: results = list(map(reverse_list_time,testing_lists))

И вот мои результаты

Это выглядит примерно O (п) ко мне.

Если это вас не убеждает, вот the implementation. Это похоже на довольно прямое решение O (n) для меня. Это мясо его:

else { 
     result = PyList_New(slicelength); 
     if (!result) return NULL; 

     src = self->ob_item; 
     dest = ((PyListObject *)result)->ob_item; 
     for (cur = start, i = 0; i < slicelength; 
      cur += step, i++) { 
      it = src[cur]; 
      Py_INCREF(it); 
      dest[i] = it; 
     } 

     return result;

источник

2016-07-03 04:35:13

Вы можете использовать dis.dis модуль Python, чтобы разобрать str[::-1]:

>>> import dis 
>>> def reverse_(str_): 
...  return str_[::-1] 
... 
>>> dis.dis(reverse_) 
    6   0 LOAD_FAST    0 (str_) 
       3 LOAD_CONST    0 (None) 
       6 LOAD_CONST    0 (None) 
       9 LOAD_CONST    1 (-1) 
      12 BUILD_SLICE    3 
      15 BINARY_SUBSCR  
      16 RETURN_VALUE

Вы можете увидеть, что означает, что каждая команда в documentation. Для LOAD_FAST документы говорят:

Помещает ссылку на локальный co_varnames[var_num] в стек.

co_varnames - это структура, которая всегда присутствует с кодовым объектом. В этом случае, str_:

>>> reverse_.__code__.co_varnames 
('str_',)

Следующая команда, LOAD_CONST, описывается так:

Заносит co_consts[consti] на стек.

Значение, помещается в стек является None (dis полезно и посмотрел его для вас). Следующие две команды: LOAD_CONST инструкции, которые вставляют значения None и -1 в стек.

Следующая команда, BUILD_SLICE, описывается как:

толкает объект ломтик в стеке. argc должно быть 2 или 3. Если оно равно 2, то slice(TOS1, TOS); если 3, slice(TOS2, TOS1, TOS) вдавлено. Для получения дополнительной информации см. Встроенную функцию slice().

TOS2, TOS1, TOS представляют значения в стеке None, None, -1, который толкают к slice() объекта из стека (объект становится slice(None, None, -1)).

BINARY_SUBSCR описывается как:

Реализует TOS = TOS1[TOS].

Это означает, что Python вычисляет str_[sli] где sli является slice() объекта помещается в стек в предыдущей инструкции. Это эквивалент

>>> str_[slice(None, None, -1)]

Наконец, RETURN_VALUE:

возвращается с ТОС к вызывающей функции.

Последняя инструкция возвращает результат предыдущего шага, который является обратным str_.

Резюме

Я вижу это очень быстро, и путь более быстрее, чем какое-то решение O (N), а также экономии памяти.

Фактически, обращение вспять списка путем нарезки требует большего объема памяти, чем некоторые другие методы обращения в Python. Короче говоря (и, не спуская длинной кроличьей дыры), большая накладная память возникает из-за того, что операция нарезки возвращает весь список.

Одним из альтернативных методов может быть: создание итератора с использованием reversed(), который обычно более эффективен для памяти и времени (хотя генерация списка из этого итератора занимает много времени).

Какой алгоритм использует Python в этом случае?

Чтобы сделать длинную историю Короче говоря, Python загружает переменную str, строит slice(None, None, -1) объект, реализующий str[slice(None, None, -1)] (source code), и возвращает обратную str.

источник

2016-07-04 04:06:53 Daniel

Как реализовать Python str [:: - 1]?

ответ

Резюме

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