Performance de la méthode select dans Ruby

La méthode select de Ruby est simple et directe. Il sélectionnera les éléments d'un tableau correspondant à un critère spécifique.Performance de la méthode select dans Ruby

Par exemple,

>> x = [4,5,7,89,4,5,3,6,8,9,4,45,56,23,2,7,3,5,4,224,234,565,546,345,23,234,234,234,23466,25,54] 
x = [4,5,7,89,4,5,3,6,8,9,4,45,56,23,2,7,3,5,4,224,234,565,546,345,23,234,234,234,23466,25,54] 
=> [4, 5, 7, 89, 4, 5, 3, 6, 8, 9, 4, 45, 56, 23, 2, 7, 3, 5, 4, 224, 234, 565, 546, 345, 23, 234, 234, 234, 23466, 25, 54] 
>> y = x.select{|m| m>20 && m<200} 
y = x.select{|m| m>20 && m<200} 
=> [89, 45, 56, 23, 23, 25, 54]

Un problème à ce sujet est évidemment la peine est de temps. Select doit parcourir toutes les valeurs de ce tableau et effectue une vérification séquentielle qui résulterait de cette exécution en temps O (n). Y a-t-il une meilleure alternative pour choisir qui le fait dans un temps moindre. L'espace n'est pas un problème pour moi.

Je parle des cas où le même select est utilisé de façon répétitive. Si je vais utiliser les mêmes conditions de sélection 1000 fois dans une boucle pour un tableau de taille n, alors je devrai faire l'opération comme 1000 * n fois. Alors que si c'est optimisé pour l'espace, je ne ferais que 1000 * 1 fois.

Merci.

Source

2011-02-09 bragboy

Vous souhaitez exécuter un test sur toutes les valeurs d'un tableau sans tester toutes ces valeurs dans le tableau? – Gareth

@The MYYN: Sur un vrai ordinateur, c'est toujours linéaire, sauf si je suis en train de bousiller mon raisonnement. Même si vous avez 24 travailleurs sur 24 cœurs, c'est O (n/24), ce qui équivaut à O (n) - c'est un facteur constant. La seule façon d'obtenir O (1) est de supposer qu'un ordinateur peut exécuter un nombre illimité de tâches en même temps (O (n/n) = O (1)), ce qui est physiquement impossible. – Chuck

Whoa whoa whoa .. Peut être mon problème n'était pas clair. Laissez-moi éditer la question pour plus de clarté – bragboy

Je ne suis pas au courant d'un moyen d'effectuer une opération sur chaque élément d'un tableau dans un délai supérieur au temps linéaire - l'idée semble contradictoire. Vous pouvez mémoize le résultat si vous devez faire le même calcul sur le même tableau plus d'une fois pour échanger de l'espace pour des performances en temps constant sur les exécutions suivantes, mais je pense que O (n) est aussi bon qu'il en obtient autrement.

Source

2011-02-09 11:23:11 Chuck

Il est possible d'avoir O (1) dans les cas où select a une seule condition. Je vais utiliser la condition comme une clé pour un hachage, de cette façon il est directement transformé en O (1). Je me demande comment cela est possible quand les conditions augmentent. – bragboy

@Bragboy: Ce n'est pas vraiment clair ce que vous voulez dire en utilisant la condition comme une clé pour un hachage. Utilisez-vous un hash comme une sorte de mémoizer? – MAK

@MAK: Oui, comment tout tableau sera converti en hash – bragboy

Performance de la méthode select dans Ruby

Répondre

Questions connexes