list.pop(0) vs. collections.dequeue

Arnaud Delobelle arnodel at
Wed Jan 27 08:34:56 CET 2010

Steve Howell <showell30 at> writes:

> On Jan 25, 1:32 pm, Arnaud Delobelle <arno... at> wrote:
>> Steve Howell <showel... at> writes:
>> [...]
>> > My algorithm does exactly N pops and roughly N list accesses, so I
>> > would be going from N*N + N to N + N log N if switched to blist.
>> Can you post your algorithm?  It would be interesting to have a concrete
>> use case to base this discussion on.
> I just realized you meant the Python code itself.  It is here:

Hi - I didn't have the time to look at it before today.  You scan
through a list called prefix_lines, and you use pop(0) as a means to
keep track of your position in this list.  It seems to me that it would
be more effective to explicitely keep track of it - and it would remove
the need to the numerous copies of sublists of indent_lines that you
have to create.

I have rewritten part of the three relevant functions (html_block_tag,
get_indented_block and recurse, within indent_lines) to show you what I
mean (see below).  I have tried to keep the changes to a minimum - you
can see that the code is no more complex like this.  The advantage is
that only one list is created, prefix_lines, and there is no need to
mutate it or copy parts of it during the algorithm.  I have not had the
time to test it though (only on one of the examples on the examples

Code follows:


def html_block_tag(output, block, start, end, recurse):
    append = output.append
    prefix, tag = block[start]
    if RAW_HTML.regex.match(tag):
        append(prefix + tag)
        recurse(block, start + 1, end)
        start_tag, end_tag = apply_jquery_sugar(tag)
        append(prefix + start_tag)
        recurse(block, start + 1, end)
        append(prefix + end_tag)


def get_indented_block(prefix_lines, start, end):
    prefix, line = prefix_lines[start]
    len_prefix = len(prefix)
    i = start + 1
    while i < end:
        new_prefix, line = prefix_lines[i]
        if line and len(new_prefix) <= len_prefix:
        i += 1
    while i-1 > start and prefix_lines[i-1][1] == '':
        i -= 1
    return i


def indent_lines(lines,
    append = output.append
    def recurse(prefix_lines, start, end):
        while start < end:
            prefix, line = prefix_lines[start]
            if line == '':
                start += 1
                block_end = get_block(prefix_lines, start, end)
                if block_end == start + 1:
                    start += 1
                    if line == pass_syntax:
                    elif line.startswith(flush_left_syntax):
                    elif line.startswith(flush_left_empty_line):
                        append(prefix + leaf_method(line))
                    branch_method(output, prefix_lines, start, block_end, recurse)
                    start = block_end
    prefix_lines = map(indentation_method, lines)
    recurse(prefix_lines, 0, len(prefix_lines))

More information about the Python-list mailing list