Towards a Measure of Algorithm Similarity
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911242774380544 |
|---|---|
| author | Sohail, Shairoz Ali, Taher |
| author_facet | Sohail, Shairoz Ali, Taher |
| contents | Given two algorithms for the same problem, can we determine whether they are meaningfully different? In full generality, the question is uncomputable, and empirically it is muddied by competing notions of similarity. Yet, in many applications (such as clone detection or program synthesis) a pragmatic and consistent similarity metric is necessary. We review existing equivalence and similarity notions and introduce EMOC: An Evaluation-Memory-Operations-Complexity framework that embeds algorithm implementations into a feature space suitable for downstream tasks. We compile PACD, a curated dataset of verified Python implementations across three problems, and show that EMOC features support clustering and classification of algorithm types, detection of near-duplicates, and quantification of diversity in LLM-generated programs. Code, data, and utilities for computing EMOC embeddings are released to facilitate reproducibility and future work on algorithm similarity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_27063 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards a Measure of Algorithm Similarity Sohail, Shairoz Ali, Taher Machine Learning Artificial Intelligence Computation and Language Information Theory Software Engineering 68Qxx, 03Dxx, 90C29 I.2.6; F.4.1; D.2.4 Given two algorithms for the same problem, can we determine whether they are meaningfully different? In full generality, the question is uncomputable, and empirically it is muddied by competing notions of similarity. Yet, in many applications (such as clone detection or program synthesis) a pragmatic and consistent similarity metric is necessary. We review existing equivalence and similarity notions and introduce EMOC: An Evaluation-Memory-Operations-Complexity framework that embeds algorithm implementations into a feature space suitable for downstream tasks. We compile PACD, a curated dataset of verified Python implementations across three problems, and show that EMOC features support clustering and classification of algorithm types, detection of near-duplicates, and quantification of diversity in LLM-generated programs. Code, data, and utilities for computing EMOC embeddings are released to facilitate reproducibility and future work on algorithm similarity. |
| title | Towards a Measure of Algorithm Similarity |
| topic | Machine Learning Artificial Intelligence Computation and Language Information Theory Software Engineering 68Qxx, 03Dxx, 90C29 I.2.6; F.4.1; D.2.4 |
| url | https://arxiv.org/abs/2510.27063 |