get1 [] n = error "List is too small"
get1 xs n|n<0 = error "Use positive numbers"
get1 (x:xs) 0 = x
get1 (x:xs) n = get1 xs (n-1)
我自己制作了函式，但是我對正數的檢查是 O(n)。我該怎么做才能使這個 O(1)？我是haskell的新手，所以請推薦我一些簡單的東西
uj5u.com熱心網友回復：
如果你繼續使用鏈表，你不能做得比 O(n) 更好。所以如果你想要更好，你就必須使用不同的資料結構；對于 O(1)，本質上您唯一的選擇是陣列，但如果您允許自己放松到 O(log n)，則有很多選擇。請記住，對于所有 n，log n < 30。
uj5u.com熱心網友回復：
[Int]是鏈表型別。使用這種資料結構，沒有比遍歷前 N 個元素更快的訪問第 N 個元素的方法了。
如果您get1在另一個函式中使用f并且發現它太慢，您要么需要切換到新的資料結構，要么（非常常見）重寫f以避免get1. 例如，這是一個常見的初學者錯誤：
-- add 10 to each element in the list
add10 :: [Int] -> [Int]
add10 xs = [ 10 get1 xs i | i <- [0 .. length xs-1] ]
此功能“有效”但效率很低。對于長度為 N 的串列，我們為每個 支付 O(N) get1，并且我們進行 O(N) 次這樣的呼叫，總共 O(N^2)，其中直觀地，O(N) 就足夠了。
在這種情況下，解決方案是避免使用索引i而是直接掃描串列。
-- add 10 to each element in the list
add10 :: [Int] -> [Int]
add10 xs = [ 10 x | x <- xs ]
在其他一些語言中，要掃描串列/陣列/序列，我們需要使用索引。在 Haskell 中，這不是正確的做法。
根據經驗，如果您是初學者并開始使用串列，您應該避免length, !!使用大多數情況下的函式。我還建議避免像head, tail. 一般來說，使用遞回和模式匹配、折疊、映射、zip/ zipWith、串列推導等方法可以有效地解決許多問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/387043.html
標籤：哈斯克尔
上一篇：訪問Ziplist中的位置