okay hello everyone so I'm going to
speak about our greens all these small
creatures that living in our codebases
even we if we don't really know about it
before we start few facts about me so
i'm vitaly i'm working for company
called upon as the leads of train
engineer in poland in broad swath i'm
Corgan eyes in meetups and i really love
to experiment with some interesting
stuff combined and expect these things
and stuff like that so and you can
follow me on twitter read my blog and
things like that so our main topic Algar
is what is actually our grids
so it's a specification how to solve
some problem step by step so it's just
instructions yes and what why we should
care about it we just using some react
components to build your eyes so we are
not doing some rocket science or things
like that but actually algorithm a way
even in all of your frameworks right so
many algorithmic optimizations to reduce
memory footprint to make them faster and
all these things might came with some
trade-offs and we will speak about them
as well so before we start I need to
introduce what is complexity how we can
measure our algorithm is it good enough
or we should look for better solution
for it so complexity is the way to
explain us how our code will scale will
work at scale for example on your test
environment you have just few tests
user's ten of them but in real
application you have millions of them or
something so you should know how it will
behave should you optimize this for more
or entities and in computer science
reset standard notation for that called
Big O so what is that it's actually a
graphical representation how our time of
algorithm will be behaved on more and
more input date so we have like near one
so it grows as we increase the entities
we pass to the functions
it could be logarithmic and it could be
quadratic and so on so forth
and there is pretty easier explanation
about it with some emojis yeah
constant time you're happy you probably
couldn't do it even faster logarithmic
good one linear okay and then you became
more and more sad and those kind of
content complexity or memory complexity
means that you actually need to improve
something or even write your code
completely and we have to management's
management's time and space complexity
time stands for how many times it takes
on some generic computer machine to
execute your code we just thinking that
we have some machine that executes one
action fair-cheeked yeah and space
complexity our memory usage we can
predict how many memory we will utilize
with our app so as I said before all
these metrics will show us where is the
bottleneck in our code what we should
improve and the sink is with algorithm
even if you have good enough or green
there is a possibility to find a better
one so there is no any limits even if
you have some knowledge in computer
science that there is the best algorithm
you could use probably you can invent a
new one better or more suited for your
situation your application and the first
thing I want to speak about is data
normalization now it's common to use
some state management tools like redox
or NGO rigs whatever and it basically a
big object containing all data sets and
usually when you want to access some
entities in list
you won't do that as fast as possible
and there is a technique called data
normalization that allows you to have a
constant time access to your entities
basically what you do you remove your
data from array to object with key of
some ID and object as a value itself
where we can use it when we have some
related data entities in our store or
any other kind of data when we have
recursive entities and we want to have
fast lookup through list of entities
let's take a look of some examples for
example data with relations imagine you
have ecommerce website with some phone
selling and each phone has a category it
relates to so it's a relation between
item in a cart and a category in your
e-commerce shop recursive data
structures your categories could have
some subcategories and basically they
should represent some kind of tree and
this and this tree could have cycles as
well sometimes so it's a recursive data
set when we can and why we can use data
normalization in such cases so for
example we want to get some product body
so instead of accessing and traversing
through the list we just accessing it
through ID the same when we want to get
some categories by ID or products by
category
and actually we can reduce some memory
footprint with that as well let's take a
look in any service just need to update
or select our data so for example we
want to get a product body we have a
list of products and we find in ID
inside this list yes it should have a
linear time complexity another thing we
want to get all products related to some
category so we going through all
products and finding if the product
related to some category and returning
them interest it will take us n by n
time complexity where the end could be a
number of our products and M is number
of our categories could be improve it
and probably yeah and we also have a
recursive access to categories for
example if we are looking for category
by ID
we iterating through them until we find
as a category we want and it could be
linear time and also we could to use
some memory because we have a recursive
call stack that actually uses memory for
each call else recursive code could look
like this you go and deeper and deeper
it's very more harder to maintain it
an't right so this the things we want to
improve so we can normalize our data
instead of list of products we can keep
products by its ID in an object and it
will be immediate access the same we can
do for categories also too if we need to
keep the order of products we can keep
the list of ID's to keep that order
instead to have additional list with all
objects the same we can do with
scattegories let's take a look how our
selectors they
the selectors could look like four get
product by D we just accessing our
Kisuke of an object
it's laning our time the same for
categories and if we want to get
categories by D be still have not the
best solution yeah
we're reducing the products by
categories and so on that's a point we
could improve even more and if you know
about databases for fast searches we
prepare indexes for search we can do
pretty similar things with our data on
client side so if we prepare the
products IDs by category in some object
we can have immediate access for it and
after that we can easily get products by
category just getting kills from the
object and map it to and map product IDs
to actual products and it will improve
our time complexity to be linear one and
I believe there are more and more
different techniques to improve these
things so how to use it in your code of
course you can always do it yourself the
code you could rely only it's only your
code isn't it but they're a bunch of
libraries for example for react you can
use something like normally is roof for
ng weeks you can use built in entity
entity module and that's easy that's a
very very important technique I want to
speak about memorization memorization is
the ability of some function to remember
the results of previous calls sounds
really easy well we can use it again
when we work in this sons like redux and
we return in completely new state on
each state changes we can trigger the
renders which
Changez more often wear than they
actually needed for examples we have
some data selection that's really really
deep in our store and if we change
something different and that property we
trigger changes on this subscription so
for data selections we can use
memorization for repeated commutations
like you repeat some product
I don't know hash or something like this
you can catch this result if it computer
CPU heavy computations and for derived
data states as well the simplest example
to explain normalization is Fibonacci
numbers yeah we call them our function
with recursive calls we optimize it with
tail recursion and if we look on call 3
these which arguments we call in our
function we can see that we're repeating
some computations all went over again
and this is the work that we actually
want to do again so to reduce recursive
expensive calls we can use memorization
and for frequently used data as well how
it will look like for example with
Fibonacci so we create another function
that will return Fibonacci 1 and this
function will contain some object for
cashing results or it could be list
actually in Fibonacci and if we already
calculated the value for the past
argument we just returning immediately
value from the cache not computing
anything again how we can use it of
course we can do it ourselves every time
but better solution to use some library
like we select on them and the thing is
that I show the some basic example of
memorization but we have multi slotted
memories
Multi slaughtered and some libraries
provide you a factory methods to create
memorization customized for your needs
so it's better to at least check those
libraries and the next more interesting
things that I want to show levenshtein
distance algorithm and how to improve
some user experience with it so what is
levenshtein distance if the algorithm
place how many edits you need to perform
to create one string from another it
calculates the number of edits number of
changes and it could be easily
introduced by Albert Livingston yes
everyone trusted information in over
Internet yes now it was a Vadim a
Livingston mathematician that created
this algorithm in 1965 we can represent
the work of this a grid with the matrix
and actually be aphelion matrices when
we have executed it so we have two
boards Honda and Hyundai and for each
letter in this world starting from the
first one we calculating do we need to
change something in target three strings
to get the first one and at the end we
get the number total number of these
changes so in this case it will be three
and that means the distance between
those two strings will be three and
actually this algorithm out that
complicated sounds like such a lines of
code and the interesting story how I
found this algorithm I was looking to
some source code of angular UI and I've
seen how they provide outer correction
for comments so they have a list of
comments and if you get a typo
they
suggest you and as a comment that
probably you want to execute and for
that they using levenshtein distance
algorithm so when it oftenly used so two
for after correction after completion or
smart suggestions for example keyboards
or Szalai tools or after correction in
text editor and who's how to look like
for example indeed if you try to call
get claim instead clone it will suggest
you that hey you might want to execute
clone command and the example in angular
sly where I found actually and treat
about levenshtein distance algorithm so
if I call to generate some component it
suggest me generate comment and it's
fast but let's try to use levenshtein
distance algorithm to create smart for
zero for pages and to prove our uux what
is the problem this usual standard for
zero for page we get a type of for
example or link is already broken or was
changed on back end and we hit an enter
and we get some helpful you Ivy's
kitties yes
it's very useful we can watch for a
while and completely forget what we want
to do but that's it solve any problem
probably not what we can do instead we
can suggest you sir proper link here's a
simple example
I have an application oh it won't play
the video ok I have an application just
few links home about contacts yeah so
let's make a typo for example hain and
at the bottom of the page I have a
suggestion for user sorry
you probably made a typo did you mean
about page or we can type contract in
instead contact and we will be
redirected to correct page so it's
actually will solve problem for user it
will have some value for them so why not
to improve our 4:04 pages with this
algorithm how we actually how it's
working so usually we have some listing
of all roads we have in our application
we can gather them in some list then we
can sort them by levenshtein distance
will calculate it to user input so user
meta title yeah came instead home then
we have abolition of all possible roads
and we sort them by Livingstone distance
to Haines and probably the first one
will be the correct one in our case home
so we can return this value to the user
and create a link to the correct page
how it looks like in code for example
for this demo I have home about contact
is just some hash map with strings of
passable roads then I have a surgeon so
I have a type of path and I have
dictionaries that I prepared that's all
the possible paths in my Rochin and then
I sort in it using levenshtein distance
al green but to prevent calls of that I
already did computations that I did for
already did I question them so if there
is no computed value in cash i
recalculate it otherwise i just return
the difference and the last step we take
in our pass with half our rows and I
also introduce some threshold for
if the levenshtein distance is too big
it's probably completely different word
so I have a threshold and if it is our
suggested value is below this threshold
I just return nothing just standard
kittens or something
otherwise I will return the first item
that's the most closed world and this
thing shows us that we can use something
like our grids and apply it to some
unexpected user cases to create some
value for the end users that's also the
case why you should actually care about
our greens why they're great why they're
cool so I want you to come home and just
try to find some interesting problem and
find some algorithms to solve this or
maybe create your own solution for that
reinvent it and maybe in a few years who
knows we will use your alga algorithm to
solve our UI problems that's all that I
have for today
thank you very much and do your auguries
[Applause]