mining.fuzzy: the fuzzy miner uses cubic Python loops with list lookups #40

Open
opened 2026-10-06 13:51:19 +00:00 by ffrauenberger · 0 comments
Owner

Severity: improvement (medium)

Where

  • app/mining_algorithms/fuzzy_mining.py:202-257, :290-325, :431-441, :481-594, :683-690, :813-826

Problem

  • Nested for i … for j … loops over all activity pairs call self.filtered_events.index(x) (O(n)) and test membership in lists (self.list_of_clustered_nodes, ret_sign_nodes, ret_nodes). That is O(n³) or worse.
  • Each util-matrix value is computed twice (val and util_matrix[i][j]), and two logger.debug string concatenations are built even when debug logging is off.
  • get_edge_statistics() is recomputed in each of the four calls to __add_edges_to_graph_for_each_method.
  • __calculate_significant_nodes scans an n×n matrix to find rows that are not all -1.

Fix

  • Precompute index = {event: i} and use sets for membership
  • Vectorize util and normalization with numpy (np.where, broadcasting)
  • Compute the edge statistics once
  • Use lazy logging (logger.debug("…%s", x))

from issues/PERF-004-fuzzy-miner-cubic-python-loops.md (code analysis of commit 6bcc646, 2026-10-03)

**Severity:** improvement (medium) ## Where - `app/mining_algorithms/fuzzy_mining.py:202-257`, `:290-325`, `:431-441`, `:481-594`, `:683-690`, `:813-826` ## Problem - Nested `for i … for j …` loops over all activity pairs call `self.filtered_events.index(x)` (O(n)) and test membership in **lists** (`self.list_of_clustered_nodes`, `ret_sign_nodes`, `ret_nodes`). That is O(n³) or worse. - Each util-matrix value is computed twice (`val` and `util_matrix[i][j]`), and two `logger.debug` string concatenations are built even when debug logging is off. - `get_edge_statistics()` is recomputed in each of the four calls to `__add_edges_to_graph_for_each_method`. - `__calculate_significant_nodes` scans an n×n matrix to find rows that are not all `-1`. ## Fix - Precompute `index = {event: i}` and use sets for membership - Vectorize util and normalization with numpy (`np.where`, broadcasting) - Compute the edge statistics once - Use lazy logging (`logger.debug("…%s", x)`) --- from `issues/PERF-004-fuzzy-miner-cubic-python-loops.md` (code analysis of commit 6bcc646, 2026-10-03)
Sign in to join this conversation.
No milestone
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
ffrauenberger/ProcessIntel#40
No description provided.