SORU
14 Aralık 2010, Salı


Eklenecek bir dize iyi bir yolu

Verimli bir şekilde başka bir dize eklemek istiyorum.

Herhangi bir iyi yerleşik bir yöntem var mı acaba?

CEVAP
14 Aralık 2010, Salı


Sadece bir dize için bir başvuru var ve sonuna kadar başka bir dizeyi bağlamak eğer CPython Şimdi özel durumlarda bu yeri dize uzatmak için çalışır.

Sonuç itfa işlemi O(n) ' dir

örn

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

O eskiden(n^2) ama şimdi(n)

Kaynak (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;
}

Kolay yeterli deneysel olarak doğrulamak için

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

Önemli değilancak bu optimizasyonu Python spec bir parçası olmadığını unutmayın. Sadece cPython uygulama bildiğim kadarıyla. Örneğin pypy veya jython aynı ampirik test(n

$ python -m timeit -s"s=''" "for i in xrange(10):s ='a'"
1000000 loops, best of 3: 1.85 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(100):s ='a'"
10000 loops, best of 3: 16.8 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000):s ='a'"
10000 loops, best of 3: 158 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(10000):s ='a'"
1000 loops, best of 3: 1.71 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(100000):s ='a'"
10 loops, best of 3: 14.6 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000000):s ='a'"
10 loops, best of 3: 173 msec per loop
) O eski performansını gösterebilir

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

Şimdiye kadar çok iyi, ama sonra

$ pypy -m timeit -s"s=''" "for i in xrange(100000):s ='a'"
10 loops, best of 3: 12.8 sec per loop

ah kuadratik daha da kötü. Pypy iyi kısa dizeleri ile çalışır, ama kötü büyük dizeleri için gerçekleştiren bir şeyler yapıyor

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Bennythecoder

    Bennythecode

    25 Mart 2008
  • Caramthros

    Caramthros

    10 AĞUSTOS 2007
  • Top Gear

    Top Gear

    27 Mart 2006