<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 Jul 28, 2017, at 05:54, Omar Charif via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class=""><div class="">Hi,</div><div class=""><br data-mce-bogus="1" class=""></div><div class="">I wonder whether there is already a way in Swift to compare a string against a large string array quickly without using the traditional ways of comparison. <br class=""><br class="">Say we have ["a", "b", "c", "d"] and we would like to find whether this array contains "a", then we decide to check if we have "b" in that same array. Don't you think there is a way to represent the array in a different way and make this comparison a lot quicker ?<br class=""><br class="">I know there are recurrent neural networks etc ... I am talking here about solution without learning anything, just representing the array differently so we can minimize that O(N).<br class=""><br class="">I have developed an algorithm and it is doing pretty well so far and I wonder whether it would be accepted so I came to propose and see if this is interesting from your perspective.<br class=""><br class="">I developed a Javascript version here <a href="https://omarshariffathi.github.io/quickhint/" class="">https://omarshariffathi.github.io/quickhint/</a><br class=""><br class="">If you think this is welcome in Swift Foundation I am ready for a pull request.<br class="">Thanks for reading.</div></div>_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""><div class="">If you’re doing only direct containment, the builtin Set will give O(1) lookups.</div><div class=""><br class=""></div><div class="">If you’re looking for, say, finding all values with a given prefix then a trie might be appropriate, and if you’re trying to do more interesting things (e.g. fuzzy search) there’s techniques like “finite state transducers” <a href="http://blog.burntsushi.net/transducers/" class="">http://blog.burntsushi.net/transducers/</a> . I don’t believe either of these have anything built-in, and I suspect they (especially FSTs) are too specialized, or have too many possible variations, to be worth including directly in the current standard library, and a SwiftPM package would work almost as well as others have suggested.</div><div class=""><br class=""></div><div class="">Huon</div></body></html>