In article <itgi3801...@news2.newsguy.com> I wrote, in part: >>Appending to the list is much faster, and if you are going to >>dump a set of new items in, you can do that with: [...]
In article <mailman.96.1308348643.1164.python-l...@python.org> Ethan Furman <et...@stoneleaf.us> wrote: >> a.append(large_list) > ^- should be a.extend(large_list) Er, right. Posted in haste (had to get out the door). I also wrote: >> If len(large_list) is m, this is O(m). Inserting each item in >> the "right place" would be O(m log (n + m)). But we still >> have to sort: >> >> a.sort() In article <mailman.98.1308353648.1164.python-l...@python.org>, Ian Kelly <ian.g.ke...@gmail.com> wrote: >> This is O(log (n + m)), hence likely better than repeatedly inserting >> in the correct place. >Surely you mean O((n + m) log (n + m)). Er, "maybe"? (It depends on the relative values of m and n, and the underlying sort algorithm to some extent. Some algorithms are better at inserting a relatively small number of items into a mostly-sorted large list. As I recall, Shell sort does well with this.) But generally, yes. See "posted in haste" above. :-) There are a lot of other options, such as sorting just the list of "items to be inserted", which lets you do a single merge pass: # UNTESTED def merge_sorted(it1, it2, must_copy = True): """ Merge two sorted lists/iterators it1 and it2. Roughly equivalent to sorted(list(it2) + list(it2)), except for attempts to be space-efficient. You can provide must_copy = False if the two iterators are already lists and can be destroyed for the purpose of creating the result. """ # If it1 and it1 are deque objects, we don't need to # reverse them, as popping from the front is efficient. # If they are plain lists, popping from the end is # required. If they are iterators or tuples we need # to make a list version anyway. So: if must_copy: it1 = list(it1) it2 = list(it2) # Reverse sorted lists (it1 and it2 are definitely # lists now) so that we can pop off the end. it1.reverse() it2.reverse() # Now accumulate final sorted list. Basically, this is: # take first (now last) item from each list, and put whichever # one is smaller into the result. When either list runs # out, tack on the entire remaining list (whichever one is # non-empty -- if both are empty, the two extend ops are # no-ops, so we can just add both lists). # # Note that we have to re-reverse them to get # them back into forward order before extending. result = [] while it1 and it2: # Note: I don't know if it might be faster # to .pop() each item and .append() the one we # did not want to pop after all. This is just # an example, after all. last1 = it1[-1] last2 = it2[-1] if last2 < last1: result.append(last2) it2.pop() else: result.append(last1) it1.pop() it1.reverse() it2.reverse() result.extend(it1) result.extend(it2) return result So, now if "a" is the original (sorted) list and "b" is the not-yet- sorted list of things to add: a = merge_sorted(a, sorted(b), must_copy = False) will work, provided you are not required to do the merge "in place". Use the usual slicing trick if that is necessary: a[:] = merge_sorted(a, sorted(b), must_copy = False) If list b is already sorted, leave out the sorted() step. If list b is not sorted and is particularly long, use b.sort() to sort in place, rather than making a sorted copy. -- In-Real-Life: Chris Torek, Wind River Systems Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603 email: gmail (figure it out) http://web.torek.net/torek/index.html
-- http://mail.python.org/mailman/listinfo/python-list