Name: 1.1 データ構造とアルゴリズム：配列展開戦略 (1.1 Data Structures & Algorithms: Array Expansion Strategies)
Uploaded: 2025-01-06T13:37:01.000Z
Duration: 9 min 22 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

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.

つまり実際には、アレイはコンピュータの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の略で、Randomの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.

ある図書館に、1冊の本を担当する司書が1人いるとしよう。

They're standing there holding their particular book.

彼らは特別な本を持って立っている。

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

1冊の本につき1人の司書がいるだけでなく、ピッチャーもいる。

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.

appendがあり、これはその最後に何かを追加することに相当する。

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.

また、多くの場合、Java配列の.lengthプロパティに相当するsizeメソッドがある。

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.

配列を管理する場合、配列のサイズの概念を2つに分けることができる。

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.

配列のスペースが足りなくなったら、いつでも正確に1つのスペースを追加する。

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.

なるほど、この2つの間にはいろいろな種類がある。

倍にする代わりに、3倍にすることもできる。

Instead of adding one, we could add four.

1つ増やす代わりに、4つ増やすこともできる。

But essentially they break down into two broad categories.

しかし、基本的には2つのカテゴリーに大別される。

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.

例えば、スペースが足りなくなるたびに箱を1つ増やすとか、配列の容量を2倍にするとか、ある種の倍数を行うとか。

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

それでは、これら2つのアプローチそれぞれを使った、いくつかの配列操作の具体例を説明しよう。

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

では、最初の戦略、配列のサイズを1つ増やす例を説明しよう。

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

つまり、この正方形は私の配列を表し、そこに1つの値を入れただけである。

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.

さて、下のグラフでは、横軸が私が行っている操作、つまり追加されるアイテムを表し、縦軸が作業を表している。

というわけで、これで1つの仕事を終えた。

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.

つ目の項目を追加するには、新しい配列を作り、すべてのデータをコピーして、2つ目の項目を追加しなければならない。

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.

つまり、配列の作成には2つのボックスを作成するために2つの作業単位が必要で、それを同時に埋めれば2つの作業単位が必要になる、と考えればいい。

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.

3つ目の項目を追加するには、新しい配列を作り、コピーして、3つ目の項目を追加する。

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.

そして4つ目の項目は、新しい配列を作成し、すべてのデータをコピーし、元の配列を破棄する必要がある。

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

そして、5番目の項目、6番目の項目、7番目の項目、8番目の項目と続く。

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.

先ほどと同じように、まずはアイテムを1つ追加し、それを1単位とカウントする。

では、2つ目の項目を追加していこう。

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

スペースがないので、配列を2倍にします。

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

2つ目のアイテムを追加し、最初の配列を破棄する。

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

最後に、3つ目のアイテムを追加しようとすると、状況は変わってくる。

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

スペースが足りないので、アレイのサイズを2倍にして4人分の容量を入れよう。

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

古い配列は捨てて、今回は4つのユニットをやったことになる。

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.

しかし、4つ目のアイテムを追加するときには、すでにそのためのスペースがあるので、追加で必要な作業は1ユニットだけだ。

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.

5つ目の項目を追加しようとすると、またしてもスペースが足りなくなるので、配列のサイズを2倍にして容量を8つにする。

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.

元の4つのデータをコピーして新しいデータを加え、配列の8つのスペースに対して8つの作業単位をカウントする。

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

これで、6番目の項目、7番目の項目、8番目の項目を追加することは些細なことだ。

Each one just requires updating one position of the array.

それぞれ、配列の1つの位置を更新するだけだ。

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.

もう一度言うが、配列は一杯なので、9番目の項目を追加するには、配列のサイズを2倍にして合計16個の容量にする必要がある。

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

すでに持っている8つのデータをもう一度コピーする。

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.

さて、10番目の項目、11番目の項目、12番目の項目、13番目の項目と、16番目の項目を追加するまで、各単位の仕事を追加していく。

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.

ここで興味深いことのひとつは、我々は基本的にタワーを建設しているのだが、各タワー間の距離が2倍になっているということだ。

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のオペレーションでは、平均してそれぞれ3ユニットほどの仕事をこなしている。

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.

しかし、全体として平均すると、配列にアイテムを追加したり配列を大きくしたりする方がずっとずっと速い。