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.

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.

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

set-intersection-tests

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

-- Download set-intersection-tests --