Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>OK, I have measured the solution. The reversed solutions are about the same. The forward <code>while</code> loop is about 4 times slower. <strong>BUT!</strong> The Patrik's <em>dirty</em> solution is about 80 times faster for the list of 100,000 random integers <strong>[bug in Patrik2 corrected]</strong>:</p> <pre><code>import timeit import random def solution_ninjagecko1(lst): for i in xrange(len(lst)-1, -1, -1): if lst[i] % 2 != 0: # simulation of the choice del lst[i] return lst def solution_jdi(lst): L = len(lst) - 1 for i, v in enumerate(reversed(lst)): if v % 2 != 0: lst.pop(L-i) # L-1 is the forward index return lst def solution_Patrik(lst): for i, v in enumerate(lst): if v % 2 != 0: # simulation of the choice lst[i] = None return [v for v in lst if v is not None] def solution_Patrik2(lst): ##buggy lst = [v for v in lst if v % 2 != 0] ##buggy return [v for v in lst if v is not None] # ... corrected to return [v for v in lst if v % 2 != 0] def solution_pepr(lst): i = 0 # indexing the processed item n = 0 # enumerating the original position while i &lt; len(lst): if lst[i] % 2 != 0: # simulation of the choice del lst[i] # i unchanged if item deleted else: i += 1 # i moved to the next n += 1 return lst def solution_pepr_reversed(lst): i = len(lst) - 1 # indexing the processed item backwards while i &gt; 0: if lst[i] % 2 != 0: # simulation of the choice del lst[i] # i unchanged if item deleted i -= 1 # i moved to the previous return lst def solution_steveha(lst): def should_keep(x): return x % 2 == 0 return filter(should_keep, lst) orig_lst = range(30) print 'range() generated list of the length', len(orig_lst) print orig_lst[:20] + ['...'] # to have some fun :) lst = orig_lst[:] # copy of the list print solution_ninjagecko1(lst) lst = orig_lst[:] # copy of the list print solution_jdi(lst) lst = orig_lst[:] # copy of the list print solution_Patrik(lst) lst = orig_lst[:] # copy of the list print solution_pepr(lst) orig_lst = [random.randint(1, 1000000) for n in xrange(100000)] print '\nrandom list of the length', len(orig_lst) print orig_lst[:20] + ['...'] # to have some fun :) lst = orig_lst[:] # copy of the list t = timeit.timeit('solution_ninjagecko1(lst)', 'from __main__ import solution_ninjagecko1, lst', number=1) print 'solution_ninjagecko1: ', t lst = orig_lst[:] # copy of the list t = timeit.timeit('solution_jdi(lst)', 'from __main__ import solution_jdi, lst', number=1) print 'solution_jdi: ', t lst = orig_lst[:] # copy of the list t = timeit.timeit('solution_Patrik(lst)', 'from __main__ import solution_Patrik, lst', number=1) print 'solution_Patrik: ', t lst = orig_lst[:] # copy of the list t = timeit.timeit('solution_Patrik2(lst)', 'from __main__ import solution_Patrik2, lst', number=1) print 'solution_Patrik2: ', t lst = orig_lst[:] # copy of the list t = timeit.timeit('solution_pepr_reversed(lst)', 'from __main__ import solution_pepr_reversed, lst', number=1) print 'solution_pepr_reversed: ', t lst = orig_lst[:] # copy of the list t = timeit.timeit('solution_pepr(lst)', 'from __main__ import solution_pepr, lst', number=1) print 'solution_pepr: ', t lst = orig_lst[:] # copy of the list t = timeit.timeit('solution_steveha(lst)', 'from __main__ import solution_steveha, lst', number=1) print 'solution_steveha: ', t </code></pre> <p>It prints on my console:</p> <pre><code>c:\tmp\_Python\Patrick\so10305762&gt;python a.py range() generated list of the length 30 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, '...'] [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28] random list of the length 100000 [915411, 954538, 794388, 847204, 846603, 454132, 866165, 640004, 930488, 609138, 333405, 986073, 318301, 728151, 996047, 117633, 455353, 581737, 55350, 485030, '...'] solution_ninjagecko1: 2.41921752625 solution_jdi: 2.45477176569 solution_Patrik: 0.0468565138865 solution_Patrik2: 0.024270403082 solution_pepr_reversed: 2.43338888043 solution_pepr: 9.11879694207 </code></pre> <p>So, I tried with longer list. Using only twice as long one makes a big difference (on my old computer). Patrik's <em>dirty</em> solution behaves very nicely. It is about 200 times faster than the reversed solutions:</p> <pre><code>random list of the length 200000 [384592, 170167, 598270, 832363, 123557, 81804, 319315, 445945, 178732, 726600, 516835, 392267, 552608, 40807, 349215, 208111, 880032, 520614, 384119, 350090, '...'] solution_ninjagecko1: 17.362140719 solution_jdi: 17.86837545 solution_Patrik: 0.0957998851809 solution_Patrik2: 0.0500024444448 solution_pepr_reversed: 17.5078452708 solution_pepr: 52.175648581 </code></pre> <p><strong>[Added after ninjagecko's comments]</strong> </p> <p>The corrected Patrik2 solution is about twice faster than 2-stage Patrick solution.</p> <p>To simulate not so frequent deletion of the elements, the test like <code>if v % 2 != 0:</code> was changed to <code>if v % 100 == 0:</code>. Then about 1 % of items should be deleted. It is obvious that it takes less time. For 500,000 random integers in the list, the results are the following:</p> <pre><code>random list of the length 500000 [403512, 138135, 552313, 427971, 42358, 500926, 686944, 304889, 916659, 112636, 791585, 461948, 82622, 522768, 485408, 774048, 447505, 830220, 791421, 580706, '...'] solution_ninjagecko1: 6.79284210703 solution_jdi: 6.84066913532 solution_Patrik: 0.241242951269 solution_Patrik2: 0.162481823807 solution_pepr_reversed: 6.92106007886 solution_pepr: 7.12900522273 </code></pre> <p>Patrick's solution is stil about 30 times faster.</p> <p><strong>[Added 2012/04/25]</strong></p> <p>Another solution that works in-place, that loops forward, and that is as fast as Patrick's solution. It does not move all the tail when the element is deleted. Instead, it moves the wanted elements to their final position and then cuts the unused tail of the list.</p> <pre><code>def solution_pepr2(lst): i = 0 for v in lst: lst[i] = v # moving the element (sometimes unneccessary) if v % 100 != 0: # simulation of the choice i += 1 # here will be the next one lst[i:] = [] # cutting the tail of the length of the skipped return lst # The following one only adds the enumerate to simulate the situation when # it is needed -- i.e. slightly slower but with the same complexity. def solution_pepr2enum(lst): i = 0 for n, v in enumerate(lst): lst[i] = v # moving the element (sometimes unneccessary) if v % 100 != 0: # simulation of the choice i += 1 # here will be the next one lst[i:] = [] # cutting the tail of the length of the skipped return lst </code></pre> <p>Compared with the above solutions for <code>v % 100 != 0</code>:</p> <pre><code>random list of the length 500000 [533094, 600755, 58260, 295962, 347612, 851487, 523927, 665648, 537403, 238660, 781030, 940052, 878919, 565870, 717745, 408465, 410781, 560173, 51010, 730322, '...'] solution_ninjagecko1: 1.38956896051 solution_jdi: 1.42314502685 solution_Patrik: 0.135545530079 solution_Patrik2: 0.0926935780151 solution_pepr_reversed: 1.43573239178 solution_steveha: 0.122824246805 solution_pepr2: 0.0938177241656 solution_pepr2enum: 0.11096263294 </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POBest method for changing a list while iterating over it
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USpepr
    1. USpepr
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COInteresting. Unfortunately you didn't check the `reversed(range(len(yourList)))` solution (though if you did, it would be about the same as the first solution). However I don't believe the benchmarks are reasonable; in those benchmarks, you are removing **half** the elements. In that case, I would just do `[x for i,x in enumerate(lst) if i%2!=0]` and ignore the in-place requirement; this achieves a result twice as fast the fastest solution you benchmarked. Furthermore the solution you provide is not the "dirty" solution because it is not in-place and uses `[...]`.
      singulars
      1. PO
      1. USninjagecko
    2. COIt is true that if you delete only 20% of the elements of the list, the Patrick method is about 4x as fast, and that if you delete only 10% of the elements of the list, the Patrick method is about 2x as fast, according to your tests, though unfortunately I do not have the time to double-check them.
      singulars
      1. PO
      1. USninjagecko
    3. CO@ninjagecko: I was also surprised. I tried to delete about 1 % of the random elements (see the edited text). Patrick's method is still about 30 times faster for 500,000 elements. The question is: *Why should we insist on an in-place solution?*
      singulars
      1. PO
      1. USpepr
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload