2011-08-07 103 views
13

不通過索引處理集合的優點之一是避免逐個錯誤。這當然不是唯一的優勢,但它是其中之一。滑動一個關閉?

現在,我經常使用Scala的一些算法sliding,但我覺得它通常會導致非常相似的off-by-一個錯誤的東西,因爲大小n的集合中msliding元素有大小n - m + 1元素。或者更簡單地說,list sliding 2是比list更短的一個元素。

我得到的感覺是在這種模式下有一個缺失的抽象,其中一部分是sliding,部分是更多的東西 - 比如foldLeftreduceLeft。然而,我想不出可能是什麼。任何人都可以幫我在這裏找到啓發嗎?

UPDATE

由於人們尚不清楚一個我在說什麼,讓我們考慮這種情況。我想大寫一個字符串。基本上,每封不是字母的字母應該是大寫字母,其他所有字母應該是小寫字母。使用sliding,我必須特殊情況下的第一個或最後一個字母。例如:

def capitalize(s: String) = s(0).toUpper +: s.toSeq.sliding(2).map { 
    case Seq(c1, c2) if c2.isLetter => if (c1.isLetter) c2.toLower else c2.toUpper 
    case Seq(_, x) => x 
}.mkString 
+0

有趣...您的具體的例子聽起來好像是一個狀態機將是適當的(你可以做那些簡潔scala?),如果你想要「滑動」的某些功能,那麼你也需要預測 - 這聽起來像一個解析器。這也意味着我不知道足以回答你的問題:)(從我讀過的微小的一點聽起來像一個類似迭代的模式可能會有幫助,所以你可能會考慮這一點,但我真的不知道)。 – Owen

+0

或者可能的方式來說,它是你需要做第一個特例,因爲它*是一個特殊情況,即它將很好有一個代表字符串的開始,這使得這個聲音甚至更像是一個狀態機/解析器。 – Owen

+0

我同意歐文:問題描述特殊情況下的第一個字符,所以代碼也需要。以下是我如何閱讀問題陳述:「如果(a)是第一個字符,或者(b)跟隨字母字符,則將每個字符都大寫」。第一個字符的行爲需要特別定義。 –

回答

2

我碰到這個問題,所有的時間在Python/R/Matlab的,你diff的()向量,然後不能與原來的一條線吧!這是非常令人沮喪的。

我認爲什麼是真正缺少的是矢量只持有依賴變量,並假定您,程序員,被跟蹤的獨立變量,即收集範圍過尺寸。

我認爲解決這個問題的方法是讓語言在一定程度上跟蹤自變量;也許靜態地通過類型,或者通過將它們與矢量一起存儲來動態化。然後它可以檢查獨立的軸,確保它們排隊,或者,我不知道這是否可能,將其混合到使他們排隊。

這是迄今爲止我所想過的最好的。

編輯

另一種考慮這種方式的方法是,爲什麼你的集合有秩序?爲什麼它不只是一個集?這個順序意味着某種東西,但是這個集合並沒有跟蹤它 - 它基本上是使用順序位置(它和數字指數一樣具有信息性)來代表真正的意義。

編輯

另一個後果是,像sliding轉變實際上代表轉變,一個因變量,一個是自己的軸。

6

我把歐文的answer作爲一個靈感。

當您想將簡單的diff()應用於列表時,可以將其視爲等同於以下矩陣乘法。

a = (0 1 4 3).T 

M = (1 -1 0 0) 
    (0 1 -1 0) 
    (0 0 1 -1) 

diff(a) = M * a = (1 3 1).T 

現在我們可以使用一般列表操作相同的方案,如果我們更換加法和乘法(如果我們在矩陣M概括數字)。

所以,用加上作爲一個列表追加操作(與flatten事後 - 或簡稱爲collect操作),和乘法當量爲或者Some(_)None,具有二的窗口尺寸的滑動變成:

M = (Some(_) Some(_) None None) 
    (None Some(_) Some(_) None) 
    (None None Some(_) Some(_)) 

slide(a) = M 「*」 a = ((0 1) (1 4) (4 3)).T 

不確定,如果這是您正在尋找的抽象類型,但它將是一類改變項目數量的操作的泛化。的順序爲長度Ñ的輸入

diffslide操作將需要使用大小N-M + 1×N矩陣。


編輯:的溶液可能是變換到List[A]List[Some[A]],然後預先考慮或追加(slideLeftslideRight)這些與None。這樣你就可以處理map方法中的所有魔法。

list.slideLeft(2) { 
    case Seq(Some(c1), Some(c2)) if c2.isLetter => if (c1.isLetter) c2.toLower else c2.toUpper 
    case Seq(_, Some(x)) => x 
} 
+0

