F # fsharp Быстрый способ поиска строки «начиная с» из двух массивов - PullRequest
Новая
       32

F # fsharp Быстрый способ поиска строки «начиная с» из двух массивов

0 голосов
/ 30 октября 2018

У меня проблема с производительностью в больших массивах (по 50 КБ каждый). Каков был бы самый быстрый способ найти строку, которая начинается с другой строки по двум массивам? Я пробовал разные вещи, но код ниже, кажется, настолько хорош, насколько я могу получить. 

let findFile (f:string, p:string, pc:string, pcn:string) =
    f.StartsWith(p + "-" + pc) || 
    f.StartsWith(p + "_" + pc) ||
    f.StartsWith(p + "-" + pcn) ||
    f.StartsWith(p + "_" + pcn)

products
|> Array.Parallel.map (fun i p ->
    allFiles |> Array.Parallel.map (fun f ->
        if findFile (f.Filename, p.Style, p.ColorCode, p.ColorName)
        then {p with Filename = f.Filename }
        else p
    ))

Заранее спасибо.

1 Ответ

0 голосов
/ 30 октября 2018

Сначала я бы порекомендовал очистить имена файлов, разделив две части и, если возможно, удалив остальные:

  • Разделите имена файлов по символу '-' или '_', чтобы сравнивать кортежи (стиль * цвет) вместо строк дважды. Также, если это вообще возможно, различайте при использовании цветового кода от имени цвета и разделяйте на 2 массива.

Теперь у вас есть 2 варианта: использовать словарь или отсортировать значения

  • Словарь: возьмите более длинный список и поместите его в словарь. Сканируйте более короткий список в поисках значений. В словарях используются хеш-таблицы, которые делают их очень эффективными, а сравнения также очень быстрыми. Это требует, чтобы вы использовали в качестве ключа только стиль и цветовой код / ​​имя, оставляя остальную часть строки вне.

Решение может выглядеть так: 

let dict () =
    let dict = new Dictionary<_, _>()
    allFiles |> Seq.iter (fun f -> f.Filename.Split '-' |> fun a -> dict.Add((a.[0], a.[1]), f) )
    products
    |> Array.Parallel.map (fun p -> 
        let vRef = ref { Filename = "" }
        if dict.TryGetValue((p.Style, p.ColorCode) , vRef)
        then {p with Filename = (!vRef).Filename }
        else p
    )

Если это невозможно, подумайте:

  • Сортировка обоих списков: продукты и имена файлов. Сканируйте оба упорядоченных списка одновременно с индексом, каждый раз увеличивая только нижнее значение.

Еще одна вещь: Если вы все еще хотите проводить сравнения строк, вы должны рассмотреть возможность использования скомпилированного Regex, который очень эффективен. Ваше регулярное выражение может быть чем-то вроде: ^code[-_](red|FF0000), которое будет соответствовать любому из 4 значений:

  • code-red
  • code_red
  • code-FF0000
  • code_FF0000

Вот как вы используете скомпилированное регулярное выражение: 

let regex = new Regex(sprintf "^%s[-_](%s|%s)" p.Style p.ColorCode p.ColorName, RegexOptions.Singleline + RegexOptions.Compiled)
for i in 1..30 do
    if regex.IsMatch(sprintf "code-%d" i) then printfn "%A" i
...