improving a huge double-for cycle

[Harald Luessen]

On Thu, 18 Sep 2008 Alexzive wrote:

>I am a python newbie and need to run following code for a task in an
>external simulation programm called "Abaqus" which makes use of python
>to access the mesh (ensamble of nodes with xy coordinates) of a
>certain geometrical model.
>
>[IN is the starting input containing the nodes to be check, there are
>some double nodes with the same x and y coordinates which need to be
>removed. SN is the output containing such double nodes]
>
>Code: Select all
>    for i in range(len(IN)): #scan all elements of the list IN
>      for j in range(len(IN)):
>        if i <> j:
>         if IN[i].coordinates[0] == IN[j].coordinates[0]:
>           if IN[i].coordinates[1] == IN[j].coordinates[1]:
>              SN.append(IN[i].label)

I did not test the syntax, but here is an idea with sorted lists.
It should be O(NlogN).

def sk(x):
    return x.coordinates[0]

IN.sort(key=sk)
for i in xrange(len(IN)):
    for j in xrange(i+1, len(IN)):
        if IN[i].coordinates[0] == IN[j].coordinates[0]:
            if IN[i].coordinates[1] == IN[j].coordinates[1]:
                SN.append(IN[i].label)
        else:
            break

Harald