Stats

  • Locked Locked
  • Replies 5
  • Subscribers 142
  • Views 7176
  • Members are here 0
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

Comparing of two huge lists containing sublists

Slawa

Hello

At me the following problem
There are 2 big lists (> 10^6 elements) a type:

list1=(
list(x11 x12 x13 x14 x15)
list(x21 x22 x23 x24 x25)
list(x31 x32 x33 x34 x35)
....................................
list(xn1 xn2 xn3 xn4 xn5)
)

list2=(
list(y11 y12 y13 y14 y15)
list(y21 y22 y23 y24 y25)
list(y31 y32 y33 y34 y35)
....................................
list(yn1 yn2 yn3 yn4 yn5)

)

It is necessary to compare and receive them the member list which are present both there and there. Comparing to lead only on
to first four elements of sublists
That is on a condition that:

xn1 == yn1 && xn2 == yn2 && xn3 == yn3 && xn4 == yn4

 

I have made it as follows:

list_overlap=nil

foreach(item1 list1
x11=nth(0 item1)
x12=nth(1 item1)
x13=nth(2 item1)
x14=nth(3 item1)

x15=nth(4 item1)
foreach(item2 list2
y11=nth(0 item2)
y12=nth(1 item2)
y13=nth(2 item2)
y14=nth(3 item2)

y15=nth(4 item2)
if(x11==y11 && x12==y12  && x13==y13 && x14==y14  then

list_overlap=cons (list(x11 x12 x13 x14 x15) list_overlap)

))

But this operation occupies too much time.
Whether there are methods to carry out it faster?

 

Regards

Slawa

  • Using a table will almost certainly make it much faster:

    hash2=makeTable('list2Hash nil)
    ; store the original items as the keys in the table
    foreach(item list2
      hash2[item]=t
    )
    ; use setof to iterate over list2 and then check if that key is in the second list
    list_overlap=setof(item list1 hash2[list1]) 

    I've made the assumption here that there are no additional entries in the lists (i.e. there aren't 6th entries you want to ignore in the comparison).

    Best Regards,

    Andrew.

  • Unfortunately additional records are present at lists... For this reason I concretized:

    "Comparing to lead only on to first four elements of sublists
    That is on a condition that:
    xn1 == yn1 && xn2 == yn2 && xn3 == yn3 && xn4 == yn4"

    From here it is visible that xn5 and yn5 in comparing don't participate

     

     

    Andrew Beckett said:
    ; use setof to iterate over list2 and then check if that key is in the second list
    list_overlap=setof(item list1 hash2[list1]) 

    list_overlap=setof(item list1 hash2[item])  <-Possibly you were mistaken

    Best Regards,

    Slawa

  •  I managed to implement it as follows:

    hash1=makeTable('listHash1 nil)
    foreach(item list2 my_list1=list(nth(0 item) nth(1 item) nth(2 item) nth(3 item)) hash1[my_list1]=t)
    list_overlap1=setof(item list1 my_list2=list(nth(0 item) nth(1 item) nth(2 item) nth(3 item)) hash1[my_list2])

     

     
    Whether I do not know the given variant is optimal but it works much faster my first example

     

    Best Regards,

    Slawa

     

  • Hi Slawa,

    The reason I was confused was because your code had changed between looking at the email sent by the forum system, and when I looked on the web - so you'd presumably edited it.

    Maybe you could use another way to build a list of the first four list elements, but I doubt it would end up being much faster. Detailed profiling would be necessary.

    Potential candidates could be:

    list(car(item) cadr(item) caddr(item) cadddr(item))

    Or

    let(((n 4) setof(_i item plusp(n--)))

    I'd be surprised if the last one was faster though.

    Regards,

    Andrew

  • Hi, Andrew
    Many thanks for the help.


    Best Regards,

    Slawa

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.