So I want to go back and I want to do another implementation where our input is truly something that we would consider to be a list.

そこでもう一度、私たちのインプットが本当にリストと言えるようなものであるような実装をしたい。

There are a couple of reasons we're doing this, partly it's because of the next thing we're going to look at, which is trying to prove that it's actually correct.

私たちがこのようなことをする理由はいくつかあるが、そのうちのひとつは、私たちが次に見ようとしていること、つまり、それが実際に正しいことを証明しようとしているからだ。

Okay, so let's go back, we'll go through sorting the exact same data we had before.

では、前に戻って、以前とまったく同じデータを並べ替えてみよう。

Whoops, my debugging duck is in the way.

おっと、デバッグのカモが邪魔だ。

So currently we don't have any data, I guess we could consider that to be completely sorted already.

だから、今のところデータはない。もう完全に整理されたと考えていいだろう。

So let's go back and look at the same sort of data set that we had before.

では、前に戻って同じようなデータセットを見てみよう。

Okay, this time I'm going to assume that this is a list.

さて、今回はこれがリストだと仮定する。

I'm going to separate my numbers just to indicate that I don't really mean for this to be an Just like before, we're going to work through from left to right to find our candidate for the lowest value, the minimum.

先ほどと同じように、左から右へ、最低値、最小値の候補を探していく。

Two looks pretty good, I get to 34, I get to 1, that's a better candidate than 2. 34, 3, 89, 13, 55.

34、3、89、13、55。

Now here's where we're going to depart from our previous approach.

さて、ここからはこれまでのアプローチから離れる。

Instead of swapping elements around, I'm going to literally remove an element from our list, and our list shrinks down to a smaller size.

要素を入れ替えるのではなく、文字通りリストから要素を削除する。

And we append the element to a new list.

そして、その要素を新しいリストに追加する。

So I'm going to go through the process again, 2 is a pretty good candidate, 34, 3, 89, 13, 55, none of those are better than 2, so I remove 2 from my list.

2がかなり良い候補で、34、3、89、13、55はどれも2より良くない。

The list gets a little bit smaller, 2 gets appended to my solution list.

リストが少し小さくなり、2が私のソリューションリストに追加された。

Repeat the process again, 34 is pretty good until I see 3, and then 89, 13, and 55, 3 gets removed from my list and appended to my solution list.

このプロセスをもう一度繰り返すと、3が表示されるまで34はかなり良い。

Repeat the process again, 34 seems pretty good, it's definitely better than 89, but 13 is better than 34, 55 isn't any better than 13, so we remove the 13, shrink our list down, and append our 13 to our solution.

34はかなり良さそうで、89よりは間違いなく良いが、13は34より良く、55は13より良くないので、13を削除してリストを縮小し、13を解答に追加する。

And we continue this process again, and again, until the last item is removed.

そして、最後のアイテムが取り除かれるまで、このプロセスを何度も何度も繰り返す。

And just like before, we've added all of our data to our list in order from smallest to largest, the data is completely sorted.

そして先ほどと同じように、すべてのデータを小さいものから大きいものへと順番にリストに追加し、データは完全にソートされた。

One of the real big distinctions here, however, is that we destroyed our initial list and created a new list instead of swapping things around in place.

しかし、ここでの本当の大きな違いのひとつは、最初のリストを破棄し、その場で入れ替えるのではなく、新しいリストを作ったことだ。

Okay, so as a programming review, let's look at some code that's going to implement this.

では、プログラミングの復習として、これを実装するコードを見てみよう。

So just like before, I've got an array of values that represents my data, and this time I'm going to put it in an array list.

前回と同じように、データを表す値の配列を用意し、今回はそれを配列リストに入れる。

So it's technically a list, but it does have an array to kind of support or hold the data.

つまり、技術的にはリストなのだが、データをサポートしたり保持したりするための配列を持っている。

So we'll look at this more in depth this week.

そこで今週は、この点についてさらに詳しく見ていくことにしよう。

So our overall goal is to have two different lists, one that represents our input values that's already been constructed, and another one that will be our sorted data.

つまり全体的なゴールは、2つの異なるリストを持つことである。1つはすでに構築された入力値を表し、もう1つはソートされたデータである。

So I'm going to create an array that represents the sorted data, and it'll be initially an empty array list, a brand new array list.

そこで、ソートされたデータを表す配列を作成することにする。最初は空の配列リストで、まったく新しい配列リストだ。

Then I'm going to prototype how I'm going to use this new method.

それから、この新しいメソッドをどのように使うか、プロトタイプを作ろうと思う。

Okay, so I'm going to call my selection sort, and I'm going to provide it with these two lists, the input list and the sorted list.

入力リストとソートされたリストという2つのリストを用意する。

