[SER222] Analytical Analysis (4/5): Analysis of ThreeSum

Summary

El 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

00:00

🔍 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.

05:02

🧮 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.

10:03

📊 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.

Keywords

💡ThreeSum

ThreeSum es un problema de programación común que consiste en encontrar triples de números en una lista que sumen un valor específico, en este caso cero. En el video, se utiliza ThreeSum como ejemplo para analizar un programa de forma analítica. El objetivo es contar cuántas veces se evalúa la condición de que la suma de tres números sea cero, lo cual es clave para entender el rendimiento del programa.

💡Análisis analítico

El análisis analítico es un método para evaluar el comportamiento de un programa a través de la creación de una función de crecimiento (growth function) que mide la cantidad de trabajo realizado por el programa en relación con la entrada. En el video, se utiliza el análisis analítico para determinar la complejidad del programa ThreeSum y para entender cuántas veces se ejecuta una cierta línea de código.

💡Growth function

La función de crecimiento (growth function), representada como f(N) en el video, es una herramienta utilizada en análisis analítico para medir la cantidad de trabajo realizado por un programa en función de la entrada. Se define como el número de veces que se evalúa una condición en particular dentro del código, y se usa para modelar el comportamiento del programa ThreeSum.

💡Sigma

El símbolo sigma (Σ) se utiliza en matemáticas para representar la suma de una serie de términos. En el video, se utilizan sumas sigma para modelar las iteraciones de los bucles for en el código de ThreeSum y para calcular la función de crecimiento. Cada sigma representa el número de veces que se ejecuta un bucle y se suma para obtener el total de evaluaciones de la condición.

💡Big O

Big O es una notación en informática que describe el comportamiento asintótico de una función cuando el tamaño de la entrada se hace muy grande. En el video, se menciona Big O para discutir cómo se podría aproximar la complejidad del programa ThreeSum sin obtener la función de crecimiento exacta, simplemente identificando el término dominante en la expresión.

💡Tilde

La tilde (~) en análisis de algoritmos indica que se está considerando el comportamiento asintótico de una función incluyendo los términos constantes. En el video, se menciona que el comportamiento asintótico de la función de crecimiento ThreeSum, con tilde, sería de la forma de una fracción del cubo de N.

💡For loop

Un bucle for es una estructura de control de flujo utilizada en programación para ejecutar un bloque de código repetidamente. En el video, los bucles for son cruciales para el análisis del programa ThreeSum, ya que la cantidad de veces que se ejecutan estos bucles influirá directamente en la complejidad del programa.

💡Comparación

La comparación es una operación fundamental en programación que se utiliza para evaluar si dos valores son iguales, mayores o menores. En el video, la comparación (==) es el foco principal del análisis, ya que se cuenta cuántas veces se verifica si la suma de tres números es cero para determinar la función de crecimiento.

💡Integral

Las integrales son una herramienta matemática utilizada para calcular el área bajo una curva y se pueden usar para aproximar sumas discretas. En el video, se sugiere la conversión de sumas sigma en integrales como una técnica para simplificar el análisis y obtener una aproximación de la función de crecimiento.

💡Computer algebra system

Un sistema de álgebra computacional (CAS) es un tipo de software que realiza cálculos matemáticos de manera simbólica. En el video, se menciona el uso de WolframAlpha, que es un CAS, para simplificar las sumas sigma y obtener la función de crecimiento exacta del programa ThreeSum.

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.