Changeset 388 for python/vendor/current/Lib/heapq.py
- Timestamp:
- Mar 19, 2014, 11:11:30 AM (11 years ago)
- File:
-
- 1 edited
-
python/vendor/current/Lib/heapq.py (modified) (15 diffs)
Legend:
- Unmodified
- Added
- Removed
-
python/vendor/current/Lib/heapq.py
r2 r388 1 # -*- coding: Latin-1 -*-1 # -*- coding: latin-1 -*- 2 2 3 3 """Heap queue algorithm (a.k.a. priority queue). … … 130 130 'nlargest', 'nsmallest', 'heappushpop'] 131 131 132 from itertools import islice, repeat, count, imap, izip, tee 133 from operator import itemgetter, neg 134 import bisect 132 from itertools import islice, count, imap, izip, tee, chain 133 from operator import itemgetter 134 135 def cmp_lt(x, y): 136 # Use __lt__ if available; otherwise, try __le__. 137 # In Py3.x, only __lt__ will be called. 138 return (x < y) if hasattr(x, '__lt__') else (not y <= x) 135 139 136 140 def heappush(heap, item): … … 168 172 def heappushpop(heap, item): 169 173 """Fast version of a heappush followed by a heappop.""" 170 if heap and heap[0] < item:174 if heap and cmp_lt(heap[0], item): 171 175 item, heap[0] = heap[0], item 172 176 _siftup(heap, 0) … … 174 178 175 179 def heapify(x): 176 """Transform list into a heap, in-place, in O(len( heap)) time."""180 """Transform list into a heap, in-place, in O(len(x)) time.""" 177 181 n = len(x) 178 182 # Transform bottom-up. The largest index there's any point to looking at … … 184 188 _siftup(x, i) 185 189 190 def _heappushpop_max(heap, item): 191 """Maxheap version of a heappush followed by a heappop.""" 192 if heap and cmp_lt(item, heap[0]): 193 item, heap[0] = heap[0], item 194 _siftup_max(heap, 0) 195 return item 196 197 def _heapify_max(x): 198 """Transform list into a maxheap, in-place, in O(len(x)) time.""" 199 n = len(x) 200 for i in reversed(range(n//2)): 201 _siftup_max(x, i) 202 186 203 def nlargest(n, iterable): 187 204 """Find the n largest elements in a dataset. … … 189 206 Equivalent to: sorted(iterable, reverse=True)[:n] 190 207 """ 208 if n < 0: 209 return [] 191 210 it = iter(iterable) 192 211 result = list(islice(it, n)) … … 205 224 Equivalent to: sorted(iterable)[:n] 206 225 """ 207 if hasattr(iterable, '__len__') and n * 10 <= len(iterable): 208 # For smaller values of n, the bisect method is faster than a minheap. 209 # It is also memory efficient, consuming only n elements of space. 210 it = iter(iterable) 211 result = sorted(islice(it, 0, n)) 212 if not result: 213 return result 214 insort = bisect.insort 215 pop = result.pop 216 los = result[-1] # los --> Largest of the nsmallest 217 for elem in it: 218 if los <= elem: 219 continue 220 insort(result, elem) 221 pop() 222 los = result[-1] 226 if n < 0: 227 return [] 228 it = iter(iterable) 229 result = list(islice(it, n)) 230 if not result: 223 231 return result 224 # An alternative approach manifests the whole iterable in memory but 225 # saves comparisons by heapifying all at once. Also, saves time 226 # over bisect.insort() which has O(n) data movement time for every 227 # insertion. Finding the n smallest of an m length iterable requires 228 # O(m) + O(n log m) comparisons. 229 h = list(iterable) 230 heapify(h) 231 return map(heappop, repeat(h, min(n, len(h)))) 232 _heapify_max(result) 233 _heappushpop = _heappushpop_max 234 for elem in it: 235 _heappushpop(result, elem) 236 result.sort() 237 return result 232 238 233 239 # 'heap' is a heap at all indices >= startpos, except possibly for pos. pos … … 241 247 parentpos = (pos - 1) >> 1 242 248 parent = heap[parentpos] 243 if newitem < parent:249 if cmp_lt(newitem, parent): 244 250 heap[pos] = parent 245 251 pos = parentpos … … 296 302 # Set childpos to index of smaller child. 297 303 rightpos = childpos + 1 298 if rightpos < endpos and not heap[childpos] < heap[rightpos]:304 if rightpos < endpos and not cmp_lt(heap[childpos], heap[rightpos]): 299 305 childpos = rightpos 300 306 # Move the smaller child up. … … 307 313 _siftdown(heap, startpos, pos) 308 314 315 def _siftdown_max(heap, startpos, pos): 316 'Maxheap variant of _siftdown' 317 newitem = heap[pos] 318 # Follow the path to the root, moving parents down until finding a place 319 # newitem fits. 320 while pos > startpos: 321 parentpos = (pos - 1) >> 1 322 parent = heap[parentpos] 323 if cmp_lt(parent, newitem): 324 heap[pos] = parent 325 pos = parentpos 326 continue 327 break 328 heap[pos] = newitem 329 330 def _siftup_max(heap, pos): 331 'Maxheap variant of _siftup' 332 endpos = len(heap) 333 startpos = pos 334 newitem = heap[pos] 335 # Bubble up the larger child until hitting a leaf. 336 childpos = 2*pos + 1 # leftmost child position 337 while childpos < endpos: 338 # Set childpos to index of larger child. 339 rightpos = childpos + 1 340 if rightpos < endpos and not cmp_lt(heap[rightpos], heap[childpos]): 341 childpos = rightpos 342 # Move the larger child up. 343 heap[pos] = heap[childpos] 344 pos = childpos 345 childpos = 2*pos + 1 346 # The leaf at pos is empty now. Put newitem there, and bubble it up 347 # to its final resting place (by sifting its parents down). 348 heap[pos] = newitem 349 _siftdown_max(heap, startpos, pos) 350 309 351 # If available, use C implementation 310 352 try: 311 from _heapq import heappush, heappop, heapify, heapreplace, nlargest, nsmallest, heappushpop353 from _heapq import * 312 354 except ImportError: 313 355 pass … … 325 367 ''' 326 368 _heappop, _heapreplace, _StopIteration = heappop, heapreplace, StopIteration 369 _len = len 327 370 328 371 h = [] … … 336 379 heapify(h) 337 380 338 while 1:381 while _len(h) > 1: 339 382 try: 340 383 while 1: 341 v, itnum, next = s = h[0] # raises IndexError when h is empty384 v, itnum, next = s = h[0] 342 385 yield v 343 386 s[0] = next() # raises StopIteration when exhausted … … 345 388 except _StopIteration: 346 389 _heappop(h) # remove empty iterator 347 except IndexError: 348 return 390 if h: 391 # fast case when only a single iterator remains 392 v, itnum, next = h[0] 393 yield v 394 for v in next.__self__: 395 yield v 349 396 350 397 # Extend the implementations of nsmallest and nlargest to use a key= argument … … 355 402 Equivalent to: sorted(iterable, key=key)[:n] 356 403 """ 404 # Short-cut for n==1 is to use min() when len(iterable)>0 405 if n == 1: 406 it = iter(iterable) 407 head = list(islice(it, 1)) 408 if not head: 409 return [] 410 if key is None: 411 return [min(chain(head, it))] 412 return [min(chain(head, it), key=key)] 413 414 # When n>=size, it's faster to use sorted() 415 try: 416 size = len(iterable) 417 except (TypeError, AttributeError): 418 pass 419 else: 420 if n >= size: 421 return sorted(iterable, key=key)[:n] 422 423 # When key is none, use simpler decoration 357 424 if key is None: 358 425 it = izip(iterable, count()) # decorate 359 426 result = _nsmallest(n, it) 360 427 return map(itemgetter(0), result) # undecorate 428 429 # General case, slowest method 361 430 in1, in2 = tee(iterable) 362 431 it = izip(imap(key, in1), count(), in2) # decorate … … 370 439 Equivalent to: sorted(iterable, key=key, reverse=True)[:n] 371 440 """ 441 442 # Short-cut for n==1 is to use max() when len(iterable)>0 443 if n == 1: 444 it = iter(iterable) 445 head = list(islice(it, 1)) 446 if not head: 447 return [] 448 if key is None: 449 return [max(chain(head, it))] 450 return [max(chain(head, it), key=key)] 451 452 # When n>=size, it's faster to use sorted() 453 try: 454 size = len(iterable) 455 except (TypeError, AttributeError): 456 pass 457 else: 458 if n >= size: 459 return sorted(iterable, key=key, reverse=True)[:n] 460 461 # When key is none, use simpler decoration 372 462 if key is None: 373 it = izip(iterable, imap(neg, count()))# decorate463 it = izip(iterable, count(0,-1)) # decorate 374 464 result = _nlargest(n, it) 375 465 return map(itemgetter(0), result) # undecorate 466 467 # General case, slowest method 376 468 in1, in2 = tee(iterable) 377 it = izip(imap(key, in1), imap(neg, count()), in2)# decorate469 it = izip(imap(key, in1), count(0,-1), in2) # decorate 378 470 result = _nlargest(n, it) 379 471 return map(itemgetter(2), result) # undecorate
Note:
See TracChangeset
for help on using the changeset viewer.