非常酷,雖然這不是我想要的。我認爲項目數量的變化是問題 - 它揭示了第一個或最後一個元素是一個例外情況。 –

1

關閉接一個錯誤,建議你嘗試把原來的列表中一個一一對應與滑動列表,但一些奇怪的事情,因爲滑動列表中有較少的元素。

您的示例中的問題陳述可粗略地表述爲:「如果它(a)是第一個字符或(b)跟隨字母字符,則將每個字符大寫」。正如歐文指出的那樣,第一個字符是一個特例,任何抽象都應該尊重這一點。這是一個可能性,

def slidingPairMap[A, B](s: List[A], f1: A => B, f2: (A, A) => B): List[B] = s match { 
    case Nil => Nil 
    case x :: _ => f1(x) +: s.sliding(2).toList.map { case List(x, y) => f2(x, y) } 
} 

(不是最好的實現,但你明白了)。這概括爲滑動三元組,以及兩個錯誤,等等。 slidingPairMap的類型清楚表明特殊外殼正在完成。

的等效簽名可能是

def slidingPairMap[A, B](s: List[A], f: Either[A, (A, A)] => B): List[B] 

然後f可以使用模式匹配來找出是否它的工作與第一元件,或與隨後的一個。


或者,正如歐文在評論中說,爲什麼不修改sliding方法,提供有關該元素是否是第一或沒有信息,

def slidingPairs[A](s: List[A]): List[Either[A, (A, A)]] 

我想這最後的想法是同構Debilski在評論中提出的建議是:用None替代列表的開頭,用Some包裝所有現有元素,然後致電sliding

+1

不錯。或者,也許另一種基本相同的做法是應用初始轉換,將每個元素都帶到First Char | NotFirst Char Char',那麼調用者可以在那裏進行模式匹配。 – Owen

+0

'slidingPairMap'看起來像一個'fold'(變形)。我懷疑我想要的是這種方式,的確如此。 –

1

你所描述的一個問題的關閉提醒我在數字信號處理中的邊界條件問題。由於數據(列表)是有限的,因此出現問題。它不會發生無限數據(流)。在數字信號處理中,通過將有限信號擴展到無限信號來解決問題。這可以通過重複數據或重複數據並在每次重複時反轉(如離散餘弦變換)來完成。

從這些接近用於滑動借貸將導致其不被一個問題呈現關斷一個抽象:

(1::2::3::Nil).sliding(2) 

將產生

(1,2), (2,3), (3,1) 

爲圓形的邊界條件和

(1,2), (2,3), (3,2) 

對於具有反轉的圓形邊界條件。

0

我會在與Some(_)映射元素之後預先設置無;注意這樣做的明顯方式(在默認情況下匹配兩個Some,如Debilski編輯所做的)是錯誤的,因爲我們必須能夠修改第一個字母。這樣,抽象就尊重這樣一個事實,即有時候不存在前任。使用getOrElse(false)可確保將缺失的前任視爲未通過測試。

((None +: "foo1bar".toSeq.map(Some(_))) sliding 2).map { 
    case Seq(c1Opt, Some(c2)) if c2.isLetter => if (c1Opt.map(_.isLetter).getOrElse(false)) c2.toLower else c2.toUpper 
    case Seq(_, Some(x)) => x 
}.mkString 
res13: String = "Foo1Bar" 

致謝:映射與Some(_)元素的想法是通過Debilski的帖子來找我。

2

在你的例子中,我認爲代碼變得更加複雜,因爲你基本上想要做一個map,但是使用sliding,它引入了邊緣條件,這種方式不能很好地工作。我想留下一個蓄電池摺疊可以記住有關國家可能更容易從概念上:

def capitalize2(s: String) = (("", true) /: s){ case ((res, notLetter), c) => 
    (res + (if (notLetter) c.toUpper else c.toLower), !c.isLetter) 
}._1 

我認爲這可能是廣義的,這樣notLetter能記住n元素,其中n爲滑動窗口的大小。

2

您所要求的轉換固有地減少了數據的大小。對不起 - 沒有其他方法可以查看它。 tail也給你一個錯誤的錯誤。

現在,您可能會說 - 很好,但我想要一種方便的方法來保持原始尺寸。

在這種情況下,你可能想在List這些方法:

initializedSliding(init: List[A]) = (init ::: this).sliding(1 + init.length) 
finalizedSliding(tail: List[A]) = (this ::: tail).sliding(1 + tail.length) 

,這將維持您的列表長度。 (你可以設想如何推廣到非列表,我敢肯定。)

這是模擬左/右摺疊,因爲您提供缺少的數據,以便執行成對(或更多)操作列表中的每個元素。

0

我不確定這是否解決了您的具體問題,但我們可以輕鬆想象一對方法,例如slidingFromLeft(z: A, size: Int)slidingToRight(z: A, size: Int)(其中A是集合的元素類型),當它在例如

