Tắt bằng cách trượt?

Question

Một trong những ưu điểm của việc không xử lý các bộ sưu tập thông qua các chỉ mục là tránh các lỗi off-by-one. Đó chắc chắn không phải là lợi thế duy nhất, nhưng nó là một trong số đó.

Bây giờ, tôi thường sử dụng sliding trong một số thuật toán trong Scala, nhưng tôi cảm thấy rằng nó thường dẫn đến một cái gì đó rất giống với off-by-one lỗi, bởi vì một sliding của m yếu tố trong một tập hợp các kích thước n có kích thước n - m + 1 yếu tố. Hoặc, trivially hơn, list sliding 2 là một phần tử ngắn hơn list.

Cảm giác tôi nhận được là có sự trừu tượng bị thiếu trong mẫu này, thứ gì đó sẽ là một phần sliding, phần nào đó khác - như foldLeft là reduceLeft. Tôi không thể nghĩ ra cái đó có thể là gì, tuy nhiên. Bất cứ ai có thể giúp tôi tìm thấy sự giác ngộ ở đây?

CẬP NHẬT

Kể từ khi mọi người không ai rõ ràng những gì tôi đang nói, chúng ta hãy xem xét trường hợp này. Tôi muốn viết hoa một chuỗi. Về cơ bản, mọi chữ cái không có chữ cái trước phải là chữ hoa, và tất cả các chữ cái khác phải là chữ thường. Sử dụng sliding, tôi phải viết hoa chữ cái đầu tiên hoặc chữ cái cuối cùng. Ví dụ:

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 

Answer 1

Tôi gặp phải sự cố này trong python/R/Matlab nơi bạn khác() một vectơ và sau đó không thể xếp hàng nó với bản gốc! Nó rất bực bội.

Tôi nghĩ rằng những gì thực sự mất tích là véc tơ chỉ giữ phụ thuộc biến, và giả định rằng bạn, các lập trình viên, đang theo dõi các biến độc lập, tức là kích thước mà bộ sưu tập dao động trên.

Tôi nghĩ cách giải quyết điều này là phải có ngôn ngữ ở một mức độ nào đó để theo dõi các biến độc lập; có lẽ tĩnh thông qua các loại, hoặc động bằng cách lưu trữ chúng cùng với vectơ. Sau đó, nó có thể kiểm tra các trục độc lập, đảm bảo rằng chúng xếp hàng hoặc tôi không biết liệu điều này có thể hay không, trộn các thứ xung quanh thành tạo thành chúng xếp hàng.

Đó là điều tốt nhất tôi đã nghĩ đến từ trước tới nay.

EDIT

Một cách khác để nghĩ về điều này là, tại sao bộ sưu tập của bạn có thứ tự? Tại sao nó không chỉ là một Set? Thứ tự có nghĩa là một cái gì đó, nhưng bộ sưu tập không theo dõi điều đó - về cơ bản nó sử dụng vị trí tuần tự (mà là về thông tin như các chỉ số số) để proxy cho ý nghĩa thực sự.

EDIT

hậu quả khác là rằng biến đổi như sliding thực sự đại diện cho hai biến đổi, một cho các biến phụ thuộc, và một cho trục của họ.

Answer 2

Tôi đang dùng Owen’s answer làm nguồn cảm hứng cho điều này.

Khi bạn muốn áp dụng đơn giản diff() vào danh sách, điều này có thể được xem là tương đương với phép nhân ma trận sau.

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 

Bây giờ chúng ta có thể sử dụng chương trình tương tự cho các hoạt động danh sách chung, nếu chúng ta thay thế bổ sung và phép nhân (và nếu chúng ta khái quát hóa số trong ma trận M của chúng tôi).

Như vậy, với cộng trở thành một hoạt động danh sách append (với flatten sau đó - hoặc đơn giản là một hoạt động collect), và tương đương với số nhân là một trong hai Some(_) hoặc None, một slide với một kích thước cửa sổ của hai trở thành:

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

slide(a) = M “*” a = ((0 1) (1 4) (4 3)).T 