Okay, then when I'm done, I'd like to print out my list to make sure that it is in fact sorted.

じゃあ、それが終わったら、リストをプリントアウトして、実際にソートされていることを確認したい。

Okay, so I've kind of set up my problem.

オーケー、それで僕の問題は解決した。

It's time to go and create a method.

そろそろメソッドを作る時期だ。

So it's going to be a public static method with a void return value, and it's going to have those two parameters, the two lists, the list of input and the list that will represent the sorted data.

2つのパラメータ、2つのリスト、入力リストとソートされたデータを表すリストを持つことになる。

Okay, so now we have to figure out how to solve our problem.

さて、それでは問題を解決する方法を考えなければならない。

So just like when I was working with this on the table, I'm going to process data while there's still data in the input.

だから、テーブル上でこの作業をしたときと同じように、入力にデータがあるうちにデータを処理しようと思う。

And basically what I have to do is find the minimum value in that input.

基本的に私がしなければならないのは、その入力の最小値を見つけることだ。

So I'm using a counting for loop here.

だから、ここではカウント・ループを使っている。

By the way, this has some subtle side effects that we'll look at in a little bit.

ところで、これには微妙な副作用がある。

But just like before, I'm creating a variable to keep track of where I found my best value, and I'm going to go through and compare each value to the best one I found so far.

しかし、前と同じように、どこでベストの値を見つけたかを記録する変数を作り、それぞれの値をこれまで見つけたベストの値と比較していく。

And if it happens to be a smaller value, I will update where I think the location of my best value overall is.

そして、もしその値が小さくなるようなことがあれば、私が考える総合的なベストバリューの位置を更新する。

Okay, so when I'm all done with the loop, I've found the minimum values location.

さて、ループがすべて終わったところで、最小値の場所を見つけた。

So now I can get the minimum value, and I need to add it on to my sorted list.

それで、最小値を得ることができたので、それをソートされたリストに追加する必要がある。

Okay, now that I've added on to the sorted list, I might as well remove it from the input list.

さて、ソートされたリストに追加したので、入力リストから削除しよう。

Okay, and that's it.

オーケー、それで終わりだ。

Let's run it and test it and see if it sorts our little sample list.

これを実行してテストし、サンプル・リストがソートされるか確認してみよう。

And in fact, it did.

そして実際、そうなった。

Okay, now I'm going to do something additional here.

さて、ここで追加でやることがある。

I'm going to go through a process called instrumentation.

インストゥルメンテーションと呼ばれるプロセスを経ていくんだ。

So the idea of instrumentation is augmenting code in various ways to track performance and gather data about it.

つまり、インスツルメンテーションのアイデアは、パフォーマンスを追跡し、それに関するデータを収集するために、さまざまな方法でコードを補強することである。

In this case, it's going to be a really, really, really crude form of instrumentation.

この場合、本当に、本当に、本当に、本当に粗雑な楽器の形になる。

I'm just going to add in some additional print messages, and we'll try and use those to get a sense of how long it takes this code to run.

このコードを実行するのにかかる時間の感覚をつかむために、いくつかのプリント・メッセージを追加してみる。

So I'm going to put a print message before I do my sorting that says I'm starting.

だから、仕分けをする前に、これから仕分けを始めますというメッセージを印刷するんだ。

I'm going to put another print message after I do my sort that says we're done.

ソートを終えたら、またプリントメッセージを出すつもりだ。

Okay, then I'm going to run my program, and it printed everything almost instantaneously.

よし、では私のプログラムを実行してみよう。すると、ほとんど瞬時にすべてが印刷された。

There seemed to be no significant difference in time between when it started and when it finished.

開始時間と終了時間に大きな差はなかったようだ。

So I'm going to go up, and I'm going to change the data that I'm supplying.

だから、上に行って、供給するデータを変えようと思う。

And so instead of supplying it just a little bit of data, I'm going to change this for loop.

そして、ほんの少しのデータを供給する代わりに、このforループを変更する。

And I'm just going to append a whole bunch of data.

そして、私は大量のデータを追加するだけだ。

So instead of using my previous values, I'm just going to generate random integers.

そこで、これまでの値を使う代わりに、ランダムな整数を生成することにする。

So I'm going to be using math.random here.

そこで、ここではmath.randomを使うことにする。

I know that math.random gives me a double number, and I want to end up with an int at the end.

math.randomが2倍の数値を与えることは知っている。

So I'm going to do some typecasting.

だから、タイプキャスティングをするつもりだ。

Basically, what this is doing is it will give me a random integer between zero and the maximum possible integer value.

基本的に、これはゼロから可能な最大の整数値の間のランダムな整数を与えてくれる。