List(1, 2, 3, 4, 5) 

帶有參數例如(0,3),應產生分別

List(0, 0, 1), List(0, 1, 2), List(1, 2, 3), List(2, 3, 4), List(3, 4, 5) 

List(1, 2, 3), List(2, 3, 4), List(3, 4, 5), List(4, 5, 0), List(5, 0, 0) 
0

這是這類問題很好地適合於像J.基本上面向陣列官能語言,我們生成用布爾一個對應每個單詞的第一個字母。爲此,我們從一個布爾值標記字符串中的空格開始。例如(行縮進三個空間是輸入;結果與左邊距沖洗;「NB.」開始的註釋):

str=. 'now is the time' NB. Example w/extra spaces for interest 
    ]whspc=. ' '=str    NB. Mark where spaces are=1 
0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 

驗證(*.-.)(「而不是」)返回一個只對「1 0」:

]tt=. #:i.4      NB. Truth table 
0 0 
0 1 
1 0 
1 1 
    (*.-.)/"1 tt     NB. Apply to 1-D sub-arrays (rows) 
0 0 1 0       NB. As hoped. 

滑入布爾跨越對我們的默契功能:

2(*.-.)/\whspc     NB. Apply to 2-ples 
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 

但這不處理的首字母的邊緣狀態,所以強迫一個INT o第一個位置。這實際上有助於減少2個電阻讓我們短路。在這裏,我們比較原始布爾的長度和目標布爾:

#whspc 
20 
    #1,2(*.-.)/\whspc 
20 
    1,2(*.-.)/\whspc 
1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 

我們得到大寫使用的索引,小寫載體從大寫矢量選擇(定義這兩個向量後):

'lc uc'=. 'abcdefghijklmnopqrstuvwxyz';'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 
    (uc,' '){~lc i. str 
NOW IS THE TIME 

檢查插入布爾給出正確的結果:

 (1,2(*.-.)/\whspc) } str,:(uc,' '){~lc i. str 
Now Is The Time 

現在是這一切組合成一個語句的時候:

(1,2(*.-.)/\' '=str) } str,:(uc,' '){~lc i. str 
Now Is The Time 
1

我意識到這是一個老問題,但我只是有類似的問題,我想解決它,而無需追加或預先準備任何東西,它會處理序列的最後一個元素以無縫方式。我想出的方法是slidingFoldLeft。你必須把第一個元素作爲一個特殊情況來處理(就像其他人提到的那樣,對於大寫字母,這是一個特殊情況),但是對於序列的結尾,你可以像處理其他情況一樣處理它。下面是實現和一些愚蠢的例子:

def slidingFoldLeft[A, B] (seq: Seq[A], window: Int)(acc: B)(
    f: (B, Seq[A]) => B): B = { 
    if (window > 0) { 
    val iter = seq.sliding(window) 
    iter.foldLeft(acc){ 
     // Operate normally 
     case (acc, next) if iter.hasNext => f(acc, next) 
     // It's at the last <window> elements of the seq, handle current case and 
     // call recursively with smaller window 
     case (acc, next) => 
     slidingFoldLeft(next.tail, window - 1)(f(acc, next))(f) 
    } 
    } else acc 
} 

def capitalizeAndQuestionIncredulously(s: String) = 
    slidingFoldLeft(s.toSeq, 2)("" + s(0).toUpper) { 
    // Normal iteration 
    case (acc, Seq(c1, c2)) if c1.isLetter && c2.isLetter => acc + c2.toLower 
    case (acc, Seq(_, c2)) if c2.isLetter    => acc + c2.toUpper 
    case (acc, Seq(_, c2))        => acc + c2 
    // Last element of string 
    case (acc, Seq(c)) => acc + "?!" 
    } 

def capitalizeAndInterruptAndQuestionIncredulously(s: String) = 
    slidingFoldLeft(s.toSeq, 3)("" + s(0).toUpper) { 
    // Normal iteration 
    case (acc, Seq(c1, c2, _)) if c1.isLetter && c2.isLetter => acc + c2.toLower 
    case (acc, Seq(_, c2, _)) if c2.isLetter    => acc + c2.toUpper 
    case (acc, Seq(_, c2, _))        => acc + c2 
    // Last two elements of string 
    case (acc, Seq(c1, c2)) => acc + " (commercial break) " + c2 
    // Last element of string 
    case (acc, Seq(c)) => acc + "?!" 
    } 

println(capitalizeAndQuestionIncredulously("hello my name is mAtthew")) 
println(capitalizeAndInterruptAndQuestionIncredulously("hello my name is mAtthew")) 

和輸出:

Hello My Name Is Matthew?! 
Hello My Name Is Matthe (commercial break) w?!