 ## 字幕列表 影片播放

• When alex did a video on linked list there's a lot of comments on it it sort of thing

• I want to use a linked list arrays a factor

• What's the point of reading this and so I was sort of thinking about is that well actually "Are arrays

• faster than the linked list or are the linked lists faster than an array, how do we go about finding out?"

• Which one's faster, so let's have a shoot out arrays versus linked list

• First question to start is

• I should just remind ourselves what the difference is between a linked list and

• An array so let's start with the array so probably the simplest

• To understand so an array is just a way of storing

• several

• values

• in memory so we start off with the first value and

• for the purposes of this demonstration, I'm going to use a

• Structure containing multiple values. We did talk about objects a while ago structures are what you had before

• We saw this object which is a collection of values in memories and store to integer values

• So this is array element zero and it's got two numbers. We then got array element one

• And it's got two numbers

• Looks like I'm playing break out got a great element

• To and it's got two numbers and so we can refer to any of these

• by

• reference to the Index starts at 0 3 4 5 6

• 7 10 so you can have an array of any size we have to know how big it is if you wanted to be when

• You create so you allocate the memory for all the things and then?

• You can store some values so we can write 42 in this one. We can put 21 in here

• I'm going to put 3 in that one and we can store them or we can put different values in here as

• Well as we need them so that's how an array works. Which is one big block of memory each thing stored one after the other

• linked list works slightly different we start off at the beginning of

• the linked list and it points at nothing but then as we add things to the list we

• Allocate the memory for it. We're going to store two things so the first thing we'll label these things inside it p

• And Q so it's a lot p here

• And we've got q but we also have an extra thing that tells us where the next they will be and that's empty, too

• So it's all put 42 and 16 so we just allocate space for that one

• Structure that one thing that we're going to store and we connect it up

• So we point this at the first thing so we often call this something like first

• And we see Alex videos to see how that have done

• So when we want to store the next thing we allocate explai for another one

• And we can store the value, so we've still got 8

• 21 in it now the difference between this could be anywhere else in memory, and we connect to the next pointer

• to point in

• To the next thing so we have some known starting point

• which points to the first thing and the first thing 22 the second thing and the second thing would point to the third thing and

• So on and that would point down and these could be all over

• anywhere

• In the computer's memory and then at the end you normally point it at some known value

• Which is often referred to as null and is often the number zero?

• So you can then walk through your list

• And when you find at the next point of zero or null you know you've come to the end of it

• There are two different ways of storing data the best or the same amount of data now

• He's got some differences this one as I says it's fixed inside, and you create it you can store

• How many things you know I've actually filled in but as soon as you get more than eleven since final top array?

• You can't go past eleven if you can see yeah the numbers all go to

• 11 on this however if we wanted to put something else thing we can just get rid of this thing

• And update this to point

• To a new thing so we can make this grow

• Quite easily, and we can also be really clever

• We can add things in the middle and the beginning very very simply, but we're going to go into that today

• So creating them. We're probably only going to do once but which one is actually faster

• Well, let's think about what actually to do. Let's define a very very simple problem

• We've created the structure here, and it's got two things in it

• It's got an integer called p and an integer called Q so saving the linked list and in

• The array let's consider an operation where we're just going to go through all the elements in our array

• Or all the elements in our linked list and sum the value of p are going to add up all the value

• So we're going to add up. What's in array

• Element Zeroes P in array of them at once P and so on so we're going to effectively do

• Something's going to add them all up. We'll do the same with the linked list as well

• So we're going to set what the first thing is to point to p

• Now that one. No. There's no time out of its value of p the next one and so on and we'll add them all up

• Why are we using missiles they want to the unique thing about this is

• That it's going to visit every single element in either the array or every single element in the linked list

• so we're going to visit every single element if you only have to visit one element then the very nature of

• Random access into array means as we fast

• There's no way you can make any difference unless it's the first element if you only one to ever access the first element

• Then look at the same speed we fuel directly to random element

• Then the array or win hands down you can just think about how it works that will be the case. We're going to consider

• We want to access every single element and do something to it and in this case

