Dev Faq
7
votes

Collecter un nombre inconnu de résultats dans une boucle

Quel est le moyen idiomatique de collecter des résultats dans une boucle dans R si le nombre de résultats finaux n'est pas connu à l'avance? Voici un exemple de jouet: 

results = list()
i=1L
while (i < bigBigBIGNumber)  {
    if (someCondition(i)) results = list(results, i)
    i = i+1
}
unlist(results)

12 commentaires

La fonction C est utilisée pour étendre les vecteurs ou les listes. Si vous pouvez estimer la taille, alloué avec vecteur ("entier", taille) aidera à réduire le coût de l'extension.

@DWIN existe-t-il des outils existants qui étendent la matrice de manière intelligente, à la demande? (E.G. Double la taille de la matrice préallocée une fois sa capacité atteinte et éviter la complexité quadratique)

@Szabolcs, pourquoi pensez-vous remplacer C avec la liste aiderait ici? À moins que vous préveniez une liste, le même problème persiste, n'est-ce pas?

@Arun Notez que C concaténés (qui déclenche une réaffectation du vecteur) lors de la liste Je construit une structure comme Liste (liste (liste (1 ), 2), 3) , une liste liée. Lorsqu'il est mis en boucle, ce dernier a une complexité linéaire, le premier a un quadratique. Vous pouvez facilement vérifier cela par un petit repère: doubler le nombre d'éléments à ajouter doublez le temps avec la liste et presque quadruples avec C . Cela signifie que pour un résultat «assez large», la liste sera toujours plus rapide. Ce que je n'ai pas réalisé quand j'ai écrit la question est que dans ce cas "assez grand" ...

@Arun ... n'est pas impraticement grand. Pour les listes de taille pratique, C sera toujours plus rapide.

@Szabolcs, exécutant votre liste de liste-de -... sur 1E5 Éléments déjà abouti à une erreur Erreur: Protect () Pile de protection Overflow . Pas tout à fait sûr de quelle est la gamme de votre BigBignumber ..

@Arun oui, je viens de le courir aussi et je me suis rendu compte que la complexité n'est pas linéaire. Je ne sais pas pourquoi. Je serais intéressé par la manière de mettre correctement implémenter une liste liée dans R, si possible du tout.

Malheureusement, une liste de liste ici est une liste imbriquée. Il ne semble pas correspondre au paradigme de la liste liée ...

@Arun Pouvez-vous expliquer pourquoi? L'idée est venue de Mathematica (un autre système fonctionnel qui préfère des structures immuables), où le mécanisme de stockage sous-jacent d'une liste imbriquée est également directement correspondant à une liste liée. Une liste Mathematica est stockée comme une gamme de pointeurs à d'autres expressions Mathematica, qui peuvent être répertoriées. Il semble donc que ce soit différent dans R. Pouvez-vous expliquer comment les listes sont stockées dans R (je suis juste curieux, mais cela n'est pas aussi pertinent), et s'il est possible de mettre en œuvre une liste liée du tout (un peu plus pertinente). ?

Pour l'instant, j'espère Cette réponse pourrait aider partiellement à aider, dans ces listes R, sont comme des structures de données de carte de hachage ..

Avez-vous lu l'inferno? Burns-stat.com/pages/Tutor/r_inferno.pdf

@ Romanluštrik je l'ai regardé. C'est l'un des documents que je regarde de temps en temps tout en apprenant. C'est bien. Merci de le pointer.

4 Réponses :

1
votes

plus proche du second que vous avez énuméré: xxx

Notez que i n'a pas besoin d'être un entier , pourrait être un caractère , etc.

aussi, vous pouvez utiliser résultats [[longueur (résultats)]] <- ... si nécessaire, mais si vous Avoir déjà un itérateur, probablement ne serait probablement pas.

10 commentaires

Cela résoudra-t-il les deux problèmes que j'ai posés sur, à savoir 1. pré-générer toutes les valeurs à itérer (je ne veux pas les garder toutes en mémoire) et 2 . est-il ajouté à la complexité quadratique, c'est-à-dire que l'ajout comme des résultats [[i]] <- ... provoque la réaffectation de l'ensemble de la liste?

Un peu de benchmarking montre qu'il échoue sur les deux points 1. et pointez 2. de mon commentaire. Cependant, il montre également que cette façon d'ajouter à une liste est plus rapide que l'approche de la liste liée que j'ai essayée jusqu'à une très grande longueur (plus que 100000 ), ainsi que cette boucle dans R De cette façon est si lent que je vais généralement "manquer de temps" avant de pouvoir manquer de mémoire lorsque vous utilisez pour .

Si l'efficacité est d'une extrême préoccupation, vous voulez probablement regarder en dehors de la base r . RCPP vous vient à l'esprit. cran.r-project.org/web/packages/rcpp/index. HTML

Toute affectation aura une "complexité quadratique" dans R. Il y a toujours au moins une copie temporaire, parfois plus, faite avant la fin de la tâche. Le conseil donné est d'avoir au moins 3 fois la RAM devait contenir le plus grand objet de votre espace de travail. (Consommé à un taux d'environ 10 octets par «double».)

