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.

2看起來不錯，我到34，我到1，這比2更好。

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 好，所以我把 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.

再次重複這個過程，34 還算不錯，直到我看到 3，然後是 89、13 和 55，3 從我的列表中刪除，並添加到我的解決方案列表中。

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.

是以，我們的總體目標是擁有兩個不同的列表，一個代表我們已經構建好的輸入值，另一個將是我們的排序數據。

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.

好的，我將調用我的選擇排序，併為它提供這兩個列表：輸入列表和排序列表。

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.

是以，這將是一個返回值為空的公共靜態方法，它將包含兩個參數，即兩個列表，輸入列表和表示排序數據的列表。

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.

是以，我在這裡使用了一個計數 for 循環。

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 會給出一個 double 數，而我希望最後得到一個 int 數。

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.

基本上，這樣做的目的是給我一個介於 0 和最大可能整數值之間的隨機整數。

Then I'm going to change my loop.

那我就改變我的循環。

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

我只是想讓它數到 10000。

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.

讓我們試試 2 萬。

That was pretty quick, too.

也挺快的。

Let's try 30,000, maybe.

也許我們可以試試 3 萬。

One, two.

一 二

Okay, so that was maybe a second.

好吧，那可能是一秒鐘。

That was at least noticeable, right?

這至少是引人注目的，對嗎？

40,000.

40,000.

One, two.

一 二

Pretty quick, too.

也很快。

But about two seconds, maybe.

不過大概兩秒鐘吧。

Two to three seconds for 40,000 items.

兩到三秒鐘可處理 40,000 件物品。

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.

好的。

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.

於是，它運行起來，把我的六個左右的數值排序在那裡。

It looks good.

看起來不錯。

OK, seven values.

好的，七個值。

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.

一、二、三

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

哇，如果你還記得的話，ArrayList 版本大約需要兩秒鐘。

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 have some really great strengths.

鏈接列表有一些非常強大的優勢。

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.

我可以對其進行重組，使關聯列表的性能與 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.

謝謝。