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