2010-01-23 12 views
29

Dos cadenas de Python con los mismos caracteres, a == b, pueden compartir memoria, id (a) == id (b), o pueden estar en la memoria dos veces, id (a)! = Id (b). Trate ¿Cuándo asigna Python nueva memoria para cadenas idénticas?

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

Aquí Python reconoce que la recién creada "a" + "b" es la misma como el "ab" ya en la memoria - no está mal.

Considere ahora una lista N-larga de nombres de estado ["Arizona", "Alaska", "Alaska", "California" ...] (N ~ 500000 en mi caso).
Veo 50 ID diferentes() s ⇒ cada cadena "Arizona" ... se almacena solo una vez, bien.
PERO escribe la lista en el disco y la vuelves a leer: la "misma" lista ahora tiene N id diferentes() s, forma más memoria, mira a continuación.

¿Cómo puede alguien explicar la asignación de memoria de cadena de 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/questions/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 

Agregado 25jan:
Hay dos tipos de cadenas en la memoria de Python (o cualquier programa de):

  • Ustrings, en un Ucache de cadenas únicas: éstos ahorra memoria y hacen a = = b rápido si ambos están en Ucache
  • Ostrings, los demás, que se pueden almacenar cualquier cantidad de veces.

intern(astring) pone astring en el Ucache (Alex +1); aparte de eso, no sabemos nada sobre cómo Python mueve los Ostrings al Ucache - ¿cómo entró "a" + "b", después de "ab"? ("Cadenas de archivos" no tiene sentido, no hay forma de saberlo)
En resumen, los Ucaches (puede haber varios) permanecen turbios.

Una nota al pie de página histórica: SPITBOL uniquified all strings ca. 1970.

Respuesta

36

Cada aplicación del lenguaje Python es libre de tomar sus propias ventajas y desventajas en la asignación de los objetos inmutables (como cadenas) - o bien hacer una nueva, o encontrar uno igual existentes y utilizando una referencia más a él, están bien desde el punto de vista del lenguaje.En la práctica, por supuesto, la implementación en el mundo real logra un compromiso razonable: una referencia más a un objeto existente adecuado al ubicar tal objeto es barato y fácil, solo haga un nuevo objeto si la tarea de localizar uno existente adecuado (que puede o puede no existir) parece que podría llevar mucho tiempo buscando.

Así, por ejemplo, múltiples apariciones del mismo literal de cadena dentro de una función única (en todas las implementaciones que conozco) utilizan la estrategia de "nueva referencia al mismo objeto", porque al construir el pool de constantes de esa función es bastante rápido y fácil de evitar duplicados; pero hacerlo a través de funciones separadas podría ser una tarea que consume mucho tiempo, por lo que las implementaciones del mundo real o no lo hacen en absoluto, o solo lo hacen en algunos subconjuntos identificados heurísticamente donde uno puede esperar una razonable compensación del tiempo de compilación (ralentizado buscando las constantes existentes idénticas) frente al consumo de memoria (aumentado si se siguen haciendo nuevas copias de las constantes).

No conozco ninguna implementación de Python (o para otros idiomas con cadenas constantes, como Java) que toma la molestia de identificar posibles duplicados (para reutilizar un único objeto a través de referencias múltiples) al leer datos desde un archivo - simplemente no parece ser una compensación prometedora (y aquí estarías pagando runtime, no compilando tiempo, por lo que la compensación es aún menos atractiva). Por supuesto, si sabe (gracias a consideraciones de nivel de aplicación) que tales objetos inmutables son grandes y bastante propensos a muchas duplicaciones, puede implementar su propia estrategia de "grupo de constantes" con bastante facilidad (intern puede ayudarlo a hacer cadenas, pero no es difícil lanzar el suyo propio, por ejemplo, tuplas con elementos inmutables, números enteros largos enormes, etc.).

+0

¿Hay algo de valor en mi respuesta que no piense que está cubierto en el suyo? Si no, borraré mi respuesta. Si la hay, ¿quieres editarla en la tuya y * entonces * borraré mi respuesta? –

+0

+1 por mencionar 'interno'. Había olvidado por completo que esta función existía. Usar 'joinsplit = [interno (n) para n en" \ n ".join (nombres) .split()]' hizo el trabajo y redujo el uso de memoria de 4,374,528 a 3,190,783 en mi MacBook. –

+0

@John, creo que tener los dos puntos de vista (el mío desde una "perspectiva interna", el tuyo de un programador experimentado sin una "perspectiva privilegiada" especial en Python) es valioso tal como está: no estoy seguro de que haya una forma óptima de obtener el la misma "triangulación" dentro de una sola respuesta! –

16

tengo la fuerte sospecha de que Python está comportando como muchos otros idiomas aquí - reconociendo constantes de cadena dentro de su código fuente y el uso de una mesa común para las personas, pero no aplicando las mismas reglas al crear cadenas de forma dinámica. Esto tiene sentido ya que solo habrá un conjunto finito de cadenas dentro de su código fuente (aunque Python le permite evaluar el código de forma dinámica, por supuesto), mientras que es mucho más probable que esté creando un gran número de cadenas en el curso de su programa. .

Este proceso generalmente se llama interna - y, de hecho, por el aspecto de this page se llama interning en Python, también.

+0

¿Alguna idea de por qué id ("ab") == id ("a" + "b")? ¿Estás de acuerdo con que no sabemos cómo funciona Python con Ucaches? – denis

+3

Para completar: la expresión '" a "+" b "' se convierte estáticamente en la expresión '" ab "', que luego se encuentra que es la misma cadena que la otra. Todo sucede en tiempo de compilación. –

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

En esta interacción, X e Y debe ser == (mismo valor), pero no es (mismo objeto) porque nos encontramos con dos expresiones literales diferentes. Porque pequeños números enteros y cadenas están en caché y reutilizados, sin embargo, nos dice que hacen referencia al mismo objeto.

De hecho, si realmente quiere mirar bajo el capó, siempre se puede pedir Python cuántas referencias hay a un objeto utilizando la getrefcount función en el módulo sys estándar devuelve la referencia del objeto contar. Este comportamiento refleja una de las muchas formas en que Python optimiza su modelo para la velocidad de ejecución de .

Learning Python

10

Una nota al margen: es muy importante conocer la vida de los objetos en Python. Tenga en cuenta la siguiente sesión:

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 

su pensamiento mediante la impresión de que los ID de dos expresiones separadas y observando “son iguales ergo las dos expresiones deben ser iguales/eq/el mismo” es defectuosa. Una sola línea de salida no implica necesariamente que todos sus contenidos se hayan creado y/o coexistido en el mismo momento.

Si desea saber si dos objetos son el mismo objeto, pregúntele a Python directamente (usando el operador is).

+5

Un poco de explicación sobre lo que está sucediendo aquí: la línea 'print id (a + b), id (b + a)' primero concatena "a" y "b" en una cadena "ab" recién asignada, luego pasa eso a 'id', luego lo desasigna porque ya no es necesario. Entonces "ba" se asigna de la misma manera, y termina siendo asignado en la misma ubicación en la memoria (CPython tiene la costumbre de hacer esto). "ba" se pasa a 'id', que devuelve el mismo resultado. Sin embargo, con la línea siguiente, tanto "ab" como "ba" se guardan para pasar al operador 'is', por lo que se asignan necesariamente en diferentes posiciones. – javawizard

Cuestiones relacionadas