From 1021c44b413ebe264a6187322447ac296a0a18a7 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Fri, 7 Nov 2003 15:38:09 +0000 Subject: Optimize reversed(list) using a custom iterator. --- Objects/enumobject.c | 4 +-- Objects/listobject.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 98 insertions(+), 4 deletions(-) diff --git a/Objects/enumobject.c b/Objects/enumobject.c index 998e381..8b2e6e1 100644 --- a/Objects/enumobject.c +++ b/Objects/enumobject.c @@ -174,8 +174,8 @@ reversed_new(PyTypeObject *type, PyObject *args, PyObject *kwds) if (!PyArg_UnpackTuple(args, "reversed", 1, 1, &seq)) return NULL; - /* Special case optimization for xrange */ - if (PyRange_Check(seq)) + /* Special case optimization for xrange and lists */ + if (PyRange_Check(seq) || PyList_Check(seq)) return PyObject_CallMethod(seq, "__reversed__", NULL); if (!PySequence_Check(seq)) { diff --git a/Objects/listobject.c b/Objects/listobject.c index fd98b63..cf00ab2 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -2349,6 +2349,11 @@ list_nohash(PyObject *self) return -1; } +static PyObject *list_iter(PyObject *seq); +static PyObject *list_reversed(PyListObject* seq, PyObject* unused); + +PyDoc_STRVAR(reversed_doc, +"L.__reversed__() -- return a reverse iterator over the list"); PyDoc_STRVAR(append_doc, "L.append(object) -- append object to end"); PyDoc_STRVAR(extend_doc, @@ -2373,6 +2378,7 @@ PyDoc_STRVAR(sorted_doc, cmp(x, y) -> -1, 0, 1"); static PyMethodDef list_methods[] = { + {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc}, {"append", (PyCFunction)listappend, METH_O, append_doc}, {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc}, {"extend", (PyCFunction)listextend, METH_O, extend_doc}, @@ -2404,8 +2410,6 @@ PyDoc_STRVAR(list_doc, "list() -> new list\n" "list(sequence) -> new list initialized from sequence's items"); -static PyObject *list_iter(PyObject *seq); - static PyObject * list_subscript(PyListObject* self, PyObject* item) { @@ -2760,3 +2764,93 @@ PyTypeObject PyListIter_Type = { 0, /* tp_descr_get */ 0, /* tp_descr_set */ }; + +/*********************** List Reverse Iterator **************************/ + +typedef struct { + PyObject_HEAD + long it_index; + PyListObject *it_seq; +} listreviterobject; + +PyTypeObject PyListRevIter_Type; + +static PyObject * +list_reversed(PyListObject *seq, PyObject *unused) +{ + listreviterobject *it; + + it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type); + if (it == NULL) + return NULL; + assert(PyList_Check(seq)); + it->it_index = PyList_GET_SIZE(seq) - 1; + Py_INCREF(seq); + it->it_seq = seq; + PyObject_GC_Track(it); + return (PyObject *)it; +} + +static void +listreviter_dealloc(listreviterobject *it) +{ + PyObject_GC_UnTrack(it); + Py_XDECREF(it->it_seq); + PyObject_GC_Del(it); +} + +static int +listreviter_traverse(listreviterobject *it, visitproc visit, void *arg) +{ + if (it->it_seq == NULL) + return 0; + return visit((PyObject *)it->it_seq, arg); +} + +static PyObject * +listreviter_next(listreviterobject *it) +{ + PyObject *item = NULL; + + assert(PyList_Check(it->it_seq)); + if (it->it_index >= 0) { + assert(it->it_index < PyList_GET_SIZE(it->it_seq)); + item = PyList_GET_ITEM(it->it_seq, it->it_index); + it->it_index--; + Py_INCREF(item); + } + return item; +} + +PyTypeObject PyListRevIter_Type = { + PyObject_HEAD_INIT(&PyType_Type) + 0, /* ob_size */ + "listreverseiterator", /* tp_name */ + sizeof(listreviterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)listreviter_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ + 0, /* tp_doc */ + (traverseproc)listreviter_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + PyObject_SelfIter, /* tp_iter */ + (iternextfunc)listreviter_next, /* tp_iternext */ + 0, +}; -- cgit v0.12