需要指針來優化Scala中的合併排序實現

我剛剛開始學習Scala和側身我也在做一些算法。下面是Scala中的合併排序實現。我知道它本質上不是「scala」，有些人甚至認爲我曾試圖在scala中編寫java。我對scala並不完全熟悉，我只是知道一些基本的語法，如果我需要更多的東西，我會繼續使用Google搜索。所以請給我一些指導，告訴我在這段代碼中可以做些什麼，使它更加實用，並且符合scala慣例和最佳實踐。請不要只給出正確/優化的代碼，我想自己做。歡迎任何建議！需要指針來優化Scala中的合併排序實現

def mergeSort(list: Array[Int]): Array[Int] = { 
    val len = list.length 
    if (len == 1) list 
    else { 
     var x, y = new Array[Int](len/2) 
     val z = new Array[Int](len) 
     Array.copy(list, 0, x, 0, len/2) 
     Array.copy(list, len/2, y, 0, len/2) 
     x = mergeSort(x) 
     y = mergeSort(y) 
     var i, j = 0 
     for (k <- 0 until len) { 
     if (j >= y.length || (i < x.length && x(i) < y(j))) { 
      z(k) = x(i) 
      i = i + 1 
     } else { 
      z(k) = y(j) 
      j = j + 1 
     } 
     } 
     z 
    } 
    }

[編輯] 此代碼工作正常和我假定現在該輸入陣列將始終是偶數長度的。

UPDATE 刪除瓦爾x和y

def mergeSort(list: Array[Int]): Array[Int] = { 
    val len = list.length 
    if (len == 1) list 
    else { 
     val z = new Array[Int](len) 
     val x = mergeSort(list.dropRight(len/2)) 
     val y = mergeSort(list.drop(len/2)) 
     var i, j = 0 
     for (k <- 0 until len) { 
     if (j >= y.length || (i < x.length && x(i) < y(j))) { 
      z(k) = x(i) 
      i = i + 1 
     } else { 
      z(k) = y(j) 
      j = j + 1 
     } 
     } 
     z 
    } 
    }

來源

2013-07-08 Sikorski

coursera？ :)如果列表爲空，將失敗。如果列表有奇數大小，x和y會有問題 – twillouer

@twillouer是的我指的是coursera的算法研究材料。而對於第二部分列表空奇和所有，我正在努力。現在我已經假定這個列表的長度總是很長（提及的也是這個問題！） – Sikorski

你想優化性能，還是隻想讓它成爲慣用的scala？如果你想學習如何編寫慣用的scala，使用Arrays不是很有幫助。但是，如果你想獲得最大的性能，他們往往沒有辦法。 –

卸下var x,y = ...將是一個良好的開端是功能性的。優先考慮對不可變數據集的不變性。

HINT：一種方法，交換採用兩個值，並返回它們有序使用謂詞

也可以考慮去除for環路（或理解）。

來源

2013-07-08 12:42:12 korefn

我沒有刪除var x，y通過引入兩個新的val x1，y1在每個數組上進行合併排序後，我的擔心是：是最優的？增加no。的vals保持功能？ – Sikorski

它不是增加val的問題，而是減少可變性。功能風格也會將功能分解爲更小更具體（純粹）的單位。可以通過添加部分函數來增強此合併排序，以允許在交換時使用謂詞。交換也可以是一個功能單元。 – korefn

需要指針來優化Scala中的合併排序實現

回答

相關問題