| import math
|
| from typing import Dict, Optional
|
|
|
|
|
| class ComplexityScorer:
|
| """
|
| Complexity scoring for feature selection algorithms
|
| based on instantiated time and space complexity.
|
| """
|
|
|
| def __init__(self, alpha: float = 0.7, log_base: float = math.e):
|
| """
|
| Parameters
|
| ----------
|
| alpha : float
|
| Weight for time complexity in the final score.
|
| Typical values: 0.6 ~ 0.8
|
| log_base : float
|
| Base of logarithm (default: natural log).
|
| """
|
| self.alpha = alpha
|
| self.log_base = log_base
|
|
|
|
|
|
|
|
|
|
|
| def _log(self, x: float) -> float:
|
| """Logarithm with configurable base."""
|
| if self.log_base == math.e:
|
| return math.log(x)
|
| return math.log(x, self.log_base)
|
|
|
| def complexity_score(self, value: float, min_value: float) -> float:
|
| """
|
| Generic complexity-to-score mapping.
|
|
|
| Parameters
|
| ----------
|
| value : float
|
| Instantiated complexity value of an algorithm.
|
| min_value : float
|
| Minimum complexity among all compared algorithms.
|
|
|
| Returns
|
| -------
|
| score : float
|
| Normalized score in (0, 1].
|
| """
|
| if value <= 0 or min_value <= 0:
|
| raise ValueError("Complexity values must be positive.")
|
|
|
| ratio = value / min_value
|
| return 1.0 / (1.0 + self._log(ratio))
|
|
|
| def time_score(self, f_t: float, f_t_min: float) -> float:
|
| """Time complexity score."""
|
| return self.complexity_score(f_t, f_t_min)
|
|
|
| def space_score(self, f_s: float, f_s_min: float) -> float:
|
| """Space complexity score."""
|
| return self.complexity_score(f_s, f_s_min)
|
|
|
| def total_score(
|
| self,
|
| f_t: float,
|
| f_t_min: float,
|
| f_s: float,
|
| f_s_min: float,
|
| ) -> float:
|
| """Combined complexity score."""
|
| s_t = self.time_score(f_t, f_t_min)
|
| s_s = self.space_score(f_s, f_s_min)
|
| return self.alpha * s_t + (1.0 - self.alpha) * s_s
|
|
|
|
|
|
|
|
|
|
|
|
|
| def instantiate_complexity(
|
| formula: str,
|
| n: int,
|
| d: int,
|
| k: Optional[int] = None
|
| ) -> float:
|
| """
|
| Instantiate asymptotic complexity formula.
|
|
|
| Supported variables: n, d, k
|
|
|
| Examples
|
| --------
|
| "n * d**2"
|
| "n * d * k"
|
| "d**2"
|
| "d + k"
|
| """
|
| local_vars = {"n": n, "d": d}
|
| if k is not None:
|
| local_vars["k"] = k
|
|
|
| try:
|
| return float(eval(formula, {"__builtins__": {}}, local_vars))
|
| except Exception as e:
|
| raise ValueError(f"Invalid complexity formula: {formula}") from e
|
|
|
|
|
| n, d, k = 1000, 50, 10
|
|
|
| algorithms = {
|
| "mRMR": {"time": "n * d**2", "space": "d**2"},
|
| "JMIM": {"time": "n * d * k", "space": "d * k"},
|
| "CFR": {"time": "n * d * k","space": "d + k"},
|
| "DCSF": {"time": "n * d * k", "space": "d + k"},
|
| "IWFS": {"time": "n * d * k", "space": "d + k"},
|
| "MRI": {"time": "n * d * k", "space": "d + k"},
|
| "MRMD": {"time": "n * d**2", "space": "d**2"},
|
| "UCRFS": {"time": "n * d + n**2", "space": "n**2"},
|
|
|
|
|
| }
|
|
|
|
|
| time_vals = []
|
| space_vals = {}
|
|
|
| for name, comp in algorithms.items():
|
| f_t = instantiate_complexity(comp["time"], n, d, k)
|
| f_s = instantiate_complexity(comp["space"], n, d, k)
|
| time_vals.append(f_t)
|
| space_vals[name] = (f_t, f_s)
|
|
|
| f_t_min = min(time_vals)
|
| f_s_min = min(v[1] for v in space_vals.values())
|
|
|
| scorer = ComplexityScorer(alpha=0.7)
|
|
|
| for name, (f_t, f_s) in space_vals.items():
|
| score = scorer.total_score(f_t, f_t_min, f_s, f_s_min)
|
| print(f"{name}: complexity score = {score:.4f}")
|
|
|
