Je recherche un conteneur qui fournit itérations non commandées les plus rapides à travers les éléments encapsulés. En d'autres termes, "Ajoutez une fois, itérer plusieurs fois".
Y a-t-il un parmi les modules standard d'OCAML suffisamment rapides (de sorte que l'optimisation supplémentaire de cela serait inutile)? Ou une sorte de tierce partie GPL-prête?
afaik Il n'y a qu'un seul compilateur OCAML, donc le concept d'être rapide est plus ou moins clair ...
... Mais après avoir vu quelques réponses, il apparaît, ce n'est pas le cas. Bien sûr, il y a beaucoup de structures de données qui permettent une itération O (n) à travers le conteneur de taille n. Mais la tâche que je résolvante est l'une de celles-ci, où la différence entre O (n) et o (2n) questions; -).
Je vois aussi que les tableaux et les listes fournissent des informations inutiles sur l'ordre des éléments ajoutés , que je n'ai pas besoin. Peut-être dans "monde fonctionnel" existe-t-il des structures de données telles que cela peut échanger cette information pour une vitesse d'itération.
en C, je ferais tranchant un tableau uni. La question est, que dois-je choisir dans OCAML?
5 Réponses :
Toutes les structures de données communes sont iTables dans O (n) du temps, de sorte que les différences entre les structures de données ne seront constantes (et très probablement pas significatives).
Au moins des listes et des tableaux permettent l'itération sans frais généraux importants. Je ne peux pas penser à une situation où cela ne serait pas assez rapide.
Le tableau - une pièce linéaire de mémoire avec les éléments visités dans un ordre séquentiel - utilise le mieux le cache de données L1 de la CPU.
C'était vrai en c ... Est-ce toujours le plus rapide de Ocaml?
S'il s'agit d'un type de données non compensé (par exemple, des entiers), les valeurs de matrice seront stockées dans un bloc de mémoire contigu. Si c'est un type de données "Boxed" (la plupart sont), ce sera un tableau de pointeurs, de sorte que vous ne gagnerez probablement pas beaucoup sur une liste.
Il est peu probable que vous fassiez mieux que des tableaux et des listes intégrés, car ils sont codés à la main dans C, à moins que vous ne liez à votre propre implémentation native d'un itérateur. Un tableau se comportera presque exactement comme un tableau en C (un bloc de mémoire contiguement alloué contenant une séquence de valeurs d'élément), éventuellement avec certaines indirections de pointeur supplémentaires dues à la boxe. La liste est implémentée exactement comment vous voudriez attendre: comme des cellules avec une valeur et un pointeur "Suivant". Les tableaux vous donneront la meilleure localité pour les types de non-boîte (en particulier Pour plus d'informations sur la mise en œuvre des tableaux et des listes, voir 18.3 du manuel OCAML et les fichiers Alors, je choisirai float S, qui ont une implémentation super-spéciale non incorporée).
byerun / mlvalues.h , byerun / aray.c et byerun / alloc.c Dans le code source OCAML.
tableau est apparu comme la solution la plus rapide. Cependant, il n'a que surperformé list de 7%. Peut-être que c'était parce que le type d'un élément de tableau n'était pas assez simple: c'était un type algébrique. hashtbl effectué 4 fois pire, comme prévu.
tableau et j'accepte celui-ci. bon.
C'est assez vieux mais toute la question a été déplacée vers le haut pour une raison quelconque. Permettez-moi de noter que les listes ne sont pas codées à la main dans C, elles sont définies comme un type de type algébrique habituel. Modulo Certains sucre syntaxiques pour la commodité, c'est juste type 'une liste = nil | Inconvénient de 'a *' une liste . Les bonnes performances sont expliquées par de bonnes options de représentation pour les fichiers de données OCAML, non sur la spécialisation. Les tableaux sont intégrés et ont une meilleure localité, cependant.
L'accès à un élément de tableau nécessite une vérification des limites, adresse arithmétique et une charge
Accès à la tête d'une liste nécessite une charge, un test de liste vide et une charge à un décalage de compilation connu.
Les détails dont sont plus rapides dépendent probablement de votre application et de ce qui se passe d'autre sur votre machine. Ils dépendent également du type d'éléments; Par exemple, s'ils sont des nombres à virgule flottante, D'autres structures de données communes telles que les tables de hachage ou les arbres équilibrés nécessitent généralement que vous allouiez un certain contexte quelque part pour garder une trace de l'endroit où vous êtes. Avec un tableau, la suivi ne nécessite qu'un indice entier; Avec une liste, garder la piste nécessite un seul pointeur. Je pense que cela va être difficile à battre dans une autre structure de données.
Enfin, veuillez noter qu'il peut y avoir un seul compilateur OCAML, mais il dispose de deux back extrémités: bytecode et code natif. Naturellement, si vous vous souciez de ce niveau de performance, vous utilisez le code natif Veuillez prendre des mesures et modifier les résultats dans votre question.
ocamlopt peut être suffisamment intelligent pour créer un tableau non compressé, ce qui vous permettra d'économiser un niveau d'indirection.
ocamlopt version. Droite?
N'oubliez pas BIGARRAY S, ils sont les plus proches des tableaux C (juste une pièce de mémoire plate), mais ne peuvent pas contenir des valeurs OCAML arbitraires. Envisagez également des limites de commutation vérifiant (insafe_set / get). Et bien sûr, vous devriez profiler en premier.
1) Pour être pédants, il n'y a pas de différence entre O (n) et O (2n). Vous parlez de facteurs constants. 2) Choisir un ordre arbitraire pour les éléments et la fixer, comme dans un tableau ou une liste, c'est exactement comment vous optimisez pour l'itération. Comment vous attendez-vous à améliorer "Incrémenter un index / suivre un pointeur, aller de la mémoire" pour la vitesse d'itération?
1) Oui, je parle de facteurs constants, car je optimise le goulot d'étranglement; 2) Je ne sais pas comment améliorer cela, mais c'est IT The Way Gundy et List Modules fonctionnent? Le tableau n'est pas dit (tandis que peut être connu ) pour occuper une mémoire consécutive. La liste a besoin de la désarférence du pointeur (lent?). Je doute toujours.
@Pavel: Qu'est-ce que Chris dit, c'est que vous abusez une grosse notation. Il ne dis pas que vous ne devriez pas vous soucier de facteurs constants, seulement que vous devriez être plus clair dans votre notation mathématique lorsque vous y parlez.
@bcat, pourquoi si sérieux? ;-) Je veux dire, je suppose que tous ceux qui lisent des questions dans la balise [OCAML], savent ce que cela signifie et peut détecter des blagues, même si elles ne sont pas si bonnes: - \ \