Name: 1.1 數據結構與算法：數組擴展策略 (1.1 Data Structures & Algorithms: Array Expansion Strategies)
Uploaded: 2025-01-06T13:37:01.000Z
Duration: 9 min 22 s

So first off, a little detail about arrays.

Arrays have what's called a random access property.

數組具有所謂的隨機存取屬性。

程度副詞

So in reality, arrays are just a proxy for your computer's RAM.

是以，實際上，數組只是計算機內存的代理。

In case you don't know, RAM stands for Random Access Memory, and the R, the random, is really, really important.

如果你不知道，RAM 是 Random Access Memory（隨機存取存儲器）的縮寫，其中的 R（隨機）非常非常重要。

Basically what it means is that you can access any location, any index in the array, in uniform time.

基本上，這意味著您可以在統一時間內訪問數組中的任何位置、任何索引。

So this is one of our constant time operations.

是以，這也是我們的一項常時作業。

Independent of which particular index we're accessing in an array, we assume that it will take a uniform amount of time.

無論我們訪問的是數組中的哪個索引，我們都假設它將花費相同的時間。

Accessing the first box takes just as long as accessing the middle box, or the end box.

訪問第一個方框和訪問中間方框或末端方框所需的時間一樣長。

I kind of think of it as a well-staffed library.

我把它想象成一個人員配備齊全的圖書館。

So imagine that you've got a library, and it's got one librarian dedicated to each book.

想象一下，你有一個圖書館，每本書都有一個專門的圖書管理員。

They're standing there holding their particular book.

他們站在那裡，手裡拿著自己特定的書。

Not only is there one librarian per book, but there are pitchers.

不僅每本書有一個圖書管理員，而且還有投球手。

So if you want a particular book, you just call out the call number or the name of the book.

是以，如果您想要某本書，只需呼喚書號或書名即可。

The librarian who has that particular book hears you, and they pitch the book to you.

有這本書的圖書管理員聽到你的聲音後，就會向你推薦這本書。

It takes a uniform amount of time to access any book, because it doesn't really matter where it's located.

訪問任何書籍都需要統一的時間，因為書籍的位置並不重要。

So we've got a whole collection of librarians, a whole collection of books, and we've got uniform access independent of location.

是以，我們有一大批圖書管理員和一大批圖書，我們可以不受地點限制地統一訪問。

You ask for the first book, it's pitched at you, gets to you at the exact same time as the last book.

你想要第一本書，它就會向你推銷，並在與上一本書完全相同的時間送到你手上。

Okay, so let's go back to our discussion on arrays.

好了，讓我們回到關於數組的討論。

So arrays have a fixed size when they're created, and that's basically due to how memory is managed.

是以，數組在創建時有固定的大小，這基本上是內存管理方式造成的。

So in order to overcome this, we have to manage our arrays.

是以，為了解決這個問題，我們必須管理我們的數組。

So a common approach is to create a class.

是以，一種常見的方法是創建一個類。

So in Java, there's already an existing ArrayList class that you can leverage, and the class will have methods to manage the array.

是以，在 Java 中，已經存在一個 ArrayList 類，您可以利用它，該類將具有管理數組的方法。

The methods will do the kind of common operations that you would normally do on an array.

這些方法將執行通常在數組上執行的常見操作。

So for example, there will be some sort of a get method, and that's equivalent to accessing something in an array and assigning it to a variable.

例如，會有某種 get 方法，這相當於訪問數組中的內容並將其賦值給變量。

There's a set, which is just the opposite.

It's equivalent to assigning a value to a particular location in an array.

這相當於將一個值賦值到數組中的一個特定位置。

There's an append, which is equivalent to adding something onto the end of it.

有一個追加，相當於在末尾添加一些東西。

And this is where we have to start worrying about the size of our array.

這時，我們就必須開始擔心數組的大小了。

Also, often there's a size method that's equivalent to the .length property on Java arrays.

