0
votes

Performance des zéros en mouvement à la fin d'un exercice de programmation de matrice

Je me demande pourquoi ma solution à ce problème de LEetCode "Déplacer Zeros" est plus lente que la majorité des autres soumissions. Existe-t-il un meilleur moyen d'aborder ce problème pour la rendre plus rapide?

La question est la suivante:

Compte tenu d'un tableau nums , écrivez une fonction pour déplacer toutes les 0 à la fin de celui-ci tout en maintenant l'ordre relatif des éléments non nuls. Vous devez faire cela en place sans effectuer une copie du tableau.
Exemple:
entrée: [0,1,0,3,12]
sortie: [1,3,12,0,0]
C'est ma solution: xxx
leetcode me donne ces statistiques:
Runtime: 52 ms, plus rapide que 40,50% de soumissions en ligne Swift pour déplacer les zéros. Utilisation de la mémoire: 19,4 Mo, moins de 13,33% des soumissions en ligne SWIFT pour déplacer les zéros. EDIT 1: Si j'approche le problème comme suit, il ne déplace pas les zéros à la fin, < un href = "https://i.stack.imgur.com/anpjf.png" rel = "nofollow noreferrer"> edit 2:


                        
                        
                            
                                                                    swift
                                                                    algorithm
                                                                    performance
                                                                    arrays
                                                            
                        
                                                    
                            
                            
                                5 commentaires
                                
                                                                            Qu'en est-il de  INPUT.FILTER {$ 0! = 0} + INPUT.FILTER {$ 0 == 0} ?

                                        
                                                                            S'il vous plaît, définissez "cela n'a pas fonctionné". Cela doit fonctionner.
                                        
                                                                            J'ai une réponse similaire avec le filtre que j'ai deviné, c'était pour vous aussi être utilisé peut être utilisé mais la commande sera partie
                                        
                                                                            Ce que vous cherchez ici s'appelle une partitionnement stable.  Stackoverflow.com/q/40010345/3141234 
                                        
                                                                            FYI, ne faites pas confiance aux chiffres. Je suis à peu près sûr qu'ils ne fonctionnent même pas de code optimisé et il semble que la plupart des  40ms  secondes sont en réalité le moment de démarrer le test de performance et le test réel est presque instantané.



                                    
                    7 Réponses :
                    
                                            
                            
                                
                                    2
 votes
                                
                            
                            
                                
                                     De ce que je peux voir, il est probable que d'autres soumissions font cela 


 Vérifiez et comptez 0 dans la chaîne 
 Supprimer 0's's 
 remplacez le nombre de 0 à la fin de la chaîne 


 Une méthode logique sans doute, mais je dirais que le vôtre choisit simplement les besoins fondamentaux du défi et y va.                                 

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     J'utiliserais personnellement:  xxx  
     
 qui peut être simplifié à un passage:   xxx  
     
 EDIT: La version la plus simple sans créer de nouvelle matrice serait une version primitive du tri des bulles, par exemple :   xxx  
                                     

                                                                    
                                    
                                    
                                        6 commentaires
                                        
                                                                                            
                                                    Désolé, j'ai oublié de mentionner dans la question que vous devez faire ce  en place  sans effectuer une copie de la matrice.                                                

                                                
                                                                                            
                                                    @Hotspring Cela signifie que vous devez utiliser une sorte de tri de bulle, je suppose.                                                
                                                
                                                                                            
                                                    @Hotspring le dupliqué de même et était pour vous aussi                                                
                                                
                                                                                            
                                                    @Sh_khan, veuillez vérifier mon édition faisant référence à la capture d'écran.                                                
                                                
                                                                                            
                                                    @Sulthan, pourriez-vous vérifier mon édition en référence à la capture d'écran en bas.                                                
                                                
                                                                                            
                                                    @Hotspring Okey, a ajouté une solution sur place.                                                
                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Swift 4.2 ou version ultérieure Utilisation de  RemoveAll  Code> Méthode de mutation: 
 Mutating de l'entrée:  P> 
let  input = [0,1,0,3,12]

