Почему строковый len () оператор O (n) в Python? - PullRequest
Новая
       62

Почему строковый len () оператор O (n) в Python?

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

Я действительно хочу знать, как работает len (). Разве временная сложность не должна быть O (n) ?

1 Ответ

1 голос
/ 25 апреля 2020

In C strlen() является операцией O ( n ), поскольку она должна сканировать терминатор \0. Очень немногие языки используют представление C для строк. Большинство, включая Python, хранят длину в отдельном поле, поэтому ее не нужно вычислять по требованию.

См. PEP 393 для точной спецификации того, как Python хранит строки. Это сложно, потому что переключается между представлениями для экономии места, когда строки состоят только из символов ASCII, но первое поле, о котором идет речь, length. 

typedef struct {
  PyObject_HEAD
  Py_ssize_t length;                    // <--------------
  Py_hash_t hash;
  struct {
      unsigned int interned:2;
      unsigned int kind:2;
      unsigned int compact:1;
      unsigned int ascii:1;
      unsigned int ready:1;
  } state;
  wchar_t *wstr;
} PyASCIIObject;

typedef struct {
  PyASCIIObject _base;
  Py_ssize_t utf8_length;
  char *utf8;
  Py_ssize_t wstr_length;
} PyCompactUnicodeObject;

typedef struct {
  PyCompactUnicodeObject _base;
  union {
      void *any;
      Py_UCS1 *latin1;
      Py_UCS2 *ucs2;
      Py_UCS4 *ucs4;
  } data;
} PyUnicodeObject;

Поля имеют следующие интерпретации :

  • length: количество кодовых точек в строке (результат sq_length)
  • interned: внутреннее состояние (SSTATE_ *) ) как в 3.2
  • kind: форма строки
    • 00 => str не инициализируется (данные в wstr)
    • 01 => 1 байт (Latin- 1)
    • 10 => 2 байта (UCS-2)
    • 11 => 4 байта (UCS-4);
  • compact : объект использует одно из компактных представлений (подразумевает готовность)
  • ascii: объект использует представление PyASCIIObject (подразумевает компактность и готовность)
  • ready: каноническое представление готово быть доступным через PyUnicode_DATA и PyUnicode_GET_LENGTH. Это устанавливается, если объект компактен, или указатель data и length были инициализированы.
  • wstr_length, wstr: представление в wchar_t платформы (с нулевым символом в конце). Если wchar_t является 16-битным, эта форма может использовать суррогатные пары (в которых приведение wstr_length отличается от формы length). wstr_length отличается от длины только в том случае, если в представлении присутствуют суррогатные пары.
  • utf8_length, utf8: представление UTF-8 (завершается нулем).
  • data: кратчайшее представление строки Unicode. Строка имеет нулевое окончание (в соответствующем представлении).

Полный исходный код для CPython реализации строки находится на GitHub.

...