Then I'm going to change my loop.

じゃあ、ループを変えるよ。

I'm just going to try and have it count up to 10,000.

ただ、10,000までカウントしてもらうつもりだ。

I'm using a notation you can use in newer versions of Java.

Javaの新しいバージョンで使える記法を使っている。

Oh, wow, that was quick.

おお、すごい、早かった。

So it sorted 10,000 items really, really quick.

だから、10,000のアイテムを本当に、本当に素早く分類したんだ。

Let's try 20,000.

20,000ドルを試してみよう。

That was pretty quick, too.

それもかなり早かった。

Let's try 30,000, maybe.

30,000ポンドでやってみよう。

One, two.

1、2

Okay, so that was maybe a second.

そう、それは一瞬のことだった。

That was at least noticeable, right?

少なくとも目立っていたよね？

40,000.

40,000.

One, two.

1、2

Pretty quick, too.

かなり速い。

But about two seconds, maybe.

でも2秒くらいかな。

Two to three seconds for 40,000 items.

4万アイテムで2〜3秒。

Now, that was on my computer.

今のは私のパソコンでの話だ。

My computer is several years old.

私のコンピューターは数年前のものだ。

Your computer might be faster, so maybe they'll run quicker for you.

あなたのコンピューターはもっと速いかもしれない。

Or maybe your computer is a different model with a different processor, and it'll run slower.

あるいは、あなたのコンピューターが別のモデルで、別のプロセッサーを搭載しているため、動作が遅くなるのかもしれない。

So this is an empirical test.

つまり、これは実証的なテストなのだ。

It's an experiment.

これは実験なんだ。

I was measuring how long it would take.

どれくらい時間がかかるか測っていたんだ。

Now, let's look at something interesting.

さて、面白いものを見てみよう。

So I used an ArrayList.

そこで、ArrayListを使った。

But an ArrayList and a LinkedList are somewhat interchangeable.

しかし、ArrayListとLinkedListはある程度互換性がある。

I mean, they've got the same operations.

つまり、同じオペレーションをしているんだ。

So let's see what happens if we do a search and replace, and replace the ArrayList with a LinkedList.

では、検索と置換を行い、ArrayListをLinkedListに置き換えるとどうなるか見てみよう。

So I'm going to search for all of the places where ArrayList is used.

そこで、ArrayListが使われている場所をすべて検索してみる。

And we'll replace it with LinkedList.

そして、これをLinkedListに置き換える。

OK.

OKだ。

Now, before I get carried away, I think I'm going to back down.

さて、調子に乗る前に引き下がろうと思う。

I'm going to test out my simple original sample problem.

僕が作った簡単なサンプル問題を試してみるよ。

So I'm going to put in the loop that uses my original test values there.

そこで、オリジナルのテスト値を使うループを入れることにする。

I'll run it with those values.

その値でやってみるよ。

Oh, yeah.

ああ、そうだ。

OK, that's cool.

オーケー、クールだね。

So it ran, sorted my six or so values there.

そこで6つほどの値を並べ替えて走った。

It looks good.

いい感じだ。

OK, seven values.

よし、7つの価値観だ。

Let's go back and try it again with more data.

もう一度、データを増やしてやってみよう。

So I'm going to put my loop back in.

だから、ループを戻すつもりだ。

I'm going to set it at 10,000.

10,000に設定するつもりだ。

One, two, three.

1、2、3

Wow, if you remember, the ArrayList version took about two seconds.

わお、覚えているかな、ArrayListバージョンは2秒くらいかかった。

But this is taking forever.

しかし、これには時間がかかる。

OK, so a very subtle change there had a huge impact on performance.

なるほど、非常に微妙な変更がパフォーマンスに大きな影響を与えたわけだ。

Huge.

巨大だ。

I mean, we're still waiting for it to finish.

つまり、まだ完成を待っているところなんだ。

Now, this does not mean LinkedLists are bad.

だからといって、LinkedListsが悪いというわけではない。

LinkedLists have some really great strengths.

LinkedListsには本当に素晴らしい強みがある。

But they've got some weaknesses, too.

しかし、彼らにも弱点はある。

And I have used a LinkedList in a poor way.

LinkedListの使い方も悪かった。

I could restructure this in ways where a LinkedList would perform just as well as the ArrayList did.

私は、LinkedListがArrayListと同じように機能するように、これを再構築することができた。

So this is one of the big takeaways from this class, understanding all of these subtle distinctions and how just a subtle change can have a huge impact on overall program performance.

つまり、この微妙な違いをすべて理解し、ほんのわずかな変化がプログラム全体のパフォーマンスに大きな影響を与えるということが、このクラスでの大きな収穫のひとつなのだ。

Thank you.

ありがとう。