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

19

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.

Code Whisperer
la source
Les algorithmes devraient-ils être plus rapides dans la plupart des cas d'utilisation après la modification? Pour le noter, il est parfois agréable de passer à une classe de complexité plus évolutive, même avec un résultat de performance moyen attendu, juste pour obtenir un comportement de performance plus cohérent.
Nat
22
Ce n'est pas refactoring
theonlygusti
6
À strictement parler, une fonction qui s'exécute dans le O(log(n))temps s'exécute également dans le O(n^2)temps. Le sens de O(n^2)«ne croît pas plus vite que quadratique». Vous vouliez probablement dire Theta (log (n)) qui signifie "grandit aussi vite que log(n)". en.wikipedia.org/wiki/…
Džuris
4
<pedantic> vous n'avez pas modifié le grand temps d'exécution d'une fonction. une fonction est une relation entre un domaine et un codomaine et existe indépendamment de vos tentatives humaines de mise en œuvre. à la place, vous avez trouvé un algorithme plus performant qui implémente la fonction </pedantic> <human> bon travail </human>
emory
5
@theonlygusti: Cela dépend. Si la fonction a précédemment fait une ou des garanties sur les complexités, ce n'est pas du refactoring. S'il ne garantit rien, c'est le refactoring. S'il était même explicite de ne pas faire de garanties, c'est surtout un refactoring.
phresnel

Réponses:

44

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.

Doc Brown
la source
10
vraiment? Je pense que la refactorisation est correcte à moins que les exigences ne changent. Donc .. Non si la fonction s'appelle BubbleSort, mais oui si c'est juste Trier
Ewan
3
@Ewan Oui, légalement, une refactorisation peut être une optimisation des performances, mais la première est beaucoup trop générale et ne saisit pas correctement l'impact des changements.
Déduplicateur
1
J'étais à une première présentation par le gars qui a inventé et inventé le refactoring (Fowler?) Et l'idée était liée à la programmation automatique et aux améliorations vérifiables prouvables du code qui n'avaient aucun effet sur l'entrée contre la sortie.
Sentinel
1
@Steve. D'accord. J'ajoutais simplement au consensus que les améliorations Big O représentent une amélioration algorithmique, et non des améliorations de la façon dont ces algorithmes sont représentés ou maintenus. En d'autres termes, l'activité est une réécriture
Sentinel
1
@Steve: oui, je le savais, j'ai pensé ajouter une note à ma réponse. Mon montage n'était qu'une note pour préciser qu'il y avait une petite zone grise.
Doc Brown
13

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.

ichantz
la source
7

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.

Derek Elkins a quitté SE
la source
5

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.

rwong
la source
2

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 2 )), 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 2 ) était une erreur, ou si vous l'avez d'abord délibérément implémenté en temps O (n 2 ), 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 2 ).

Jon Hanna
la source
1

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.

Joop Eggen
la source