Quand 'optimisation du code' == 'structuration des données'?

Un article récent de ycombinator énumère un commentaire avec les principes d'un grand programmeur.

#7. Bon programmeur: j'optimise le code. Meilleur programmeur: je structure les données. Meilleur programmeur: Quelle est la différence?

Reconnaître les concepts subjectifs et litigieux - quelqu'un a-t-il une position sur ce que cela signifie? Je le fais, mais je voudrais modifier cette question plus tard avec mes pensées afin de ne pas prédisposer les réponses.

Neuf fois sur dix, lorsque vous structurez bien votre code / modèles, l'optimisation deviendra évidente. Combien de fois avez-vous vu un nid de frelons et l'avez trouvé totalement sous-optimal, où lors de sa restructuration, de nombreuses redondances sont devenues extrêmement évidentes.

Un designer sait qu'il a atteint la perfection non pas quand il n'y a plus rien à ajouter, mais quand il n'y a plus rien à retirer. - Antoine de Saint-Exupéry

Un système bien structuré sera de nature minimale et, en raison de sa nature minimale, il sera optimisé car le peu qu'il contient est directement lié au peu qu'il fait pour atteindre son objectif.

Edit: Pour expliquer le point que d'autres ont retiré de cela, il est également tout à fait exact de voir la déclaration comme identifiant la relation entre le code et les données. Cette relation est donc la suivante: si vous changez la structure de vos données, vous devrez changer votre code pour respecter la structure modifiée. Si vous souhaitez optimiser votre code, vous devrez probablement modifier la structure de vos données pour rendre votre code capable de gérer les données de manière plus optimale.

Cela dit, il y a une possibilité totalement distincte qui était éludée ici, et ce serait que cet homme ayant des relations avec YCombinator fasse référence aux données de code AS dans la tradition d'homiconicité LISP. C'est un bout droit de supposer que c'est le sens dans mon esprit, mais c'est YCombinator donc je n'écarterais pas que la citation dit simplement que LISPers sont les "meilleurs programmeurs".

Je pense que l'auteur laisse entendre que toute restructuration des données conduit à une restructuration du code. Par conséquent, la restructuration des données dans le but d'optimiser votre système vous obligera également à optimiser votre code, ce qui vous demandera "quelle est la différence?" réponse.

Notez qu'un "excellent programmeur" peut répondre à "quelle est la différence?" qu'il y a une différence: une fois que vous vous aventurez à optimiser pour une meilleure utilisation du cache du processeur, vous pouvez conserver la disposition de vos structures de données, mais changer l'ordre dans lequel vous y accédez peut faire beaucoup différence.

Prenons l'exemple le plus évident de cela - "la recherche de données utilisateur est trop lente!"

