Name: 4 14 計數1's 29 00 高級 (4 14 Counting 1 's 29 00 Advanced)
Uploaded: 2021-01-14T07:02:44.000Z
Duration: 29 min 1 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

現在進行式

祈使句型

take up a particular problem that has a very non-trivial solution.

We assume the stream elements are bits, zeroes or

one, and we want to know how many bits in the last N are one.

we can use the solution like the one discussed for averages.

In fact the algorithm would be even simpler.

However, we're going to address the situation where N bits don't fit

Perhaps N is a trillion or N is a reasonable number but

there, there are so many streams that we can't store complete windows for all.

If we want exact answers then we can show that it is impossible to do

anything better than to store the entire window.

However, what is interesting is that we can store on the order of

the square of log in bits, where N is the window size, and

still answer queries about the counted ones with answers that are off by at

most a small factor, as small as we like if we do enough work.

The problem we're going to discuss is this.

At any time we have to be prepared to answer a query of the form.

Here k can be any integer from one up to some large upper limit N.

We can surely do this if we use a windows size N and store the last N bits.

When a new bit arrives, we throw away the oldest bit in the windows since it

can never again be useful to answer one of these queries.

But one disadvantage of this approach is that answering one query requires that we

examine k bits, since k can be quite large, and both inputs and

queries may be arriving very rapidly, that may be time we cannot afford.

Another potential problem is that we may not be able to afford the space.

As we just mentioned we could be trying to handle a large number of streams or

N could be so large that even one window does not fit in main memory.

Both these concerns suggests that we should consider a method that uses less

And that also allows us to answer queries about the last k

It turns out that we can't get an exact answer to queries without using N

But we can get close using much less space than all of N,

We're going to introduce the right algorithm with the discussion of

something that seems like it should work but doesn't quite.

Our goal was the be off by no more than a factor of 2 in

estimating the number of ones in the last k bits.

So we will summarize blocks of the stream as blocks will have exponentially

increasing lengths, that is 1, 2, 4, 8, 16, so on.

And the summary of a block will be simply the count of

When we want to know the count of ones for last k bits, we can find

some blocks that lie wholly within the last k bits and we add up their counts.

It is only the last block, the one furthest back in time that gives us pause.

We don't know how many of its ones within the last k bits so we have to guess.

But if we've created these exponentially growing blocks for

all time units then there would be as many blocks of length one as there are bits in

the window, as well as blocks or size two, four, eight, and so on.

Instead, we have to drop blocks if their left end, that is, the end that is

earliest in time, coincides with the left end of the larger block.

And we also drop a small block if there's a larger block completely to their right,

As a result, you never have more than two blocks of any one size.

So, here is an example of the blocks we might retain at some time.

The five rows of blocks are of lengths 1, 2, 4, 8 and 16.

The more recent has a count of 0 because it consists of a single 0.

While the other has a count of 1 because it consists of a single 1.

That has a count of 1 because it represents 0 1.

Notice that we've previously deleted the block of length 1 that would go here,

because it begins at the same point as the block of length 2 above it.

Also all other blocks of length 1 are deleted because they have

a block of length 2 completely to their right.

Its count is 2 because it represents, this 1 1.

There are two blocks of length 4 and they have counts of 2 and 3.

They represent, well, this guy represents this sequence, 0 0 1 1, so it has two 1's.

Well let's see, because it represents these eight bits.

And notice that, that the count for second block of length 8 is not

needed because we can figure out it has six ones.

Since that's tad, that 6 is the difference between the number of

ones in this block of length 16 and that block of length 8.

So if this block existed, it would have, surely have six once.

Now, suppose we get a query for how many ones there are in the most recent 28 bits.

We can add up the counts of certain blocks.

Some little blocks at the right end, and then some bigger blocks going to the left.

We want to pick blocks so that each of the most recent 28 bits is covered by

We don't want this block of length 8 because we have this block of length

字幕列表影片播放

4 14 計數1's 29 00 高級 (4 14 Counting 1 's 29 00 Advanced)

entire

expression

constant

completely