let zerosMoved = moveZeroes(input)
zerosMoved   // [1, 3, 12, 0, 0]

                                

                                                                    
                                    
                                    
                                        3 commentaires
                                        
                                                                                            
                                                    C'est vraiment une bonne approche mais ne peut pas gérer un scénario que j'ai attaché dans la ma question comme  edit 2                                                 

                                                
                                                                                            
                                                    à peu près sûr que vous devriez faire itérair à partir de la fin. Cependant, l'élimination des éléments du milieu de la matrice est probablement pire qu'un simple filtre  .                                                

                                                
                                                                                            
                                                    @Sulthan oui si je n'étais pas ajouté à l'élément retiré à la fin du tableau.                                                
                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Une autre approche est l'algorithme de partition demi-stable. La prestation est que les éléments sont échangés plutôt que retirés et insérés / annexés. 
  demi-stable  em> signifie que l'ordre du côté gauche du point de division est préservé.  P> 
extension Array {

    mutating func halfStablePartition(indexes : IndexSet) { // code is O(n)
        guard var i = indexes.first, i < count else { return }
        var j = index(after: i)
        var k = indexes.integerGreaterThan(i) ?? endIndex
        while j != endIndex {
            if k != j { swapAt(i, j); formIndex(after: &i) }
            else { k = indexes.integerGreaterThan(k) ?? endIndex }
            formIndex(after: &j)
        }
    }
}

var input = [0,1,0,3,12]

let indices = IndexSet(input.indices.filter{input[$0] == 0})
input.halfStablePartition(indexes: indices)

                                

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Voici une solution de 36 ms sur place pour vous:  xxx  
                                     

                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    Je ne m'inquiéterais pas trop sur l'individu  MS . Il y a probablement une assez grande tolérance depuis la même solution soumise plusieurs fois différents résultats (+ 10 ms dans mes tests). Malheureusement, la majeure partie de l'utilisation de la mémoire est probablement la durée d'exécution rapide, par conséquent, de petites différences sont également peu fiables.                                                

                                                
                                                                                            
                                                    En fait, il semble qu'il faut environ  40ms  pour le test de performance pour démarrer et le test réel est presque instantané. Quel mauvais test de performance! Je dirais que ce n'est même pas optimisé.                                                

                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     Une solution rapide consiste à déplacer des éléments non nuls à gauche par la quantité de zéros rencontrée jusque-là: 
func moveZeroes(_ nums: inout [Int]) {
    var offset = 0
    for i in 0..<nums.count {
        if nums[i] == 0 { offset += 1 }
        else { nums.swapAt(i, i-offset) }
    }
}

                                

                                                                    
                                    
                                    
                                        3 commentaires
                                        
                                                                                            
                                                     nums.indices.foreach {nums [0 $] == 0? offset + = 1: numswapat (0 $, 0 $ - Décalage)}                                                 

                                                
                                                                                            
                                                    J'ai utilisé exactement la même solution, avec une attribution manuelle au lieu de  Swapat . Pour être honnête, en fait, j'ai fait des tests de performance et toutes les solutions ont presque la même performance. Bien sûr, vous pouvez vous améliorer légèrement en utilisant des microoptimizations (suppression des appels de fonction), mais vous avez besoin d'un tableau avec des éléments de 10 m pour voir vraiment une différence significative (0,02 seconde dans mes tests).                                                

                                                
                                                                                            
                                                    @Sulthan Je pense que les chiffres sont similaires car toutes les réponses sont O (n). Certaines des solutions utilisent plus de n étapes dues aux détails de la mise en œuvre, cependant, comme vous avez indiqué que la différence de temps n'est pas perceptible pour les matrices de petite à moyenne.                                                
                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     pour modifier la matrice en place et le garder: 
  O (n)  pour la complexité de temps  
  o (1)  pour l'espace Complexité  
 fissuré la tête de la tête à long terme pour celui-ci. Le moyen le plus propre si vous échangez un élément qui n'est pas zéro:   xxx                                  


                                                                    
                                    
                                    
                                        0 commentaires

Articles qui pourrait vous intéresser : Comment corriger l'erreur "Hash mismatch for chunk" avec iOS 13 + Apple On Demand Resources Comment tester une méthode qui répartit le travail de manière asynchrone dans Swift Comment masquer l'en-tête sur la disposition de composition de la vue de collection iOS 13 Vue SwiftUI - viewDidLoad ()?