Si vos données utilisateur ne sont pas indexées ou au moins triées, la restructuration de vos données entraînera rapidement une augmentation des performances du code. Si les données sont correctement structurées et que vous parcourez simplement la collection (plutôt que d'utiliser les index ou de faire quelque chose comme une recherche binaire), la modification du code permet d'augmenter les performances du code.

Les programmeurs résolvent les problèmes. Bien qu'il soit utile de faire la distinction entre les algorithmes et les structures de données, ils ne peuvent pas souvent exister isolément. Les meilleurs programmeurs le savent et ne s'isolent pas inutilement.

Je ne suis pas d'accord avec la déclaration mentionnée ci-dessus, enfin du moins sans explication. Je vois que le codage est l'activité impliquant l'utilisation de certaines structures de données. Les structures de données influenceraient généralement le codage. Il y a donc à mon avis une différence entre les deux.

Je pense que l'auteur aurait dû écrire la dernière partie comme "Meilleur programmeur: j'optimise les deux."

Il existe un excellent livre (du moins il l'était lors de sa publication) intitulé: Algorithms + Data Structures = Programs .

L'optimisation du code peut parfois améliorer la vitesse d'un facteur deux, et parfois d'un facteur dix ou même vingt, mais c'est à peu près tout. Cela peut sembler beaucoup, et si 75% du temps d'exécution d'un programme est dépensé dans une routine de cinq lignes dont la vitesse pourrait facilement être doublée, une telle optimisation pourrait bien être utile. D'un autre côté, la sélection des structures de données peut affecter la vitesse d'exécution de plusieurs ordres de grandeur. Un processeur multithread hyper-optimisé moderne exécutant du code super-optimisé pour rechercher des données par clé dans une liste de liens linéaires de 10000000 éléments stockés dans la RAM serait plus lent qu'un processeur beaucoup plus lent exécutant une table de hachage imbriquée assez simplement codée. En effet, si l'on disposait correctement des données, même un 1980 '

Cela dit, la conception de structures de données efficaces nécessite souvent des compromis plus complexes que l'optimisation du code. Par exemple, dans de nombreux cas, les structures de données qui permettent d'accéder aux données le plus efficacement sont moins efficaces à mettre à jour (parfois par ordre de grandeur) que celles qui permettent des mises à jour rapides, et celles qui permettent les mises à jour les plus rapides peuvent permettre l'accès le plus lent. En outre, dans de nombreux cas, les structures de données qui sont optimales pour les grands ensembles de données peuvent être comparativement inefficaces avec les petites. Un bon programmeur doit s'efforcer d'équilibrer ces facteurs concurrents avec la quantité de temps nécessaire au programmeur pour implémenter et maintenir diverses structures de données, et être capable de trouver un équilibre décent entre eux.

Les structures de données entraînent beaucoup de choses par rapport aux performances. Je pense que nous pouvons regarder les problèmes dur et longtemps avec une idée préconçue sur la structure de données idéale, et dans ce contexte de réflexion, même créer des preuves (souvent par induction) d'optimalité. Par exemple, si nous mettons une liste triée dans un tableau et évaluons des choses comme le coût d'insertion d'un élément, nous pourrions décider en moyenne que nous devons déplacer la moitié du tableau pour chaque insertion. Pour chaque recherche binaire , nous pouvons trouver un élément correspondant (ou non) dans les étapes du journal n.

Alternativement, si nous reportons notre décision sur la structure des données (évitons l' optimisation prématurée ) et étudions les données entrant et le contexte dans lequel nous les utiliserons, leur taille, les latences qui se produisent et celles qui importent aux utilisateurs, la quantité de mémoire dont nous disposons vs utiliserait avec des représentations de données que nous connaissons ou pouvons concevoir.

Dans un domaine comme le tri et la recherche, il y a beaucoup à savoir. De très bons programmeurs y travaillent depuis longtemps. Bien comprendre ces problèmes est utile, et c'est une bonne chose si vous connaissez plus de méthodes que lorsque vous avez terminé la classe de structures de données de premier cycle. Les arbres binaires peuvent fournir des performances supérieures pour les insertions en échange d'une utilisation plus importante de la mémoire. Les tables de hachage offrent des améliorations encore plus importantes, mais pour encore plus de mémoire. Un arbre et un tri radix peuvent apporter des améliorations encore plus.

Une structuration créative des données peut aider à recadrer un problème et à ouvrir la porte à de nouveaux algorithmes qui rendent les applications difficiles plus rapides et parfois des tâches parfois impossibles.

Pour articuler ma meilleure estimation de la signification de l'article, je suppose qu'un sous-texte non dit (qui semble manquer dans l'article) que tout programmeur devrait comprendre à propos de l'optimisation:

• l'optimisation ne survient qu'après que le programme est correctement installé et fonctionne:
  • faites-le fonctionner correctement, puis faites-le fonctionner rapidement
  • ce principe est le point de la maxime de Knuth, "l'optimisation prématurée est la racine de tout mal"
• si et quand vous avez déterminé que l'optimisation n'est pas prématurée, vous devez d'abord la mesurer correctement pour déterminer ce qui doit réellement être optimisé, et encore et encore pendant l' optimisation, pour savoir quels sont les effets de vos tentatives d'optimisation.
  • si votre code est en cours de développement, le profileur est votre ami.
  • si votre code s'exécute en production, vous devez instrumenter votre code et vous lier d'amitié avec votre système de journalisation.

Maintenant, alors: vos mesures vous diront où dans votre code la machine brûle le plus de cycles. Un "bon" programmeur se concentrera sur l'optimisation de ces parties du code, plutôt que de perdre du temps à optimiser les parties non pertinentes.

Cependant, vous pouvez souvent réaliser des gains plus importants en examinant le système dans son ensemble et en trouvant un moyen de permettre à la machine de faire moins de travail. Souvent, ces changements nécessitent de retravailler l'organisation de vos données; ainsi, un «meilleur» programmeur se retrouvera le plus souvent à structurer des données.

Le "meilleur programmeur" aura un modèle mental approfondi du fonctionnement de la machine, une bonne base dans la conception d'algorithmes et une compréhension pratique de la façon dont ils interagissent. Cela lui permet de considérer le système comme un tout intégré - il ne verra aucune différence entre l'optimisation du code et des données, car il les évalue au niveau architectural.

Meilleur programmeur: Quelle est la différence?

Meilleur programmeur? Non. Programmeur pourri. Je suppose que le mot "optimisation" signifie les choses que les programmeurs essaient généralement d'optimiser, la mémoire ou le temps CPU. En ce sens, l'optimisation va à l'encontre de presque toutes les autres métriques logicielles. Compréhensibilité, maintenabilité, testabilité, etc.: tout cela prend peu de temps lorsque l'optimisation est l'objectif - à moins que ce que l'on essaie d'optimiser soit la compréhensibilité humaine, la maintenabilité, la testabilité, etc. Sans parler du coût. L'écriture d'un algorithme optimal vitesse / espace coûte beaucoup plus cher en temps de développement que le codage naïf de l'algorithme tel que présenté dans certains textes ou journaux. Un mauvais programmeur ne fait pas la différence. Un bon fait. Le meilleur programmeur sait comment déterminer exactement ce qui doit être optimisé et le fait judicieusement.