[SER222] Empirical Analysis (1/8): The Empirical Process
Summary
TLDREste video ofrece una visión general del proceso para construir empíricamente la función de crecimiento de un algoritmo. Se explican los pasos clave: establecer una serie de pruebas con diferentes entradas, medir el tiempo de ejecución, realizar un análisis de regresión para construir un modelo matemático y, finalmente, validar la precisión del modelo con nuevos datos. Se destacan las ventajas y desventajas de este enfoque, incluyendo su independencia de la implementación y la rapidez del proceso, pero también su inexactitud y dependencia del entorno de evaluación.
Takeaways
- 🔍 La meta es analizar un algoritmo como un 'caja negra' observando su comportamiento con diferentes entradas.
- 📊 Para construir una función de crecimiento empírica, se requiere de un conjunto de pruebas con diferentes entradas y sus tamaños asociados.
- ⏱ Se debe medir el tiempo que toma el algoritmo para procesar cada entrada y crear un mapa de tamaño de problema a tiempo de ejecución.
- 📈 Se utiliza análisis de regresión para construir un modelo que relacione el tamaño de entrada con el tiempo de ejecución.
- 🔍 Se busca un modelo empírico que sea una aproximación de la función de crecimiento del algoritmo.
- 🔄 Es necesario validar el modelo con entradas de tamaño no utilizados en la creación del modelo para asegurar su precisión.
- 🔄 Si el modelo no es preciso, se debe regresar a la fase de benchmarking y ajustar el conjunto de pruebas.
- 🌐 La ventaja del enfoque empírico es que no se requiere el código fuente del algoritmo, lo cual es útil para bibliotecas de terceros.
- ⏱ Este método es más rápido que el análisis analítico, ya que no se examina cada línea de código.
- ⚠️ Los desafíos incluyen la inexactitud inherente al modelo, la posibilidad de no capturar casos extremos y la dependencia del entorno de evaluación.
- 🔄 El proceso iterativo de prueba, modelado y validación es similar al método científico de hipótesis y verificación.
Q & A
¿Cuál es el objetivo principal de analizar un algoritmo como si fuera una caja negra?
-El objetivo principal es observar cómo actúa el algoritmo con diferentes entradas para modelar o predecir su comportamiento en función del tamaño de las entradas.
¿Qué significa el enfoque empírico para el análisis de un algoritmo?
-El enfoque empírico implica realizar pruebas observacionales para modelar el comportamiento del algoritmo basándose en los datos obtenidos, sin necesidad de analizar el código fuente.
¿Cómo se inicia el proceso de análisis empírico de un algoritmo?
-Se inicia definiendo un conjunto de entradas diferentes, ejecutando el algoritmo con esas entradas y midiendo el tiempo que toma cada ejecución.
¿Por qué es importante asociar un tamaño de entrada a cada prueba realizada?
-Es necesario para crear un mapa del tamaño de la entrada al tiempo de ejecución, lo cual es esencial para construir una función de crecimiento empírica.
¿Qué es la análisis de regresión y cómo se relaciona con el análisis de un algoritmo?
-El análisis de regresión es una técnica estadística utilizada para construir un modelo que predice el tiempo de ejecución del algoritmo a partir del tamaño de la entrada.
¿Qué es una función de crecimiento empírica y cómo se obtiene?
-Una función de crecimiento empírica es un modelo matemático aproximado que relaciona el tamaño de la entrada con el tiempo de ejecución del algoritmo, obtenida a partir de los datos de pruebas.
¿Por qué es necesario probar el modelo con un tamaño de entrada que no se haya utilizado en la creación del modelo?
-Es necesario para evaluar la precisión del modelo y asegurarse de que pueda predecir adecuadamente el tiempo de ejecución para nuevos tamaños de entrada.
¿Cuáles son las ventajas de utilizar el enfoque empírico para analizar un algoritmo?
-Las ventajas incluyen no necesitar el código fuente, ser más rápido que el análisis analítico y ser útil para bibliotecas de terceros sin acceso al código fuente.
¿Cuáles son las desventajas del enfoque empírico en el análisis de algoritmos?
-Las desventajas incluyen la imprecisión de las predicciones, la dependencia del entorno de evaluación y la posibilidad de no capturar todos los comportamientos del algoritmo debido a casos extremos no probados.
¿Cómo se relaciona el proceso de análisis empírico con el método científico?
-El proceso de análisis empírico sigue el método científico al hacer predicciones basadas en pruebas, evaluar esas predicciones y actualizar el modelo en base a los resultados.
¿Qué sucede si el modelo no es capaz de predecir adecuadamente el tiempo de ejecución para una nueva entrada?
-Si el modelo no predice adecuadamente, se debe volver a la fase de benchmarking para incluir más entradas en el conjunto de pruebas y construir un nuevo modelo.
Outlines
🔍 Análisis empírico del crecimiento de un algoritmo
El video ofrece una visión general del proceso para construir de manera empírica la función de crecimiento de un algoritmo. Se destacan cuatro pasos principales para analizar un algoritmo como si fuera un cuadro negro, observando su comportamiento con diferentes entradas. Se menciona la necesidad de realizar un conjunto de pruebas para diferentes tamaños de entrada y calcular el tiempo que toma el algoritmo para ejecutarse. A partir de estos datos, se realiza un análisis de regresión para construir un modelo que relacione el tamaño de la entrada con el tiempo de ejecución. Finalmente, se sugiere probar el modelo con nuevos tamaños de entrada para evaluar su precisión y, si es necesario, ajustar el modelo con más pruebas.
🔧 Ventajas y desventajas del análisis empírico
El video también discute las ventajas y desventajas del enfoque empírico. Entre las ventajas, se destaca la independencia de la implementación y la rapidez del proceso, lo cual es especialmente útil para bibliotecas de terceros que no proporcionan el código fuente. Sin embargo, los desafíos incluyen la imprecisión inherente al enfoque empírico, ya que siempre hay un margen de error en las predicciones. Además, existe la posibilidad de que ciertos casos extremos no sean capturados por el conjunto de pruebas y, por lo tanto, no se tomen en cuenta al construir el modelo. También se señala que los resultados pueden variar según el entorno de evaluación, aunque los patrones generales, como la relación N o N cuadrado, son consistentes entre diferentes computadoras.
Mindmap
Keywords
💡Algoritmo
💡Función de crecimiento
💡Enfoque empírico
💡Benchmarking
💡Entrada
💡Tamaño de la entrada
💡Regresión
💡Modelo
💡Predicción
💡Validación
💡Método científico
Highlights
Empirical approach to constructing an algorithm's growth function
Four main steps for empirical analysis of an algorithm
Analyzing algorithms as a black box to observe behavior with different inputs
Benchmarking an algorithm with a set of different inputs
Importance of associating input size with each test
Timing the algorithm's execution for each input size
Using regression analysis to build a model of the algorithm's runtime
Creating an empirical growth function from the model
The necessity of testing the model with new, unseen input sizes
Evaluating the model's prediction against actual runtime
Iterating the process to improve model accuracy
Advantages of the empirical approach over analytical methods
Disadvantages such as in-exact predictions and dependence on the evaluation environment
The empirical process resembling the scientific method
How the empirical approach can be applied to benchmark a sample program
The impact of different hardware on the empirical results
The generalizability of variables in empirical growth functions across different computers
Transcripts
- In this video, I'm going to give an overview
of the process for constructing
an algorithm's growth function empirically.
So, on the left here, I have four main steps,
and we'll go through those one by one.
As kind of a reminder, our goal is the following.
We're in the section, right, talking
about different ways to analyze an algorithm
and one way you can have, right, instead
of looking at every single line of code
in a program is to actually take a look at that algorithm
out of that program in terms of a black box.
Basically, you just observe how it acts
when put in different inputs.
From that, we can basically try to model, right,
or guess, how that algorithm will act, right,
when I give it different size inputs
or I can do it purely based on observation
and that's what called the Empirical Approach.
So how do I do that?
Well, let's assume for a moment
that we already have an algorithm
or a method, let's say I'll be listing a method
that I want to analyze, right,
I wanna find out it's growth function.
First thing I need to do is I need to benchmark it.
So what I'll do is I'll come up
with an entire set of different inputs, right,
and sometimes, right, maybe you run it
on two different inputs, sometimes you run it
on a hundred different inputs.
Whatever you think is appropriate
for determining how the thing grows, right, how that thing,
how much time or how much work it takes
for that algorithm to run or that method to run.
All right, so if it's something really simple,
maybe you can get away with just a few inputs,
but if you're looking at a thousand lines of code
and their's all sorts of different variations
of the inputs you could probably put into that thing,
well, then that means you just have a bunch
of different tests for it, right,
and so all this little suite here,
basically you have a suite of tests, right?
Maybe, so let's say you have a dozen
just for sake of argument.
Take all those different possible inputs,
they all should have associated
with them an input size, right?
So there's always the size N, right,
am I gonna test my certain algorithm
I'll assume it has a hundred elements in it.
Of course then it has one element in it,
ten elements in it, whatever, right?
Every single one of my tests has
to have a problem size associated with it.
The reason, is that, at the end of the day, we want a map
from problem size to how long it takes to run.
All right, so we have all our different inputs.
Feed them all into the method one by one,
and time how long it takes, right?
So all of a sudden we have is these parings,
is they say, "okay, for this size input,
this is how long it took, for this size input,
this is how long it took" and so on and so forth.
Given that we have all those different pairs of data,
what we can next think about doing is some sort
of regression analysis, right?
We can build a model that somehow calculates the run time,
from the size of the input, right?
So we can picture, go back to basic algebra,
you have maybe a graph, right,
and you have your scatter plot of the different pairs
of how long something took to run based
on what its input size is, and we have that, right,
and we could think about doing something like a regression,
and it usually won't be that simple, but, you know,
for sake of argument, we could say it's a regression,
right, and you found, you know,
a linear function for a quadratic function.
Whatever it is, right, we can discover that for that input
and so what that gives us is a potential mathematical model
that relates the size of the input
to how long it takes to run.
Basically what we have is an empirical growth function.
Keep it mind that it will be an approximate.
Now, at that point, we're not done
and it might seem that we are,
because we have a growth function for us,
but that's not really good enough for us.
What we wanna do is the following.
What we wanna do is you wanna pick a problem size,
that's not in one of our input tests, right?
Not something we use to create the model,
we wanna pick something new.
So if we use sizes a hundred, ten,
I want to check how well my sort algorithm works,
or maybe I'll try something else, like two hundred,
I don't know.
It can just be something that's outside of the input set,
and we want to take that input size, feed it
to our mathematical model, right,
our approximate growth function, and figure out how long
that growth function thinks our algorithm will run for
or our method will run for, right?
So we have basically a prediction being made from our model.
Then we can evaluate that prediction, right?
We can go to our basic code, and we can feed it
this new test input or the new size, right?
Size two hundred, or whatever,
and then see how closely the run time
that it actually gives us in practice is to the input,
well, is to the result that was calculated
by our potential growth function, right?
What we wanna do is you wanna check
that our model is accurate, right,
or we wanna basically assess the accuracy
of our model, right?
If our model is not able to predict
how long it takes for this new input to run,
well then it's worthless, right?
We want a model that, when I give it an input size,
has a decent shot at computing
for me how long that method will take.
Now, if I run into a situation where,
maybe I get a good result, right,
it looks pretty close, I'm not done yet.
Probably, I'm gonna check in on a couple more results,
maybe I check on three hundred,
maybe I take on five, now if those also look good,
well, then I'm good to go, right?
That first function that I got from my regression,
that first model, right, that I got
from my regression stuff is good to go.
I can use that.
Otherwise, what I have to think about is, "Oh, hey,
this, you know, maybe there's something not being captured
by the set of input I have to that regression test."
So I'm gonna return to my benchmarking faze, right?
Maybe come up with a different, a couple more inputs,
right, that have different sizes, feed that to that,
you know, that method that benchmark,
figure how long it takes to run,
and then, right, build a new model
that's now inclusive of that data.
Right, so I've basically updated my tests,
say, I get a new model, now I can repeat the process, right?
So then I make a new prediction
from my new model, and then I check that prediction again,
see what the method actually does, right, and I'll need
to repeat this until my model is accurately
predicting my sample inputs to it, right?
Once I have that, then I'm pretty sure
that I have a decent level of accuracy.
I mean, there will always be the case
that there was something that's not really captured
in our inputs sets, but that's basically just one
of the risks we run with doing this.
Now I'm gonna talk about advantages,
disadvantages in a second, but just to draw your attention
to this little note in the right-hand side,
there's a note that says "seem familiar?"
Hopefully, this does seem familiar.
Basically, what this is is the scientific method,
right, of making predictions, of hypothesis,
and checking them, right?
Maybe using those to update our views,
our understanding of the situation,
making a new prediction, right, a new hypothesis.
So this is very much a scientific approach in my opinion.
So let's talk a little more of the advantages
and disadvantages of doing analysis this way.
So, advantages.
First big thing, right, is that we don't really have
to worry about the implementation.
In fact, I don't even need the code
for that function because I don't care.
All I care about is that I can invoke
that function or that method, right,
because I need to give it some input,
time how long it takes, right, and then, you know,
make a note of that somewhere,
but what happens inside is none of my business.
I don't need to worry about the different operations
that are in there; I don't need to have the source code.
So this is great for something like a third party library.
Third party library typically don't give you source code,
so, well, you can still benchmark it, right?
In that case, right, the analytical approach,
looking line by line, doesn't even apply,
because we don't have the original code.
Here, if we're just doing it as a black box,
well, then, we're good to go, right?
We can take a look of their function
that they gave us in the library,
run a DLL, run it, see how long it takes.
No problem for us.
It's fast, right, this is another advantage.
We already said there was issues in analytical
where we have to look at every line, it just takes forever.
Here maybe you can hope to do this in an hour, right?
It's mostly plug-and-chug, as long as you can
have a good way of coming up with your test sets,
right, and then collect your data,
I mean, regression is really easy.
So it's generally a much faster process
than doing it the analytical way.
So, disadvantages, some of these,
right, are a little bit related.
First of the disadvantages is in-exact, right?
So there's always going to be some margin
of error in our prediction.
So, even if my model, right, is generally matching,
you know, what I expected to give,
right, when I do an arbitrary test, you know,
the model can correctly predict the run time
or how long it takes, right, to run
on that particular input.
There will always be, right, some sort
of little margin of error.
Just because you don't really know what's happening, right?
There could always be, you know, some little if branch
that just gets run, you know, one in a thousand times,
you don't really know that and so there will always be
these little fluctuations in your data
and in your predictions, and that's kind of,
really, the second bullet point there
which is the black box, right?
There's always the chance that there is some code
in my function that maybe takes a lot more time
than what, you know, how long it typically takes,
right, and in my test cases I'm just not seeing it
for whatever reason, right?
There's some sort of edge case, you know,
that changes how this thing acts.
Well, with an empirical approach,
if there's something that's not seen by that test suite,
well, then it's not going to be taken into account
when we create our model, right, using regression.
So we just have this chance, right,
that all of a sudden the function is completely different
than what we expect just because
we are taking a black box approach
and we can't guarantee that we've looked
at all the different ways it can behave.
Last note here is that it depends on evaluation environment.
So if we're writing a function, or if we're trying
to determine the growth function, right,
in terms of time, right, it's very exact hopefully,
well, it's gonna be approximate
but maybe it can give us at least down to the second,
right, maybe millisecond's off
but second's fine, how long something takes,
well, there's the issue in that
whatever results we get will be specific to the computer
that we did the tests on, right?
So, if I have different hardware,
it's gonna take a different amount of time, right?
Obviously.
I have different programs running in the background,
well, then it's gonna take a different amount of time.
There are a thousand factors that influence
how long it takes your program or your method to run.
So these results we get really only apply
to the machine that we run then on.
That said, what will generalize is somehow,
like the variables in there.
So, the part that tends to vary is somehow the constants
and the expression recover, maybe are not so useful
because they are depending on the machine,
but in there they'll be saying like,
you know, N or N squared.
Generally those things are depending on variables,
those will be the same between different computers
and so that is going to be valuable for us.
All right, so there we have it,
that's an overview of The Empirical Process,
now we're going to take a look at how we're to apply
this to benchmark a sample program.
Weitere ähnliche Videos ansehen
Ep1 | ¿Qué es probar? Fundamentos de ISTQB en español #CTFL #Probar #QA #ISTQB
Práctica: Caracterización de un Voltímetro Analógico
¿Qué es un modelo de competencias? y ¿Cómo hacer una gestión por competencias?
[SER222] Empirical Analysis (7/8): Modeling Small Datasets
[SER222] Empirical Analysis (6/8): Predicting and Validating ThreeSum
Pronósticos de Producción (Teoría) #1
5.0 / 5 (0 votes)