@Dwin voulez-vous dire que même x = 1: 10; x [[3]] <- 10 réaffecte le tableau complet ? Cela ne fera sûrement pas cela, car vous avez suggéré de pré-allocation vous-même dans votre autre commentaire. La complexité quadratique n'est pas de l'affectation, mais de l'ajout répété n fois. (Cela prendra O (n ^ 2) temps.)

@Szabolcs, pourquoi indexez-vous un vecteur avec [[]] au lieu de [] ?

@Dwin, je ne comprends pas si vous dites que la solution de Ricardo est efficace ou non ... Pourriez-vous s'il vous plaît clarifier? La liste est pas préallocated. Cela serait également inefficace que je suppose que je suppose.

@Arun suppose juste [ si vous l'aimez mieux et si cela ne fait aucune différence.

@Szabolcs tant que vous n'accédez pas à une liste, [[ et [ ne fait pas une différence, oui.

Je dis que l'inefficacité ne peut être éliminée. Copier sur la mission en r est juste m = pas évitable sans stratégies de codage spéciales qui ne sont sans doute en dehors de la portée de la langue appropriée. Si vous voulez une efficacité, je vous suggère de regarder dans le paquet de données.Table ou de la RCPP. Il y a plusieurs exemples de données de données.

2
votes

Si vous ne pouvez pas calculer 1: bigbignumber , comptez les entrées, créez le vecteur, puis remplissez-le. XXX

(Ce code n'est pas testé. )

Si vous pouvez calculer 1: bigbigbignumber , cela fonctionnera également:

Je suppose que vous souhaitez appeler une fonction, et non simplement sur les indices eux-mêmes. Quelque chose comme ça peut être plus proche de ce que vous voulez: xxx

2 commentaires

+1 pour indiquer la valeur potentielle de vectorisation dans les valeurs [Somécontion (valeurs)]

Le problème étant, bien sûr, que somécontion (i) est calculé deux fois . S'il s'agit d'un calcul complexe, alors cela peut le faire deux fois peut manger des gains de performance. J'ai une question dans ces lignes , toutes les pensées seraient appréciées.

6
votes

Voici un algorithme qui double la taille de la liste de sortie tel qu'il remplit, obtenant des temps de calcul quelque peu linéaires, comme indiquez les tests de référence: 

test <- function(bigBigBIGNumber = 1000) {

  n <- 10L
  results <- vector("list", n)
  m <- 0L
  i <- 1L
  while (i < bigBigBIGNumber)  {
    if (runif(1) > 0.5) {
      m <- m + 1L
      results[[m]] <- i
      if (m == n) {
        results <- c(results, vector("list", n))
        n <- n * 2L
      }
    }
    i = i + 1L
  }
  unlist(results)
}

system.time(test(1000))
#    user  system elapsed 
#   0.008   0.000   0.008 
system.time(test(10000))
#    user  system elapsed 
#   0.090   0.002   0.093 
system.time(test(100000))
#    user  system elapsed 
#   0.885   0.051   0.936 
system.time(test(1000000))
#    user  system elapsed 
#   9.428   0.339   9.776

2 commentaires

Merci, c'est très pratique, alors je l'accepterai, mais les autres réponses / commentaires ont également contribué à comprendre ce que les gens considèrent idiomatique dans R.

Je suppose que la linéarité est vraiment en tête dans la boucle (générant des nombres aléatoires, attribuant des résultats, etc.); Le temps de croissance est égal à juste (par exemple, pour 2 ^ 20 éléments) system.time ({x = entier (1); pour (i in 1:19) x <- C (x, entier (2 ^ i))}) (une fraction d'une seconde).

4
votes

Il y a probablement une taille maximale que vous êtes prêt à tolérer; Pré-allouer et remplir ce niveau, puis couper si nécessaire. Cela évite le risque de ne pas pouvoir satisfaire la demande de double taille, même lorsque seule une petite quantité supplémentaire de mémoire pourrait être nécessaire; Il échoue tôt et implique une seule réaffectation plutôt que de log (n). Voici une fonction qui prend une taille maximale, une fonction génératrice et un jeton que la fonction génératrice retourne quand il n'y a plus rien à générer. Nous obtenons jusqu'à n résultats avant de retourner xxx

voici un générateur xxx

et en action xxx

Nous pouvons comparer les frais généraux, approximativement, en comparant quelque chose qui sait à l'avance combien d'espace est requis xxx

ici, nous vérifions le calendrier et la valeur d'un résultat unique xxx

lequel pour cet exemple est bien sûr éclipsé par la simple solution vectorielle xxx

0 commentaires

Articles qui pourrait vous intéresser :

Comment créer une barre de couleur dégradée discrète avec geom_contour_filled?
Variable de bande dans R
Mélanger le vecteur dans R, mais les éléments identiques doivent avoir une distance minimale
Pour imprimer la valeur de l'année bissextile suivante en utilisant la variable dans la programmation R