[prev in list] [next in list] [prev in thread] [next in thread] 

List:       python-dev
Subject:    [Python-Dev] First shot at some_set.get()
From:       Willi Richert <w.richert () gmx ! net>
Date:       2009-10-23 10:23:08
Message-ID: 200910231223.08470.w.richert () gmx ! net
[Download RAW message or body]

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

["setobject_get.patch" (text/x-patch)]

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/python-dev%40progressive-comp.com


[prev in list] [next in list] [prev in thread] [next in thread]