Как сделать слово freq counter более эффективным? - PullRequest
Новая
       5

Как сделать слово freq counter более эффективным?

3 голосов
/ 08 марта 2012

Я написал этот код F # для подсчета частот слов в списке и возврата кортежа в C #.Не могли бы вы сказать мне, как я могу сделать код более эффективным или короче? 

let rec internal countword2 (tail : string list) wrd ((last : string list), count) =
match tail with
| [] -> last, wrd, count
| h::t -> countword2 t wrd (if h = wrd then last, count+1 else last @ [h], count)

let internal countword1 (str : string list) wrd =
let temp, wrd, count = countword2 str wrd ([], 0) in
temp, wrd, count

let rec public countword (str : string list) =
match str with
| [] -> []
| h::_ ->
  let temp, wrd, count = countword1 str h in
       [(wrd, count)] @ countword temp

Ответы [ 3 ]

15 голосов
/ 08 марта 2012

Даже версия пэда может быть сделана более эффективной и лаконичной: 

let countWords = Seq.countBy id

Пример: 

countWords ["a"; "a"; "b"; "c"] //returns: seq [("a", 2); ("b", 1); ("c", 1)]
7 голосов
/ 08 марта 2012

Если вы хотите посчитать частоты слов в списке строк, ваш подход кажется излишним.Seq.groupBy хорошо подходит для этой цели: 

let public countWords (words: string list) = 
   words |> Seq.groupBy id
         |> Seq.map (fun (word, sq) -> word, Seq.length sq)
         |> Seq.toList
2 голосов
/ 08 марта 2012

Ваше решение перебирает список ввода несколько раз для каждого нового слова, которое оно находит. Вместо этого вы можете выполнить итерации по списку всего один раз и создать словарь, содержащий количество всех вхождений для каждого слова.

Чтобы сделать это в функциональном стиле, вы можете использовать F # Map, который является неизменным словарем: 

let countWords words = 
  // Increment the number of occurrences of 'word' in the map 'counts'
  // If it isn't already in the dictionary, add it with count 1
  let increment counts word =
    match Map.tryFind word counts with
    | Some count -> Map.add word (count + 1) counts
    | _ -> Map.add word 1 counts

  // Start with an empty map and call 'increment' 
  // to add all words to the dictionary
  words |> List.fold increment Map.empty

Вы также можете реализовать то же самое в императивном стиле, который будет более эффективным, но менее элегантным (и вы не получите всех преимуществ функционального стиля). Тем не менее, стандартный mutable Dictionary также может быть использован из F # (это будет похоже на версию C #, поэтому я не буду писать здесь).

Наконец, если вы хотите простое решение, использующее только стандартные функции F #, вы можете использовать Seq.groupBy, как предложено pad. Вероятно, это будет почти так же эффективно, как версия на основе Dictionary. Но если вы только изучаете F #, то написание нескольких рекурсивных функций, таких как countWords, - отличный способ выучить!

Чтобы дать вам несколько комментариев о вашем коде - сложность вашего подхода немного выше, но это, вероятно, должно быть хорошо. Есть, однако, некоторые распространенные проблемы:

  • В вашей функции countword2 у вас есть if h = wrd then ... else last @ [h], count. Вызов last @ [h] неэффективен, поскольку ему необходимо клонировать весь список last. Вместо этого вы можете просто написать h::last, чтобы добавить слово в начало, потому что порядок не имеет значения.

  • В последней строке вы снова используете @ в [(wrd, count)] @ countword temp. Это не обязательно. Если вы добавляете отдельный элемент в начало списка, вы должны использовать: (wrd,count)::(countword temp).

...