<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Nov 13, 2016, at 1:58 PM, Nial Giacomelli via swift-users <<a href="mailto:swift-users@swift.org" class="">swift-users@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Using Swift 3 I have a function that's called extremely frequently and is appearing regularly in Profiler runs. The function takes two Set<String> instances and simply attempts to determine whether all items from Set A are present in Set B (it's important to note that Set B may well contain additional items).<div class=""><br class=""></div><div class="">I've attempted to approach the problem in two ways:</div><div class=""><br class=""></div><div class=""><div class="">let diff = a.subtracting(b)</div><div class="">guard diff.count == 0 else { return false }</div></div><div class=""><br class=""></div><div class="">And also by simply iterating over the contents of Set A, like so:</div><div class=""><br class=""></div><div class=""><div class="">for item in a {</div><div class=""><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>if !b.contains(item) {</div><div class=""><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>return false</div><div class=""><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>}</div><div class="">}</div></div><div class=""><br class=""></div><div class="">Both ultimately end up spending the majority of their time in String._compareDeterministicUnicodeCollaton(String) -> Int. Which makes sense, given what I'm doing - but ideally I'd like to come up with a more efficient way of performing the above check. Swift's String representation is incredibly robust, but for my needs the strings could be adequately represented in ASCII encoding. I've also considered storing and comparing the hashValue of the strings, to speed up comparisons...</div><div class=""><br class=""></div><div class="">Hopefully this is an acceptable question for this mailing list. I'm aware that this may not be a Swift-specific question and could well be solved with a more efficient data structure or approach, but I'd really appreciate some input from more experienced Swift developers :-)</div></div></div></blockquote><br class=""></div><div>How often do the sets change? And where do you get them from? I’m wondering, if there’s enough time between when you get the strings and when you need to know if setA is a subset of setB, could you somehow compute the answer asynchronously in a background thread or something? Strictly speaking it wouldn't be any less work, but if you can move it to where you’re waiting for user input or something you’ll probably get your answer sooner.</div><div><br class=""></div><div>Regarding how to get the answer using less work in the first place, I think you’re doing a tiny bit of extra work — just some allocation overhead, really — by calculating the set difference and checking that its count == 0, rather than just checking if a.isSubset(of: b). Beyond that, I’m not really sure… You might be able to do something with the strings’ hash values. I mean, I don’t know if they really “work like that” (I’m quite foggy on how hash values are calculated and exactly what they’re suitable for… this might be a horrible idea), but if they do, comparing hash values (Ints) will definitely be faster than comparing Strings. I did some quick’n’dirty testing on my machine with some code very much like:</div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(209, 47, 27);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> setA: </span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Set</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">String</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">> = [</span><span style="font-variant-ligatures: no-common-ligatures" class="">"some"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"set"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"of"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"random"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"strings"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">]</span></div></div><div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(209, 47, 27);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> setB: </span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Set</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">String</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">> = [</span><span style="font-variant-ligatures: no-common-ligatures" class="">"some"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"other"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"set"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"of"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span><span style="font-variant-ligatures: no-common-ligatures" class="">"strings"</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">]</span></div></div><div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> hashedA = </span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Set</span><span style="font-variant-ligatures: no-common-ligatures" class="">(</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">setA</span><span style="font-variant-ligatures: no-common-ligatures" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">map</span><span style="font-variant-ligatures: no-common-ligatures" class="">{$0.</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">hashValue</span><span style="font-variant-ligatures: no-common-ligatures" class="">})</span></div></div><div><div style="margin: 0px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> hashedB = </span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Set</span><span style="font-variant-ligatures: no-common-ligatures" class="">(</span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">setB</span><span style="font-variant-ligatures: no-common-ligatures" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">map</span><span style="font-variant-ligatures: no-common-ligatures" class="">{$0.</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">hashValue</span><span style="font-variant-ligatures: no-common-ligatures" class="">})</span></div></div><div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(61, 29, 129);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">setA</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">.</span><span style="font-variant-ligatures: no-common-ligatures" class="">isSubset</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">(of: </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">setB</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">)</span></div></div><div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(79, 129, 135);" class=""><span style="font-variant-ligatures: no-common-ligatures" class="">hashedA</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">isSubset</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">(of: </span><span style="font-variant-ligatures: no-common-ligatures" class="">hashedB</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">)</span></div></div></blockquote><div><div class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><br class=""></span></div></div><div><span style="font-variant-ligatures: no-common-ligatures;" class="">The actual execution of </span><span style="color: rgb(79, 129, 135); font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">hashedA</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">.</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures; color: rgb(61, 29, 129);" class="">isSubset</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">(of: </span><span style="color: rgb(79, 129, 135); font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">hashedB</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">)</span> seems to be very roughly 2x faster than <span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures; color: rgb(79, 129, 135);" class="">setA</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">.</span><span style="color: rgb(61, 29, 129); font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">isSubset</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">(of: </span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures; color: rgb(79, 129, 135);" class="">setB).</span> However, if you include the overhead of calculating them, using hash values drops to about 5x <i class="">slower</i>. So unless you’d be reusing the hashed values a lot or something, I think you’re already doing about the least amount of work I can think of.</div><div><br class=""></div><div>- Dave Sweeris</div></body></html>