此外，通常還有一個 size 方法，相當於 Java 數組中的 .length 屬性。

Okay, so when we're managing an array, we can separate the notion of the size of the array into two different ideas, into the capacity, which is really like the length of the array.

好了，在管理數組時，我們可以將數組的大小抽成兩個不同的概念，一個是容量，實際上就是數組的長度。

It's how much the array can actually hold.

And also maybe some other variable, perhaps n, indicating the actual amount of data in the array at any particular time.

也許還有其他變量，也許是 n，表示在任何特定時間數組中的實際數據量。

Okay, so now we can pick different resizing strategies based on the separated notion of capacity and actual count of contents, capacity versus n.

好了，現在我們可以根據容量和實際內容數（容量與 n）的不同概念來選擇不同的調整策略了。

So one of our strategies would be the perfect size strategy.

是以，我們的戰略之一就是完美規模戰略。

We'll add exactly one space any time our array is out of space.

當數組空間不足時，我們將增加一個空格。

So the capacity would be equal to n at all times.

是以，容量在任何時候都等於 n。

The other approach that we can take is the doubling approach.

我們可以採取的另一種方法是加倍法。

So when we're out of space, we could double the capacity of our array.

是以，當空間不夠時，我們可以將陣列的容量增加一倍。

Okay, there are all kinds of varieties in between these two.

好吧，在這兩者之間還有各種各樣的品種。

Instead of adding one, we could add four.

我們可以增加四個，而不是增加一個。

But essentially they break down into two broad categories.

Either we're adding a fixed constant amount of space every time we're out, for example, just one extra box every time we're out of space, or we're doing some sort of multiple, like doubling the capacity of our array.

要麼我們每次都增加固定數量的空間，比如每次空間用完都增加一個額外的盒子，要麼我們進行某種倍數的增加，比如將陣列的容量增加一倍。

Okay, so let's walk through kind of a concrete example of several array operations with each of these two approaches.

好了，讓我們分別用這兩種方法舉例說明幾個數組操作。

So let's go over an example of the first strategy, increasing the array size by one.

讓我們以第一個策略為例，將數組大小增加一個。

So this square represents my array, and I've just put one value in it.

是以，這個正方形代表我的數組，我只在其中輸入了一個值。

Now on the graph below, the horizontal axis represents the operation I'm doing, the item that's being added, and the vertical axis represents the work.

現在，在下圖中，橫軸代表我正在進行的操作，即正在添加的項目，縱軸代表工作。

現在我已經完成了一個單元的工作。

To add a second item, I'm going to have to create a new array, copy all my data over, and add my second item.

要添加第二個項目，我必須創建一個新數組，複製所有數據，然後添加第二個項目。

So if we think of the array creation as requiring two units of work to create the two boxes, and maybe we fill them in simultaneously, we're now up to two units of work, and so on.

是以，如果我們認為創建數組需要兩個工作組織、部門來創建兩個方框，並且我們可能同時填入它們，那麼我們現在就需要兩個工作組織、部門，以此類推。

To add my third item, I create a new array, copy things over, add my third item, and I'm up to three units of work.

為了添加第三個項目，我創建了一個新的數組，複製了一些東西，添加了第三個項目，這樣我就有了三個工作組織、部門。

And then my fourth item requires creating a new array, copying all of my data over, discarding my original array, and now I'm up to another four units of work.

然後，我的第四個項目需要創建一個新數組，複製我所有的數據，丟棄我原來的數組，現在我又多了四個工作單元。

And so on with the fifth item, the sixth item, the seventh item, the eighth item.

依次是第五項、第六項、第七項、第八項。

Okay, at this point you probably noticed that this is a lot of work.

好了，說到這裡，你可能已經注意到這是個大工程了。

So now let's try another approach to manage the size of the array.

現在，讓我們嘗試另一種方法來管理數組的大小。

When we run out of space, let's double it.

當空間不夠時，我們就把它加倍。

Just like before, we'll start by adding one item, and we'll count that as one unit of work.

