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

Две строки Python с одинаковыми символами, a == b, может совместно использовать память, id (a) == id (b), или может быть в памяти дважды, id (a)!= id (b). Попробуйте

ab = "ab"
print id( ab ), id( "a"+"b" )

Здесь Python распознает, что вновь созданный "a" + "b" является тем же как "ab" уже в памяти - неплохо.

Теперь рассмотрим N-длинный список названий состояний [ "Аризона", "Аляска", "Аляска", "Калифорния"...] (N ~ 500000 в моем случае).
Я вижу 50 разных id() s → каждая строка "Аризона"... хранится только один раз, отлично.
НО напишите список на диск и снова прочитайте его: "тот же самый" список теперь имеет N разных идентификаторов(), больше памяти, см. ниже.

Как получилось: может ли кто-нибудь объяснить выделение строки строки Python?

""" when does Python allocate new memory for identical strings ?
    ab = "ab"
    print id( ab ), id( "a"+"b" )  # same !
    list of N names from 50 states: 50 ids, mem ~ 4N + 50S, each string once
    but list > file > mem again: N ids, mem ~ N * (4 + S)
"""

from __future__ import division
from collections import defaultdict
from copy import copy
import cPickle
import random
import sys

states = dict(
AL = "Alabama",
AK = "Alaska",
AZ = "Arizona",
AR = "Arkansas",
CA = "California",
CO = "Colorado",
CT = "Connecticut",
DE = "Delaware",
FL = "Florida",
GA = "Georgia",
)

def nid(alist):
    """ nr distinct ids """
    return "%d ids  %d pickle len" % (
        len( set( map( id, alist ))),
        len( cPickle.dumps( alist, 0 )))  # rough est ?
# cf http://stackoverflow.com/info/2117255/python-deep-getsizeof-list-with-contents

N = 10000
exec( "\n".join( sys.argv[1:] ))  # var=val ...
random.seed(1)

    # big list of random names of states --
names = []
for j in xrange(N):
    name = copy( random.choice( states.values() ))
    names.append(name)
print "%d strings in mem:  %s" % (N, nid(names) )  # 10 ids, even with copy()

    # list to a file, back again -- each string is allocated anew
joinsplit = "\n".join(names).split()  # same as > file > mem again
assert joinsplit == names
print "%d strings from a file:  %s" % (N, nid(joinsplit) )

# 10000 strings in mem:  10 ids  42149 pickle len  
# 10000 strings from a file:  10000 ids  188080 pickle len
# Python 2.6.4 mac ppc

Добавлено 25jan:
В памяти Python (или любой программы) есть два типа строк:

Установки в Ucache уникальных строк: они сохраняют память и быстро делают == b, если оба находятся в Ucache
Ostrings, остальные, которые могут храниться любое количество раз.

intern(astring) помещает вёрстка в Ucache (Alex +1); кроме того, что мы ничего не знаем о том, как Python перемещает Ostrings в Ucache - как "a" + "b" встал после "ab"? ( "Строки из файлов" бессмысленны - нет способа узнать.)
Короче говоря, Ucaches (может быть несколько) остаются мутными.

Историческая сноска: SPITBOL uniquified все строки ca. 1970.

Ответ 1

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

Так, например, несколько вхождений одного и того же строкового литерала внутри одной функции будут (во всех реализациях, которые я знаю) использовать стратегию "новая ссылка на тот же объект", потому что при построении этой функции константы-пул это довольно быстро и легко избежать дубликатов; но сделать это через отдельные функции потенциально может быть очень трудоемкой задачей, поэтому реалии реального мира либо не делают этого вообще, либо делают это только в некоторых эвристически определенных подмножествах дел, где можно надеяться на разумный компромисс между время компиляции (замедление путем поиска идентичных существующих констант) и потребление памяти (увеличивается, если сохраняются новые копии констант).

Я не знаю о какой-либо реализации Python (или, на самом деле, других языках с постоянными строками, таких как Java), которые берут на себя задачу идентифицировать возможные дубликаты (для повторного использования одного объекта через несколько ссылок) при чтении данных из файл - он просто не кажется многообещающим компромиссом (и здесь вы будете оплачивать время выполнения, а не компилировать время, поэтому компромисс еще менее привлекателен). Конечно, если вы знаете (благодаря соображениям уровня приложения), что такие неизменные объекты большие и довольно подвержены многим дублированиям, вы можете легко реализовать свою стратегию "константы-пул" (intern может помочь вам сделать это для строк, но это не сложно выполнить самостоятельно, например, кортежи с неизменяемыми элементами, огромные длинные целые числа и т.д.).

Ответ 2

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

Этот процесс обычно называется интернингом - и, действительно, выглядит эта страница, он также вызывает интернирование в Python.

Ответ 3

Замечание: очень важно знать время жизни объектов в Python. Обратите внимание на следующий сеанс:

Python 2.6.4 (r264:75706, Dec 26 2009, 01:03:10) 
[GCC 4.3.4] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> a="a"
>>> b="b"
>>> print id(a+b), id(b+a)
134898720 134898720
>>> print (a+b) is (b+a)
False

Ваше мнение, что, напечатав идентификаторы двух отдельных выражений и отметив "они равны ergo, два выражения должны быть равными/эквивалентными/одинаковыми" ошибочными. Одна строка вывода не обязательно подразумевает, что все ее содержимое было создано и/или сосуществует в один и тот же момент времени.

Если вы хотите знать, являются ли два объекта одним и тем же объектом, спросите Python напрямую (используя оператор is).

Ответ 4

x = 42
y = 42
x == y #True
x is y #True

В этом взаимодействии X и Y должны быть == (то же значение), но не является (тот же объект), потому что мы запускали два разных буквальные выражения. Потому что маленький целые числа и строки кэшируются и reused, тем не менее, говорит нам, что они ссылку на один и тот же объект.

На самом деле, если вы действительно хотите посмотреть под капотом вы всегда можете спросить Python, сколько ссылок есть к объекту с использованием getrefcountфункция в стандартном модуле sys возвращает счетчик объектов. Такое поведение отражает один из многих Python оптимизирует свою модель для скорость выполнения.

Обучение Python

Ответ 5

Я нашел хорошую статью, чтобы объяснить поведение intern CPython: http://guilload.com/python-string-interning/

Короче:

Строковый объект в CPython имеет флаг, чтобы указать, что если он в intern.
Внутренние строки, сохраняя их в обычном словаре с ключами и значениями, являются строковыми указателями. Это принимает только string класс.
Interning помогает Python уменьшить потребление памяти, потому что объекты могут ссылаться на один и тот же адрес памяти, и ускорить скорость сравнения, потому что ему нужно только сравнивать строковые указатели.
Python выполняет intern в процессе компиляции, что означает только литеральные строки (или строка может быть вычислена во время компиляции, как 'hello' + 'world')
На ваш вопрос: интернируются только строки длиной 0 или длиной 1 или содержащие только буквы ASCII (az, AZ, 0-9)
Intern в Python из-за строк являются неизменяемыми, иначе не имеет смысла.

Это действительно хорошая статья, я настоятельно рекомендую посетить его сайт и проверить другие, стоящие нашего времени.