Databases
StackOverflow2013
Postsdbo
POWhat is the most efficient way to add an element to a list only if isn't there yet?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat is the most efficient way to add an element to a list only if isn't there yet?
    primarykey
    data
    text
    <p>I have the following code in Python:</p> <pre><code>def point_to_index(point): if point not in points: points.append(point) return points.index(point) </code></pre> <p>This code is awfully inefficient, especially since I expect <code>points</code> to grow to hold a few million elements.</p> <p>If the point isn't in the list, I traverse the list 3 times:</p> <ol> <li>look for it and decide it isn't there</li> <li>go to the end of the list and add a new element</li> <li>go to the end of the list until I find the index</li> </ol> <p>If it <em>is</em> in the list, I traverse it twice: 1. look for it and decide it is there 2. go almost to the end of the list until I find the index</p> <p>Is there any more efficient way to do this? For instance, I know that:</p> <ul> <li>I'm more likely to call this function with a point that isn't in the list.</li> <li>If the point is in the list, it's likelier to be near the end than in the beginning.</li> </ul> <p>So if I could have the line:</p> <pre><code>if point not in points: </code></pre> <p>search the list from the end to the beginning it would improve performance when the point is already in the list.</p> <p>However, I don't want to do:</p> <pre><code>if point not in reversed(points): </code></pre> <p>because I imagine that <code>reversed(points)</code> itself will come at a huge cost.</p> <p>Nor do I want to add new points to the beginning of the list (assuming I knew how to do that in Python) because that would change the indices, which must remain constant for the algorithm to work.</p> <p>The only improvement I can think of is to implement the function with only one pass, if possible from the end to the beginning. The bottom line is:</p> <ul> <li>Is there a good way to do this?</li> <li>Is there a better way to optimize the function?</li> </ul> <p><strong>Edit:</strong> I've gotten suggestions for implementing this with only one pass. Is there any way for <code>index()</code> to go from the end to the beginning?</p> <p><strong>Edit:</strong> People have asked why the index is critical. I'm trying to describe a 3D surface using the <a href="http://shape.cs.princeton.edu/benchmark/documentation/off_format.html" rel="nofollow noreferrer">OFF file format</a>. This format describes a surface using its vertices and faces. First the vertices are listed, and the faces are described using a list of indices of vertices. That's why once I add a vortex to the list, its index must not change.</p> <p><strong>Edit:</strong> There have been some suggestions (such as <a href="https://stackoverflow.com/questions/1319254/what-is-the-most-efficient-way-to-add-an-element-to-a-list-only-if-isnt-there-ye/1319470#1319470">igor's</a>) to use a dict. This is a good solution for <em>scanning</em> the list. However, when I'm done I need to print out the list in the same order it was created. If I use a dict, I need to print out its keys sorted by value. Is there a good way to do that?</p> <p><strong>Edit:</strong> I implemented <a href="https://stackoverflow.com/users/55225/www-brool-com">www.brool.com</a>'s <a href="https://stackoverflow.com/questions/1319254/what-is-the-most-efficient-way-to-add-an-element-to-a-list-only-if-isnt-there-ye/1321039#1321039">suggestion</a>. This was the simplest and fastest. It is essentially an ordered Dict, but without the overhead. The performance is great!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USNathan Fellman
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhat is the most efficient way to add an element to a list only if isn't there yet?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhat is the most efficient way to add an element to a list only if isn't there yet?
      1. USMichael Foukarakis
      1. VTFavorite
    3. VO
      singulars
      1. POWhat is the most efficient way to add an element to a list only if isn't there yet?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIs there a reason why you're using a list and not a set?
      singulars
      1. POWhat is the most efficient way to add an element to a list only if isn't there yet?
      1. USAndrew Medico
    2. COWhy do you need the index of the point in the list? If you could add all your elements at once into a set, you could run this code in 5-10 seconds, at a guess.
      singulars
      1. POWhat is the most efficient way to add an element to a list only if isn't there yet?
      1. UShughdbrown
 

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