Placeholder Image

字幕表 動画を再生する

  • 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 we can certainly see the relative patterns between it will call that

  • 166 clock ticks over to run the linked list version of the program it takes

  • 166 clock ticks

  • So let's now run the array version of the program

  • So now we're going to do exactly the same thing