py_pal.analysis¶

py_pal.analysis.complexity¶

Definition of complexity classes.

class py_pal.analysis.complexity.Complexity[source]¶

Bases: object

Abstract class that fits complexity classes to timing data.

compute(n: numpy.ndarray) → float [source]¶: Compute the value of the fitted function at n.

fit(n: numpy.ndarray, t: numpy.ndarray) → float [source]¶

Fit complexity class parameters to timing data.

Parameters

n (numpy.ndarray) – Array of values of N for which execution time has been measured.
t (numpy.ndarray) – Array of execution times for each N in seconds.

Returns

Residuals, sum of square errors of fit

Return type

numpy.ndarray

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

transform_y(t: numpy.ndarray)[source]¶: Transform time as needed for fitting. (e.g., t->log(t)) for exponential class.

class py_pal.analysis.complexity.Constant[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

class py_pal.analysis.complexity.Cubic[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

class py_pal.analysis.complexity.Exponential[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

transform_y(t: numpy.ndarray)[source]¶: Transform time as needed for fitting. (e.g., t->log(t)) for exponential class.

class py_pal.analysis.complexity.Linear[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

class py_pal.analysis.complexity.Linearithmic[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

class py_pal.analysis.complexity.Logarithmic[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

exception py_pal.analysis.complexity.NotFittedError[source]¶: Bases: Exception

class py_pal.analysis.complexity.Polynomial[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

transform_y(t: numpy.ndarray)[source]¶: Transform time as needed for fitting. (e.g., t->log(t)) for exponential class.

class py_pal.analysis.complexity.Quadratic[source]¶

Bases: py_pal.analysis.complexity.Complexity

classmethod format_str()[source]¶

Return a string describing the fitted function.

The string must contain one formatting argument for each coefficient.

transform_n(n: numpy.ndarray)[source]¶

Terms of the linear combination defining the complexity class.

Output format: number of Ns x number of coefficients.

exception py_pal.analysis.complexity.UnderDeterminedEquation[source]¶: Bases: Exception

py_pal.analysis.estimator¶

class py_pal.analysis.estimator.AllArgumentEstimator(*args, arg_selection_strategy: py_pal.analysis.estimator.ArgumentDataSelectionStrategy = <ArgumentDataSelectionStrategy.MEAN: 'mean'>, opcode_selection_strategy: py_pal.analysis.estimator.ArgumentDataSelectionStrategy = <ArgumentDataSelectionStrategy.MEAN: 'mean'>, **kwargs)[source]¶

Bases: py_pal.analysis.estimator.Estimator

py_pal.analysis.estimator implementation that treats all arguments as one by averaging out the proxy value of all arguments.

infer_complexity_per_argument(data_frame: pandas.core.frame.DataFrame, arg_names: List[str]) → Tuple[List[str], Union[Exception, py_pal.analysis.complexity.Complexity], pandas.core.frame.DataFrame][source]¶: View all argument axes together and sort argument proxy value ascending

class py_pal.analysis.estimator.ArgumentDataSelectionStrategy(value)[source]¶

Bases: enum.Enum

An enumeration.

MAX = 'max'¶

MEAN = 'mean'¶

MIN = 'min'¶

class py_pal.analysis.estimator.Estimator(call_stats: numpy.ndarray, opcode_stats: numpy.ndarray, per_line: bool = False, filter_function: str = False, filter_module: str = False)[source]¶

Bases: abc.ABC

Base class which provides functionality to transform statistics collected by the py_pal.data_collection.Tracer to pandas.DataFrame objects, ways to aggregate opcode statistics per function call and fit the py_pal.analysis.complexity classes.

aggregate_opcodes_per_target(target: List[py_pal.settings.Columns]) → pandas.core.frame.DataFrame[source]¶

analyze() → Tuple[str, int, str, List[str], py_pal.analysis.complexity.Complexity, int, pandas.core.frame.DataFrame, float][source]¶

property calls: pandas.core.frame.DataFrame¶

export() → pandas.core.frame.DataFrame[source]¶: Export results. The output order can be controlled with df_analyze_order.

group_opcodes_by_call(data: pandas.core.frame.DataFrame, group_by: List[py_pal.settings.Columns], result_columns: List[py_pal.settings.Columns]) → Tuple[str, int, str, List[str], pandas.core.frame.DataFrame, float][source]¶

static infer_complexity(data_frame: pandas.core.frame.DataFrame, arg_column: py_pal.settings.Columns) → py_pal.analysis.complexity.Complexity [source]¶

Derive the big O complexity class.

Parameters

arg_column (py_pal.util.Columns) – Argument column to use as x-axis.
data_frame (pandas.DataFrame) – Time series-like data, x-axis is argument size, y-axis is executed opcodes.

Returns

Best fitting complexity class

Return type

py_pal.analysis.complexity.Complexity

abstract infer_complexity_per_argument(data_frame: pandas.core.frame.DataFrame, arg_names: List[str]) → Tuple[List[str], py_pal.analysis.complexity.Complexity, pandas.core.frame.DataFrame][source]¶

Abstract method definition for the data transformation function. The implementation prepares the dataset for evaluation with the least squares method. The dataset is transformed with respect to the arguments (their proxy value) of the function. Finally, py_pal.analysis.estimator.infer_complexity() is executed and the result is returned.

Arguments:
data_frame (pandas.DataFrame): dataset arg_names (List[str]): argument names of function

Returns:
pandas.DataFrame: arguments considered in the analysis, estimated complexity class and the data considered in the analysis

property iterator: Tuple[str, int, str, List[str], pandas.core.frame.DataFrame, float]¶

property opcodes: pandas.core.frame.DataFrame¶

class py_pal.analysis.estimator.SeparateArgumentEstimator(call_stats: numpy.ndarray, opcode_stats: numpy.ndarray, per_line: bool = False, filter_function: str = False, filter_module: str = False)[source]¶

Bases: py_pal.analysis.estimator.Estimator

Voodoo py_pal.analysis.estimator that tries to infer complexity for each argument separately. Even though the influence of arguments on each other is minimized this may not produce reliable results and therefore should be viewed as experimental.

analyze_args_separate_ascending(data_frame: pandas.core.frame.DataFrame)[source]¶

infer_complexity_per_argument(data_frame: pandas.core.frame.DataFrame, arg_names: List[str])[source]¶: Try to look at each argument individually and sort the argument proxy value in ascending order.

static map_arg_names(pos, names: List[str])[source]¶

static unpack_tuples(data_frame: pandas.core.frame.DataFrame)[source]¶