Le matériel / l'implémentation affecteront-ils la complexité spatio-temporelle des algorithmes?

32

Je ne suis même pas un étudiant CS, donc cela pourrait être une question stupide, mais veuillez me supporter ...

À l'ère pré-informatique, nous ne pouvons implémenter une structure de données de tableau qu'avec quelque chose comme un tableau de tiroirs. Puisqu'il faut localiser le tiroir avec l'index correspondant avant d'en extraire la valeur, la complexité temporelle de la recherche de tableau est , en supposant une recherche binaire.O(log(n))

Cependant, l'invention des ordinateurs a fait une grande différence. Les ordinateurs modernes peuvent lire à partir de leur RAM si rapidement que nous considérons maintenant la complexité temporelle de la recherche de tableau comme étant (même si ce n'est techniquement pas le cas, car cela prend plus de temps pour déplacer le registre sur une plus grande distance, etc.)O(1)

Un autre exemple est celui des dictionnaires Python. Bien que l'on puisse obtenir une complexité d'accès au dictionnaire de avec une méthode magique surchargée mal écrite (ou ridiculement malchance, c'est-à-dire des clés ayant beaucoup de collisions de hachage), il est généralement présumé être . Dans ce cas, la complexité temporelle dépend à la fois de l'implémentation de table de hachage des dictionnaires Python et de l'implémentation des clés des fonctions de hachage.O ( 1 )O(n)__hash__O(1)

Est-ce à dire que le matériel / l'implémentation peuvent affecter la complexité temporelle des algorithmes? (Bien que les deux exemples concernent des structures de données au lieu d'algorithmes, ces derniers sont construits sur les premiers, et je n'ai jamais entendu parler de la complexité temporelle des structures de données, donc j'utilise ici le terme "algorithmes")

Pour moi, les algorithmes sont abstraits et conceptuels, dont les propriétés comme la complexité temps / espace ne devraient pas être affectées par leur mise en œuvre d'une manière spécifique, mais le sont-elles?

nalzok
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Gilles 'SO- arrête d'être méchant'

Réponses:

42

Sûr. Certainement. Voici comment concilier votre inconfort.

Lorsque nous analysons le temps d'exécution des algorithmes, nous le faisons par rapport à un modèle particulier de calcul . Le modèle de calcul spécifie des choses comme le temps qu'il faut pour effectuer chaque opération de base (est-ce un temps de recherche de tableau ou O ( 1 ) ?). Le temps d'exécution de l'algorithme peut dépendre du modèle de calcul.O(logn)O(1)

Une fois que vous avez choisi un modèle de calcul, l'analyse de l'algorithme est un exercice mathématique purement abstrait, conceptuel qui ne dépend plus du matériel.

Cependant, dans la pratique, nous voulons généralement choisir un modèle de calcul qui reflète la réalité de notre matériel - au moins dans une mesure raisonnable. Donc, si le matériel change, nous pourrions décider d'analyser nos algorithmes sous un modèle de calcul différent qui est plus approprié au nouveau matériel. C'est ainsi que le matériel peut affecter la durée de fonctionnement.

La raison pour laquelle cela n'est pas évident est que, dans les classes d'introduction, nous ne parlons souvent pas du modèle de calcul. Nous faisons simplement implicitement certaines hypothèses, sans jamais les rendre explicites. C'est raisonnable, à des fins pédagogiques, mais cela a un coût - cela cache cet aspect de l'analyse. Maintenant tu sais.

DW
la source
Comme vous l'avez dit, nous utilisons le modèle d'accès aléatoire comme modèle de calcul, mais lorsque nous utilisons le GPU pour certains calculs, la complexité temporelle de certains algorithmes change car il utilise les instructions SIMD.
Deep Joshi
6
Notez également que la notation O () est une limite supérieure. Même si vous utilisez l'analogie de tiroir pour trouver un tiroir de taille limitée (la mémoire réelle est de taille limitée), la construction prend O (1). Même si cela vous prend 20 minutes pour atteindre le tiroir le plus éloigné (tout le cache manque et vous devez même charger les données de swap), c'est toujours O (1) car 20 minutes seront votre constante cachée pour accéder à la mémoire.
Goswin von Brederlow
2
O(1)O(n)
1
@CortAmmon: Même sur un grand tableau, l'utilisation de la recherche linéaire peut être plus rapide que l'utilisation d'une carte de hachage si tous, sauf quelques-uns des éléments recherchés, sont très proches du début. Par exemple, si 50% des éléments correspondent au premier élément, 25% correspondent au deuxième, 12,5% correspondent au troisième, etc., sauf qu'un élément excentrique correspondra à quelque chose qui pourrait être n'importe où dans le tableau, le nombre attendu de comparaisons avec effectuer des recherches M sur une liste de taille N serait 2M + N.
supercat
5
Les instructions @DeepJoshi SIMD ne changent pas la complexité des algorithmes. Ils ne changent que la constante multiplicative.
Gilles 'SO- arrête d'être méchant'
5

