「Example9.3」の編集履歴（バックアップ）一覧はこちら
「Example9.3」(2011/02/24 (木) 08:46:47) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
#co(){
9.3 Example: Merge sort
The insertion sort presented earlier in this chapter is simple to formulate, but also not very efficient. It's average complexity is proportional to the square of the length of the input list. We now design a program to sort the elements of a list which is more efficient than insertion sort. A good algorithm for this is merge sort, which works as follows.
}
** 9.3 例 : マージソート (Merge sort)
この章で前に示した挿入ソートは、書くのは簡単ですがあまり効率的ではありません。その平均的な計算量は入力リストの長さの２乗に比例します。さて、挿入ソートより効率的にリスト要素をソートするプログラムをデザインしましょう。そのためのよいアルゴリズムは&bold(){マージソート}です。次のように動きます。
#co(){
First, if the list has zero or one elements, it is already sorted, so one returns the list unchanged. Longer lists are split into two sub-lists, each containing about half the elements of the original list. Each sub-list is sorted by a recursive call to the sort function, and the resulting two sorted lists are then combined in a merge operation.
}
はじめに、もしリストが０個あるいは１個の要素を持つなら、それはすでにソートされているので、そのままリストを返します。長いリストは２つのサブリストに分割され、それぞれが元のリストの半分の要素を含むようにします。各サブリストはソート関数への再帰呼び出しでソートされ、得られる２つのソート済みリストは、マージ操作にて結合されます。
#co(){
For a general implementation of merge sort, we still have to specify the type of list elements to be sorted, as well as the function to be used for the comparison of elements. We obtain a function of maximal generality by passing these two items as parameters. This leads to the following implementation.}
マージソートを汎用的な実装とするために、ソートされるリストの要素型だけではなく、要素の比較に使う関数も指定できるようにすべきです。それら２つの要素を引数として渡すことで、可能な限り汎用性のある関数が得られます。以上から次の実装を得ます。
def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {
def merge(xs1: List[A], xs2: List[A]): List[A] =
if (xs1.isEmpty) xs2
else if (xs2.isEmpty) xs1
else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
else xs2.head :: merge(xs1, xs2.tail)
val n = xs.length/2
if (n == 0) xs
else merge(msort(less)(xs take n), msort(less)(xs drop n))
}
#co(){
The complexity of msort is O(Nlog(N)), where N is the length of the input list. To see why, note that splitting a list in two and merging two sorted lists each take time proportional to the length of the argument list(s). Each recursive call of msort halves the number of elements in its input, so there are O(log(N)) consecutive recursive calls until the base case of lists of length 1 is reached. However, for longer lists each call spawns off two further calls. Adding everything up we obtain that at each of the O(log(N)) call levels, every element of the original lists takes part in one split operation and in one merge operation. Hence, every call level has a total cost proportional to O(N). Since there are O(log(N)) call levels, we obtain an overall cost of O(Nlog(N)). That cost does not depend on the initial distribution of elements in the list, so the worst case cost is the same as the average case cost. This makes merge sort an attractive algorithm for sorting lists.
Here is an example how msort is used.
}
msort の計算量は O(N log (N))、ただし N は入力リストの長さです。理由を見てみます。リストを二つに分割し、ソートされた２つのリストをマージするには、それぞれに引数のリストの長さに比例した時間を要します。msort の再帰呼び出しの度に入力の要素数は半分になり、リスト長が１に達するまでに O(log (N)) 回の再帰呼び出しが行われます。しかし長い方のリストについては、各呼び出しで更に２回の呼び出しが生じます。すべてを足し合わせると、O(log(N)) 回の呼び出しレベルのそれぞれに対して、元のリストの全要素が１回の分割操作と１回のマージ操作に関わります。すなわち各呼び出しレベルは、全部で O(N) に比例するコストがかかります。O(log(N)) の呼び出しレベルがあるため、全体で O(N log(N)) のコストとなります。このコストはリストの要素の初期分布には依存せず、最悪ケースのコストは平均ケースと同じです。このためマージソートは、リストのソートとして魅力的なアルゴリズムです。
次は msort を使う例です。
msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
#co(){
The definition of msort is curried, to make it easy to specialize it with particular comparison functions. For instance,
}
msort の定義はカリー化されていて、特定の比較関数を使って簡単に特化できます。たとえば
val intSort = msort((x: Int, y: Int) => x < y)
val reverseSort = msort((x: Int, y: Int) => x > y)
#center(){[[前ページ>Example9.2]] [[ 9 章>Chapter 9 Lists]] [[目次>ScalaByExample和訳]] [[次ページ>Example9.4]]}
----
#comment
#co(){
9.3 Example: Merge sort
The insertion sort presented earlier in this chapter is simple to formulate, but also not very efficient. It's average complexity is proportional to the square of the length of the input list. We now design a program to sort the elements of a list which is more efficient than insertion sort. A good algorithm for this is merge sort, which works as follows.
}
#setmenu2(ex-r-menu)
** 9.3 例 : マージソート (Merge sort)
この章で前に示した挿入ソートは、書くのは簡単ですがあまり効率的ではありません。その平均的な計算量は入力リストの長さの２乗に比例します。さて、挿入ソートより効率的にリスト要素をソートするプログラムをデザインしましょう。そのためのよいアルゴリズムは&bold(){マージソート}です。次のように動きます。
#co(){
First, if the list has zero or one elements, it is already sorted, so one returns the list unchanged. Longer lists are split into two sub-lists, each containing about half the elements of the original list. Each sub-list is sorted by a recursive call to the sort function, and the resulting two sorted lists are then combined in a merge operation.
}
はじめに、もしリストが０個あるいは１個の要素を持つなら、それはすでにソートされているので、そのままリストを返します。長いリストは２つのサブリストに分割され、それぞれが元のリストの半分の要素を含むようにします。各サブリストはソート関数への再帰呼び出しでソートされ、得られる２つのソート済みリストは、マージ操作にて結合されます。
#co(){
For a general implementation of merge sort, we still have to specify the type of list elements to be sorted, as well as the function to be used for the comparison of elements. We obtain a function of maximal generality by passing these two items as parameters. This leads to the following implementation.}
マージソートを汎用的な実装とするために、ソートされるリストの要素型だけではなく、要素の比較に使う関数も指定できるようにすべきです。それら２つの要素をパラメータとして渡すことで、可能な限り汎用性のある関数が得られます。以上から次の実装を得ます。
def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {
def merge(xs1: List[A], xs2: List[A]): List[A] =
if (xs1.isEmpty) xs2
else if (xs2.isEmpty) xs1
else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
else xs2.head :: merge(xs1, xs2.tail)
val n = xs.length/2
if (n == 0) xs
else merge(msort(less)(xs take n), msort(less)(xs drop n))
}
#co(){
The complexity of msort is O(Nlog(N)), where N is the length of the input list. To see why, note that splitting a list in two and merging two sorted lists each take time proportional to the length of the argument list(s). Each recursive call of msort halves the number of elements in its input, so there are O(log(N)) consecutive recursive calls until the base case of lists of length 1 is reached. However, for longer lists each call spawns off two further calls. Adding everything up we obtain that at each of the O(log(N)) call levels, every element of the original lists takes part in one split operation and in one merge operation. Hence, every call level has a total cost proportional to O(N). Since there are O(log(N)) call levels, we obtain an overall cost of O(Nlog(N)). That cost does not depend on the initial distribution of elements in the list, so the worst case cost is the same as the average case cost. This makes merge sort an attractive algorithm for sorting lists.
Here is an example how msort is used.
}
msort の計算量は O(N log (N))、ただし N は入力リストの長さです。理由を見てみます。リストを二つに分割し、ソートされた２つのリストをマージするには、それぞれに引数のリストの長さに比例した時間を要します。msort の再帰呼び出しの度に入力の要素数は半分になり、リスト長が１に達するまでに O(log (N)) 回の再帰呼び出しが行われます。しかし長い方のリストについては、各呼び出しで更に２回の呼び出しが生じます。すべてを足し合わせると、O(log(N)) 回の呼び出しレベルのそれぞれに対して、元のリストの全要素が１回の分割操作と１回のマージ操作に関わります。すなわち各呼び出しレベルは、全部で O(N) に比例するコストがかかります。O(log(N)) の呼び出しレベルがあるため、全体で O(N log(N)) のコストとなります。このコストはリストの要素の初期分布には依存せず、最悪ケースのコストは平均ケースと同じです。このためマージソートは、リストのソートとして魅力的なアルゴリズムです。
次は msort を使う例です。
msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
#co(){
The definition of msort is curried, to make it easy to specialize it with particular comparison functions. For instance,
}
msort の定義はカリー化されていて、特定の比較関数を使って簡単に特化できます。たとえば
val intSort = msort((x: Int, y: Int) => x < y)
val reverseSort = msort((x: Int, y: Int) => x > y)
#center(){[[前ページ>Example9.2]] [[ 9 章>Chapter 9 Lists]] [[目次>ScalaByExample和訳]] [[次ページ>Example9.4]]}
----
#comment
