Une bonne façon d'ajouter à une chaîne

Question

Je veux un moyen efficace d'ajouter une chaîne à l'autre.

Est-il bien intégré dans la méthode à utiliser?

Answer 1

Si vous avez seulement une référence à une chaîne et que vous concaténer une autre chaîne à la fin, Disponible maintenant des cas particuliers et essaie de prolonger la chaîne en place.

Le résultat final est que l'opération est amorti O(n)

par exemple

s = ""
for i in range(n):
    s+=str(n)

utilisé pour être en O(n^2), mais maintenant il est O(n)

À partir de la source (bytesobject.c)

void
PyBytes_ConcatAndDel(register PyObject **pv, register PyObject *w)
{
    PyBytes_Concat(pv, w);
    Py_XDECREF(w);
}


/* The following function breaks the notion that strings are immutable:
   it changes the size of a string.  We get away with this only if there
   is only one module referencing the object.  You can also think of it
   as creating a new string object and destroying the old one, only
   more efficiently.  In any case, don't use this if the string may
   already be known to some other part of the code...
   Note that if there's not enough memory to resize the string, the original
   string object at *pv is deallocated, *pv is set to NULL, an "out of
   memory" exception is set, and -1 is returned.  Else (on success) 0 is
   returned, and the value in *pv may or may not be the same as on input.
   As always, an extra byte is allocated for a trailing \0 byte (newsize
   does *not* include that), and a trailing \0 byte is stored.
*/

int
_PyBytes_Resize(PyObject **pv, Py_ssize_t newsize)
{
    register PyObject *v;
    register PyBytesObject *sv;
    v = *pv;
    if (!PyBytes_Check(v) || Py_REFCNT(v) != 1 || newsize < 0) {
        *pv = 0;
        Py_DECREF(v);
        PyErr_BadInternalCall();
        return -1;
    }
    /* XXX UNREF/NEWREF interface should be more symmetrical */
    _Py_DEC_REFTOTAL;
    _Py_ForgetReference(v);
    *pv = (PyObject *)
        PyObject_REALLOC((char *)v, PyBytesObject_SIZE + newsize);
    if (*pv == NULL) {
        PyObject_Del(v);
        PyErr_NoMemory();
        return -1;
    }
    _Py_NewReference(*pv);
    sv = (PyBytesObject *) *pv;
    Py_SIZE(sv) = newsize;
    sv->ob_sval[newsize] = '\0';
    sv->ob_shash = -1;          /* invalidate cached hash value */
    return 0;
}

Il est assez facile de vérifier empiriquement

$ python -m timeit -s"s="" "for i in xrange(10):s+='a'"
1000000 boucles, best of 3: 1.85 usec par boucle
$ python -m timeit -s"s="" "for i in xrange(100):s+='a'"
10000 boucles, best of 3: 16.8 usec par boucle
$ python -m timeit -s"s="" "for i in xrange(1000):s+='a'"
10000 boucles, best of 3: 158 usec par boucle
$ python -m timeit -s"s="" "for i in xrange(10000):s+='a'"
1000 boucles, best of 3: 1.71 msec par boucle
$ python -m timeit -s"s="" "for i in xrange(100000):s+='a'"
10 boucles, best of 3: 14.6 msec par boucle
$ python -m timeit -s"s="" "for i in xrange(1000000):s+='a'"
10 boucles, best of 3: 173 ms par boucle

Il est important cependant de noter que cette optimisation n'est pas une partie de l'Python spec. C'est seulement dans le disponible de la mise en œuvre autant que je sache. Les mêmes tests empiriques sur pypy ou jython par exemple, pourrait montrer au plus O(n**2) le rendement

$ pypy -m timeit -s"s="" "for i in xrange(10):s+='a'"
10000 boucles, best of 3: 90.8 usec par boucle
$ pypy -m timeit -s"s="" "for i in xrange(100):s+='a'"
1000 boucles, best of 3: 896 usec par boucle
$ pypy -m timeit -s"s="" "for i in xrange(1000):s+='a'"
100 boucles, best of 3: 9.03 msec par boucle
$ pypy -m timeit -s"s="" "for i in xrange(10000):s+='a'"
10 boucles, best of 3: 89.5 msec par boucle

C'est très bien, mais alors

$ pypy -m timeit -s"s="" "for i in xrange(100000):s+='a'"
10 boucles, best of 3: 12.8 s par boucle

aïe, encore pire que les quadratique. Donc, pypy est en train de faire quelque chose qui fonctionne bien avec des chaînes courtes, mais fonctionne mal pour les plus grandes chaînes

Answer 2

Ne pas prématurément optimiser. Si vous n'avez aucune raison de penser qu'il y a un goulot d'étranglement de vitesse causée par concaténations de chaîne il suffit ensuite de coller avec + et +=:

s  = 'foo'
s += 'bar'
s += 'baz'

Cela dit, si vous visez pour quelque chose comme Java StringBuilder, les canonique Python langage consiste à ajouter des éléments à une liste et ensuite utiliser str.join pour concaténer tous à la fin:

l = []
l.append('foo')
l.append('bar')
l.append('baz')

s = ''.join(l)

Answer 3

Ne le faites pas.

C'est, pour la plupart des cas, vous êtes mieux de générer l'ensemble de la chaîne de caractères en une seule fois plutôt que d'ajouter du texte à une chaîne existante.

Par exemple, ne pas faire: obj1.name + ":" + str(obj1.count)

Au lieu de cela: utiliser "%s:%d" % (obj1.name, obj1.count)

Ce sera plus facile à lire et plus efficace.

Answer 4

str1 = "Hello"
str2 = "World"
newstr = " ".join((str1, str2))

Qui se joint à str1 et str2 avec un espace comme séparateurs. Vous pouvez aussi le faire "".join(str1, str2, ...). str.join() prend un objet iterable, de sorte que vous auriez à mettre les chaînes dans une liste ou un tuple.

C'est aussi efficace qu'il obtient pour un builtin méthode.

Answer 5

Si vous avez besoin de faire beaucoup ajouter des opérations à la construction d'une grande chaîne, vous pouvez utiliser StringIO ou cStringIO. L'interface est semblable à un fichier. c'est à dire: vous write pour ajouter du texte.

Si vous êtes juste de concaténer deux chaînes de caractères, utilisez +.