Je veux évaluer une expression mathématique comme Y = 2 (x * x) + 2.
mais j'en ai besoin dans une boucle, où le x change peut-être 100 000 fois. P>
J'ai code écrit pour traduire l'expression dans un arbre d'analyse. p>
alors j'ai une méthode pour évaluer l'arbre d'analyse. P>
- (double) evaluate:(TreeNode *)node variable:(double)x
{
if ([node _operand] != 0)
{
return [node _operand];
}
else if ([node _variable] != NULL)
{
return x;
}
else if ([node _operator] != NULL)
{
if ([[node _operator] isEqualToString: @"+"])
{
return ([self evaluate:[node left] variable:x] + [self evaluate:[node right] variable:x]);
}
else if ([[node _operator] isEqualToString: @"-"])
{
return ([self evaluate:[node left] variable:x] - [self evaluate:[node right] variable:x]);
}
else if ([[node _operator] isEqualToString: @"*"])
{
return ([self evaluate:[node left] variable:x] * [self evaluate:[node right] variable:x]);
}
else if ([[node _operator] isEqualToString: @"/"])
{
return ([self evaluate:[node left] variable:x] / [self evaluate:[node right] variable:x]);
}
}
return 0;
}
6 Réponses :
Vous pouvez obtenir un analyseur d'expression existant. Certains d'entre eux peuvent "compiler" de telles expressions à la volée à un format interne qui ferait évaluer l'expression plus rapidement, puis vous permettant de lui fournir des valeurs pour les variables. La "compilation" serait effectuée avant la boucle et la substitution une fois chaque itération de boucle.
Je sais que ces analyses d'expression / évaluateurs existent pour Delphi, mais je ne sais aucun pour C, désolé. Je suppose que vous pouvez les trouver en ligne, car c possède une base de code mondiale beaucoup plus importante que DELPHI. Juste google (ou bing, etc.) pour "analyseur d'expression" puis regardez si ceux que vous avez trouvés peuvent faire de telles substitutions sans avoir à repérer l'expression.
Merci, j'ai un analyseur, mais c'est lent dans une boucle avec 100 000 fois.
Vous ne pouvez pas générer et exécuter du code de machine sur iOS, mais vous pouvez toujours faire mieux que de marcher un arbre d'analyse. Depuis l'arborescence d'analyse, génère des instructions pour une machine à piles fictive (Pensez-le, X87 Code de la machine, Java Bytecode, CLR Bytecode). Tout en générant, vous pouvez déterminer la quantité d'espace de pile (chiffres) dont vous avez besoin. Ensuite, interpréter ces instructions pour chaque valeur de x. Ceci est plus rapide car les instructions sont plus compactes et ont une meilleure localité que l'arbre d'analyse et car aucune récursion C n'est utilisée.
EDIT: Par exemple, l'expression sqrt (x + 1) est traduite dans quatre instructions: une pour appuyer sur la variable x sur la pile, une pour appuyer sur la constante 1, une pour faire sauter les deux nombres et poussez la somme et un pour remplacer la somme avec sa racine carrée. Tout arbre d'analyse peut facilement être traduit dans une telle liste d'instructions à l'aide d'une fonction récursive. Une instruction pourrait être représentée par une structure contenant un énorme pour le type de l'instruction et un nombre pour les instructions constantes. La "pile" n'est pas la pile c mais simplement une gamme de nombres avec un entier qui indique combien il est actuellement utilisé (qui commence à 0 et se terminera à 1).
Salut Jilles, comment puis-je faire mieux que de marcher un arbre d'analyse? Je ne sais pas comment puis-je faire cela avec la pile espace et interpréter les instructions. Pouvez-vous s'il vous plaît me donner un exemple? Merci beaucoup ! Chris
J'ai ajouté d'autres détails; Si ce n'est toujours pas clair, veuillez utiliser un moteur de recherche avec les mots-clés que j'ai fournis.
Si vous étiez à la performance analysez ce code, vous trouverez [très probablement presque 100% assuréement] que la comparaison de chaînes est ce qui tue votre performance.
Un correctif facile consiste à scinder l'analyse de l'évaluation. C'est-à-dire analyser l'expression dans une forme intermédiaire (comme ce que les jilles et Rudy allusion à, mais plus simples), puis évaluent cette forme intermédiaire. P>
c'est-à-dire que vous pouvez créer une méthode "parse:" [ Récursivement] marche à votre arbre de nœuds, analyses chacun, puis définit une propriété sur un # représentant l'opérateur. P> puis, votre évalue: la variable: code> SI / sinon serait remplacé par une instruction de commutation. P> @property(nonatomic) OperatorID _operator;
Salut, merci beaucoup. Mais j'ai déjà analysé l'expression et j'ai construit un arbre, que j'évalue avec la méthode ci-dessus. Ce dont j'ai besoin, c'est une évaluation plus rapide dans une boucle.
Comment puis-je faire cela dans Objective-C?
Comme il l'a dit: en n'utilisant pas Strings pour stocker dans l'arbre d'analyse. Les opérateurs peuvent être désignés par des entiers au lieu de chaînes. Vous n'avez donc pas à utiliser relativement (comparé à un simple comparaison d'égalité) lent isequaltostring: .
Merci, c'est vrai. C'est vraiment plus rapide. Mais j'ai besoin d'une manière plus rapide. J'ai entendu parler de quelqu'un, qu'il "compile l'expression mathématique à la volée". Dans son application, l'évaluation est très rapide, même lorsqu'il utilise des boucles avec 100 000 fois. Comment puis-je y arriver?
L'avez-vous mesuré avec un outil d'analyse de performance? Qu'est-ce qui prend votre CPU maintenant? Compiler des expressions à la volée n'est ni magique ni facile; Sans connaître vos objectifs de performance et où vos problèmes de performance sont maintenant, il est impossible de dire plus.
Peut-être que vous avez une idée, comment puis-je commencer par compiler des expressions à la volée? Pouvez-vous m'aider ? C'est ce dont j'ai besoin.
Non - ce n'est pas ce dont vous avez besoin tant que vous avez des données de performance dans la main qui montre exactement où les cycles de la CPU sont consommés. La réponse de Dave de Long est une solution meilleure si votre solution [travail, mais lente] ne peut être suffisamment optimisée. En tout état de cause, jusqu'à ce que vous ayez des chiffres, il n'ya aucune raison de croire que la fixation de ce problème particulier résoudra un véritable problème.
Qu'est-ce qui ne va pas avec simplement en utilisant OO Design? L'équivalent en C ++ pourrait être un peu plus rapide.
Ce serait une énormément de cours ... mais cela fonctionnerait. Une autre pensée amusante; OP pourrait stocker le SEL chaque opérateur et simplement l'utiliser directement.
@bbum, qui pourrait ne pas interagir si bien avec le cache de méthode (par classe?). Alternativement, stockez simplement le IMP!
Nah - ça va bien fonctionner avec le cache de méthode. Stocker que l'IMP fonctionnerait aussi bien, bien que vous perdiez des capacités KVO ou des capacités primordiales.
Mon conseil: n'écrivez pas ce code vous-même . Ayant un code écrit qui le fait, il y a des choses à prendre conscience de: L'analyse des expressions mathématiques n'est pas un problème trivial, si vous allez le faire correctement et pleinement. Vous devez considérer des choses comme l'associativité de chaque opérateur: que se passe-t-il si vous trouvez plus d'un des mêmes opérateurs dans une expression? Lequel évaluez-vous en premier? Comment gérez-vous des opérateurs dont la priorité change en fonction de leur contexte? (Par exemple, l'opérateur de négation) Ce sont des questions difficiles et très peu d'implémentations réussissent bien. Comme mentionné dans un commentaire sur la question, il y a des choses qui peuvent le faire pour vous déjà: évidemment, je recommande Cependant, si vous êtes bien de sacrifier une certaine précision (et quelques cas d'être incorrects) en échange de la vitesse rapide de flambage, Je vous recommanderais d'utiliser
nspredicate . Avantages: précision intégrée, raisonnablement rapide et décente. Inconvénients: L'exposant est analysé d'une associativité incorrecte, non extensible, ne prend pas en charge la multiplication implicite (I.e., 2 (x * x) ), n'analyse pas correctement l'opérateur de négation.
gcmathparser . Avantages: très vite , précision décente. Inconvénients: non extensible, ne prend pas en charge la multiplication implicite, n'utilise pas correctement l'opérateur de négation.
DDMATHPARSER . Avantages: Excellente précision, extensible, prend en charge la multiplication implicite. Inconvénients: Pas aussi vite que les deux autres, en raison du moteur analysant et de la haute précision Math
ddmathparser (je l'ai écrit). Dans votre cas, vous voudriez faire quelque chose comme ceci: ddmathparser est disponible sur github: Https://github.com/davedelong/dddmathparser . S'il vous plaît soyez conscient de sa licence (gratuitement pour une utilisation avec attribution). gcmathparser .
Bonjour, merci pour une réponse précise. J'utilise déjà gcmathparser. Et j'ai essayé votre DDMATHPARSER. Mais j'ai besoin d'un moyen plus rapide de la boucle. Je veux calculer une intégration avec la règle Simpson et je dois le faire assez souvent dans la boucle (100 000 ou plus) en raison de la précision. Comment puis-je faire une évaluation plus rapide. Puis-je faire cela avec bytecode à la volée?
@ Chris2810 je doute vraiment. À ce stade, je dirais que votre meilleur pari pour la vitesse est gcmathparser . C'est vraiment incroyablement rapide. Si vous avez des problèmes de vitesse avec cela, veuillez poster une autre question demandant «Comment puis-je optimiser cela?» Et je serai heureux de vous aider à sortir là-bas. De cette façon, nous ne sommes pas pris dans une discussion de commentaires super longue et restrictive.
Peut-être que vous avez une idée, comment puis-je commencer par compiler des expressions à la volée? Pouvez-vous m'aider ? C'est ce dont j'ai besoin.
@ Chris2810 Le gcmathparser est un exemple de la manière dont vous pouvez "compiler" une expression une fois, puis la réévaluer avec une valeur différente pendant x plusieurs fois.
Bonjour Dave, j'utilise déjà le gcmathparser avec ça. Mais c'est trop lent pour moi. Par conséquent, j'ai fait mon propre analyseur avec l'arbre d'analyse une récursion. Il est plus rapide, mais toujours trop lent en boucle avec 1000000 fois. J'ai besoin d'une telle boucle, à cause du résultat exact. Y a-t-il un moyen plus rapide que de marcher dans un arbre d'analyse?
@ Chris2810 Postez votre code lent dans une nouvelle question et demandez de l'aide à l'optimiser.
Je veux évaluer une expression mathématique comme Y = 2 (x * x) + 2. Mais j'en ai besoin dans une boucle, où le X change peut-être 100 000 fois. P>
Vous devez envisager d'utiliser le bibliothèque d'évaluation d'expression mathématique TinyExpr . Il est écrit en C et fera exactement ce que vous voulez. Si vous préférez la coder vous-même, Tinyexpr est seulement 500 lignes de code. C'est donc probablement l'exemple complet le plus simple que vous trouverez. P>
Voici comment vous résoudriez votre problème avec
x Code> Changement constant: P>double x; te_variable vars[] = {{"x", &x}}; te_expr *expr = te_compile("2*(x*x)+2", vars, 1, 0); for (x = 0; x < 100000; ++x) { double y = te_eval(expr); printf("x=%f, y=%f\n", x, y); }
Je parie que votre évaluateur d'expression pourrait faire 100 000 itérations dans une seconde (ou du moins à proximité). Avez-vous mesuré sa performance?
Oui c'est rapide, mais c'est trop lent pour moi. Le code ci-dessus n'est pas terminé. J'ai beaucoup plus "si" pour péché, cos, bronzage, ... donc, il sera plus lent si j'ajoute plus de fonctions.
Merci, mais que puis-je faire d'autre pour accélérer l'évaluation des mathématiques en boucle. J'en ai besoin très vite.
Je ne suis pas expert à ce sujet, alors grain de sel, etc. - mais pourquoi de l'utilisation du moteur JavaScript dans WebKit. C'est un interpréteur de bytecode intégré et apparemment bien optimisé.
Comment puis-je utiliser cela dans une application iOS?
Si vous autorisez une petite pensée latérale, il existe également SQLite - "Sélectionnez 2 + 4 comme" Calc "". Juste une idée, bien sûr, et je n'ai aucune idée de la performance et que cela puisse faire une déclaration préparée qui améliore la performance.
Je ne suis pas tout à fait sûr que vous ne pouvez pas , mais vous n'êtes certainement pas censé.
Avez-vous envisagé
gcmathparserouDDMATHPARSER? Ils sont supposés être incroyablement rapides.@Dave bien, bien sûr. ;) Les grands projets méritent de la reconnaissance.
@Itai est-ce qu'ils la toux mérite aussi des votes aussi? ;)
@Dave oh ouais, ça aussi.
Bonjour, je sais ddmathparser. Mais ce n'est pas la bonne chose pour moi. J'ai fait mon propre analyseur. Ça marche. L'évaluateur est supérieur. Ce dont j'ai besoin est un moyen rapide d'évaluer. Peut-être avec BitCode à la volée.
Duplicailler possible de Stackoverflow.com/Questtions/4892152/...