Dans les systèmes de type LISP, le inconvénient est le moyen normal de préparer un élément à une liste. Les fonctions qui appendent à une liste sont beaucoup plus chères car elles marchent la liste à la fin, puis remplacent la dernière null avec une référence à l'élément annexé. Iow (pseudolisp) question est de savoir si la situation est similaire à Mathemtica? Dans la plupart des regards, les listes de Mathematica semblent être liées seules telles que les listes de LISP et, dans l'affirmative, nous pouvons présumer que l'annexe [liste, élément] est beaucoup plus coûteuse que la liste de préparation [Liste, élément]. Cependant, je n'ai rien pu trouver dans la documentation Mathematica pour répondre à cette question. Si les listes de Mathematica sont doublement liées ou mises en œuvre plus intelligemment, disent, dans un tas ou simplement entretenir un pointeur à la dernière fois, l'insertion peut avoir un profil de performance complètement différent. Tout conseil ou expérience serait apprécié.
4 Réponses :
Les listes de Mathematica ne sont pas des listes de liaison téléphoniques telles que dans les LISP communes. Il vaut mieux penser aux listes Mathematica sous forme de tableau ou de vecteur comme des structures. La vitesse d'insertion est O (n), mais la vitesse de récupération est constante.
Consultez ceci page de Structures de données et algorithmes efficaces dans Mathematica qui couvre Mathematica répertorie plus en détail.
En outre, veuillez consulter Cette Stack Overflow Question sur des listes liées et leur performance dans Mathematica.
+1. Juste pour ajouter à cette belle réponse, le fait que les listes de mathématica soient mises en œuvre, car des tableaux ont des conséquences très graves, affectant tous les aspects de la programmation en mathématica, des styles de programmation (basés sur des règles, fonctionnels, etc.) au réglage de la performance. En particulier, il convient de bien connaître cela pour écrire n'importe quel code où la performance est importante.
Je pense qu'il est malheureux que la structure la plus importante soit manquante dans Mathematica, qui est la structure (ou l'enregistrement). Cela rend difficile de gérer des données dans de grands programmes, lorsque l'on passe de nombreuses choses entre les fonctions, comme on ne peut pas disposer de données connexes dans des enregistrements, au lieu de passer des paramètres individuels. Pour les petits programmes, cela n'a pas d'importance. Je ne vois pas comment on peut concevoir de très grands programmes sans avoir au moins une structure de données d'enregistrement. Toutes les solutions actuelles pour imiter une structure dans Mathematica ne fonctionnent pas trop bien.
@Nasser, voici votre conduct: Nom [VAL11, VAL2, ...] Écrire Sélecteurs getval1 [A_NAME]: = A [[1]], etc et de votre part. Mathematica est écrit en mathématica à une grande étendue (environ 1mloc), je pense que c'est grand.
@Rubenko, peut-on passer une telle "structure" aux fonctions compilées?
@Nasser - J'utilise les définitions comme des enregistrements; Je pense à eux comme des objets de hashable ou JavaScript. Pour modéliser une paire de valeurs de clé "à l'intérieur" une variable R, faire quelque chose comme ce r ["A"] = 1; R [2] = "B"; Signaler toutes les valeurs avec ?? r. Récupérer une valeur comme R ["A"] ou R [2]. Vérifiez la non-existence d'une valeur pour la touche FOO avec R [FOO] === R [FOO]. J'ai écrit une bibliothèque d'enregistrement entière (ou une bibliothèque K-V DB, si vous préférez) avec ce truc. Peut-on facilement aller-retour avec des listes d'associations (listes explicites des paires K-V). Je posterai un lien plus tard.
@Nasser - Une meilleure façon de vérifier la non-existence est MatchQ [R [FOO], R [_]]. Ce chèque n'est pas bon pour certaines structures cycliques, c'est-à-dire où R [FOO] réalise intentionnellement R [quelque chose], mais c'est bon pour la plupart des scénarios de données simples.
@Nasser - voici une poussée de ma bibliothèque "Records": github.com/rebcabin/mathematica-minidata < / a>
En tant que petit ajouter, voici une alternative efficace à "APPENDTO" dans M-
myBag = Internal`Bag[]
Do[Internal`StuffBag[myBag, i], {i, 10}]
Internal`BagPart[myBag, All]
Y a-t-il un moyen de mettre en place une pile utilisant sac [] ? C'est-à-dire que nous pouvons
@Ruebenko - Comment puis-je inspecter certaines des autres définitions de l'espace de noms "interne"? ?? interne et ?? interne` n'a pas fonctionné :)
Au meilleur de ma connaissance qui n'est pas possible.
@ Reb.cabin, vous souhaitez utiliser ? Interne` * qui génère une liste de tout dans le contexte . Mais ils sont sans papiers, vous ne trouverez donc qu'une liste, pas ce qu'ils peuvent faire.
Et la plupart des trucs sont hors de propos, il ne s'agit que d'une utilisation extérieure.
Étant donné que, comme déjà mentionné, les listes Mathematica sont implémentées comme des tableaux, des opérations telles que l'annexe et la préparation, car la liste doit être copiée à chaque fois qu'un élément est ajouté. Une méthode plus efficace consiste à prélever une liste et à le remplir, mais mon expérience ci-dessous n'a pas montré une grande différence que je m'attendais. Mieux vaut toujours, apparemment, est la méthode de liste liée, que je devrai enquêter. < Strong> Modifier Utilisation de la modification suggérée de Nixeagle a considérablement amélioré le chronométrage de Nixeagle, c'est-à-dire avec une liste liée du formulaire {{{startlist}, Data1}, Data2} fonctionne encore mieux et a le grand avantage que la taille n'a pas besoin d'être connue à l'avance , comme pour préallocativement. Comparaison de chronométrage de la liste liée vs préallocativement. (Temps d'exécution: 6 secondes) 
PreAllocatedlist = joindre [Startlist, Constantarray [0, {DataList]}]]]; 
Au moins sur mathematica 8, je reçois une amélioration de la performance vaste en modifiant la table [null, {DataList]}] à CONDUCTARRAY [0, {Longueur [Datatalist]}] Le comportement résultant est au moins un ordre de grandeur plus rapide pour les grandes entrées et reflète la complexité algorithmique attendue.
L'amélioration vient du remplacement de NULL avec 0. PreAllocatedList = JOIS [DÉTAILLISTE, TABLEAU [0, {LONGUEUR [DATALISTE]}]] donne la même amélioration de la performance
Les deux table null et table 0 sont assez rapides dans V7, beaucoup plus rapidement que montré dans la première parcelle ci-dessus. ConstantArray est un peu plus rapide encore. Il apparaît qu'il existe un grand ralentissement introduit dans V8 concernant la table [null, {x}] .
Ce qui précède pourrait toujours être amélioré. Vous mélangez des types. Startlist est entier pendant que la liste de données est réelle. Vous pouvez ajouter un développeur`topackedarray @ Flatten [Linkinglist] pour une joie ultérieure. Notez également que la préallocatedlist n'est pas emballée. Le pays - n'est pas nécessaire. Utilisez do [bla; bla, {compte, longueur [], 1}]. Il était également agréable de comparer cela au sac montré ci-dessus.
Un autre commentaire - Tout à Offten je vois le code qui utilise une sorte d'ajout. Il y a bien sûr des situations où c'est la bonne chose à faire. Je trouve utile de réfléchir au problème pour un peu et de voir si la taille peut être préalable et que le jeu vectorisé A Data = Constantarray [0, {.}] Data [[pos]] = Vals.
@Chris - C'est un peu magnifique que la solution de liaison de liaison est la plus rapide - explicite (évitant la fonction ajoutée) suivie d'un gigantesque aplatiré! Idéal à savoir, cependant! BTW, j'ai reproduit tous vos résultats.
Je pense que je vois ce qui se passe: la "liste imbriquée" dans Mathematica est en fait une simulation des cellules de la SIGL, retourné! C'est une structure chaînée de 2 matrices avec CDR à gauche et voitures à droite, c'est-à-dire I.e. {{{{{}, 1}, 2}, 3}. L'addition des extrémités de ceux-ci est efficace pour la même raison que l'ajout au début des listes LISP est efficace. Ensuite, juste aplatir!
Si vous savez combien d'éléments votre résultat auront et, si vous pouvez calculer vos éléments, l'ensemble de l'annexe, l'annexe, la liste liée, etc. n'est pas nécessaire. Dans le test de vitesse de Chris, la préallocation ne fonctionne que, car il connaît le nombre d'éléments à l'avance. L'opération d'accès à DaTelist signifie le calcul virtuel de l'élément actuel.
Si la situation est comme ça, je n'utiliserais jamais une telle approche. Une table simple combinée à une jointure est l'enfer plus vite. Permettez-moi de réutiliser le code de Chris: j'ajoute la préallocation à la mesure de l'heure, car lors de l'utilisation de l'annexe ou de la liste liée, l'allocation de mémoire est également mesurée. En outre, j'utilise vraiment les listes qui en résultent et que vous vérifiez que, ils sont égaux, car un interprète intelligent reconnaîtrait peut-être des commandes simples et inutiles d'optimiser ces éléments. donne {5.151575, 0.250336, 0.128624, 0.148084}. La construction est heureusement réellement lisible et rapide. Faites attention à essayer ce dernier exemple à la maison. Ici, sur mon Ubuntu 64bit et MMA 8.0.4 L'annexe de N = 10 ^ 5 prend 10 Go de mémoire. n = 10 ^ 6 prend tout mon bélier qui est de 32 Go pour créer une matrice contenant 15 Mo de données. Drôle. 
< P> À mon avis, les situations intéressantes sont, lorsque vous ne connaissez pas le nombre d'éléments à l'avance et que vous devez décider ad hoc si vous devez ou non ajouter / prépender quelque chose. Dans ces cas, récoltez [] et Sow [] vaut peut-être un look. En général, je dirais que l'appends est diabolique et avant de l'utiliser, jetez un coup d'œil aux alternatives: remarque