Tìm các bản sao trong một trình tự chưa được phân loại hiệu quả

Question

Tôi cần một cách rất hiệu quả để tìm các bản sao trong một chuỗi chưa phân loại. Đây là những gì tôi đã đưa ra, nhưng nó có một vài thiếu sót, cụ thể là nó

1. cách không cần thiết đếm lần xuất hiện ngoài 2
2. tiêu thụ toàn bộ chuỗi trước khi bản sao năng suất
3. tạo ra nhiều chuỗi trung gian

module Seq = 
    let duplicates items = 
    items 
    |> Seq.countBy id 
    |> Seq.filter (snd >> ((<) 1)) 
    |> Seq.map fst 

Bất kể những thiếu sót nào, tôi không thấy lý do để thay thế điều này bằng hai lần mã. Có thể cải thiện điều này bằng mã súc tích tương đối không?

Answer 1

Dưới đây là một giải pháp cấp bách (đó là phải thừa nhận là hơi dài hơn):

let duplicates items = 
    seq { 
     let d = System.Collections.Generic.Dictionary() 
     for i in items do 
      match d.TryGetValue(i) with 
      | false,_ -> d.[i] <- false   // first observance 
      | true,false -> d.[i] <- true; yield i // second observance 
      | true,true ->()      // already seen at least twice 
    } 

Answer 2

Giả sử chuỗi của bạn là hữu hạn, giải pháp này đòi hỏi phải có một lần chạy thử trên chuỗi:

open System.Collections.Generic 
let duplicates items = 
    let dict = Dictionary() 
    items |> Seq.fold (fun acc item -> 
          match dict.TryGetValue item with 
          | true, 2 -> acc 
          | true, 1 -> dict.[item] <- 2; item::acc 
          | _ -> dict.[item] <- 1; acc) [] 
     |> List.rev 

Bạn có thể cung cấp chiều dài của chuỗi như năng lực của Dictionary, nhưng nó đòi hỏi phải liệt kê toàn bộ chuỗi một lần nữa.

EDIT: Để giải quyết vấn đề thứ 2, người ta có thể tạo ra các bản sao theo yêu cầu:

open System.Collections.Generic 
let duplicates items = 
    seq { 
     let dict = Dictionary() 
     for item in items do 
      match dict.TryGetValue item with 
      | true, 2 ->() 
      | true, 1 -> dict.[item] <- 2; yield item 
      | _ -> dict.[item] <- 1 
    } 

Answer 3

giải pháp chức năng:

let duplicates items = 
    let test (unique, result) v = 
    if not(unique |> Set.contains v) then (unique |> Set.add v ,result) 
    elif not(result |> Set.contains v) then (unique,result |> Set.add v) 
    else (unique, result) 
    items |> Seq.fold test (Set.empty, Set.empty) |> snd |> Set.toSeq 

Answer 4

Đây là giải pháp "chức năng" tốt nhất mà tôi có thể đưa ra mà không tiêu thụ toàn bộ chuỗi lên phía trước.

let duplicates = 
    Seq.scan (fun (out, yielded:Set<_>, seen:Set<_>) item -> 
     if yielded.Contains item then 
      (None, yielded, seen) 
     else 
      if seen.Contains item then 
       (Some(item), yielded.Add item, seen.Remove item) 
      else 
       (None, yielded, seen.Add item) 
    ) (None, Set.empty, Set.empty) 
    >> Seq.Choose (fun (x,_,_) -> x) 

Answer 5

Một giải pháp chức năng thanh lịch hơn:

let duplicates xs = 
    Seq.scan (fun xs x -> Set.add x xs) Set.empty xs 
    |> Seq.zip xs 
    |> Seq.choose (fun (x, xs) -> if Set.contains x xs then Some x else None) 

Sử dụng scan để tích lũy bộ của tất cả các yếu tố thấy cho đến nay. Sau đó, sử dụng zip để kết hợp từng phần tử với tập hợp các phần tử trước đó. Cuối cùng, sử dụng choose để lọc ra các phần tử nằm trong tập hợp các phần tử đã xem trước đó, tức là các bản sao.

EDIT

Thực ra câu trả lời ban đầu của tôi là hoàn toàn sai. Thứ nhất, bạn không muốn bản sao trong kết quả đầu ra của bạn. Thứ hai, bạn muốn hiệu suất.

Dưới đây là một giải pháp hoàn toàn chức năng mà thực hiện các thuật toán bạn đang sau:

let duplicates xs = 
    (Map.empty, xs) 
    ||> Seq.scan (fun xs x -> 
     match Map.tryFind x xs with 
     | None -> Map.add x false xs 
     | Some false -> Map.add x true xs 
     | Some true -> xs) 
    |> Seq.zip xs 
    |> Seq.choose (fun (x, xs) -> 
     match Map.tryFind x xs with 
     | Some false -> Some x 
     | None | Some true -> None) 

này sử dụng một bản đồ để theo dõi xem mỗi yếu tố đã được thấy trước đây một lần hoặc nhiều lần và sau đó phát ra nguyên tố này nếu nó được nhìn thấy chỉ được nhìn thấy một lần trước đây, tức là lần đầu tiên nó được nhân đôi.

Đây là một phiên bản cấp bách nhanh hơn:

let duplicates (xs: _ seq) = 
    seq { let d = System.Collections.Generic.Dictionary(HashIdentity.Structural) 
     let e = xs.GetEnumerator() 
     while e.MoveNext() do 
      let x = e.Current 
      let mutable seen = false 
      if d.TryGetValue(x, &seen) then 
      if not seen then 
       d.[x] <- true 
       yield x 
      else 
      d.[x] <- false } 

Đây là khoảng 2 × nhanh hơn so với bất kỳ câu trả lời khác của bạn (ở thời điểm viết bài).

Sử dụng một vòng lặp for x in xs do để liệt kê các yếu tố trong một chuỗi là chậm hơn đáng kể so với sử dụng GetEnumerator trực tiếp nhưng tạo Enumerator riêng của bạn không phải là đáng kể nhanh hơn so với sử dụng một biểu thức tính toán với yield.

Lưu ý rằng TryGetValue viên của Dictionary cho phép tôi để tránh phân bổ trong vòng lặp bên trong bằng cách biến đổi một giá trị stack giao trong khi các thành viên TryGetValue phần mở rộng được cung cấp bởi F # (và được sử dụng bởi kvb trong/câu trả lời của mình) phân bổ tuple trở lại của mình.