On Jun 2, 2009, at 11:22 PM, Wilson MacGyver wrote:
>
> More newbie questions. :)
>
> If I have two sequences as follow:
>
> (2 3 4 5 6 7 8 9 10)
> (4 6 8 10)
>
> what's the best way to subtract the 2nd sequence from the first one?
>
> The best I can come up with was to do (first) on 2nd sequence and
> turn around
> and do a (remove) on the first sequence, etc until I exhaust the 2nd
> sequence.
In Clojure, the set data structure is awesome. I have nothing to add
to that. However, I had to do this the other day in Javascript (which
lacks a decent set type) and the algorithm I came up with is this:
sort both sequences
walk down both sequences:
if the remove list item is greater than the list item, add it to
the result and increment the remove list index
if the remove list item is less than the list item, increment the
list index
if they are equal, increment the remove list index
I believe this algorithm to be O(n log n) because the subtraction
operation should take O(MAX(n,m)) and that ought to be dominated by
the O(n log n) for sorting whichever input list is bigger. The naive
method ought to be O(n*m) because for each element of one list you
have to do a complete traversal of the other list. If the lists are
comparable in size it would start to resemble O(n^2).
Pretty off-topic, I know, but the function I came up with is this:
// returns the subtraction of two sorted lists
function subtract(a1, a2) {
var i = 0, j = 0, result = [];
// walk down both lists
while (i < a1.length && j < a2.length) {
// the list item is less than the remove item
if (a1[i] < a2[j]) {
// stick it on the result and move along the list
result.push(a1[i]);
i++;
}
else if (a1[i] > a2[j])
// the list item exceeds the remove item, so we need to
move along
the
// remove items
j++;
else
// the items are equal, so continue testing the list
with this item
of
// the remove list
i++;
}
// glob on the remainder of the list
if (i < a1.length)
result = result.concat(a1.splice(i));
return result;
}
I'm sure Clojure's sets do this kind of thing more efficiently but if
you have to do it in a language without a decent set data structure
you can fall back on that algorithm. Of course, I don't think you'll
notice an improvement over the naive method until you hit several
thousand elements or have similarly sized input lists.
—
Daniel Lyons
http://www.storytotell.org -- Tell It!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
