c# - Check if one collection of values contains another -

-

suppose have 2 collections follows:

collection1: "a1" "a1" "m1" "m2"

collection2: "m2" "m3" "m1" "a1" "a1" "a2"

all values string values. want know if elements in collection1 contained in collection2, have no guarantee on order , set may have multiple entries same value. in case, collection2 contain collection1 because collection2 has 2 a1's, m1 , m2. theres obvious way: sorting both collections , popping off values find matches, wondering if there's faster more efficient way this. again initial collections have no guarantee on order or how many times given value appear

edit: changed set collection clear these aren't sets can contain duplicate values

yes, there faster way, provided you're not space-constrained. (see space/time tradeoff.)

the algorithm:

just insert elements in set2 hashtable (in c# 3.5, that's hashset<string>), , go through elements of set1 , check if they're in hashtable. method faster (Θ(m + n) time complexity), uses o(n) space.

alternatively, say:

bool issuperset = new hashset<string>(set2).issupersetof(set1);

edit 1:

for people concerned possibility of duplicates (and hence misnomer "set"), idea can extended:

just make new dictionary<string, int> representing count of each word in super-list (add 1 count each time see instance of existing word, , add word count of 1 if it's not in dictionary), , go through sub-list , decrement count each time. if every word exists in dictionary and count never 0 when try decrement it, subset in fact sub-list; otherwise, had many instances of word (or didn't exist @ all), it's not real sub-list.

edit 2:

if strings big , you're concerned space efficiency, , algorithm works (very) high probability works you, try storing hash of each string instead. it's technically not guaranteed work, probability of not working pretty darn low.


Comments

Post a Comment

Popular posts from this blog

c# - How to set Z index when using WPF DrawingContext? -

-
how set z-index drawing object when using drawingcontext.drawxxx() methods? the object drawn last have higher z index. can't change index of drawn objects. way draw in order. if using wpf (as placed tag), can use, example, canvas control. create shapes need like polyline obj = new polyline(); //... // ... set properties of obj and add them canvas uielementcollection: yourcanvasname.children.add(obj); //or yourcanvasname.children.insert(i, obj); first items of collection have higher z index. advantages in way: no need redraw on window changes, can anytime move objects , change order.
Read more

razor - Is this a bug in WebMatrix PageData? -

-
i think may have found bug in webmatrix's pagedata, not sure. concerns how pass data partial page calling page. in webmatrix documentation (tutorials, e.g. " 3 - creating consistent look ", , example code), pagedata recommended mechanism pass data between pages (e.g. content page layout page, or partial page). however have found not work other way, pass data partial page calling page. modifying or adding entries in pagedata in partial page, not seem calling page. cutting right down simplest possible example, in test page may have this: @{ pagedata["test"] = "initial entry"; } <p>before calling partial page, test value @pagedata["test"]</p> @renderpage("_testpartial.cshtml") <p>after returning calling page, test value @pagedata["test"]</p> and in _testpartial.cshtml page might have this: @{ pagedata["test"] = "modified entry"; } <p>in partial page...
Read more

android - layout with fragment and framelayout replaced by another fragment and framelayout -

-
edit: so after comments below, revisted , realized hanging me up. imagine client list , client details activity started : public class clientsmainactivity extends fragmentactivity { @override public void oncreate(bundle savedinstancestate) { super.oncreate(savedinstancestate); //studiotabopenhelper db; setcontentview(r.layout.main_client_activity); } } so works great, starts main_client_activity (defined in layout below, , call activity when button on main screen clicked): intent intent = new intent(getactivity(), clientsmainactivity.class); startactivity(intent); easy issue is, clientsmainactivity not call oncreateview or anything, sets layout layout defines fragment, , listfragment. fine cause not trying pass clientsmainactivity , if have hypothetical activity like: sessionmainsactivity called when click on session edit of client, not calling sessionsmainactivity same way (starts activity sets alayout), want layout set defines...
Read more