Je suis d'accord avec toi sur le principe, mais même avec une grosse structure de données, si on suppose un accès régulier (du genre le traitement examine toujours les mêmes champs de la structure), alors O(N) ou O(N log N) ne devraient différer qu'en termes de complexité non?
Ensuite, c'est sûr qu'après quelques itérations de ton algo en O(N log N) tu risques de te retrouver avec un jeu de données suffisamment petit pour tenir en cache, et là il peut être plus avantageux de passer à un algorithme en théorie moins performant du point de vue complexité, mais qui en pratique tire parti de l'architecture cible. Un bon exemple est le tri fusion, où on fait du diviser et régner jusqu'à atteindre un certain niveau de récursion, pour ensuite utiliser un tri rapide ou par insertion car l'algo a un meilleur comportement avec les caches (ne serait-ce que parce qu'ils trient sur place).
Mais lorsqu'on parle de comportement hors caches (communications inter-nœuds de calcul par ex), je ne vois pas vraiment de raison pour ne pas utiliser l'algo avec la complexité la plus basse, vu que les données devront être copiées sur le réseau de toute manière (je ne sais pas si je suis clair).
[^] # Re: migre
Posté par lasher . En réponse au journal Java (EE) Sapu cépalibre.. Évalué à 5.
Je suis d'accord avec toi sur le principe, mais même avec une grosse structure de données, si on suppose un accès régulier (du genre le traitement examine toujours les mêmes champs de la structure), alors O(N) ou O(N log N) ne devraient différer qu'en termes de complexité non?
Ensuite, c'est sûr qu'après quelques itérations de ton algo en O(N log N) tu risques de te retrouver avec un jeu de données suffisamment petit pour tenir en cache, et là il peut être plus avantageux de passer à un algorithme en théorie moins performant du point de vue complexité, mais qui en pratique tire parti de l'architecture cible. Un bon exemple est le tri fusion, où on fait du diviser et régner jusqu'à atteindre un certain niveau de récursion, pour ensuite utiliser un tri rapide ou par insertion car l'algo a un meilleur comportement avec les caches (ne serait-ce que parce qu'ils trient sur place).
Mais lorsqu'on parle de comportement hors caches (communications inter-nœuds de calcul par ex), je ne vois pas vraiment de raison pour ne pas utiliser l'algo avec la complexité la plus basse, vu que les données devront être copiées sur le réseau de toute manière (je ne sais pas si je suis clair).