[SER222] Analytical Analysis (4/5): Analysis of ThreeSum
Summary
TLDREl video trata sobre el análisis de un programa ThreeSum utilizando un enfoque analítico. Se discute cómo se puede usar una función de crecimiento para medir la eficiencia del código, centrándose en la línea de código que verifica si hay un triple que sume cero. Se explica el uso de sigmas para modelar el comportamiento del código y se sugiere la posibilidad de simplificar la función de crecimiento obtenida mediante integrales o sistemas algebraicos computacionales para obtener una solución exacta. Finalmente, se menciona la importancia de elegir el modelo de costo adecuado y se invita a reflexionar sobre por qué no se debe contar el número de incrementos en el código.
Takeaways
- 🔍 El objetivo del vídeo es discutir cómo analizar un programa ThreeSum mediante un enfoque analítico.
- 📊 Se centra en el comportamiento del código dentro del método ThreeSum, en lugar de las funciones externas.
- 📏 Se elige como métrica de costo contar el número de veces que se evalúa la condición de triple suma igual a cero.
- 🌟 Se sugiere que para una función de crecimiento (growth function), es más útil contar operaciones que ocurren con frecuencia o son costosas.
- 🔢 Se utiliza la notación sigma (Σ) para modelar y calcular el número de veces que se ejecuta la comparación dentro del bucle.
- 🔄 Se abordan tres bucles anidados, cada uno representado por una sigma, para obtener la función de crecimiento exacta, F(N).
- 📉 Se menciona la posibilidad de simplificar la expresión de F(N) mediante la conversión de sigmas en integrales para obtener una aproximación.
- 📚 Se hace referencia a WolframAlpha y otros sistemas algebraicos como herramientas útiles para evaluar y simplificar expresiones complejas.
- 📘 Se destaca la importancia de obtener la función de crecimiento exacta en lugar de solo usar notaciones de Big O para analizar el rendimiento de un programa.
- ❓ Se plantea la pregunta de por qué no se debe contar el número de incrementos ('plus plus') como métrica de costo, dejando la respuesta para un vídeo futuro.
- 🔧 Se sugiere que ajustar ligeramente los límites de las sigmas puede ser una técnica válida para facilitar la evaluación de expresiones, siempre y cuando se preserven las variables y los coeficientes.
Q & A
¿Qué método de análisis se discute en el video?
-Se discute el enfoque analítico para analizar un programa ThreeSum.
¿Cuál es el objetivo principal al analizar el código dentro del método ThreeSum?
-El objetivo es comprender cómo se comporta el código dentro del método, específicamente la línea de código que verifica si hay un triple que suma cero.
¿Qué tipo de líneas de código no son útiles para analizar en este caso?
-Las líneas de código que siempre ocurren una vez, como la inicialización de variables o la asignación de la longitud de un array, no son útiles para el análisis.
¿Cuál es la función de crecimiento (growth function) que se elige para analizar el método ThreeSum?
-La función de crecimiento elegida es el número de veces que se evalúa la línea 'if' que verifica la existencia de un triple que suma cero.
¿Qué es lo que se busca al seleccionar una parte del programa para analizar?
-Se busca algo que sea costoso o que tome mucho tiempo en ejecutarse o que suceda muy frecuentemente.
¿Cómo se utiliza la notación sigma para determinar la función de crecimiento f(N)?
-La notación sigma se utiliza para sumar el trabajo realizado en cada iteración de los bucles 'for' que están dentro del método ThreeSum.
¿Por qué se prefiere usar la notación sigma en lugar de una aproximación en Big O?
-La notación sigma proporciona una función de crecimiento exacta, dando el número específico de veces que algo sucede en el programa, a diferencia de Big O, que es solo una estimación de la tasa de crecimiento.
¿Qué es un Computer Algebra System (CAS) y cómo se utiliza en el análisis?
-Un CAS es un sistema que realiza cálculos algebraicos de manera automática. Se utiliza para evaluar y simplificar las expresiones sigma, proporcionando una solución exacta sin tener que realizar los pasos algebraicos manualmente.
¿Cómo se simplifica la función de crecimiento f(N) al final del análisis?
-La función de crecimiento f(N) se simplifica al evaluar y combinar las expresiones sigma, lo que resulta en una expresión algebraica exacta que representa el número de comparaciones necesarias para analizar una entrada dada.
¿Qué significa Big O y cómo se determina en el contexto de este análisis?
-Big O representa una estimación de la tasa de crecimiento de un algoritmo. En este análisis, se determina identificando el término dominante en la expresión algebraica simplificada de f(N), que en este caso es uno sexto N al cubo.
¿Cuál es la importancia de mantener los límites de las sumas sigma ajustados correctamente?
-La importancia de mantener los límites correctos es para asegurar que la función de crecimiento refleje con precisión el número de operaciones que se ejecutan en el programa, lo que a su vez ayuda a obtener un análisis preciso del rendimiento del algoritmo.
Outlines
🔍 Análisis del programa ThreeSum
El vídeo trata sobre cómo emplear un enfoque analítico para examinar el rendimiento de un programa ThreeSum. Se destaca la importancia de identificar la parte del código que se desea analizar y definir un métrica de costo. Se sugiere que no se deben considerar las líneas de código que se ejecutan una sola vez, sino en su lugar, buscar líneas que sean costosas o que se ejecuten con frecuencia. El vídeo enfatiza la necesidad de contar el número de veces que se evalúa una condición específica dentro del método, utilizando una función de crecimiento (growth function) para medir el número de asignaciones que ocurren en relación con el tamaño de la entrada (N). Se introduce el uso de sigmas matemáticas para calcular este crecimiento.
🧮 Utilización de Sigmas para la Análisis
El vídeo explica cómo convertir los bucles for del código en expresiones sigma para poder analizar cuántas veces se ejecuta un bloque de código específico. Se describe el proceso de anidamiento de bucles y cómo cada sigma representa un bucle y se suma para obtener el total de operaciones. También se discute la posibilidad de simplificar la función de crecimiento obtenida mediante la conversión de sigmas en integrales, proporcionando una aproximación del crecimiento del programa. Se menciona la utilización de sistemas algebraicos de computadora (CAS) como WolframAlpha para evaluar y simplificar las expresiones sigma.
📊 Obtención de la Función de Crecimiento Exacta
El vídeo concluye con la obtención de una función de crecimiento exacta para el programa ThreeSum mediante la simplificación de las expresiones sigma. Se menciona la posibilidad de usar técnicas de análisis asintótico para obtener una estimación de(big O) del comportamiento del programa, pero también se enfatiza la importancia de obtener una solución exacta para comprender mejor el rendimiento del código. Se sugiere que, en caso de que la expresión sea difícil de evaluar, se pueden ajustar ligeramente los límites de las sigmas para simplificar la expresión sin cambiar significativamente la precisión del análisis.
Mindmap
Keywords
💡ThreeSum
💡Análisis analítico
💡Growth function
💡Sigma
💡Big O
💡Tilde
💡For loop
💡Comparación
💡Integral
💡Computer algebra system
Highlights
Discussing the analytical approach to analyze a ThreeSum program
Focusing on the code inside the method rather than the functions entered
Deciding on a cost metric for the growth function
Ignoring constant-time operations for the growth function
Selecting a part of the program that is either expensive or frequently executed
Counting the number of times a triple sums to zero as the main work of the program
Defining the growth function f(N) based on the number of assignments
Using mathematical approach with sigmas to analyze the program
Translating for loops into sigma notation to find the exact growth function
Adjusting sigma bounds to match the for loops in the code
Summing up the work done during all iterations of the for loops
Repeating the process for nested for loops
Converting sigmas into integrals for an approximation
Using a computer algebra system (CAS) like WolframAlpha to simplify sigmas
Obtaining the exact growth function F(N) using CAS
Deriving the Big O notation from the most dominant term of the growth function
Considering the use of tables of summations as an old school method
Adjusting bounds for easier evaluation when the exact expression is hard to compute
Transcripts
- So in this video,
I wanna discuss how we can use the analytical approach
to analyze a ThreeSum program.
So it's pretty simple,
but it'll still be a nice example to do.
So we have over there the code that we had
for ThreeSum in our previous video.
So,
the bit of stuff we're basically interested in analyzing
is the code inside of that method.
We don't really care about the functions entered,
that's just kinda information for the program right,
it doesn't really matter.
What we wanna know is
how does the code inside this method actually behave?
So I have all these different lines here.
First thing I need to really do
is think about what do I wanna analyze, right?
What is gonna be my cost metric, right?
What is it that I'm gonna count up right,
with my growth function?
I don't want to count something like
this line over here.
So this is int count equals zero.
If I want to write a growth function for this method,
I don't wanna do it for something like this
because this is always gonna happen just one time, right?
That's not very useful, right, is it really useful to say
that the growth function of this is just equal to one?
No, it's not.
Same thing for the line about it.
N equal a.length.
That again is something where you look at it and you're like
well it happens once.
So is it really useful for my growth function for it?
So look at all program,
what we wanna do is basically pick up a particular
part of it, to analyze, to count up.
Now the general idea is we wanna look for something
that's maybe either expensive or takes a long time to do.
Takes a long time to do,
or something that happens very very frequently.
So where I wanna go actually is with this
assignment line here, this comparison line here.
So this line is basically where we check to see
whether there's a triple that sums to zero.
That's basically my main work that I'm doing, right?
The whole point of my program is to count up
how many times that thing is true.
So to me, it makes sense to say, okay.
That's what I'm gonna count up.
I wanna count up how many times that is evaluated.
So that line there, this if line,
will be exactly what I count up.
So my growth function, or my f(N) is basically gonna say
okay, for particular size and input might mean
the number of data points.
f(N) is gonna compute the number of times
that assignment happens, right?
And so that'll be a pretty good metric for us,
just because that number of assignments
is definitely gonna grow with the input size.
So we'll use that.
So before I do the analysis for us, what can we do?
So I'm going to actually use maybe a little bit more of a
mathematical approach than some of the other
examples we've done here.
And what I'm actually gonna do is I'm goin' to use
sigmas to figure this thing out.
So you notice there I have this expression already drawn
at the bottom, these three sigmas,
and then there's the one in there.
But let's talk through this.
This is actually, basically this is our f(N) if you would.
Actually I can draw it in there,
let's say I write it as f(N), I'll stick with capital N
just because it's in the picture already.
Is equal to these three sigmas.
So that'll be our end result, but I mean,
how do we get there?
Well look at our code.
What we wanna do is basically start
at the line that we're analyzing.
So we're analyzing this line here, this if statement.
And this line, just for sake of argument,
if we're kind of blind to what happens
in other places in this method,
it'll be run exactly once.
So that's actually where my one comes from, right?
'Cause that line is only exists once.
If there was maybe two if statements in there,
then maybe check those three values or somethin',
you maybe check it twice
and you'll have two different if statements,
then maybe I have a different number in there,
like two or three.
Well, it would be two in that case.
But because I only have that one if statement,
there's only one thing happening there,
just one comparison, I'll put a one in there.
Then what I'll do is I'll work from outside the N.
So the next thing I'll analyze
is basically my first for loop.
So this for loop is basically sayin' that
that if statement's gonna happen a bunch of times.
So what I'm doin' in this approach is say okay,
I'm going to write a sigma to sum up
the amount of work that's done by this for loop.
So this for loop runs a bunch of times,
and each time it runs,
inside it does an if statement,
it does that equality check.
That is the work it is doing.
So my summation is summing up
all the different times that if statement is evaluated.
So I want to basically figure out or model
how many times that for loop will run.
To figure out how much work it'll incur.
So what I'm doin' is basically
adding up all the different iterations,
the work that's done during all the different iterations.
And so I'm writing the sigma here
that basically follows the bounds of my if statement.
So my if statement starts, or 'scuse me, my for statement.
My for statement starts at j+1.
And you may notice that our j+1
basically ends up over here.
Or you still see we've even got our k equals over here.
And our upper bound, or our N, appears over here,
the top of the sigma.
So our usage here of a sigma in terms of math
is basically just copied from that for statement, right?
We're gonna start a certain place,
we're gonna end a certain place.
And that's gonna basically serve
to sum up the number of operations that's needed
to execute that loop and everything within it.
Once we have that, we can basically just repeat the process.
So we can say okay, look at the next line,
the next for loop.
Write another sigma, right?
And this other sigma will again use this
basically the same starting place, the same ending place
as what's given in the code.
So we're just indicating over here.
All right, obviously these things are nested,
so we wanna put them basically inside of one another, right?
So we're summing a sum.
It's actually a little bit different
than just multiplying the different for loops together.
This is kinda a more direct way to do it,
you're summing up the work of the work that's being summed.
And you can picture maybe there's,
if you distribute it in your head right,
you can see maybe the multiplication
is happening behind the scenes.
Now we just do this one final time
with this last for loop here.
This last for loop, of course, amounts to one sigma.
And then we have basically our bounds
being copied over again,
we start at zero, end at one.
Over here, our lower bounds are adjusted by one
basically to make the sigmas line up, right?
Because in a for loop,
we have the issue of that end point
is basically less than, rather than less than equal to,
and so there's kinda this thing we need to massage
to make sure that we're touching exactly as many,
or we're analyzing exactly as many items
as will actually be seen by that for loop.
Okay.
So we've basically gone through right,
and converted each of these for loops to a sigma.
And so now we have what amounts to an exact expression.
Now if we want to do some sort of other analysis,
where we maybe say oh hey, this looks like,
goes from zero to N, so therefore it happens O(N) times.
And the other one happens O(N) times.
The other one happens O(N) times,
we could have done sort of analysis as well.
That would have been fine.
There we basically would have had to multiply
everything at the end, and at the end, we would have said
that this is O(N) cubed.
That's completely fine.
But that's basically an approximation, right?
Big O is an upper bound, it's not an exact value.
It's not a tight bound.
Here what we're interested in
is trying to obtain the actual growth function right?
The function that exactly gives me
the number of times something happens in this program.
So that's what we've done here with our sigma notation.
And every sigma is mapping exactly to a for loop
with the bounds copied over.
All right, so we have this expression here.
So this is our F(N).
So we have our exact growth function
that we can basically plug in our particular problem size
and get back out how many different comparisons
are gonna be needed in order to analyze that input.
All right.
So, okay there's actually a question here about a side
that I do wanna talk about, so it says,
"Could we instead pick the numbers in increment",
so this is referring back to what is our cost model, right?
How are we picking what it is we wanna count up.
We decided we would go with the equal,
but then the other choice maybe would have been
this plus plus because that's something that maybe happens
frequently in a program.
It's gonna be less frequently than the equal equal,
but it's still pretty frequent.
Now that plus plus,
well...
It's not gonna be the best thing for us to choose.
And rather than answer that question right now,
I want you to think about that
and then in a future video, probably the next one,
we'll discuss it more in detail.
So I'll give you a hint,
it's not a good idea to count the plus plus, but why is it?
All right, so getting back to that growth function,
that F(N).
It's kind of bulky right,
if I want to evaluate F(N) for a particular value of N,
then I need to evaluate three sigmas,
then I'll take me a little bit of time.
I maybe actually need to get a calculator out,
it's not something I can easily do.
So what can I do?
I could try to simplify this.
So ideally, I would just have some polynomial
on the right hand side that has basically
the closed loop solution to this, right?
It basically just has okay,
something something, N cubed plus N squared
plus something something.
That's what I want.
So what can I do?
I can maybe think of having this,
well I could try to flatten it, basically.
And there's a bunch of different approaches to doing this.
One maybe easy thing you could do
is basically convert those sigmas into integrals.
And basically those discrete sums,
instead we treat them as container sums.
We can put those in there and evaluate all those,
and we'll get an approximation.
So over here, we're basically saying,
okay the sigma formula that I talked about,
I'll take that, convert it into integral form.
We have to put on our dxes of course.
And then that gets us in the end
this one sixth N cubed.
But that's an approximation, right?
Remember the integrals are at about,
basically this assumption that we're treating
our variables as being these containers things,
whereas the sigmas are about discrete variables, right?
So there's kinda this little margin of error,
if you maybe picture back to when you took calculus
and there's this idea of
your integration where you have
either your thin slices you cut out from your graph,
or these thick ones, right?
The thick ones are kind of more discrete.
There's always this little area between those thick ones
in the graph that's basically your margin of error.
So that's what we've kind of lost here.
We've only recovered in approximation.
That said, it's still a nice thing to do
because usually integrals like this
are gonna be pretty easy to evaluate,
and you could just do them in your head.
So.
That's one thing to do.
The other thing people do a lot, or used to do,
and thankfully we don't have to do it anymore,
is they used to use tables of summations.
So what they would have is you would go,
and if you were taking discrete math,
you'd flip to the last couple pages of that textbook,
and the last couple pages of that textbook
would basically just be tables of all these sigmas,
and say okay, if you had this sigma
that goes from this bound to this bound,
it's gonna be equal to this polynomial.
And there'd just be pages and pages and pages.
I mean there's literally, if go look,
there's a book out there, I forget the exact name,
but it's about 600 pages just of tables like that.
And basically, summarizing common integrals,
or summarizing common sigmas or products or whatever.
But that's really kind of old school,
and we don't have to do that anymore.
What we should just do is this, right?
Make a machine do it for us.
So in this case, I have WolframAlpha.
So what I basically did is I said okay,
for that sigma that I've written by hand,
I know it's right because I figured it out
right from the code.
I wanna write that in the syntax required by WolframAlpha,
and then that syntax, I just feed in there.
And I click Run, right?
I have the CAS system evaluate it.
CAS stands for computer algebra system.
You don't have to do this just in WolframAlpha,
you can put this into something like Mathematica,
you can put this on your TI-89
if you're lucky enough to have one.
And find out what is the result.
So don't actually bother with all the algebraic steps,
don't bother looking up stuff.
Just make a machine do it right?
There's no sense in us having to memorize how to do this.
And so then over here, what we have
is the result that we're looking for.
So this is the exact result.
So my F(N), right,
my F(N) at the end of the day,
once we've cleared out and simplified the sigmas,
is equal to one sixth N times, and then in parentheses,
N two minus N three plus two, closed parenthese.
So that's an exact solution,
and that's what we want when we talk about growth functions,
we want an exact number of times something happened, right?
Exact number of comparisons in this case.
So.
That is our kind of end result, right,
we have our F(N) and we're good to go.
Now if I wanna do something like figure out big O,
then I would, well I'd do a little bit of work, right?
I guess maybe just for a practice real quick,
if you look at this,
big O comes from the most dominant term.
And so what would happen if we're tryin' to figure out big O
is we'd have to multiply this out.
And then pick the most dominant term.
In that case, I would actually end up being
one sixth N cubed.
Throw away the constant 'cause it's big O.
And that would give us O(N) cubed.
For tilde right?
Tilde we don't throw away the constant,
so the tilde of this would be one sixth N cubed.
Okay.
So there you have it.
That's our analysis of the ThreeSum program
using the sigma approach to give us the exact answer.
One kind of note here
is that sometimes you'll play with your bounds.
So over here, why we adjust these a little bit
in order to get them to match exactly with the code.
Sometimes people won't do that.
If the expression you're sharing
is really really really really hard to evaluate,
and not even the CAS can do it.
Then maybe you can play with your bounds a little bit
and maybe loosen them up.
Now you're not gonna get an exact answer.
It'll be an approximation.
But it'll be a better approximation
than just doing the big O thing
and throwing away everything but the dominant term.
Or throwing away everything but the overall character
of each of those loops.
So that is fair game and people'll do that,
just to adjust those, basically that starting point
and ending point on those sigmas.
Main thing, you wanna make sure
you always preserve the variables, right?
So I, J, K, and those for sure need to stay the same.
Or the coefficients on them need to stay the same for sure.
But if you wanna play with the plus minus,
make things simpler, that's fair game.
浏览更多相关视频
[SER222] Characterizing Algorithms (5/5): Analysis Approaches
Functions | Computer Programming | Khan Academy
Function Parameters | Computer Programming | Khan Academy
[SER222] Analytical Analysis (1/5): Defining f(n)
15 - Definir funciones en PHP - Curso PHP 8 desde cero (Actualizado)
[MOOC] - Apps para dispositivos móviles (ed. 2016) - iOS. Desarrollo de una App
5.0 / 5 (0 votes)