• You're just going to sum up the values, but it could be if things were representing say windows on the screen

• We want to move them around we want to redraw them

• Whatever it is will then do something to every single wall so we sort of set out the problem?

• I'm going to go over an array of values and a linked list of values

• I'm going to in sum in the visits all and we do actually add up all the numbers

• Stored in the element P. Which is part of the structure so what I've done is I've written

• To see poems which are more or less identical

• I'm going to create

• 125,000 elements in my array

• or mailing list and in the linked list I've got a structure which contains an integer p and an integer Q and

• in the array version

• I've got a structure which contains an integer p and interested Q in the array item

• The only difference is that the linked list has one extra item which is the next pointer to the next thing?

• So very listen see so hopefully we'll go as fast as we possibly can most of the rest of the program

• is

• identical

• so I have my main Routine here which creates a

• List or an array of random number generator?

• 125,000 random numbers which is a slowest part of the program you'll see and then store them

• So allocate memory for each element in the linked list and then we set the value

• Everything else will just leave with 0 and we do the same with the array just as we did on the paper

• We then run the program

• 100 times and all going to here is time

• How long it takes to run a function which adds afforda numbers either in the list or in the array?

• I will do that 100 times

• And then we can work out the average time it takes to calculate one and we'll print out the values as we go

• So we're just using the built-in clock function in C. Which should be accurate accurate enough for what we want to do

• so the real meat the body of the program is this function here some list or

• Some array

• Let's start with the array one because possibly the simplest we said a variable to be zero that's going to be asked some

• You have another variable

• I which is going to be our index through the array and we go from I equals zero

• I first element until we get to the end the number of elements in there

• and we just say this sum equals the value that was already in sum plus the value in the ice element in the array a

• P element

• Remember we said the array had a p and a Q in it we want the value stored in the p space within the structure

• in our array, so I'm just going to add get them together the list version very very similar we set the someone to be 0

• We say while p does not equal null

• So why we haven't reached the end of the list and we set p initially to be the first thing in the linked list?

• So pointing out that first thing sum equals sum plus

• P inside p. We using P inside p

• Confusing variable names, but then I'm asleep programmer, and then we set p ir pointer to point to the next thing

• So we follow the link to the next thing in the linked list and we keep doing that until we come to the end

• There are two programs as simple as you get in terms of implementing a linked list or on array

• so we're going to do is run them and

• We should get some values output

• But we're not going to run them on the I max we're not going to run them on the raspberry Pi

• we're actually going to run them on the atari behind me which means I need a very high Peak high-tech piece of

• Equipment, so I need a floppy disk to transfer other programs from the iMac

• Go topping them off the iMac, and then we can run them on the AtAri

• so go over to the Atari and

• Assurance that it's cameras and spot. We can see it. So what I'm gonna do at first is they got to run

• the list first also going to generate

• 125,000

• linked list values to let it Run

• Right while it loads off the floppy disk

• that's what it used to be like back in the 80s and 90s you had to wait one you crave them ran a

• While a

• long While

• And this is just a simple program

• So there is good

• So it's not

• Initializing the link list it's allocating all the memory for the different elements and then putting a random number

• In the P value of each one, so we'll let that run

• In the words of the old Hobbit computer game time passes or in the words of every apple of this

• secret short

• How long does this take?

• A while lots of oil, I don't know another time this bit

• 125,000 times however long it takes to allocate a random number and allocate some memory

• On the clock speed of what this is actually an 8 MegAhertz cPU

• So it's a takes a while the computer loaded off all the code for the program and off the floppy disk into memory

• And it's now running it to generate the data set that we need then Gonna sum all the values

• So everything is happening now will happen off memory

• It's just taking a while to process it

• But we are recording it in 4k which is a slight overkill. I hope you're getting into that

• extra bit

• So the programs going through now and we'll let it run 400 times

• We'll get an average, but actually looking at the values of the coming up

• I think we can safely assume that the average is going to end up being

• 166 clock ticks now when I say qwop takes each of the machines. We're going to look at are going to have

• Different clocks perms that they use the time things so we can't compare the values directly what we could come read with the seconds

• But