Сравнение алгоритма автозаполнения в Python, Go, Haskell

import json, datetime

def autocomplete(typed, possibilities):
    """The basic breadth-first algorithm: add the biggest prefix common to all continuations."""
    # Exclude things that don't match the typed prefix.
    matches = [p for p in possibilities if p.startswith(typed)]
    # str.startswith is slower than slicing, but more idiomatic, so it's a fairer comparison.
    # If there's nothing that starts with the given prefix, proceed to the next rule.
    if not matches: return autocomplete_contiguous(typed, possibilities)
    # Scan the common prefix 1 char at a time.
    i = len(typed)
    while True:
        char = None
        for s in matches:
            if len(s) <= i or char and s[i] != char:
                return s[:i]
            if not char:
                char = s[i]
        i += 1

def autocomplete_contiguous(typed, possibilities):
    """Fallen back to if nothing starts with typed. Checks for things that contain it."""
    matches = [p for p in possibilities if typed in p]
    if len(matches) == 1: return matches[0]
    if not matches: return autocomplete_in_order(typed, possibilities)
    return typed

def autocomplete_in_order(typed, possibilities):
    """Fallen back to if nothing contains the typed characters contiguously. Checks if anything has them in order."""
    matches = []
    for s in possibilities:
        lastmatch = 0
        for char in typed:
            index = s.find(char, lastmatch)
            if index < lastmatch: break
            lastmatch = index + 1
        else:
            # It's ambiguous.
            if matches: return typed
            matches.append(s)
    # There's less than 2 matches.
    if matches: return matches[0]
    return typed


if __name__ == '__main__':

    with open('data') as f:
        sets = json.load(f)

    start = datetime.datetime.now()
    for s in sets:
        autocomplete(s['typed'], s['possibilities'])
    end = datetime.datetime.now()

    print(end - start)

package main

import (
    "encoding/json"
    "fmt"
    "io/ioutil"
    "strings"
    "time"
)

type Case struct {
    Typed         string
    Possibilities []string
}

func main() {
    var rawData, err = ioutil.ReadFile("data")
    if err != nil {
        panic(err)
    }
    var data = make([]Case, 0, 1000000)
    err = json.Unmarshal(rawData, &data)
    if err != nil {
        panic(err)
    }
    var before = time.Now()
    for i := range data {
        autocomplete(data[i].Typed, data[i].Possibilities)
    }
    var after = time.Now()
    fmt.Printf("Took %f\n", float64(after.Sub(before))/float64(time.Second))
}

func autocomplete(typed string, possibilities []string) string {
    var matches []string
    // Exclude things that don't match the typed prefix.
    for _, s := range possibilities {
        if strings.HasPrefix(s, typed) {
            matches = append(matches, s)
        }
    }
    if len(matches) == 0 {
        return autocompleteContiguous(typed, possibilities)
    }
    // Scan the common prefix 1 char at a time.
    for i := len(typed); true; i++ {
        var char byte = '~' // A dumb hack: this char doesn't appear in the dataset.
        for _, s := range matches {
            if len(s) <= i || char != '~' && s[i] != char {
                return s[:i]
            }
            if char == '~' {
                char = s[i]
            }
        }
    }
    // Go can't tell this is unreachable
    panic("Shouldn't happen")
}

func autocompleteContiguous(typed string, possibilities []string) string {
    var matches []string
    // Exclude things that don't match the typed prefix.
    for _, s := range possibilities {
        if strings.Contains(s, typed) {
            matches = append(matches, s)
        }
    }
    if len(matches) == 1 {
        return matches[0]
    } else if len(matches) == 0 {
        return autocompleteInOrder(typed, possibilities)
    }
    return typed
}

