Comment l'appelez-vous lorsque vous modifiez le temps d'exécution Big O d'une fonction [fermé]

Disons que j'ai une fonction qui trie une base de données dans le O(n^2)temps. Je veux le refactoriser pour qu'il s'exécute dans le O(n log(n))temps, et ce faisant, je vais changer la façon fondamentale dont fonctionne l'opération, tout en gardant les valeurs de retour et les entrées équivalentes.

Comment appeler cette activité de refactoring?

"Accélérer-ifying" ne semble pas tout à fait correct, car vous pouvez accélérer un algorithme sans changer la grande vitesse O à laquelle il s'exécute.

"Simplifier" ne semble pas non plus juste.

Comment dois-je appeler cette activité?

Mise à jour

La meilleure réponse que j'ai pu trouver est de réduire la complexité du temps asympotique.

Il est généralement appelé "optimisation des performances" , mais je ne l'appellerais pas "refactoring", car ce terme fait généralement référence à des changements de code qui ne changent pas son comportement visible . Et un changement dans Big-O est certainement quelque chose que j'appellerais un changement visible.

ce faisant, je vais changer la façon fondamentale de fonctionner

Dans ce cas, votre optimisation est une réécriture de cette fonction. Toutes les optimisations, même si elles changent "Big-O", ne sont pas nécessairement une réécriture, parfois seulement de petits changements sont nécessaires pour obtenir une telle amélioration, mais même dans ce cas, j'hésite à utiliser le terme "refactoring" pour cela, car il tend à donner une mauvaise impression de la nature du changement.

EDIT: J'ai vérifié la liste de refactorisation de Fowler , et parmi ces ~ 100 refactorisations nommées, la toute dernière s'appelle "Algorithme de substitution" . Donc, si nous prenons cela comme référence canonique, il y a une petite zone grise où une optimisation de la forme décrite pourrait être appelée un type spécial de refactorisation (mais à mon humble avis pas typique). Notez également que l'objectif de Fowler avec toutes les refactorisations était toujours d'améliorer la conception en mettant l'accent sur la maintenabilité et l'évolutivité du code existant sans le réécrire, et clairement pas sur l'optimisation des performances.

Je ne pense pas qu'il existe un terme standard, un terme couramment utilisé est l' optimisation bien que l' amélioration , ou l' accélération serait également correcte en précisant que vous parlez de modifications de code et non de modifications matérielles.

Comme d'autres l'ont dit, "l'optimisation" est le terme général pour améliorer les performances d'un algorithme. Cependant, l'optimisation signifie souvent l'amélioration de facteurs constants. Si je voulais déclarer de façon concise mais claire que j'ai réduit la complexité asymptotique (temporelle), je dirais que j'ai "amélioré les performances asymptotiques". Parfois, les gens décriront cela comme "améliorant la mise à l'échelle", mais c'est particulièrement ambigu de nos jours.

Avertissement : Réduire la complexité temporelle asymptotique n'est pas nécessairement la même chose qu'optimiser dans un contexte pratique . Souvent, des algorithmes asymptotiquement non optimaux sont utilisés parce que sur la plage d'entrées, le programme est en fait exposé aux algorithmes moins optimaux qui fonctionnent mieux.

Cela dépendra du contexte.

"Correction d'un bogue de performance d'exécution quadratique" est généralement ce que je vois. Cependant, la question de savoir si cela mérite d'être corrigé (un changement de code) dépend du contexte.

Gardez à l'esprit que les bases de données fournissent de nombreux outils pour améliorer la complexité du temps. Par exemple, pour obtenir les meilleurs résultats N d'une base de données, dites-le simplement. Lors de la conversion de kludge inefficace en appel optimisé intégré, l'explication semble superflue.

La raison pour laquelle je considère qu'un algorithme avec une exécution quadratique mérite une révision de code (discussion) n'est pas tant parce qu'il est lent (lent est relatif; quadratique est rapide par rapport à exponentiel), mais parce que l'intuition humaine (comme vos clients, ou collègues programmeurs) sont intrinsèquement mal à l'aise avec une fonctionnalité logicielle qui s'écarte trop loin de l'exécution linéaire, en raison du mélange des attentes de la vie quotidienne.

