Python listesinin iç yayınları, erişim ve yeniden boyutlandırma çalışma zamanları

Question

Python'un [] listesi veya dizisi var mı?
Dizin O (1) erişim zamanı bir dizi veya O (n) bir liste gibi mi?
O (1) bir liste veya O (n) gibi bir dizi gibi ekleme/yeniden boyutlandırma veya erişim ve yeniden boyutlandırma için O (1) yönetebilen bir melez mi? Dizi erişimi Python'da gerçekten yavaş olan read here . Ancak, bir sözlük (Python'un sözlüğü gerçekten hızlı olması için varsayalım) kullanarak bir yinelemeli fibonacci prosedürün bir hatırlatılmış bir sürümünü yazdığımda, onlar eşit zamanları vardı. Bu neden?

Bir Python programı, bir python listesinden daha hızlı erişim süresine sahip midir?

Answer 1

Python en [] bir dizide değil, bir bağlantılı liste olarak uygulanmaktadır. Yeniden boyutlandırma O (n) olmasına rağmen, eksi O (1) amortize edilir, çünkü yeniden boyutlandırmalar çok nadiren gerçekleşir. Bunun nasıl çalıştığını bilmiyorsanız, bu Wikipedia entry on dynamic arrays'u okuyun. Python'un listesi her seferinde 2 kat artmaz, bundan biraz daha karmaşıktır, ancak genişletmeler hala eklenmiş Oortifikasyonu yapmak için tasarlanmıştır (1). n ürün taşınması gerekir, çünkü orta takma

Ancak, her zaman için etkisiz bir O (n) 'dir.

Tuplelar listeden daha hızlı değil - yalnızca başlık (*) altındaki değişmez listelerdir.

Sözlük testinizle ilgili olarak: tam uygulamanıza bağlı olarak, bir listedeki önbelleğe alma bir dikte ile olduğundan daha hızlı olacaktır. Ancak, Python'un dikteleri son derece optimize edildi ve özellikle küçük miktarlarda tuşlar harika performans gösterecek.

PyObject * 
PyList_GetItem(PyObject *op, Py_ssize_t i) 
{ 
    if (!PyList_Check(op)) { 
     PyErr_BadInternalCall(); 
     return NULL; 
    } 
    if (i < 0 || i >= Py_SIZE(op)) { 
     if (indexerr == NULL) 
      indexerr = PyString_FromString(
       "list index out of range"); 
     PyErr_SetObject(PyExc_IndexError, indexerr); 
     return NULL; 
    } 
    return ((PyListObject *)op) -> ob_item[i]; 
} 

Ve bu tuple en geçerli::

PyObject * 
PyTuple_GetItem(register PyObject *op, register Py_ssize_t i) 
{ 
    if (!PyTuple_Check(op)) { 
     PyErr_BadInternalCall(); 
     return NULL; 
    } 
    if (i < 0 || i >= Py_SIZE(op)) { 
     PyErr_SetString(PyExc_IndexError, "tuple index out of range"); 
     return NULL; 
    } 
    return ((PyTupleObject *)op) -> ob_item[i]; 
} 

Gördüğünüz gibi, bunlar'

---

(*) İşte liste en Python 2.6 C fonksiyonunu "öğe olsun" var neredeyse tamamen aynı. Sonunda, bazı tür ve sınır kontrolünden sonra, bir indeksle basit bir işaretçi erişimi.

[Referans: Python documentation on Time Complexity for data type operations]

Answer 2

piton veri türlerinin zaman karmaşıklığını özetleyen büyük bir liste here yoktur. Durumunuzda eşya alımı O (1) zaman olmalıdır.

Answer 3

Tuples listelerine göre hızlıdır. Temel uygulamayı bilmiyorum. Bunu bir noktada 'Python'a Dalış' bölümünde okudum :) İlgili alıntı:

"Tupler, listelerinden daha hızlıdır. Eğer sabit bir değerler kümesini tanımlarsanız ve bununla yapacağınız tek şey bunun üzerinden yinelenir, bir liste yerine bir tuple kullanın. "

Answer 4

Python'un liste Java ArrayList karşılaştırılabilir. Listeden ve listeden bir öğe almak için access time, O(1) olmalıdır.Norvig'in makalesinde, Python'un listesinin, Java'daki Vector veya Lisp'de Ayarlanabilir Array ile karşılaştırılabilir olduğuna ve gerçekten daha fazla alana ihtiyacınız olduğuna, ancak erişim süresinin O(1) olduğuna dikkat çekilmektedir.