就像之前一樣，我們先添加一個項目，並將其算作一個工作組織、部門。

現在，我們將添加第二個項目。

We're out of space, so we'll double the array.

我們的空間不夠，所以要把陣列擴大一倍。

We'll add our second item, discard our first array, and we've added two more units of work.

我們添加第二個項目，丟棄第一個數組，這樣就增加了兩個工作組織、部門。

Finally, things will be different when we go to add our third item.

最後，當我們添加第三個項目時，情況會有所不同。

We're out of space, so we'll double the size of our array to contain a capacity of four.

我們的空間不夠了，所以我們要把陣列的大小增加一倍，容納四個。

We'll discard our old array, and we've done four units of work this time.

我們將丟棄舊的數組，這次我們已經完成了四個單元的工作。

We're including creating the array in our count of work.

我們將創建數組也納入了我們的工作範圍。

So at this point we've done more work than at the equivalent time in the other approach.

是以，在這一點上，我們所做的工作比其他方法的同等時間要多。

But when we add in our fourth item, there's already a space for it, so it only requires one additional unit of work.

但當我們添加第四個項目時，已經有了一個空間，是以只需要增加一個工作組織、部門。

When we go to add our fifth item, we're again out of space, so we'll double the size of our array to have a capacity of eight.

當我們要添加第五個項目時，空間又不夠了，所以我們要將數組的大小增加一倍，使其容量達到八個。

We copy over our original four pieces of data, and add in our new piece of data, and we're going to count that as eight units of work for the eight spaces in our array.

我們複製原來的四個數據，然後添加新的數據，這樣數組中的八個空格就有八個工作組織、部門。

Now adding the sixth item, the seventh item, and the eighth item are trivial.

現在增加第六項、第七項和第八項都是微不足道的。

Each one just requires updating one position of the array.

每次只需更新數組的一個位置。

Once again, our array is full, so to add in the ninth item, we're going to have to double the size of our array to have a total capacity of sixteen.

再一次，我們的數組已經滿了，所以要添加第九個項目，我們必須將數組的大小增加一倍，使總容量達到 16。

We'll again copy over the eight pieces of data that we've already got.

我們將再次複製已經獲得的八項數據。

And now we've done sixteen more units of work to create this array with sixteen positions.

現在我們又做了 16 個組織、部門的工作，創建了這個有 16 個位置的數組。

Now to add in our tenth item, and our eleventh item, and our twelfth item, and our thirteenth item, for each one unit of work, all the way up until we add in our sixteenth item.

現在，每完成一個工作組織、部門，就增加第十個項目，第十一個項目，第十二個項目，第十三個項目，直到第十六個項目。

One of the things that's interesting here is we're essentially building these towers, but the distance between each tower keeps getting twice as far apart.

這裡有趣的一點是，我們基本上是在建造這些大廈，但每座大廈之間的距離卻一直是原來的兩倍。

If you wanted to think about the average amount of work we were doing, you could rearrange these, knock the towers over and flatten them out, and try and get an estimate of the average amount of work being done over those sixteen operations.

如果你想知道我們的平均工作量，你可以重新排列這些塔，把它們推倒壓平，然後試著估算出這 16 次操作的平均工作量。

So here you can kind of see a visual depiction of the amount of work that's being done on average.

在這裡，你可以看到平均工作量的直觀描述。

Over our sixteen operations, on average, we're doing about three units of work each.

在我們的 16 項行動中，平均每項行動要完成約三個組織、部門的工作。

And that's the real advantage of the array doubling strategy.

這就是陣列加倍策略的真正優勢。

Sometimes you do a little bit of work that might be strictly necessary, and you might use more space than you absolutely need.

有時，你做的一些工作可能是絕對必要的，你可能會使用比絕對需要更多的空間。

 But overall, on average, it's much, much faster to add items to the array and grow the array.

但總的來說，平均而言，向數組添加項目和增長數組的速度要快得多。