Không chắc chắn, nếu đây là loại trừu tượng bạn đang tìm kiếm, nhưng nó sẽ là một khái quát về một loại hoạt động mà thay đổi số lượng các mặt hàng.

diff hoặc slide hoạt động của trật tự m cho một đầu vào có độ dài n sẽ cần phải sử dụng Khuôn kích thước n-m + 1 × n.

---

Edit: Một giải pháp có thể được chuyển đổi List[A] để List[Some[A]] và sau đó để thêm vào trước hoặc nối thêm (slideLeft hoặc slideRight) này với None. Bằng cách đó bạn có thể xử lý tất cả phép thuật bên trong phương thức 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 
} 

Answer 3

Off-by-one lỗi cho thấy rằng bạn đang cố gắng để đưa danh sách ban đầu trong one-to-one tương ứng với danh sách trượt, nhưng một cái gì đó kỳ lạ đang xảy ra, kể từ khi danh sách trượt có yếu tố ít hơn.

Tuyên bố vấn đề cho ví dụ của bạn có thể được nói gần như là: "Viết hoa mỗi ký tự nếu ký tự đầu tiên (a) là ký tự đầu tiên hoặc (b) theo ký tự chữ cái". Như Owen điểm, nhân vật đầu tiên là một trường hợp đặc biệt, và bất kỳ trừu tượng nên tôn trọng điều này. Đây là một khả năng,

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) } 
} 

(không thực hiện tốt nhất, nhưng bạn có ý tưởng). Điều này khái quát hóa để trượt ba, với lỗi off-by-two, và như vậy. Loại slidingPairMap làm cho nó rõ ràng rằng vỏ đặc biệt đang được thực hiện.

Một chữ ký tương đương có thể là

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

Sau đó f có thể sử dụng mô hình phù hợp để tìm ra nếu nó làm việc với các yếu tố đầu tiên, hoặc với một tiếp theo.

---

Hoặc, như Owen nói trong các ý kiến, tại sao không làm một sửa đổi sliding phương pháp cung cấp thông tin về việc liệu các phần tử là lần đầu tiên hay không,

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

Tôi đoán ý tưởng cuối cùng này là đẳng cấu với những gì Debilski gợi ý trong các ý kiến: pad đầu danh sách với Không, bọc tất cả các phần tử hiện có với Some, và sau đó gọi sliding.

Answer 4

Tắt bởi một sự cố bạn mô tả nhắc tôi về vấn đề điều kiện biên trong xử lý tín hiệu kỹ thuật số. Vấn đề xảy ra vì dữ liệu (danh sách) là hữu hạn. Nó không xảy ra cho dữ liệu vô hạn (stream). Trong xử lý tín hiệu số, các vấn đề được khắc phục bằng cách mở rộng tín hiệu hữu hạn đến một tín hiệu vô hạn. Điều này có thể được thực hiện theo nhiều cách khác nhau như lặp lại dữ liệu hoặc lặp lại dữ liệu và đảo ngược nó trên mọi sự lặp lại (giống như nó được thực hiện cho phép biến đổi cosin rời rạc).

Vay từ những tiếp cận cho trượt sẽ dẫn đến một sự trừu tượng mà không biểu hiện tắt bởi một vấn đề:

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

sẽ mang lại

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

cho điều kiện biên tròn và

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

cho điều kiện biên tròn có đảo ngược.

Answer 5

Tôi sẽ thêm tiền vào Không sau khi ánh xạ với Some(_) các phần tử; lưu ý rằng cách rõ ràng để thực hiện nó (khớp với hai Some trong trường hợp mặc định, như được thực hiện trong chỉnh sửa bởi Debilski) là sai, vì chúng ta phải có khả năng sửa đổi ngay cả chữ cái đầu tiên. Bằng cách này, sự trừu tượng tôn trọng thực tế rằng chỉ đơn giản là đôi khi không có người tiền nhiệm. Sử dụng getOrElse(false) đảm bảo rằng người tiền nhiệm bị thiếu được coi là đã thất bại trong thử nghiệm.

