[Résolu] Temps d'exécution d'une boucle en Swift

Salut à tous,

J’ai passé un petit test en ligne, pour connaitre mes compétences en Swift, et je devais implémenter une fonction qui prend en paramètre un Array et un Int

Elle retourne true si le Int est dans le tableau, et false sinon

Voilà ce que j’ai fait :

Je sais qu’on pourrait aussi passer par une boucle while, ou même un « for _ in … » ou toute autre manière de faire, mais même résultat :

Ma question c’est comment faire pour que ça soit le plus rapide possible ?

En faisant des recherches, je suis tombé sur une réponse de stackoverflow, qui parle d’utiliser un Set au lieu d’un Array, c’était super intéressant car je ne connaissais pas Set en Swift

Petite explication ici si ça vous intéresse https://www.programiz.com/swift-programming/sets

Mais j’ai refait le test en ligne, et même résultat en utilisant Set au lieu d’un Array: trop lent pour un tableau d’1 million

J’ai aussi tenté la dichotomie (couper un tableau en deux, et ne garde que la partie où se trouve l’élément), trop lent aussi :

Essaye en créant une extension de Array. Le problème des fonctions, c’est que les données sont copiées au moment de l’exécution. Tu ne travailles pas sur le tableau lui-même, mais sur une copie.

Il est possible que l’extension travaille sur le tableau lui-même et non un double, ce qui évite la phase duplication des données et fait gagner du temps. A tester.

Testé, fonctionnel, mais toujours aussi lent :confused:

Je ne suis pas surpris que le Set pose problème. C’est un ensemble de données triées avec des clés de recherche, pour une vérification rapide. Mais UN MILLION DE DONNEES TRIEES c’est vraiment beaucoup.

Tu peux quand même montrer ton code avec le Set ?

T’as essayé avec .contains ?

https://developer.apple.com/documentation/swift/array/2945493-contains

C’est certainement le plus efficace, vu que tout est implémenté en bas niveau.


Au fait, il sort d’où ton test ? C’est une évaluation par une machine avec des réponses pré-enregistrées ou par un être humain ?

Contains c’est le premier que j’utilise, regarde la première image dans mon post initial

Le test c’est issu de Codingame, un site que les recruteurs utilisent pour mesurer ton niveau

Ta manière de montrer du code dans une copie d’écran n’est pas pratique. Tu devrais plutôt insérer le code dans le texte, comme nous le faisons tous, ici …

A mon avis le système de réponse automatique est bugé !

Il y a des informations supplémentaires sur le tableau de départ ? Est-il déjà trié par ordre croissant ?
Idéalement si tu pouvait copier coller l’énoncé ce serait super :slight_smile:

Je reçois un lien avec un token unique, et je dois résoudre les exercices dans un temps déterminé.

La fonction copier-coller est désactivé dans le navigateur, de ce fait je peux seulement faire une capture d’écran.

@mbritto oui c’est un tableau trié. J’ai essayé la dichotomie, qui consiste à diviser le tableau en deux, et créer un autre tableau avec le sous-tableau précédent qui contient la valeur recherchée. Et trop lent également …

Ah, mais ça change tout, si le tableau est déjà trié. C’est effectivement une recherche dichotomique qu’il faut faire, mais pas en créant de nouveaux tableaux. Il faut juste faire une recherche sur l’index, avec affinement progressif de la localisation. Quelque chose comme : -

Tu regardes le contenu de la dernière case du tableau. Si c’est inférieur à la valeur recherchée, pas de solution => return false

Si c’est supérieur, tu regardes la valeur de la case située au milieu du tableau, pour réduire la recherche à la partie supérieure et inférieure. Et tu continues le processus en réduisant à chaque fois la zone de recherche par deux, jusqu’à trouver la bonne valeur. C’est très rapide, même avec un tableau d’un million d’items, puisque tu élimines 50% du tableau à chaque itération de la boucle.

1 000 000
500 000
250 000
125 000
62 500
31 250
15 625
etc …

Evidement, c’est lent de créer un nouveau tableau en mémoire, surtout s’il contient 1 million d’objets ! Alors que la lecture d’une case à partir d’un index est quasi-instantanée.

Merci à toi @Draken pour les explications.

Effectivement, quand j’avais la tête dans le code, j’avais pas forcément la meilleure approche. Maintenant avec du recul, il est vrai que c’est inutile de créer un autre tableau, il aurait suffit de travailler avec les index.

Malheureusement, mon temps était compté, fallait que je fasse vite : 20 min c’est trop peu quand tu n’as pas l’habitude …

Vous savez où je pourrais trouver des cours d’algo pour ne plus refaire cette erreur ?

Je connais déjà le Swift Algorithm Club, mais ce qui me gêne c’est que je n’ai pas la possibilité de tester si l’algo est assez rapide sur de gros tableaux (comme celui d’1 million) … il faudrait un compilateur en ligne ou un programme qui te dit combien de temps a mis le code pour retourner une valeur …

D’ailleurs @mbritto voici une idée pour de futurs cours: pourquoi pas des exercices d’algo comme la recherche d’un élément dans un tableau (selon s’il est trié ou pas), tri des tableaux dans un temps défini, etc … :slightly_smiling_face:

EDIT: voici l’exercice avec l’ennoncé au complet :

Bon, j’ai trouvé la (ou une) solution.

Voici le code pour ceux que ça intéresse:

J’ai suivi les explications de Reinder, et comme l’avait dit @Draken, il suffit de travailler avec des index sans modifier le tableau.

Merci à tous !

Je pense à un truc, je ne sais pas du tout si ça aiderait, ou si c’est une bonne idée, mais en faisant appel au multithreading, en coupant ton tableau en plusieurs section chacune testée dans un thread concurrent pour parvenir au résultat un peu plus vite ? (combien de threads faudrait-il, idéalement, sur un tableau d’un million, pour que leur exécution soit plus rapide et contrebalance la perte de temps de la mise en œuvre ?)

Ah, si on sait qu’en effet le tableau est trié au dé part, ça aide. Bravo !