Identifying differences between two datasets... Options

[Triane]

I know this topic has come up before, but I'd like to re-open the discussion of the best ways to rapidly compare two datasets to distinguish the differences between them...

The example that springs most readily to mind (probably because it's what I'm working on), is with the DSWorld dataset. I want to be able to take "snapshots" of the decal environment at intervals, and be able to discern (instantly?) what has changed in the interval... Currently I have an involved code-structure configured as follows:
Initialisation:

[DaMOB]

Triane, I did it pretty much like this and honestly it doesn't take that long. I did it in my last seen part of my macro and it updates every 3 secs (snapshots) and really with 40-60 people it took hardly anytime at all on a 700mhz classic Athlon. I set it for 3 sec because I felt thats good enough but it could be squeezed down to 1 sec and then it would do nothing else but that task.

I think we may have done some things a little different though (mine was as tweaked as I could get it at the time).

This is the code and it might not make sense out of context but here goes
When the macro first fires up:

Initialization

[DaMOB]

Oh, and watch out for ghosts cause the worldfilter will rip you a new one (and reason I have to distance you). LoadDecalWorld DISTANCE will give you ghosts too so be careful.

[Ipa]

Efficiency wise, you can tweak this to perform less dataset lookups if you slap an ascending index on the GUID field in both of them.

You then grab the 1st record from each DS and run this algorithm until EOF in both datasets.

If Backup[GUID] = Current[GUID]
// Nothing to do - DSNext in both of them
Else
If Backup[GUID] < Current[GUID]
// Object was there, now it's not. Add to LeftScene then DSNext in Before
Else
// Object wasn't there, not it is. Add to NewOnScene and DSNext in After
End
End



Of course, you could request that Cam throw together a SQL parser for datasets, so you could express this as:
SELECT Before.*, After.*
FROM Before FULL OUTER JOIN After on Before.GUID = After.GUID

j/k

[DaMOB]

I sorta tried it like that at first but not until I came up with how I finally HAD to do it di it work right. A lot of it is because of ghosts and stuff. Might re look at it again but after 24 hours back then I said fook it it works, its fast enough to do what I want so leave it be.

See the big HUGE, nay, ENORMOUS problem is that I would do my compares thinking, okay OLDDATASET is 10 long, NEW IS 10 LONG now scan each. PROBLEM was that 10 could be 9 people that were here and aren't now and 1 new person or any combo. If the world filter actually updated right then the scheme could be done in one very simple procedure.

If Backup[GUID] = Current[GUID]
// Nothing to do - DSNext in both of them
Else
This next line makes no sense to me because your GUID might be greater than mine but it could be less (in which case this would fire). Can you explain this a bit more?
If Backup[GUID] < Current[GUID]
// Object was there, now it's not. Add to LeftScene then DSNext in Before
Else
// Object wasn't there, not it is. Add to NewOnScene and DSNext in After
End
End

In that simple routine of yours it makes no allowances for Ghosts or false echoes that you will get all the time. As I said my simple routine started out very similiar to this but with all the false echoes I got I had to tweak and tweak and twe...

[kgober]

perhaps this example will help explain how the algorithm Ipa posted works:

take two decks of cards, and randomly remove 20 cards from each deck. now, what would be a good way to find out which cards are present only in the *first* stack, which cards are present only in the *second* stack, and which cards are present in *both* stacks, if you're only allowed to look at two cards at a time (as a computer does)?

first, sort each stack of 20 cards. aces through kings, grouped by spades then hearts then diamonds then clubs. place the two sorted stacks side by side, with the lowest card facing up.

now, look at the lowest card of each stack. if both cards are the same, take both of them and put them in the 'both' pile. if the card in the left stack is lower, remove only the left card and put it in the 'left stack only' pile. if the card in the right stack is lower, remove only the right card and put it in the 'right stack only' pile.

repeat the preceding paragraph until there are no cards left.

using this method, you can find out what's the same and what's different between two stacks of cards (or sets of objects) by doing only one comparison for each card you sort, and each comparison is guaranteed to properly sort at least one card, possibly two. for 20 cards, that's between 20 and 39 comparisons, depending on the particular cards you got. if the sets are mostly the same, the average number of comparisons will be near 20.

the alternative is to take an arbitrary card from the first stack, one at a time, then compare it to every card in the second stack to see if it matches any of them. in the worst case, that's 400 comparisons. if the sets are mostly the same, the average will still be over 100.

For a dataset containing 60 objects, the difference is even more extreme. This is because Ipa's algorithm grows linearly (so that 3 times the number of items takes 3 times as long). The alternative algorithm grows quadratically (n^2) (so that 3 times the number of items takes 9 times as long).

-ken

[Ipa]

[DaMOB]

Ahhh, okay Ipa.

Ken, like a bubble sort?

[kgober]

[DaMOB]

Ipa, what happens when one set is smaller than the other?

1111 1111
2222 2222
3333 4444
4444 5555
5555 EOF
EOF

Where your blank is at wouldn't be a blank but all the remaing data would have been shifted up one notch. Therefore, if I am not mistaken, from that point forward they would all be <, right?

[Triane]

Pardon me a moment, I'm thinking out loud

First "snapshot" {Backup}:

[Ipa]

DaMob:
Yes, the pseudocode is simplistic and doesn't specifically deal with EOF. If you hit EOF in one set, you automatically know that the remainder in the other set are unmatched, so you need to add an Or condition to the comparisons to check EOF.

Triane:
Re-reading my example, I had some typos (I had originally named the example sets 'Before' & 'After" then decided to rename them to match your code, but didn't globally rename in the sample pseudo-code).

Re-worded:

[DaMOB]

Something like this (haven't tested this)?

[Rojon]

Man, I got lost three lines into this stuff.

I don't suppose any kind sould would mind doing an even more detailed explanation of what the most important lines of code are doing?

Kind of a "Dataset for Dummies" primer?

[kgober]

perhaps it would help if you arrange your 'sample' datasets this way: