OCaml的：在對列表計數不同值

我有對OCaml的：在對列表計數不同值

let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)];;

對於計數存在於列表中的每個單個不同值I有此過程

let rec flat lst visited = 
match lst with 
[]->visited 
| (x,y)::xs -> flat xs (x::y::visited)) ;; 


let newLst = flat myList [];; 

val newLst : int list = 
    [4; 3; 5; 6; 5; 4; 3; 5; 2; 4; 1; 5; 0; 3; 0; 2; 0; 1] 

let rec count lista = 
match lista with 
[]->0 
| x::xs -> 
if (List.mem x xs) then count xs 
else 1+count xs;; 

count newLst;; 
- : int = 7

的代碼運行正確的列表，但我的問題是：

有沒有更優雅或高效的方法來做到這一點？ 例如獨特的功能，而不是兩個

來源

2016-01-23 daniele3004

您的方法有效，簡單易懂。它唯一的缺點是你的代碼使用Shlemiel the painter's algorithm。這意味着處理時間表現爲列表大小的二次函數。

如果您想刪除它，則可以使用sets：將列表中的所有數字添加到一個集合並計算其大小。現在時間表現在n log（n）並且縮放好得多。

let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)] 

module IntegerSet = Set.Make(struct 
    type t = int 
    let compare = Pervasives.compare 
    end) 

let count lst0 = 
    let rec loop acc lst = 
    match lst with 
    | [] -> IntegerSet.cardinal acc 
    | (a,b)::tl -> loop IntegerSet.(add b (add a acc)) tl 
    in 
    loop IntegerSet.empty lst0

該代碼使用的累加器ACC 其通過在列表上進行迭代填充。當所有列表都被讀取後，返回累加器中的元素數量。

來源

2016-01-23 12:20:11

非常有趣的解決方案 – daniele3004

優雅不具有特定的含義，所以很難回答。

我認爲這是解決問題的一個合理的方法。如果你認爲你有很多不同的結構（對，樹等列表），那麼將平移列表轉換爲平整列表然後以不同方式處理列表的想法具有良好的感覺。

您的解決方案的一個問題是，它在最壞的情況下是二次的，因爲您正在搜索n對長度爲0,1,2，... n * 2的列表。

我懷疑這不應該是生產代碼，所以計算複雜性可能無關緊要。

如果您打算在產品代碼中進行這項工作，其中列表很長且效率非常重要，您可以直接在對列表中進行計數。而且你不會一直在列表中搜索重複項。你會使用某種設置（甚至可能有點像向量一樣）來跟蹤你所看到的內容。很可能這對您的預期用途來說是矯枉過正的（它看起來像是我的班級作業）。

來源

2016-01-23 08:02:54

例如一個獨特的函數，而不是兩個 – daniele3004

您可以編寫一個直接處理對的函數，而不是製作所有值的列表。它會更有效率，因爲它不需要創建中間列表。但優雅和效率往往是衝突:-) –

我不會爲優雅而爭辯...... 寫代碼的不同方式：使用摺疊操作。你平功能，可以這樣寫：

let flat = List.fold_left (fun acc (x,y) -> x::y::acc) [] ;;

來源

2016-01-23 08:17:44

你的解決方案基本上是你如何做到這一點，而不訴諸廣泛的庫函數（並在二次最壞情況下的性能爲代價）。您可以使用List庫中的函數來獲得更簡單的解決方案，但雖然這樣做更簡單一些，但它將主要教您如何使用該庫，而不是將OCaml作爲一種語言[1]。這就是說，這裏的，不只是一個解決方案：

let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)] 

let count l = 
    let open List in 
    let (a, b) = split l in length (sort_uniq compare (a @ b)) 

let() = 
    Printf.printf "=> %d\n" (count myList)

它使用List.split和列表追加操作@把對整數的列表爲整數的列表，然後排序，並刪除重複項（List.sort_uniq），然後使用List.length來計算結果。這由於sort_uniq而在時間O（n * log（n））中運行。

替代的解決方案是使用Set或Hashtbl模塊來跟蹤重複的更高效的方式比List.mem，從而還避免二次最壞情況下的時間（還能令代碼的過程中更復雜）。

[1]我在這裏假設你正在學習OCaml，所以一個工業強度的解決方案並不一定是幫助你學習過程的最好的解決方案，這取決於你的位置。

來源

2016-01-23 08:19:02

OCaml的：在對列表計數不同值

回答

相關問題