[Python-checkins] r86905 - in python/branches/py3k: Misc/NEWS Objects/setobject.c

Tue Nov 30 23:23:20 CET 2010

Author: antoine.pitrou
Date: Tue Nov 30 23:23:20 2010
New Revision: 86905
Log:
Issue #8685: Speed up set difference `a - b` when source set `a` is
much larger than operand `b`. Patch by Andrew Bennetts.
Modified:
 python/branches/py3k/Misc/NEWS
 python/branches/py3k/Objects/setobject.c
Modified: python/branches/py3k/Misc/NEWS
==============================================================================

--- python/branches/py3k/Misc/NEWS	(original)
+++ python/branches/py3k/Misc/NEWS	Tue Nov 30 23:23:20 2010
@@ -10,6 +10,9 @@
 Core and Builtins
 -----------------
 
+- Issue #8685: Speed up set difference ``a - b`` when source set ``a`` is
+ much larger than operand ``b``. Patch by Andrew Bennetts.
+
 - Issue #10518: Bring back the callable() builtin.
 
 - Issue #8879. Add os.link support for Windows.
Modified: python/branches/py3k/Objects/setobject.c
==============================================================================
--- python/branches/py3k/Objects/setobject.c	(original)
+++ python/branches/py3k/Objects/setobject.c	Tue Nov 30 23:23:20 2010
@@ -1525,6 +1525,20 @@
 "Remove all elements of another set from this set.");
 
 static PyObject *
+set_copy_and_difference(PySetObject *so, PyObject *other)
+{
+ PyObject *result;
+
+ result = set_copy(so);
+ if (result == NULL)
+ return NULL;
+ if (set_difference_update_internal((PySetObject *) result, other) != -1)
+ return result;
+ Py_DECREF(result);
+ return NULL;
+}
+
+static PyObject *
 set_difference(PySetObject *so, PyObject *other)
 {
 PyObject *result;
@@ -1532,13 +1546,13 @@
 Py_ssize_t pos = 0;
 
 if (!PyAnySet_Check(other) && !PyDict_CheckExact(other)) {
- result = set_copy(so);
- if (result == NULL)
- return NULL;
- if (set_difference_update_internal((PySetObject *)result, other) != -1)
- return result;
- Py_DECREF(result);
- return NULL;
+ return set_copy_and_difference(so, other);
+ }
+
+ /* If len(so) much more than len(other), it's more efficient to simply copy
+ * so and then iterate other looking for common elements. */
+ if ((PySet_GET_SIZE(so) >> 2) > PyObject_Size(other)) {
+ return set_copy_and_difference(so, other);
 }
 
 result = make_new_set_basetype(Py_TYPE(so), NULL);
@@ -1560,6 +1574,7 @@
 return result;
 }
 
+ /* Iterate over so, checking for common elements in other. */
 while (set_next(so, &pos, &entry)) {
 int rv = set_contains_entry((PySetObject *)other, entry);
 if (rv == -1) {
