summaryrefslogtreecommitdiffstats
path: root/Objects/listobject.c
Commit message (Collapse)AuthorAgeFilesLines
* complete backout of listobject.c v2.171Andrew MacIntyre2003-12-281-4/+0
|
* Revert previous two checkins to repair test failure.Jeremy Hylton2003-12-261-24/+6
| | | | | | The special-case code that was removed could return a value indicating success but leave an exception set. test_fileinput failed in a debug build as a result.
* use the correct macro to access list sizeAndrew MacIntyre2003-12-261-1/+1
|
* Performance of list([]) in 2.3 came up in a thread on comp.lang.python,Andrew MacIntyre2003-12-251-6/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | which can be reviewed via http://coding.derkeiler.com/Archive/Python/comp.lang.python/2003-12/1011.html Duncan Booth investigated, and discovered that an "optimisation" was in fact a pessimisation for small numbers of elements in a source list, compared to not having the optimisation, although with large numbers of elements in the source list the optimisation was quite beneficial. He posted his change to comp.lang.python (but not to SF). Further research has confirmed his assessment that the optimisation only becomes a net win when the source list has more than 100 elements. I also found that the optimisation could apply to tuples as well, but the gains only arrive with source tuples larger than about 320 elements and are nowhere near as significant as the gains with lists, (~95% gain @ 10000 elements for lists, ~20% gain @ 10000 elements for tuples) so I haven't proceeded with this. The code as it was applied the optimisation to list subclasses as well, and this also appears to be a net loss for all reasonable sized sources (~80-100% for up to 100 elements, ~20% for more than 500 elements; I tested up to 10000 elements). Duncan also suggested special casing empty lists, which I've extended to all empty sequences. On the basis that list_fill() is only ever called with a list for the result argument, testing for the source being the destination has now happens before testing source types.
* Guido grants a Christmas wish:Raymond Hettinger2003-12-171-37/+0
| | | | sorted() becomes a regular function instead of a classmethod.
* * Added a new method flag, METH_COEXIST.Raymond Hettinger2003-12-131-0/+5
| | | | | * Used the flag to optimize set.__contains__(), dict.__contains__(), dict.__getitem__(), and list.__getitem__().
* Fix memory error treatment correctly. Going to dsu_fail causesHye-Shik Chang2003-12-101-1/+1
| | | | | deallocating garbage pointers; saved_ob_item and empty_ob_item. (Reviewed by Raymond Hettinger)
* Fixes and tests for various "holding pointers when arbitrary Python codeMichael W. Hudson2003-12-041-35/+46
| | | | | | can run" bugs as discussed in [ 848856 ] couple of new list.sort bugs
* Make sure the list.sort's decorate step unwinds itself before returningRaymond Hettinger2003-11-281-2/+9
| | | | | an exception raised by the key function. (Suggested by Michael Hudson.)
* Improve the reverse list iterator to free memory as soon as the iteratorRaymond Hettinger2003-11-081-1/+4
| | | | is exhausted.
* Minor code fixup. Make sure that len reflects the current list size.Raymond Hettinger2003-11-081-0/+1
|
* Optimize reversed(list) using a custom iterator.Raymond Hettinger2003-11-071-2/+96
|
* Fix compiler warning about possible use of n without assignment.Jeremy Hylton2003-11-031-5/+6
| | | | Also fix use of n for two different variables in two different blocks.
* Add list.sorted() classmethod.Raymond Hettinger2003-10-291-0/+37
|
* Fix typo found by Neal Norwitz.Raymond Hettinger2003-10-161-1/+1
|
* * list.sort() now supports three keyword arguments: cmp, key, and reverse.Raymond Hettinger2003-10-161-5/+228
| | | | | | | key provides C support for the decorate-sort-undecorate pattern. reverse provide a stable sort of the list with the comparisions reversed. * Amended the docs to guarantee sort stability.
* My last fix left n used unitialized in tha a==b case.Michael W. Hudson2003-08-151-1/+1
| | | | | | Fix, by not using n at all in that case. Needs to be applied to release23-maint, too.
* Fix reference leak noted in test_types:Michael W. Hudson2003-08-141-9/+9
| | | | | | Check for a[:] = a _before_ calling PySequence_Fast on a. release23-maint candidate Reference leak doesn't happen with head of release22-maint.
* Use _PyEval_SliceIndex to handle list.index() calls withWalter Dörwald2003-06-171-1/+3
| | | | huge start and stop arguments. Add tests.
* Fix sloppy index() implementation:Guido van Rossum2003-06-171-2/+12
| | | | | - don't use min() and max() - interpret negative start/stop argument like negative slice indices
* SF #754014: list.index() should accept optional start, end argumentsRaymond Hettinger2003-06-171-5/+10
| | | | Also, modified UserList.index() to match and expanded the related tests.
* SF bug #604716: faster [None]*n or []*nRaymond Hettinger2003-05-211-0/+12
| | | | Fulfilled request to special case repetitions of lists of length 0 or 1.
* SF bug #730296: Unexpected Changes in list IteratorRaymond Hettinger2003-05-071-2/+0
| | | | | | | | | | | | Reverted a Py2.3b1 change to iterator in subclasses of list and tuple. They had been changed to use __getitem__ whenever it had been overriden in the subclass. This caused some usabilty and performance problems. Also, it was inconsistent with the rest of python where many container methods access the underlying object directly without first checking for an overridden getter. Users needing a change in iterator behavior should override it directly.
* Patch #708604: Check more function results. Will backport to 2.2.Martin v. Löwis2003-05-031-1/+8
|
* Squashed new compiler wngs about trying to compare pointers toTim Peters2003-04-241-1/+1
| | | | functions with different signatures.
* SF bug 665835: filter() treatment of str and tuple inconsistentRaymond Hettinger2003-04-241-0/+2
| | | | | | | | As a side issue on this bug, it was noted that list and tuple iterators used macros to directly access containers and would not recognize __getitem__ overrides. If the method is overridden, the patch returns a generic sequence iterator which calls the __getitem__ method; otherwise, it returns a high custom iterator with direct access to container elements.
* - list.insert(i, x) now interprets negative i as it would beGuido van Rossum2003-04-141-2/+5
| | | | | | interpreted by slicing, so negative values count from the end of the list. This was the only place where such an interpretation was not placed on a list index.
* Renamed PyObject_GenericGetIter to PyObject_SelfIterRaymond Hettinger2003-03-171-1/+1
| | | | | | to more accurately describe what the function does. Suggested by Thomas Wouters.
* Created PyObject_GenericGetIter().Raymond Hettinger2003-03-171-9/+1
| | | | Factors out the common case of returning self.
* Allow list sort's comparison function to explicitly be None. See SF patchSkip Montanaro2003-01-021-1/+4
| | | | 661092.
* SF patch #659536: Use PyArg_UnpackTuple where possible.Raymond Hettinger2002-12-291-1/+1
| | | | | | | Obtain cleaner coding and a system wide performance boost by using the fast, pre-parsed PyArg_Unpack function instead of PyArg_ParseTuple function which is driven by a format string.
* SF Bug 645777: list.extend() works with any iterable and is no longerRaymond Hettinger2002-12-291-1/+1
| | | | experimental.
* The final tweaks before closingMichael W. Hudson2002-12-051-20/+23
| | | | | | [ 633152 ] list slice ass ignores subtypes of list Allow arbitrary sequences on the RHS of extended slices.
* SF patch 637176: list.sort crasherTim Peters2002-11-121-96/+29
| | | | | | | | | | | Armin Rigo's Draconian but effective fix for SF bug 453523: list.sort crasher slightly fiddled to catch more cases of list mutation. The dreaded internal "immutable list type" is gone! OTOH, if you look at a list *while* it's being sorted now, it will appear to be empty. Better than a core dump.
* Use PyOS_snprintf() instead of sprintf and wrap the long lineNeal Norwitz2002-11-051-2/+4
|
* This is Alex Martelli's patchMichael W. Hudson2002-11-051-9/+12
| | | | | | [ 633870 ] allow any seq assignment to a list slice plus a very silly little test case of my own.
* Darn! Don't divide by zero. Bad fix. :-)Guido van Rossum2002-10-111-1/+1
|
* Add checks for size overflow on list*n, list+list, tuple+tuple.Guido van Rossum2002-10-111-0/+4
| | | | Will backport.
* PyObject_RichCompareBool() already returns -1, 0, or 1, so return its valueNeal Norwitz2002-09-051-5/+1
|
* Micro-optimization for list_contains. Factored double if testRaymond Hettinger2002-09-051-8/+7
| | | | out of the loop.
* 1. Combined the base and length arrays into a single array of structs.Tim Peters2002-08-101-30/+54
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is friendlier for caches. 2. Cut MIN_GALLOP to 7, but added a per-sort min_gallop vrbl that adapts the "get into galloping mode" threshold higher when galloping isn't paying, and lower when it is. There's no known case where this hurts. It's (of course) neutral for /sort, \sort and =sort. It also happens to be neutral for !sort. It cuts a tiny # of compares in 3sort and +sort. For *sort, it reduces the # of compares to better than what this used to do when MIN_GALLOP was hardcoded to 10 (it did about 0.1% more *sort compares before, but given how close we are to the limit, this is "a lot"!). %sort used to do about 1.5% more compares, and ~sort about 3.6% more. Here are exact counts: i *sort 3sort +sort %sort ~sort !sort 15 449235 33019 33016 51328 188720 65534 before 448885 33016 33007 50426 182083 65534 after 0.08% 0.01% 0.03% 1.79% 3.65% 0.00% %ch from after 16 963714 65824 65809 103409 377634 131070 962991 65821 65808 101667 364341 131070 0.08% 0.00% 0.00% 1.71% 3.65% 0.00% 17 2059092 131413 131362 209130 755476 262142 2057533 131410 131361 206193 728871 262142 0.08% 0.00% 0.00% 1.42% 3.65% 0.00% 18 4380687 262440 262460 421998 1511174 524286 4377402 262437 262459 416347 1457945 524286 0.08% 0.00% 0.00% 1.36% 3.65% 0.00% 19 9285709 524581 524634 848590 3022584 1048574 9278734 524580 524633 837947 2916107 1048574 0.08% 0.00% 0.00% 1.27% 3.65% 0.00% 20 19621118 1048960 1048942 1715806 6045418 2097150 19606028 1048958 1048941 1694896 5832445 2097150 0.08% 0.00% 0.00% 1.23% 3.65% 0.00% 3. Added some key asserts I overlooked before. 4. Updated the doc file.
* PyList_Reverse(): This was leaking a reference to Py_None on every call.Tim Peters2002-08-081-1/+4
| | | | | I believe I introduced this bug when I refactored the reversal code so that the mergesort could use it too. It's not a problem on the 2.2 branch.
* Sped the usual case for sorting by calling PyObject_RichCompareBoolTim Peters2002-08-041-10/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | directly when no comparison function is specified. This saves a layer of function call on every compare then. Measured speedups: i 2**i *sort \sort /sort 3sort +sort %sort ~sort =sort !sort 15 32768 12.5% 0.0% 0.0% 100.0% 0.0% 50.0% 100.0% 100.0% -50.0% 16 65536 8.7% 0.0% 0.0% 0.0% 0.0% 0.0% 12.5% 0.0% 0.0% 17 131072 8.0% 25.0% 0.0% 25.0% 0.0% 14.3% 5.9% 0.0% 0.0% 18 262144 6.3% -10.0% 12.5% 11.1% 0.0% 6.3% 5.6% 12.5% 0.0% 19 524288 5.3% 5.9% 0.0% 5.6% 0.0% 5.9% 5.4% 0.0% 2.9% 20 1048576 5.3% 2.9% 2.9% 5.1% 2.8% 1.3% 5.9% 2.9% 4.2% The best indicators are those that take significant time (larger i), and where sort doesn't do very few compares (so *sort and ~sort benefit most reliably). The large numbers are due to roundoff noise combined with platform variability; e.g., the 14.3% speedup for %sort at i=17 reflects a printed elapsed time of 0.18 seconds falling to 0.17, but a change in the last digit isn't really meaningful (indeed, if it really took 0.175 seconds, one electron having a lazy nanosecond could shift it to either value <wink>). Similarly the 25% at 3sort i=17 was a meaningless change from 0.05 to 0.04. However, almost all the "meaningless changes" were in the same direction, which is good. The before-and-after times for *sort are clearest: before after 0.18 0.16 0.25 0.23 0.54 0.50 1.18 1.11 2.57 2.44 5.58 5.30
* SF bug 590366: Small typo in listsort:ParseTupleTim Peters2002-08-031-1/+1
| | | | The PyArg_ParseTuple() error string still said "msort". Changed to "sort".
* Replaced samplesort with a stable, adaptive mergesort.Tim Peters2002-08-011-406/+772
|
* Fix forMichael W. Hudson2002-07-291-3/+8
| | | | | | [ 587875 ] crash on deleting extended slice The array code got simpler, always a good thing!
* Patch #574867: Correct list.extend docstring.Martin v. Löwis2002-07-281-1/+1
|
* More sort cleanup: Moved the special cases from samplesortslice intoTim Peters2002-07-191-65/+73
| | | | | | | | | | | listsort. If the former calls itself recursively, they're a waste of time, since it's called on a random permutation of a random subset of elements. OTOH, for exactly the same reason, they're an immeasurably small waste of time (the odds of finding exploitable order in a random permutation are ~= 0, so the special-case loops looking for order give up quickly). The point is more for conceptual clarity. Also changed some "assert comments" into real asserts; when this code was first written, Python.h didn't supply assert.h.
* binarysort() cleanup: Documented the key invariants, explained why theyTim Peters2002-07-191-2/+13
| | | | imply this is a stable sort, and added some asserts.
* listreverse(): Don't call the new reverse_slice unless the listTim Peters2002-07-191-1/+2
| | | | has something in it (else ob_item may be a NULL pointer).
generated by cgit v0.12 at 2025-01-25 19:07:28 (GMT)