set-intersection-tests


Information

Created with NetLogo version NetLogo 4.0.4
Running with NetLogoLite.jar version 404.


A demonstration of two methods of determining the intersection of two agentsets (the agents that both sets have in common)
The "naive" method simply uses the MEMBER? primitive. Its performance is O(N^2).
The "sorted" method sorts the sets, then scans the sets in parallel to find the items in common. Its performance is approximately O(N)
In a set of 14,000 items, sorted is about 100 times faster.

Procedures

NetLogo Version: NetLogo 4.0.4

globals
[ s-time
]

to setup
   ca
   clear-output
   display
   op "test setup"
   let pop count patches
   let w sqrt pop
   let s floor (.5 * w)
   let sub floor (pop * .8)
   let a n-of sub patches
   let b n-of sub patches
   ask patches [ set pcolor red  ]
   ask a [ set pcolor pcolor + 10 ]
   ask b [ set pcolor pcolor + 20 ]
   display
   op "test running"
   op "------------"
   
   op (word "Finding intersection of items\nin two sets of " pop " items.")
      
   let c []
   
   start-time
     set c intersect2 a b
   end-time "sorted"
   
   set c intersect2 a b
   op (word "Intersection set has " count c " members.")
   
   ask c [ set pcolor violet ]
   
   start-time
     set c intersect1 a b
   end-time "naive"
   
   set c intersect2 a b
   op (word "Intersection set has " count c " members.")
   
   
   op ""
   op "done"
   op ""
end

to start-time
   set s-time timer
end

to end-time [ title ]
   let d-time timer - s-time
   op (word "Duration: " title ": " d-time)
end      

to op [ input ]
   output-print input
end   

to-report intersect1 [a b ] 
   report (a with [ member? self b ])
end

;; NOTE: Above is for agentsets.

to-report intersect1b [a b ] 
   report (filter [ member? self b ] a)
end

to-report intersect2 [ a b ]
   set a sort a
   set b sort b
   let c []
   while [ not (empty? a or empty? b ) ]
   [ if-else first a < first b
     [ set a but-first a
     ]
     [ if-else first a > first b
       [ set b but-first b
       ]
       [ set c fput first a c
         set a but-first a
         set b but-first b
       ]
     ]
   ]
   report (patch-set c)
end

;; above reports a PATCH agentset
;; to use with lists, just report C, without PATCH-SET


                    


Download Link

View or download the complete model file (to download: right-click, save-link-as):
-- Download set-intersection-tests --