func autocompleteInOrder(typed string, possibilities []string) string {
    var matches []string
    // Exclude things that don't match the typed prefix.
    for _, s := range possibilities {
        var lastmatch = 0
        for i, char := range typed {
            var index = strings.IndexRune(s[lastmatch:], char)
            if index == -1 {
                break
            }
            // The index will be offset by our slicing, so account for that.
            lastmatch += index + 1
            // If we just found the last character, record this as a match.
            if i+1 == len(typed) {
                // There's already a match. It's ambiguous.
                if len(matches) > 0 {
                    return typed
                }
                matches = append(matches, s)
            }
        }
    }
    // If we get here, there's less than 2 matches.
    if len(matches) == 1 {
        return matches[0]
    }
    return typed
}

{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE OverloadedStrings #-}

import Data.Time
import Data.Text (Text)
import qualified Data.Text as Text
import Data.Aeson
import Data.Maybe
import Control.Exception
import Control.DeepSeq
import GHC.Generics

data Case = Case
  { typed :: !Text
  , possibilities :: ![Text]
  } deriving (Generic, Show, Read, Eq)

instance FromJSON Case
instance NFData Case

-- | The simple algorithm.
autocomplete :: Case -> Text
autocomplete (Case typed possibilities) =
  let suffixes = mapMaybe (Text.stripPrefix typed) possibilities
  in if not $ null suffixes
    then typed <> commonPrefix suffixes
    else autocompleteContiguous typed possibilities

commonPrefix :: [Text] -> Text
commonPrefix [] = ""
commonPrefix [x] = x
commonPrefix (x:y:xs) =
  case Text.commonPrefixes x y of
    Nothing -> ""
    Just (p,_,_) -> commonPrefix (p:xs)

autocompleteContiguous typed possibilities =
    let matches = filter (Text.isInfixOf typed) possibilities
    in if length matches > 1
        then typed
        else if length matches == 1
            then head matches
            else autocompleteSparse typed possibilities

autocompleteSparse typed possibilities =
    let matches = filter (isMatch typed) possibilities
    in if length matches == 1
        then head matches
        else typed
    where
        isMatch "" str = True
        isMatch substr str =
            case Text.findIndex (== Text.head substr) str of
                Nothing -> False
                Just index -> isMatch (Text.tail substr) (Text.drop (index + 1) str)

main = do
    cases <- (fromJust <$> decodeFileStrict' "data") :: IO [Case]
    mapM_ (evaluate . force) cases
    start <- getCurrentTime
    mapM_ (evaluate . autocomplete) cases
    end <- getCurrentTime
    putStrLn $ "Took " ++ (show $ diffUTCTime end start)

import string, json, time, random

allowed_chars = string.ascii_lowercase + string.digits

def gendata():
    start = time.time()
    funcs = (
        mkset_full_prefix_completion,
        mkset_partial_prefix_completion,
        mkset_typed_no_completion,
        mkset_prefix_ambiguous,
        mkset_contain_ambiguous,
        mkset_contain_completion,
        mkset_sparse_ambiguous,
        mkset_sparse_completion,
    )
    sets = [random.choice(funcs)() for i in range(1000000)]
    end = time.time()
    print(f"generated data in {end - start}")
    with open('data', 'w') as f:
        json.dump(sets, f)

def mkset_full_prefix_completion():
    """Full completion from prefix is possible."""
    typed = randomchars(allowed_chars, 1, 4)
    target = typed + randomchars(allowed_chars, 5, 10) 
    # To ensure there's only one possibility, others can't have the last char in typed.
    new_chars = ''.join(c for c in allowed_chars if c != typed[-1])
    possibilities = [target,
        *(randomchars(allowed_chars, 5, 15) for i in range(random.randint(2, 19)))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def mkset_partial_prefix_completion():
    """Partial completion from prefix is possible."""
    typed = randomchars(allowed_chars, 0, 3)
    common = typed + randomchars(allowed_chars, 1, 5)
    # Make sure there's one that uses a continuation the others don't, so full completion isn't possible.
    dropped_char = random.choice(allowed_chars)
    new_chars = ''.join(c for c in allowed_chars if c != dropped_char)
    possibilities = [common + dropped_char + randomchars(allowed_chars, 5, 10),
        *(common + randomchars(new_chars, 5, 10) for i in range(random.randint(2, 19)))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def mkset_typed_no_completion():
    """The user's typed something with no completion."""
    typed = randomchars(allowed_chars, 5, 10)
    # Don't allow choosing some char in the typed string.
    dropped_char = random.choice(typed)
    new_chars = ''.join(c for c in allowed_chars if c != dropped_char)
    possibilities = [randomchars(new_chars, 5, 15) for i in range(random.randint(2, 20))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def mkset_prefix_ambiguous():
    """There are multiple things that start with what the user's typed, and immediately diverge."""
    typed = randomchars(allowed_chars, 1, 5)
    p1 = typed + randomchars(allowed_chars, 5, 10)
    # Pick another possibility that immediately diverges from p1.
    p2_chars = ''.join(c for c in allowed_chars if c != p1[len(typed)])
    p2 = typed + randomchars(p2_chars, 5, 10)
    possibilities = [p1, p2,
        *(randomchars(allowed_chars, 5, 15) for i in range(random.randint(2, 18)))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def mkset_contain_ambiguous():
    """There's nothing that starts with what the user's typed, but two that contain it."""
    typed = randomchars(allowed_chars, 1, 5)
    p1 = randomchars(allowed_chars, 2, 5) + typed + randomchars(allowed_chars, 2, 5)
    # Pick another possibility that immediately diverges from p1.
    new_chars = ''.join(c for c in allowed_chars if c != p1[len(typed)])
    p2 = randomchars(new_chars, 2, 5) + typed + randomchars(new_chars, 2, 5)
    possibilities = [p1, p2,
        *(randomchars(new_chars, 5, 15) for i in range(random.randint(2, 18)))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def mkset_contain_completion():
    """There's nothing that starts with what the user's typed, but one that contains it."""
    typed = randomchars(allowed_chars, 1, 5)
    match = randomchars(allowed_chars, 2, 5) + typed + randomchars(allowed_chars, 2, 5)
    # Make sure nothing else can contain it.
    dropped_char = random.choice(typed)
    new_chars = ''.join(c for c in allowed_chars if c != dropped_char)
    possibilities = [match,
        *(randomchars(new_chars, 5, 15) for i in range(random.randint(2, 19)))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def mkset_sparse_ambiguous():
    """There's nothing that starts with what the user's typed, nothing that contains it,
    but two that contain all the characters."""
    typed = randomchars(allowed_chars, 2, 5)
    p1 = intersperse_chars(typed, randomchars(allowed_chars, 5, 15))
    p2 = intersperse_chars(typed, randomchars(allowed_chars, 5, 15))
    # Make sure nothing else can contain it.
    dropped_char = random.choice(typed)
    new_chars = ''.join(c for c in allowed_chars if c != dropped_char)
    possibilities = [p1, p2,
        *(randomchars(new_chars, 5, 15) for i in range(random.randint(2, 18)))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def mkset_sparse_completion():
    """There's nothing that starts with what the user's typed, nothing that contains it,
    but one that contains all the characters."""
    typed = randomchars(allowed_chars, 2, 5)
    match = intersperse_chars(typed, randomchars(allowed_chars, 5, 15))
    # Make sure nothing else can contain it.
    dropped_char = random.choice(typed)
    new_chars = ''.join(c for c in allowed_chars if c != dropped_char)
    possibilities = [match,
        *(randomchars(new_chars, 5, 15) for i in range(random.randint(2, 19)))]
    random.shuffle(possibilities)
    return {'typed': typed, 'possibilities': possibilities}

def randomchars(charset, lower, upper):
    return ''.join(random.choice(charset) for i in range(random.randint(lower, upper)))

def intersperse_chars(chars, string):
    final, string = string[0], string[1:]
    for c in chars:
        skip = random.randint(0, 3)
        final += c
        final += string[skip:]
        string = string[:skip]
    return final + string

if __name__ == '__main__': gendata()