How to get the difference between two lists?

[Frank D. Engel, Jr.]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Interesting.  Note that it would not be difficult to modify that code 
to support lists which do not meet those criteria (as long as both 
lists are still sorted, or else you'd need to sort them first), but I 
already lost the old stats: is this 15ms faster. or slower?

Given the problems with that one, I'm curious: how does something like 
this compare (this version only requires that both lists are in 
ascending numeric order):

put empty into the targetList
put 1 into x
put the number of lines in the masterList into maxX
put line 1 of the masterList into y

repeat for each line z in the exceptList
   repeat while (y < z) and (x <= maxX)
     put (y & cr) after the targetList
     add 1 to x
     put line x of the masterList into y
   end repeat

   repeat while (y = z) and (x <= maxX)
     add 1 to x
     put line x of the masterList into y
   end repeat
end repeat

repeat with x = x to maxX
   put (line x of the masterList) & cr after the targetList
end repeat

delete the last char of the targetList


On Apr 4, 2005, at 1:27 PM, Alex Tweedly wrote:

> Frank D. Engel, Jr. wrote:
>
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Okay, so anyone want to report on this one (untested, but should be 
>> rather efficient):
>>
>> This algorithm assumes that every item in the exclusion list is 
>> included in the master list, that there are no duplicate items in 
>> either list, and that both lists are in ascending numeric order:
>
> That assumption isn't met by the earlier test data - so I can't do an 
> exact comparison with the earlier cases.
>
> But with 10,000 in the full list, and 1,667 in the smaller list 
> (instead of 5000), the times are
> new code: 183 ms
> difference: 15 ms
>
> Surprising - I expected it to be faster, but I tried a few variants 
> and they all had much the same timings.
>
> -- 
> Alex Tweedly       http://www.tweedly.net
>
>
>
> -- 
> No virus found in this outgoing message.
> Checked by AVG Anti-Virus.
> Version: 7.0.308 / Virus Database: 266.8.6 - Release Date: 30/03/2005
>
> _______________________________________________
> use-revolution mailing list
> use-revolution at lists.runrev.com
> http://lists.runrev.com/mailman/listinfo/use-revolution
>
>
- -----------------------------------------------------------
Frank D. Engel, Jr.  <fde101 at fjrhome.net>

$ ln -s /usr/share/kjvbible /usr/manual
$ true | cat /usr/manual | grep "John 3:16"
John 3:16 For God so loved the world, that he gave his only begotten 
Son, that whosoever believeth in him should not perish, but have 
everlasting life.
$
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (Darwin)

iD8DBQFCUX327aqtWrR9cZoRApgRAJ96CZkw6IseDfnRyeV5nsVa3d8SGQCfYQ23
CSOK7Y1hy9S50fKTpxl7klk=
=Nil+
-----END PGP SIGNATURE-----



___________________________________________________________
$0 Web Hosting with up to 200MB web space, 1000 MB Transfer
10 Personalized POP and Web E-mail Accounts, and much more.
Signup at www.doteasy.com