This is a bit off topic, but does anybody know the data structure that supports Xcode’s fabulous case-insensitive-in-order-yet-disjoint-substring search?
-Kenny > On Jul 28, 2017, at 1:57 PM, Huon Wilson via swift-evolution > <[email protected]> wrote: > > >> On Jul 28, 2017, at 05:54, Omar Charif via swift-evolution >> <[email protected] <mailto:[email protected]>> wrote: >> >> Hi, >> >> 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. >> >> 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 ? >> >> 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). >> >> 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. >> >> I developed a Javascript version here >> https://omarshariffathi.github.io/quickhint/ >> <https://omarshariffathi.github.io/quickhint/> >> >> If you think this is welcome in Swift Foundation I am ready for a pull >> request. >> Thanks for reading. >> _______________________________________________ >> swift-evolution mailing list >> [email protected] <mailto:[email protected]> >> https://lists.swift.org/mailman/listinfo/swift-evolution > > If you’re doing only direct containment, the builtin Set will give O(1) > lookups. > > 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” > http://blog.burntsushi.net/transducers/ > <http://blog.burntsushi.net/transducers/> . 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. > > Huon > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
