Data Structures - Ref List in C#

hello hello so today I wanted to talk to you about what our breath lists in.net C sharp how they compared to your old like playing lists and since there's no support of reference at all here we're gonna have to implement our own and I'm going to talk about why would you ever want to implement your own rough list so let's jump into some code and let's see what's up so if you're using a list and dot that most of the time you're interested in having any data structure that expands inside because for example you don't know let's just say that we have a class like here transaction and you don't know how many transactions to expect you have no clue so you're going to use the list because that's gonna expand like the package are right for you so there's no need to like you're not gonna overflows there's no need to like guess how many of the transactions are and a half and that's all good that's all fine this is a class there's no problems here so if you wanted for example do stuff like let's just say that we have a bunch of these transactions and we would like to actually calculate the total amount of these transactions that would be fine right there's no problems here but let's just say that you're interested in performance you care about their access buttons because with a class like that there's no time where it's going to end up and if you want to use like data in the design perhaps you want to like stuff to go really fast then what you do here is actually use a struct to make the that they are all one else and there are like positions more predictable so what happens now still there is a for each loop that that isn't the problem that's actually not the performance of this solution so I have here my like super simple function to be able to measure a performance of something it's just going to call this a measure time it's gonna do a quick warm-up where it's gonna call this multiple times to not have the call start problem but all in all it's pretty simple and it gets the job done in this context so we're gonna see how it performs so let's actually start with the class just what the problem is so I plus actually in this example took 52 milliseconds and if we're gonna like change it to a struck it's gonna take 100 milliseconds but if we're gonna add stuff to it like just say the date and that's right string again string not stop except and let's actually add something else here let's actually run it again as a struct and as you can probably see the performance down even it's even install right so it's gonna downplay and like so if we're in the heart to this it's going to get slower slower slower and why is that let's actually verify if a class actually got slower no the class didn't actually get slow the class is just fine the struct is not so what's the problem here problem is that each time we use this for each look it has something that we can call an enumerator so it's just a simple data structure which has three things so it will actually move our like iterator and it's going to give it a stefani but if we're gonna it's gonna probably create something like a local variable even if it doesn't it will just give give it to us and then we're gonna do some manipulation of it and the problem here is that the compiler will actually do a defensive copy so every time we're actually opening up this transaction here we're getting a copy of the transaction we're not actually manipulating the transactions of behalf on this list and that's a problem because we're doing a lot of copies that we don't actually want to do and the solution to that problem is to actually pass it by reference but that list at least from by now doesn't have any way of like creating this sort of hybrid implementation there are some ways but they're pretty cocky in my opinion so what we can do here is to implement like a simple ref list which will have the exact same functionality as the list but it's gonna actually go and create a ref enumerator so let's actually try and do that so let's create a class G let's create a room for it let's feed them index capacity and it's just about 284 for you for now I'm going to actually create the restless and initialize the capacity which will not use in chainsaw and actually have the capacity here so let's just say this capacity capacity and let's do a array using this capacity and this actually this constructor actually allows us to say that with cannon all were kind of expecting a certain capacity so in order to not like create small arise and just copy them over from if they overflow we can have this constructor where we say well I'm I'm kinda I sure that it should be something around here this this value but if it's nothing just expand anyone okay so what else do we need in order to make this work well so so we have to add the add method right and now how to implement the simplest add method now so let's use the array say that equals five but we still need to expand it if we ran over phone right so let's create a method called expand and in this method we have a documentation in a bit but let's just do if our index is greater or equal to our capacity then next time and how to implement the expand function well present so we have to say that the new new capacity because the old capacity times T this is the simplest way how to explain that right you just multiply by two and that's it and now we have to create a new array so when you array equals new Jeany with the new capacity right and now what we need to do is we need to copy the right so how to me copy the array well you could use a copy that's the simplest solution it's not the fastest one but it's gonna get the job done so what's the signature here so I'm sorry this mission went right and what so let's use that all right don't use our new array and let's actually say it's gonna be our length I know what we need to do is we need to assign these new capacities and all right so are all foreign equals new array and our new our capacity act masculine equals three and that's it okay so we have a very simple breakfast let's actually add some girls let's add a indexer becomes that actually helps a lot so lets the public see this and index and we have to implement any getter and etc again and then imma get we're gonna return our array of the index and on set we're gonna assign to a body and that's it that's pretty much it okay so what we have here is a very simple implementation of the reference but that's not really complete because we're not passing anything by reference but let's see if it actually works with the phone right well as it as it turns out it doesn't because we're not Jennifer to work in a foreign ship usually what you have to resort to is to have a memorable interface and we don't really have an interface like that because that signature is different but the error actually tells us that we don't need an interface what we just need is a method called get and numerator and that's very convenient because we'll have to implement an interface here not for its you like work so this is one of the like implicit tricks of the compiler and I'm not fond of it but it's something that they had to result to obviously and if you just have this like magical method that has the specific signature you're gonna add certain functionality just like that so there's no implement like there is no explicit way to say that I'm gonna support a forged loop it's only this dislike method signature but that's that's okay for now because if that would be an interface then we will have a problem but now we dot okay so what we need to do here is we have to implement something that's called get a numerator and that action user should simply return something it's virtually to the top nozzle let's return new of course it's faster public and let's actually see if it works it doesn't object so there's this and now we have to do is we have to implement three methods so it's get current move next this polls if I do it correctly and reset and since I don't remember these signatures it's actually the eye tracker we say that we're gonna implement it I'm a numerator here but we're not gonna do that actually it's another trick because that has a very specific signature and we don't have that because what we want during the count as we monthly return and that's the wind only real breath and here we're gonna do our right of index and let's just pass it in so now we're passing the struct for reference so we shouldn't have that problem all right so what we need to do is we need to implement these two so we set the simple so recent local set the index to minus 1 and the move next we have to just increment the index and we have to also provide information if we can move to the next step so what we can do is we can clean come in the end up on the side of the hostage he wasn't there then the capacity and that's it now we can actually use this here and what we can say is let's pass out all right but let's not pass our capacity because like I said this is different let's pass our index and actually field and now hopefully if I haven't like made any like off by one errors that she just worked so let's listen up it works it's it's if I'm not mistaken it takes the same time as the class version I'm actually using the wrong list here but still the the alt like built-in list took around 130 milliseconds to 150 so it seems that it's working correctly ok so hopefully you see that implementing like stuff like that isn't very hard we just implemented a functional ref list and now we can use this replaced with structs and we can use the for each loop without like any problems so what else is that we can do here to make this even more interesting so let me show you some other like compiling magic sort of thing so each time you have a list like that you can normally decouples just a couple is depends we have this initializer here and to be able to have that this sort of initializer we have to have two things we'd have to implement an ienumerable and we have to have a method with a specific signature again this method is called add and if we have these two things then we can handle this initializer and all of the classes can actually have this initializer it's not just don't that the list or something else I've traded in the past classes that have like wacky initializers for like different purposes but again I'm not a fan of this sort of approach because it's like it looks like compiler magic and you know I get that they have to resort to that but you have to be careful when you're actually doing this stuff so let's try and do the same thing on our new cutter breakfast it's going to crash because we have the signature of the bad function here but we don't have that ienumerable still so let us implement a number able so since we have this we only need this and let's just say that for now we're going to have a implemented exception so what's the problem here all because it's we have transactions so let's do a transaction and it works so we're not going to be able to pass this rough and numerator here because it doesn't implement this interface so we could actually provide that but again we would have this rough problem so actually there are this since this is like an implicit sorry explicit so we have to have an interface to be able to call this then what we can do is we can actually do a couple of things but let's for now let's actually result in the simplest thing that's just from an exception and just say that this interface shouldn't be years with wreckless because you're not going to have the functionality that you want to have you have to use the concrete implementation here and that would be it okay so hopefully you'd like that you see the benefit of adding breakfasts and like I said they're gonna be used every time you trying to do interesting things on structs and if you'd like to do if you'd like to know more value with you I actually ever wanted to you struct I have a lecture on their own into design and that's not the only like case why what you want you structs they're useful and a couple of things like concurrency distributed systems like I said they are all design and a couple of things you can actually use them in a lot of places you have just something to create a better okay so that's that's all for now I hope you like it and yeah hopefully there's gonna be more interesting videos like that so okay bye

Channel: LevelUp

Views: 1,535

Keywords: dotnet, C#, performance, data structures, programming, lecture

Id: G7_IJlUsW-A

Length: 20min 23sec (1223 seconds)

Published: Fri Jun 12 2020