J'aime savoir si j'utilise Set au lieu de Array puis ma méthode de first(where:) est devenue Complexity: O (1)?
Apple dit que la first(where:) méthode first(where:) est O (n), est-ce en général le cas ou cela dépend de la façon dont nous l'utilisons?
par exemple, regardez ces deux façons de coder:
var numbers: Set<Int> = Set<Int>()
numbers = [3, 7, 4, -2, 9, -6, 10, 1]
if let searchResult = numbers.first(where: { value in value == -2 })
{
print("The number \(searchResult) Exist!")
}
else
{
print("The number does not Exist!")
}
et ça:
var numbers: [Int] = [Int]()
numbers = [3, 7, 4, -2, 9, -6, 10, 1]
if let searchResult = numbers.first(where: { value in value == -2 })
{
print("The number \(searchResult) Exist!")
}
else
{
print("The number does not Exist!")
}
peut-on dire que dans un second temps, la complexité est O (1)?
4 Réponses :
C'est toujours O (n) même lorsque vous utilisez un Set . .first(where:) est défini sur une séquence , et il est nécessaire de vérifier les éléments de la séquence un par un pour trouver le premier qui rend le prédicat true .
Votre exemple vérifie simplement si l'élément existe dans l' Set , mais puisque vous utilisez .first(where:) et un prédicat { value in value == -2} Swift exécutera ce prédicat pour chaque élément de la séquence jusqu'à ce que il en trouve un qui renvoie true . Swift ne sait pas que vous êtes vraiment en train de vérifier si l'élément est dans l'ensemble.
Si vous voulez O(1) , utilisez .contains(-2) sur l' Set .
Alors puis-je dire avec array et first (où :) j'obtiendrais O (n), mais avec Set ou Dictionary j'obtiendrais O (1) Complexity? Est ce juste?
Si vous voulez O (1) pour Set , utilisez .contains(element) au lieu de .first(where: { $0 == element }) .
J'ai recherché contient (élément) c'est la même histoire! Apple dit: Complexité: O (n), où n est la longueur de la séquence. je suis confus
Non, si vous command-cliquez sur .contains lorsqu'il est exécuté sur un Set , la documentation indique que c'est O(1) .
c'est vrai! J'ai testé! il dit: /// - Complexité: O (1) mais vérifiez le premier plz! il dit: /// - Complexité: O ( n ), où n est la longueur de la séquence. Comment pouvons-nous trouver LE N ?
À droite, d' first(where:) est O(n) pour Set . Que voulez-vous dire "Comment pouvons-nous trouver LE N"? Que veux-tu dire par là?
Cela dit, nous pouvons dire que first (où :) est une méthode O (n), que nous utilisions array ou set! Mais .contains est O (1) pour set et O (n) pour array. Parce que je l'ai vérifié pour l'ensemble dit O (1) mais pour tableau dit O (n)
C'est correct. .contains est O (1) pour les ensembles et O (n) pour les tableaux, mais d' first(where:) est O (n) pour les deux.
Et je pense que .contains est bien meilleur que first (où :) parce que j'essaie de savoir si cette valeur existe! c'était vraiment bon
L' Set et le Dictionary sont tous deux conformes au protocole Sequence , qui est celui qui expose la first(where:) . Et cette fonction a l'exigence suivante, tirée de la documentation :
Complexité: O (n), où n est la longueur de la séquence.
Maintenant, c'est la limite supérieure de la complexité de la fonction, il se pourrait bien que certaines séquences optimisent la recherche en fonction de leur type de données et des détails de stockage.
Bottom line: vous devez accéder à la documentation pour un type particulier si vous voulez en savoir plus sur les performances de certaines fonctionnalités, mais si vous ne faites circuler que quelques références de protocole, alors vous devriez supposer le "pire" - c'est-à-dire ce qu'il y a dans le documentation du protocole.
parce que Set est hashable, donc l'application n'a pas besoin de commencer à demander à chaque index de Set de nous donner un résultat, car si nous parlons de tableau, cela placerait un tableau dans une boucle pour trouver le cas mach avec lequel il n'est pas le même Set ou Dictionary, c'est pourquoi je voulais être sûr que lorsque j'utilise Set avec ces méthodes, que se passe-t-il?
@Omid sauf si vous avez accès au code source, vous ne pouvez pas être sûr de ce qui se passe sous le capot. Et même si vous y avez accès, les détails de mise en œuvre peuvent changer à tout moment sans aucun avertissement. C'est pourquoi il est préférable de s'appuyer sur un comportement documenté, qui change moins souvent.
Je recommande d'en savoir plus sur la notation Big-O. O (1) est un sous-ensemble strict de O (n). Ainsi, toute fonction qui est O (1) est également dans O (n).
Cela dit, la documentation d'Apple est en fait trompeuse car elle ne prend pas en compte la complexité de la fonction de prédicat. Ce qui suit est clairement O (n ^ 2):
numbers.first(where: { value in numbers.contains(value + 42) })
merci, comment trouvez-vous O (2) ici? pouvez-vous expliquer plz?
appelle d' first la fonction passée n fois dans le pire des cas, qui à son tour appelle `contains` et effectue des comparaisons O (n), conduisant à des comparaisons O (n ^ 2) dans l'ensemble.
Voici l'implémentation de la première fonction (où :) dans la séquence:
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func first(
where predicate: (Element) throws -> Bool
) rethrows -> Element? {
for element in self {
if try predicate(element) {
return element
}
}
return nil
}
À partir du code source Swift sur le Github
Comme vous pouvez le voir, c'est une simple boucle for et la complexité est O ( n ) (en supposant que la complexité du predicate est 1 🤠· 🠻⠀ â ™‚ ï¸).
Le predicate s'exécute n fois. Donc le pire des cas est O ( n )
L' Set n'a pas de surcharge pour cette fonction (car c'est un non-sens et il n'y aura rien de plus que le premier dans un Set ). Si vous connaissez la séquence et que vous recherchez simplement une valeur (pas un prédicat), utilisez simplement contains ou firstIndex(of:) . Ces deux ont des surcharges avec la complexité de O ( 1 )
À partir du code source Swift sur le Github
Hou la la! C'est génial! comment et où vous codez trouver ces informations! c'est un ancien (for-if) est-ce que ce code source se produit vraiment dans notre Xcode lorsque nous utilisons func first ()? vraiment?
Vérifiez les liens. Les deux proviennent directement du compte officiel d'Apple.
Merci beaucoup! cela aidera beaucoup à comprendre!