((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" 

Lời cảm ơn: ý tưởng lập bản đồ các thành phần với Some(_) đã đến với tôi qua bài đăng của Debilski.

Answer 6

Trong ví dụ của bạn, tôi nghĩ rằng mã được làm phức tạp hơn, về cơ bản bạn muốn làm map nhưng làm việc với sliding giới thiệu các điều kiện cạnh theo cách không hoạt động tốt. Tôi nghĩ rằng một lần trái với một ắc mà nhớ trạng thái liên quan có thể được dễ dàng hơn khái niệm:

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

Tôi nghĩ rằng điều này có thể được khái quát hóa để notLetter thể nhớ n yếu tố trong đó n là kích thước của cửa sổ trượt.

Answer 7

Biến đổi bạn đang yêu cầu làm giảm kích thước dữ liệu vốn có. Xin lỗi - không có cách nào khác để nhìn vào nó. tail cũng cung cấp cho bạn các lỗi ngoại tuyến.

Bây giờ, bạn có thể nói - tốt, tốt, nhưng tôi muốn có một phương pháp tiện lợi để duy trì kích thước ban đầu.

Trong trường hợp đó, bạn có thể muốn những phương pháp trên List:

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

mà sẽ duy trì chiều dài danh sách của bạn. (Bạn có thể hình dung cách khái quát hóa thành các danh sách không, tôi chắc chắn.)

Đây là điểm tương tự để gấp trái/phải ở chỗ bạn cung cấp dữ liệu còn thiếu để thực hiện thao tác theo cặp (hoặc nhiều hơn) mọi phần tử trong danh sách.

Answer 8

Tôi không chắc liệu điều này có giải quyết được vấn đề cụ thể của bạn hay không, nhưng chúng tôi có thể dễ dàng hình dung một cặp phương pháp, ví dụ:slidingFromLeft(z: A, size: Int) và slidingToRight(z: A, size: Int) (trong đó A là loại phần tử của bộ sưu tập), khi được gọi, ví dụ:

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

với các đối số, ví dụ: (0, 3), nên sản xuất tương ứng

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

và

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

Answer 9

Đây là loại vấn đề độc đáo-phù hợp với một ngôn ngữ chức năng mảng theo định hướng như J. Về cơ bản, chúng tôi tạo ra một boolean với một chữ cái tương ứng với chữ cái đầu tiên của mỗi từ. Để làm điều này, chúng ta bắt đầu với một boolean đánh dấu các dấu cách trong một chuỗi. Ví dụ (dòng thụt vào ba chỗ là đầu vào, kết quả là ngang bằng với lề trái; "NB." bắt đầu một bình luận):

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 

Xác minh rằng (*.-.) ("chứ không phải") trả về chỉ duy nhất có "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. 

Trượt chức năng ngầm của chúng tôi qua cặp trong boolean:

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 

Nhưng điều này không xử lý các điều kiện cạnh của bức thư ban đầu, vì vậy buộc một int o vị trí đầu tiên. Điều này thực sự giúp làm giảm 2-ples lại cho chúng tôi một ngắn. Ở đây chúng ta so sánh độ dài của boolean gốc và boolean mục tiêu:

#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 

Chúng tôi nhận được chữ hoa bằng cách sử dụng các chỉ số vào vector chữ thường để chọn từ các vector hoa (sau khi xác định hai vectơ này):

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

Kiểm tra xem chèn bởi boolean cho kết quả chính xác:

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

Bây giờ là lúc để kết hợp tất cả điều này thành một tuyên bố:

01.

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

Answer 10

Tôi nhận ra đây là một câu hỏi cũ nhưng tôi chỉ có một vấn đề tương tự và tôi muốn giải quyết nó mà không cần phải thêm hoặc thêm bất cứ thứ gì, và nơi nó sẽ xử lý các phần tử cuối cùng một cách liên tục. Cách tiếp cận tôi đưa ra là slidingFoldLeft. Bạn phải xử lý phần tử đầu tiên như một trường hợp đặc biệt (như một số trường hợp khác được đề cập, để viết hoa, nó là trường hợp đặc biệt), nhưng cho đến cuối chuỗi, bạn có thể xử lý nó giống như các trường hợp khác. Đây là việc thực hiện và một số ví dụ ngớ ngẩn:

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")) 

Và kết quả:

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