Mercurial > hg
comparison mercurial/hbisect.py @ 16803:107a3270a24a
cleanup: use the deque type where appropriate
There have been quite a few places where we pop elements off the
front of a list. This can turn O(n) algorithms into something more
like O(n**2). Python has provided a deque type that can do this
efficiently since at least 2.4.
As an example of the difference a deque can make, it improves
perfancestors performance on a Linux repo from 0.50 seconds to 0.36.
author | Bryan O'Sullivan <bryano@fb.com> |
---|---|
date | Tue, 15 May 2012 10:46:23 -0700 |
parents | 14913fcb30c6 |
children | cafd8a8fb713 |
comparison
equal
deleted
inserted
replaced
16802:7e5d94381cd1 | 16803:107a3270a24a |
---|---|
9 # GNU General Public License version 2 or any later version. | 9 # GNU General Public License version 2 or any later version. |
10 | 10 |
11 import os, error | 11 import os, error |
12 from i18n import _ | 12 from i18n import _ |
13 from node import short, hex | 13 from node import short, hex |
14 import util | 14 import collections, util |
15 | 15 |
16 def bisect(changelog, state): | 16 def bisect(changelog, state): |
17 """find the next node (if any) for testing during a bisect search. | 17 """find the next node (if any) for testing during a bisect search. |
18 returns a (nodes, number, good) tuple. | 18 returns a (nodes, number, good) tuple. |
19 | 19 |
67 raise util.Abort(_("inconsistent state, %s:%s is good and bad") | 67 raise util.Abort(_("inconsistent state, %s:%s is good and bad") |
68 % (badrev, short(bad))) | 68 % (badrev, short(bad))) |
69 | 69 |
70 # build children dict | 70 # build children dict |
71 children = {} | 71 children = {} |
72 visit = [badrev] | 72 visit = collections.deque([badrev]) |
73 candidates = [] | 73 candidates = [] |
74 while visit: | 74 while visit: |
75 rev = visit.pop(0) | 75 rev = visit.popleft() |
76 if ancestors[rev] == []: | 76 if ancestors[rev] == []: |
77 candidates.append(rev) | 77 candidates.append(rev) |
78 for prev in clparents(rev): | 78 for prev in clparents(rev): |
79 if prev != -1: | 79 if prev != -1: |
80 if prev in children: | 80 if prev in children: |