Je pense qu'il y a un malentendu fondamental dans la question. Vous comparez une personne trouvant un objet dans une liste triée (par exemple, une page spécifique dans un livre, compte tenu de son numéro) avec un ordinateur recherchant un élément d'un tableau.

O(logn)O(1)

Donc, oui, le matériel (c'est-à-dire le modèle de calcul) affecte le temps d'exécution des algorithmes, comme l' explique DW , mais ce n'est pas ce sur quoi votre exemple d'accès au tableau semble se baser.

David Richerby
la source
2
Pour être honnête, vous avez sauté toutes les pièces entre "le contrôleur de mémoire définit les tensions sur les fils d'adresse à la représentation binaire de dix-sept" et "les données reviennent". L' une de ces pièces presque certainement est un arbre de recherche binaire du type décrit par l'OP; mais il s'exécute néanmoins en temps constant car log n est d'environ 64, pour tout n .
Quuxplusone
@Quuxplusone Quelle partie de la mémoire utilise la recherche binaire? Les lignes d'adresse sélectionnent directement les cellules mémoire.
David Richerby
Nous fonctionnons bien loin de mon domaine d'expertise, mais ce que j'essayais d'impliquer, c'est qu'un décodeur d'adresse sera implémenté en termes d' arbre de démultiplexeurs . (En supposant que nous frappons directement la mémoire physique, en ignorant toute complication supplémentaire qui vient avec la mise en cache .) Encore une fois, toutes ces complications supplémentaires ne font qu'ajouter O(lg size-of-memory), c'est-à-dire négligeables - mais c'est exactement le bit qu'OP demandait!
Quuxplusone
2

Non, le matériel n'affecte pas la complexité des algorithmes.

Mais , cela affecte le choix de l'algorithme, et il peut affecter l'utilité de l'analyse de complexité à un point où l'analyse devient à peu près vide de sens (ou simplement d'intérêt académique).

Trouver le bon tiroir (comme accéder à un élément de tableau) utilise l'algorithme "ouvrir le Nème élément directement par index", pas l'algorithme "rechercher linéairement" ou "faire une recherche binaire". Les algorithmes ne sont pas modifiés, mais le choix.

D'un autre côté, l'analyse de la complexité elle-même, ou plutôt sa signification, est grandement affectée par le matériel.

De nombreux algorithmes qui sont stellaires par leur analyse de complexité sont peu performants voire inutiles en pratique car le facteur constant insignifiant n'est pas du tout insignifiant, mais dominant .

Ou, parce que des hypothèses qui étaient autrefois vraies (ou pour la plupart vraies) ne sont plus valables. Tels que, par exemple, chaque opération est essentiellement la même (seulement de petites différences constantes qui n'ont pas d'importance), ou cela ne fait aucune différence sur les emplacements de mémoire auxquels vous accédez dans quel ordre. Par l'analyse de la complexité, vous pouvez conclure que certains algorithmes sont largement supérieurs car ils n'ont besoin que de tant d'opérations. Dans la pratique, vous pouvez constater que chaque opération provoque un échec de cache garanti (ou pire encore, un défaut de page), ce qui introduit un k si énorme qu'il n'est plus insignifiant, mais qu'il domine tout.
Si l'algorithme A prend 500 opérations pour traiter un ensemble de données d'une taille donnée et que l'algorithme B n'en prend que 5, mais que B provoque 5 défauts qui brûlent vingt millions de cycles chacun, alors malgré ce que l'analyse ou le bon sens peuvent vous dire, A est mieux.

Cela a conduit à de drôles de surprises comme par exemple dans Cuckoo Hashing il y a quelques années. Ce qui était largement supérieur parce que [longue liste d'avantages]. Une fois le battage médiatique refroidi, il s'est avéré qu'il était largement inférieur car il garantissait deux échecs de cache (défauts, pour des ensembles de données plus volumineux) à chaque accès.

Il en est de même pour l'identification et le traitement de sous-ensembles de données. Souvent, la solution correcte de nos jours est: "faites tout" , c'est-à-dire qu'au lieu de déterminer ce dont vous avez besoin pour procéder et faire cela, traitez le jeu de données complet de manière linéaire même si vous n'en avez peut-être besoin que de la moitié. Parce que, croyez-le ou non, c'est plus rapide en raison d'aucune erreur de prédiction de branche, d'aucun échec de cache, d'aucun défaut de page.
Besoin de lire les 8 premiers Ko et les 3 derniers Ko d'un fichier de 3 Mo? Eh bien, lisez le fichier complet et jetez ce que vous ne voulez pas, car la recherche entre les deux sera dix fois plus lente que la simple lecture du tout.

Utiliser une carte car elle a une complexité logarithmique? Ou une table de hachage, qui a un temps d'accès constant? Constant semble génial. Eh bien, pour tout ce qui contient moins d'un millier de choses (selon le matériel, la taille des données et le modèle d'accès), une recherche linéaire peut être tout aussi bonne ou meilleure. Surprise.

Ce ne sont donc pas les algorithmes en soi qui sont affectés, mais leur utilité et leur choix.

Damon
la source