tags:

views:

112

answers:

3

Hello

I have 2 string arrays, and I would like to return if any of them exists in _authRole array. How is that done?

 string[] _userRoles = userdata.Split(',');

 string[] _authRoles = AuthRoles.Split(',');


 bool isAuthorized = _authRoles.Any(_userRoles ??);

/M

+4  A: 

Try this:

Boolean isAuthorized =
    _userRoles.Any(user => _authRoles.Contains(user));
Andrew Hare
+5  A: 

If what you want is to determine if _authRoles and _userRoles have at least one common item, then use:

bool isAuthorized = _authRoles.Intersect(_userRoles).Any();

You can also query the result of Intersect in any other way you choose.

Jon
+1. I haven't used `Any` in that fashion before; that's better than the solution that I proposed.
Adam Robinson
Thanks. It's one of those things that are immediately obvious... after they cross your mind for the first time. :-)
Jon
+2  A: 

Suppose the lists are of size N and M and that the likely scenario is no match. Andrew's solution is O(NM) in time and O(1) in extra memory. Adam's solution is O(N+M) in time and memory, but could be written more clearly as Jon's solution.

Another solution which is basically the same as Adam and Jon's would be to join the two lists:

var joined = from user in userRoles 
             join auth in authRoles 
             on user equals auth 
             select user;
return joined.Any();

That's a bit heavier weight than necessary but it reads nicely. :-)

Eric Lippert
I can't resist saying that having Eric Lippert reply with not a better solution that yours definitely feels good. :-) Cheers Eric, by a longtime reader of your blog.
Jon
Are they definitely O(NM) and O(N+M), or does LINQ optimise it, as with the `Any()` on the end of Jon's solution, it only needs to find one result before it can return.
ck
@ck: Big-O notation as O(f(x)) is specified as the limit as x goes to infinity. As such any early-out is irrelevant to the time complexity (unless you are always considering best-case O(1)).
Ron Warholic
@ck: Ron is a bit imprecise in his characterization of asymptotic order but his point is well taken. Note that I said "and that the likely scenario is no match". If the likely scenario is no match then you are always going to have to build the complete data structure and iterate the whole thing to discover that there is no match. Building efficient data structures that can be queried quickly *when the query is likely to be "junk"* is quite tricky.
Eric Lippert
About the O(N+M) speed, out of curiosity: How is it derived? I 've been trying to figure out how you can do it in O(N+M) when you do not know a) if the items can be less-than compared, b) if it is feasible and reasonable to use the items as array indexes, and I 'm stumped. Maybe O(M+N) takes into account that strings are less-than comparable?
Jon
@Jon: Take the first list. Build a hash table HT out of that list. Cost to build HT is O(N) in time. For each item in the second list, ask HT if the item was in the first list. That's O(M) tests, each one costs O(1) in time if HT is well written. Total: O(N) + O(M) in time. Your idea about ordering is good though; if for some reason we didn't have an O(1) hash table we could at least build a binary searchable array at cost O(N lg N). Each search would cost O(lg N), so total cost would be O(N lg N) + O(M lg N).
Eric Lippert
@Eric: Hash tables crossed my mind (what can you do with `IEquatable` but not with `IComparable`?) but I dismissed it because surely the BCL can't be building HTs behind your back unless it has a good reason to believe that the overhead of setting up a HT will pay off? But on second thought, if you are writing the BCL then you will need conditional algorithm selection based on problem size to cater to all customers. Right?
Jon
Also about HTs: since the O in O(N) (building) is different than the O in O(M) (hashing/testing), can you really assert that it adds up to O(N+M)? Of course this is rather an academic question, building a HT is not going to be 10K times slower than looking items up in practice.
Jon
Hmm, just to correct my comment which mentions `IEquatable` and `IComparable`: of course I should have written "with `ΙΕquatable` which is not also `IComparable`". Guilty of bad syntax and slow error detection. :-)
Jon
@Jon: I think you'll find that LINQ-to-objects builds hash tables on your behalf all the time. If you don't like its behaviour then feel free to write your own implementation of LINQ-to-objects; nothing is stopping you. And the implementation often doesn't *know* the size of the problem; if the input is not an IList then calculating the size is itself O(n).
Eric Lippert
@Jon: Re: "The O in O(N) is different than the O in O(M)". I have not got the *faintest* idea what on earth you are talking about. Yes, I can and do assert that O(N) + O(M) = O(N+M). Can you explain what you mean by "The O in O(N) is different than the O in O(M)"? They sure look like the same O to me.
Eric Lippert
@Eric I like what works, so until the day comes when those hash tables are in my inner loop I probably won't bother. :-) But I would still find it hard to believe if someone told me "LINQ will build a hash table even if your collections have 3 items each and it knows that", that's all.
Jon
About the Os: For each of M items, build a proper binary tree with 20K nodes. And for each of N items, compute their hashes. As both M and N grow, the time will be say 1000 * M + N. Which is less than 1000 * (M+N), which is still O(M+N). That's how I started thinking, but obviously I stopped too early. Thanks!
Jon
As a final aside: this exchange has also taught me that a non-naive implementation of `GetHashCode` can be very important even where this would not be immediately obvious. Thanks again.
Jon