[swift-evolution] Fast String Comparison From String Arrays

[Kenny Leung]

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 <swift-evolution at swift.org> wrote:
> 
> 
>> On Jul 28, 2017, at 05:54, Omar Charif via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> 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
>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>> 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
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170730/aa9f4785/attachment.html>