De nombreuses plaintes des clients concernant les performances des logiciels entrent dans ces deux catégories:

• L'ensemble du système (logiciel et matériel) a été spécifié en fonction de l'utilisation estimée. La semaine dernière, tout se passe bien, une certaine fonctionnalité a pris moins de 5 secondes. Cette semaine, après l'installation d'une mise à jour, la même fonctionnalité prend plus d'une minute.

  • Il s'agit d'une comparaison avec une performance précédemment référencée. Le client maintient les performances futures à l'aune absolue d'une échelle de temps humaine (de la seconde à la minute).

• J'ai soumis 100 emplois au système. Pourquoi cela prend-il 400 fois plus de temps à traiter que le temps nécessaire pour un seul travail?

  • Le client s'attend à ce que le temps de traitement soit linéaire. En fait, le client ne peut pas comprendre ou accepter qu'il existe des tâches plus lentes que linéaires.

Pour cette raison, un client considérera le temps d'exécution comme un bug si les deux sont vrais:

• Plus lent que linéaire
• Remarquable (c.-à-d. Se situe dans la plage de temps humain (plus de secondes ou de minutes) compte tenu des tailles de tâches typiques)

Arguments légitimes qui expliquent qu'un algorithme d'exécution quadratique ne pose pas de problème (c'est-à-dire qu'il ne mérite pas de changement de code):

• La taille de la tâche généralement gérée par cette fonction d'exécution quadratique est quelque peu limitée
• Compte tenu de la plage de taille typique, le temps d'exécution réel (absolu) est encore suffisamment petit pour être ignoré
• Si un utilisateur essaie réellement de soumettre une tâche suffisamment volumineuse pour être visible, l'utilisateur recevra un message d'avertissement sur le long temps d'exécution
• Les utilisateurs du système sont tous des experts, ils savent donc ce qu'ils font. Par exemple, les utilisateurs d'une API doivent avoir lu les petits caractères de la documentation de l'API.

Beaucoup d'algorithmes utiles pour le développement d'applications typiques sont en fait plus lents que linéaires (principalement O (N log N), comme dans le tri), donc les logiciels à grande échelle essaieront en fait de contourner cela, en ne triant que la partie pertinente du des données, ou utiliser des techniques de filtrage histologique (statistique) qui produisent un effet similaire.

Cela s'applique aux clients logiciels, mais si vous considérez que les utilisateurs d'une bibliothèque de logiciels ou d'une fonction API sont également des "clients", la réponse s'applique toujours.

Si l'algorithme d'origine a été correctement implémenté (ou tout bogue non pertinent), alors "changer l'algorithme" ou "substitution d'algorithme" , car de tels changements signifient que vous faites exactement cela; substituer un algorithme de complexité temporelle différente de celui précédemment utilisé.

Si la complexité temporelle précédente était due à un bogue dans l'implémentation (par exemple, supposons que vous réinitialisiez accidentellement le point de départ d'une boucle interne sur une séquence de sorte que ce qui aurait dû être O (n) devienne O (n ² )), puis "correction un bug de coût quadratique " ou similaire.

Il y a un chevauchement, dans ce cas, l'effet sur le code est le même si vous savez d'emblée que le travail pourrait être effectué en temps O (n) et que le temps O (n ² ) était une erreur, ou si vous l'avez d'abord délibérément implémenté en temps O (n ² ), puis vous avez réalisé qu'il fonctionnerait toujours correctement sans réinitialiser le point de départ, et vous avez donc substitué un algorithme O (n) à un algorithme O (n ² ).

Optimisation de la vitesse par ordre / ordres de grandeur. Bien que ce soit un langage mathématiquement incorrect, il transmet le mieux l'idée que l'Ordre est changé.

Amélioration de l'évolutivité. entendu aussi.