Hi,
here is the first shot to provide a faster means of retrieving an arbitrary
element from a set without removing it.
The times for
=========================
from timeit import *
stat1 = "for i in xrange(100): iter(s).next()"
stat2 = "for i in xrange(100): s.get()"
for stat in [stat1, stat2]:
t = Timer(stat, setup="s=set(range(10000))") # outside the
try/except
try:
print t.timeit(number=1000)
except:
t.print_exc()
=========================
are
stat1: 0.0451760292053
stat2: 0.0148510932922
The patch is attached. Feel free to criticize.
I would love to see something like that in the standard Python interpreter.
Regards,
wr
Index: Objects/setobject.c
===================================================================
--- Objects/setobject.c (Revision 75593)
+++ Objects/setobject.c (Arbeitskopie)
@@ -757,6 +757,49 @@
PyDoc_STRVAR(pop_doc, "Remove and return an arbitrary set element.\n\
Raises KeyError if the set is empty.");
+static PyObject *
+set_get(PySetObject *so)
+{
+ register Py_ssize_t i = 0;
+ register setentry *entry;
+ PyObject *key;
+
+ assert (PyAnySet_Check(so));
+ if (so->used == 0) {
+ PyErr_SetString(PyExc_KeyError, "get from an empty set");
+ return NULL;
+ }
+
+ /* Set entry to "the first" unused or dummy set entry. We abuse
+ * the hash field of slot 0 to hold a search finger:
+ * If slot 0 has a value, use slot 0.
+ * Else slot 0 is being used to hold a search finger,
+ * and we use its hash value as the first index to look.
+ */
+ entry = &so->table[0];
+ if (entry->key == NULL || entry->key == dummy) {
+ i = entry->hash;
+ /* The hash field may be a real hash value, or it may be a
+ * legit search finger, or it may be a once-legit search
+ * finger that's out of bounds now because it wrapped around
+ * or the table shrunk -- simply make sure it's in bounds now.
+ */
+ if (i > so->mask || i < 1)
+ i = 1; /* skip slot 0 */
+ while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
+ i++;
+ if (i > so->mask)
+ i = 1;
+ }
+ }
+ key = entry->key;
+ Py_INCREF(key);
+ return key;
+}
+
+PyDoc_STRVAR(get_doc, "Return an arbitrary set element without removing it.\n\
+Raises KeyError if the set is empty.");
+
static int
set_traverse(PySetObject *so, visitproc visit, void *arg)
{
@@ -2043,6 +2086,8 @@
issuperset_doc},
{"pop", (PyCFunction)set_pop, METH_NOARGS,
pop_doc},
+ {"get", (PyCFunction)set_get, METH_NOARGS,
+ get_doc},
{"__reduce__", (PyCFunction)set_reduce, METH_NOARGS,
reduce_doc},
{"remove", (PyCFunction)set_remove, METH_O,
@@ -2355,6 +2400,16 @@
return set_pop((PySetObject *)set);
}
+PyObject *
+PySet_Get(PyObject *set)
+{
+ if (!PySet_Check(set)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ return set_get((PySetObject *)set);
+}
+
int
_PySet_Update(PyObject *set, PyObject *iterable)
{
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
