[swift-evolution] Fast String Comparison From String Arrays

[Omar Charif]

The main advantage I introduce is actually no just a substring search, my main goal is to achieve high performance repeated search on the same given array of strings. I have tested my algorithm against something like spotlight for example searching for files etc … Actually my code is a bit faster on execution in a 1 to 1 single search. But if you go further and try to search for 2, 3, or more substrings in the same array my implementation will be even faster. My implementation is also simple and easy to use, you can simply see how easy and intuitive it is once you try it. I think this is basic String functionality that should already come with Swift Foundation library and it is additive with zero conflicts with Swift Foundation library. One last thing I have to say is that I have been testing this for 5 months so it is not new and I am not experimenting here :)

 

> On Jul 30, 2017, at 7:11 PM, Kenny Leung via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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 <mailto: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 <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 <mailto:swift-evolution at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> _______________________________________________
> 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/20170731/dbc11426/attachment.html>