queue versus list

[duncan smith]

Hello,
      I have generator code along the following lines,


Q = queue.Queue()
Q.put(x)
while not Q.empty():
    x = Q.get()
    if <some condition that depends on x>:
        yield x
    else:
      Q.put(<some value that depends on x>)


If I change it to,


Q = []
Q.append(x)
for x in Q:
    if <some condition that depends on x>:
        yield x
    else:
      Q.append(<some value that depends on x>)


then it runs approximately 3 times more quickly. I seem to remember
(from somewhere) that the language specification doesn't guarantee that
the latter will continue to work, but that it's unlikely that future
implementations will break it. Apart from that, is there any good reason
why I shouldn't use the list? Is there another approach that might avoid
the overhead of using a queue? Results from profiling the two
implementations below in case it makes anything clearer. TIA.

Duncan


         88752234 function calls in 68.603 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   68.603   68.603 <string>:1(<module>)
     1009   18.343    0.018   68.602    0.068
bit_trees.py:699(paired_tries_search)
  8425934    6.116    0.000   10.373    0.000 bit_trees.py:751(hamdist)
        1    0.000    0.000    0.000    0.000 bit_trees.py:809(cum_shape)
  2350867    5.970    0.000   18.200    0.000 queue.py:115(put)
  2350867    6.114    0.000   16.639    0.000 queue.py:147(get)
        1    0.000    0.000    0.000    0.000 queue.py:199(_init)
  4701735    1.951    0.000    2.686    0.000 queue.py:202(_qsize)
  2350867    1.149    0.000    1.512    0.000 queue.py:206(_put)
  2350867    1.042    0.000    1.446    0.000 queue.py:210(_get)
        1    0.000    0.000    0.000    0.000 queue.py:27(__init__)
  2350868    2.991    0.000    4.397    0.000 queue.py:90(empty)
        3    0.000    0.000    0.000    0.000 threading.py:215(__init__)
  4701734    2.661    0.000    3.742    0.000 threading.py:239(__enter__)
  4701734    2.097    0.000    2.719    0.000 threading.py:242(__exit__)
  4701734    2.483    0.000    3.872    0.000 threading.py:254(_is_owned)
  4701734    8.185    0.000   12.057    0.000 threading.py:334(notify)
        1    0.000    0.000    0.000    0.000 {built-in method
_thread.allocate_lock}
  8425934    1.874    0.000    1.874    0.000 {built-in method builtins.bin}
        1    0.000    0.000   68.603   68.603 {built-in method
builtins.exec}
  4701736    0.735    0.000    0.735    0.000 {built-in method builtins.len}
  4701734    1.080    0.000    1.080    0.000 {method '__enter__' of
'_thread.lock' objects}
  4701734    0.622    0.000    0.622    0.000 {method '__exit__' of
'_thread.lock' objects}
  4701734    1.389    0.000    1.389    0.000 {method 'acquire' of
'_thread.lock' objects}
  2350867    0.363    0.000    0.363    0.000 {method 'append' of
'collections.deque' objects}
  8425934    2.384    0.000    2.384    0.000 {method 'count' of 'str'
objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of
'_lsprof.Profiler' objects}
  4701734    0.649    0.000    0.649    0.000 {method 'items' of 'dict'
objects}
  2350867    0.404    0.000    0.404    0.000 {method 'popleft' of
'collections.deque' objects}



32331417 function calls in 26.992 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.142    0.142   26.992   26.992 <string>:1(<module>)
     1009   16.741    0.017   26.851    0.027
bit_trees.py:699(paired_tries_search)
  8425934    5.270    0.000    9.175    0.000 bit_trees.py:755(hamdist)
        1    0.000    0.000    0.000    0.000 bit_trees.py:813(cum_shape)
  8425934    1.576    0.000    1.576    0.000 {built-in method builtins.bin}
        1    0.000    0.000   26.992   26.992 {built-in method
builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
  2350867    0.310    0.000    0.310    0.000 {method 'append' of 'list'
objects}
  8425934    2.329    0.000    2.329    0.000 {method 'count' of 'str'
objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of
'_lsprof.Profiler' objects}
  4701734    0.624    0.000    0.624    0.000 {method 'items' of 'dict'
objects}