[Music]
Welcome back to education everybody. I
get the great honor of introducing Izzy.
This is Izzy. Izzy is a secondyear
software engineering student at UTS.
Currently volunteers coordinator for
PyCon AU. I think we get a little round
of applause for that one.
Uh, and so you've probably already seen
her today. Uh, she's the administrator
for the girls programming network. As
well as being a tutor/room leader and
intrinsic to the national content
creation team. She coaches at a maker
space and robotics team for upper
primary age students. She drinks too
many energy drinks. Uh, she gamifies
meeting people by collecting LinkedIn.
So, hit her up in the breaks. Thank you
very much, Izzy.
[Applause]
Okay, so the title of this talk is data
structures a learning journey. I came up
with this title a while ago and then
somebody told me a much better title. So
that is now the subtitle.
Self-inflicting first principles of data
structures for learning purposes.
Now I spent too long on this animation
so you're all going to have to be really
impressed by it.
[Applause]
[Music]
Oh my god, I love
[Applause]
Who am I? Well, you were just told, but
I am Izzy. I'm 19.
That's me. That one is not me. Oh, I
went backwards. That one's not me.
I am very into music. I think my
analytics from last year said I listen
to 60,000 minutes. Um, that is 41 days
straight. I have calculated it. That's
about a ninth of the time in the year.
Yeah.
Um again, yes, I am very mildly into
energy drinks. Um I don't have any stats
for this one, but I should come up with
some for next time because they would be
high. Um I think I'm fine, but my
parents apparently think I have a
problem.
I spend my time teaching several
different students in several different
capacities. So again, I'm part of the
girls programming network, which you
might have heard of before and was just
referenced. Um, we teach free coding
courses for girls uh once a term. I went
as a student for nine years, and so I'm
now a tutor now that I've graduated. So
that's two years of being a tutor, but
I'm also their administrator, so I do
all their emailing and flights and
paying and do a lot of stuff. There's a
lot of things. I write content for them
and I tutor for them once a term. I also
do robotics. I teach robotics at a
school and other things,
but mostly robotics because the other
people don't want to pay attention to
me. That's fine. Anyway, I recently did
an internship and that leads us to a
couple months ago. Here is the story. So
I was in this internship um it was more
than a couple months ago now but um we
were mostly I was doing JavaScript tests
so I wasn't really doing anything
important but there was some really
intense code in the background that I
wasn't really being told about but my
boss was trying to like help me learn
things and so to do that one day when we
were at lunch he was telling me about
how some of the other code worked and he
told me about this data structure um
that we were using and I didn't really
understand what he was saying. He tried
to explain it several times. He tried uh
it wasn't enough. Anyway, um then I went
to Wikipedia. That also did not help. Um
and at the same time, I was in a class
called data structures and algorithms
for uni, which is a similar class to
what a lot of people have. And I was
like, well, it's got data structures in
the name. So, I went to tutors, two of
them, and neither of them had heard of
this one before. Uh, so that didn't help
either. So I decided that I was just
going to make one from scratch in Python
because I figured that would definitely
help me learn. Um, anyway, the data
structure was called a skip list. But
what is a skip list? It's quite niche.
So I'm going to have to run you through
it. So here's our real life example.
You can kind of think of it like IKEA.
So in IKEA you have all those sections.
You've got like the dining room section,
the office section, the bedroom section,
the kids stuffed animal section, and
they're all kind of you're meant to go
through them in a line so that you can
buy all the things from all the
sections. But sometimes you're just
looking for one thing like you just want
one thing. You want the blahage and it's
all the way at the end. If you know,
like at least in my IKEA, it is at the
end. So, you could just go all the way
through and search everything in every
single section and it would take you
forever. Or you could use some shortcuts
that they've actually got to cut through
and then you only have to search the one
section, the stuffed animal section.
I love a blah. I have a 1.7 meter blah.
It's great. I love it. Anyway, so how do
they actually work? Well, we got to
start from the start, which is linked
lists as skip list are built off them.
Basically, with a linked list, if you
want to store a bunch of data, um you
can either store them next to each other
in memory, but that can get a little bit
confusing if you want to add things or
take things away.
So, it gets a little bit confusing. So,
what we do for a linked list is when we
have a piece of data that looks like
this, we have two sections. one is the
data and one is this other section that
kind of works like an arrow. It points
to the next thing in line. And then you
can string them together like that and
you've got all of your data connected,
but then it's much easier to add into
the middle because you can just cut
those arrows like strings. This the way
that I think about this is sort of like
those really old uh snake games on the
Nokia. Every time it eats an apple, it
adds to the string. Um and so you can
break apart the string in the middle. I
have a diagram for anyone who doesn't
know what that looks like. Um, that's
pretty much how I think about link
lists. So, how would we go about
searching one? So, this one's in order,
as you can see. Um, but if we wanted to
look for the number eight, it would take
us forever. Let's see how long it would
take. So, we have to start at the start.
It's the only place you can start. And
you can't really do anything
interesting. You just have to go from
one to the next one through the next one
to the next one and next one and then
you can get to the end. And we found
what we're looking for. And that was
five jumps. Counted it.
So what can we do to make this better or
faster especially for something much
bigger than
six six items? Yeah. The short answer is
skip lists. Skip lists introduce what's
called fast lanes. um which only
contains some of the numbers in the
entire linked list with arrows that
point downwards. I've said references,
but it's the same thing. They're
basically just arrows. So, here's a
diagram of what a skip list would look
like using our initial linked list. So,
we start with this, our linked list.
It's exact same. And then we have these
ones which are our fast lanes and they
are just link lists but they also point
downwards instead of just pointing to
the right. So that means that we can
start at the top and then go down. And I
can explain how the search will go in
words but I have an animation later. So
we'll get to that when we get to that.
But if we're looking at this, how would
we add a number? There's some special
steps we have to do. So I'll run you
through it. We start with our skip list.
Then say we want to add number nine.
First of all, it always gets add to
added to where it needs to go. And
because nine's the largest, it goes to
the end. And then we flip a coin.
Heads. It's very fun. Uh that means we
can go up a level. So now we add our
nine up. And then we do it again. We
flip a coin. And this one doesn't
succeed. This one's tails, which means
we don't get to add it any higher, which
means that's where it ends. But why
would we be flipping a coin? That
doesn't make any sense.
So, the reason why we're doing it is to
get it closer to what our perfect skip
list looks like. Here's a This is what
it's supposed to look like. So,
basically, a perfect skip list is where
you have the base list and then every
second item goes up and every second
item from that goes up. So basically it
ends up looking like a really nice curve
and it makes it so that it's sort of
like a binary search when you're looking
for it. You can split everything in half
in half in half which makes it really
fast for searching. Um if we look at how
many are in the top we've only got one
and then three and then seven. So
since every succeeding layer has half as
many elements roughly um that means that
every element has one in two chance of
being raised up a level hence flipping a
coin.
So told you I was coming back to it.
This is how we can search a skip list
again. We start at the t start except
this time we start all the way at the
top. And because we know that 8 is
greater than two,
we check across. And we know that it's
greater than two. So we can check the
next one. And it's also greater than
seven. So we can jump across. And then
there's nothing in front of the seven.
So we can just go down and then down.
And since there's now something in front
of the seven, we check across. And oh
look, we found it.
Now, this was only four jumps, which is
shorter. I know it's like so different.
Um, that's because this is quite a small
skip list, so it's not going to be very
obvious, but there is a way that we can
think about how complex or how much work
that took. Um, so I actually wrote this
talk and performed did it in a very
smaller capacity and they were slightly
more technical. So they probably
understood complexity like they've heard
of big O before and not all of you have.
So instead I'm explaining it for you.
Woo. This is proof I learned things in
my unique clauses. Anyway, so when we're
looking at complexity, uh it looks at
the comp computation required to do a
task relative to the size of the data
set. So that's basically how many times
we have to loop or call functions or do
like these really big tasks for how long
your data structure is. So ours is only
six elements. So it doesn't matter how
many loops we do, that's still going to
be very small. In order to show this
relationship, all constants are ignored.
So if it's like n on two, which is
technically the average for a lot of
things, it would just be ignored. So
it's just the n because that shows more
of the relationship between smaller and
larger sizes of data and this like
complexity. We call it big O. I actually
don't know why. Um probably somebody
told me at some point, but big O is to
test what the worst case scenario for
this would be. and big theta is for
averages. So if we want to look at the
complexity of searching a linked list
versus a skip list, we start with our
big O. We've got for a linked list,
that's N. Which means if we have 20
elements, our complexity is roughly 20.
You have to look at every single element
in the worst case.
For a skip list, it's also n. Um,
but why would you do it if it's
literally the same? because that doesn't
make any sense. So let's look at the
averages instead. So the average for a
linked list is n. Technically it's n /
two, but because we ignore the
constants, it's n. But the average for a
skip list is log n. Now, some of you
might not be able to do graphs in your
head, so I have made you one.
Basically, that's a really big
difference. Not when you're really
little, like five or six, but when you
get all the way over here, it's a very
big difference. That's I have this
written down. That's the difference
between 1 million and 20. So if you had
a linked list of the size of 1 million
and you had to search for an item, your
average would be 1 million searches.
Whereas with a linked list, it would be
only 20, which is significantly better.
So now we got to go into the section of
how I actually went about coding it.
So I had three main steps. First one was
to create a linked list. Skip lists are
based off them and they require them to
run as you can remember from the
diagram. So I had to start there
especially because I needed to have a
lot more control than if I just used a
linked list that already existed. And
then step two was practicing. Um I will
get back to that but there was
practicing involved and then step three
was actually making the skip list.
So to make the skip list it involved
three separate classes which is a lot.
We had one to store the individual
values. So that's like our boxes from
the diagram. One to store the uh
positions in list which is like the
little ball. Basically it remembers
where we're at. so we can loop through
it much easier and then one to connect
everything together so it actually
becomes a linked list.
This meant creating a total of 40
methods which is so many.
This is an overview of the functionality
I made for linked list specifically. Um
first thing I made and this is based off
the link lists uh class that's in C++
which is what my data structures and
algorithms class was in but I wanted to
do it in Python so that I could practice
my classes in Python and also because um
I can't put Python on a resume if I'm
not confident in it. So I felt like I
had to be confident and do it in Python.
So first thing I did was pushing to the
front and back of the list. So that's
just adding anything to the front or
back specifically.
Um then the next one was making indexing
work which is basically saying making it
so that I can do list position X and
either find the value that's there or
store one in there. And that's using
those funky looking methods called get
item and set item. These are specific
methods that are actually known in
Python. They're called dunder methods
because they have two double two
underscores either side. And basically,
Python looks out for them and it's like,
well, I know this one. So, it means that
I can use standard notation like list
position x equals something just like
you would do with a regular Python list.
I didn't really know about these very
much. I knew of them, but I'd never used
them before. Um, so I had to learn a lot
about them while I was doing this. Next
one was popping the first and last
elements, which basically means taking
it and cutting it off from the list. It
doesn't exist anymore. Disappears. Next
one was getting the len and the in
functions to work. So that's more dunder
methods. So I can find out the length
and uh check if things are in my link
list. Then adding and deleting. Deleting
is very hard actually in Python because
in C++ it's really easy. You just kind
of say delete in Python that's not a
thing. So I'm hoping it counts as
deleting to just ignore the memory. But
it is technically there still. Um and
then being able to print the list was
the next thing. This is not in order of
what I did it obviously but printing the
list. Um you can actually use this
dunder method. the format one to make it
so that when you print the list it can
print however you want it to look like
which was really helpful especially for
the skip list um it meant that I could
look at it and test it um then I had to
make this one so that the skip list
would work and that's sorting so with a
skip list everything is sorted and it
has to start sorted if you're starting
with a list initially um and to make
that faster I made a sort algorithm for
my links list Uh, I couldn't be bothered
to do anything better than bubble sort.
Uh, I did think about doing quicksort at
one point and then I didn't because I
did not want to. Um, there are lots
more.
I don't even know why I did as many as I
did, but there are tons. Um, some of
them were required for my practice and
some of them were just because I'd heard
of them.
Okay, next one. So, the practice
section, in order to practice making
difficult data structures in Python, I
decided to recreate an assignment I'd
done for my class, which was making a
hashet.
Um, which took a lot of work in C++, a
slightly less work in Python, luckily.
Um, so yeah, I made a hashet from
scratch because I was really confident I
knew exactly how it worked because I'd
done it before. I had to make every
single method before and all of it I had
to do in C++ which
is C++.
This took another 18 methods which
aren't even in the final skip list. So
it was like 18 methods that I didn't
even need to do. But still I that's even
more.
I am not keeping a running count of
methods but I think we're up to 58.
Anyway, finally making the skip list
took two more classes. Yay.
One was to use the linked list object
for the I think that this was this
doesn't make sense. Um anyway, one was
basically the skip list and one was the
positions in the skip list. So when you
have the higher levels, those sort of
work like the regular elements of um the
linked list, but not really because they
have the arrows pointing down. That
means my linked list uh iterators
wouldn't work anymore because they have
more information to store. Um yeah, so
all of that I kind of had to do that
from scratch again. This was another 28
methods. So what is that? That's
70
80 something. I have people yelling it
out. I can't hear. Anyway, so the
functionality for the skip list. Um,
this was something that I learned you
could do in C++ and but struggled with
it a lot in Python. So in C++ you can
have several of the same method but have
it have different parameters or
different types for its parameters so
that it can work differently based off
different types. So I tried to do that
in Python and I had to do some funky
stuff with the type function to test
what type it was in order to do separate
things with separate parameters. So this
was basically so I could allow initial
values to be passed in whether that was
a linked list or a regular list. And at
some point I'll probably add a skip list
in there. So you can start it off with
some values in it already.
Um again I had to allow it to print but
this time I could let it print in
several different styles um so that I
could see it from different views
especially if one of the formatting
styles wasn't working. Made it much
easier. Um, and then I had to search the
skip list. But that search isn't very
standard. Like with a link list, you're
just going one, then the next one, the
next one. It's just a basic loop. But
with a skip list, it is actually
recursive, which is I'm not great at
recursion, but it technically works. So,
you know, that's all I can ask for. Um,
and then some other functions like
getting specific lanes given the height.
Um, and then converting it from a skip
list into a standard Python list, being
able to reconfigure it for a different
height. So, the way skip lists usually
work is using maths to find out the
height. But I figured that the easiest,
the best way to do it was to allow the
user to pass in a height when they were
creating the skip list so that they
could uh decide how high they want it to
be based off how much space they have
pretty much. Um, and then I had to make
some other helper methods to make sure
that the rest of my stuff worked.
So, we're going to go over things I
learned. So, I talked about this
earlier, but I had to use the type
function in order to get some
polymorphism. So, example of me using
that was to allow the user to insert a
value into a linked list as either at
either the index it would need to go or
an iterator for where it needed to go.
And I've got some code. You don't have
to read it, but it is there.
You can see it says type in there
somewhere. Um, next thing I had to get
really confident with the dunder
methods. They're most of my methods at
this point are dunder methods. These are
the ones with the double underscores
before and after. They're the known
Python methods. Um, like one of the
examples I had to use format to print
the skip list in different readable
styles.
This is I think actually this is my
linked list one but that is some code
that has a format method in it. Um
another one I got to practice using
exceptions
which I didn't really cover but
basically if somebody was using a type
in a parameter that I wasn't checking
for and I hadn't written the code for I
would raise an exception which basically
throws an error. So it tells the user
that they're not allowed to do that.
Here's an example.
Um, and finally, I got really good at
classes, algorithms, recursion, and
debugging because I had to do all this
on my own. I had no help. The only help
I had was YouTube.
Um, and that wasn't great. So, I got
really good at a lot of things really
quickly. Okay, conclusion.
This was a massive pain.
Um,
I definitely do understand skip list
now. Like I really understand them. Like
really really understand them cuz I had
to make them and it was really hard but
I learned a ton and I think that means
that you guys should do it too. I'm not
100% sure I would do it in Python next
time. Um it just it comes with pros and
cons. Cons are that you don't have
direct data management. So a lot of it
you have to fake and it kind of gets a
bit messy and the pros are that you get
to do stuff like dunder methods and also
you get to practice doing some of this
harder stuff in a different language
that doesn't really support it but you
can do it anyway. So doing something
that the language isn't really meant to
do means that you're practicing doing
stuff that's a bit hard.
Uh, but also doing this in any language
is really helpful for learning like I
really understand hashets and exactly
how they work, exactly how they're set
up, what the like UML diagram would look
like. Another thing I learned in uni.
But yeah, it was it was really good.
Anyway, thanks
[Applause]
I I thought you were going I can
I'm just going to go and give you a high
five. Look at me stalling.
Um we we do have a minute or two for
questions.
We can Yeah. Here we go.
Did you create any test cases to see if
your functions did what they're supposed
to do and maybe compare between like
your C++ and your your Python
implementations?
So I every time I made a method I tested
it. I didn't test it very deeply um as I
found out recently when I was trying to
test it with some larger skip lists. Um
so there are definitely issues and uh
the testing was very minimal but the
methods mostly work how they should
except for when you get past 10 elements
because mostly the issue is printing
just I haven't I didn't account for
second digits when I was printing so it
kind of looks really ugly. Um but yeah
no majority of the methods work. I
didn't really think about doing this in
C++, so I haven't looked at testing it
alongside C++, but the functionality
does exactly what it would do in C++.
Um, a lot of the functionality because
skip lists aren't really a thing that
you can just use. They're not a data
structure that is natively implemented
in Python. You'd have to use a module.
Same in C++. I didn't really have
anything to compare against except I
just used the standard things that you
would have like add, delete, front,
back, push, pop, all of those things.
Basically, I made the linked list with
everything that would be in a C++ linked
list and then I made a skip list and I
made as many functions as I could think
of. Um, but that was like the extent of
my testing. Some of the functions don't
work one specifically, but that's fine.
Great talk. Um, what data structure are
you going to build next?
I was thinking a red black binary tree.
Oh, I don't know how to build that.
Yeah. Um, that's another when I did this
in a smaller version. Um, somebody asked
me why I didn't use that in my
internship and um, I didn't have an
answer for them because I'd never heard
of it before and I had to I think they
were mostly asking it cuz they wanted
everyone to know that they knew what a
red black binary tree was.
So yeah, but that will be next maybe if
I ever look at this code again.
Um, you mentioned the special format
method. What does that actually do?
So, with the format method, if you've
looked at format uh strings or frings in
printing before, basically it means that
you can customize how those fstrings
behave with your object. So, when you're
printing, usually you can print any type
of object and once it gets to objects,
it doesn't really recognize. It just
prints a thing that says the object type
and then a random code of numbers and
letters. But if you use fstrings and use
the format method, you can customize how
that gets printed. So if I go back to
the section of code that I have for
that. Uh is that it? Yeah. Um basically
what this one's doing is it's looping
through the list. Like it starts by
printing out the open list. Then it
loops through every item in the list and
it prints out the item plus a comma and
a space and then prints out a closed
list. So that's basically how it would
happen for a regular list. This was just
so my linked list would look the same
when you printed it out. This means when
you use an fstring or a format string on
the object, it will print out like a
regular list. And so I have several of
these for my skip list. Uh if you look
up the top there's a parameter called
format specs that's required for this
function. Um and that's basically you
can pass in whatever code you want to
write. Uh like it's usually a code like
ll or whatever string. Um you pass it in
and then you can test for those. So you
can format it differently based off what
you've passed in. So I did a link list
version. I did a skip list version and I
did one other version for my skip list
so that they printed in different
styles.
Okay, I think we've run out of time for
questions. Can we please thank Izzy
again?