list.pop(0) vs. collections.dequeue

[Arnaud Delobelle]

Steve Howell <showell30 at yahoo.com> writes:

> On Jan 25, 1:32 pm, Arnaud Delobelle <arno... at googlemail.com> wrote:
>> Steve Howell <showel... at yahoo.com> 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:
>
> https://bitbucket.org/showell/shpaml_website/src/tip/shpaml.py

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
webpage).

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)
    else:
        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:
            break
        i += 1
    while i-1 > start and prefix_lines[i-1][1] == '':
        i -= 1
    return i

[...]

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