Il modo più veloce per risolvere calcoli a catena

Ho un input come

string input = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34"; // up to 10MB string size int result = Calc(input); // 11 
  • il calcolo va da sinistra a destra, numero per numero
  • i numeri sono da 0 a 99
  • la moltiplicazione prima dell’aggiunta viene ignorata, quindi 14 + 2 * 32 è 512
  • i possibili calcoli sono +-*/
  • la divisione per 0 non è ansible, quindi dopo / non può essere uno 0

Il mio approccio

 public static int Calc(string sInput) { int iCurrent = sInput.IndexOf(' '); int iResult = int.Parse(sInput.Substring(0, iCurrent)); int iNext = 0; while ((iNext = sInput.IndexOf(' ', iCurrent + 4)) != -1) { iResult = Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3), iNext - (iCurrent + 2)))); iCurrent = iNext; } return Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3)))); } public static int Operate(int iReturn, char cOperator, int iOperant) { switch (cOperator) { case '+': return (iReturn + iOperant); case '-': return (iReturn - iOperant); case '*': return (iReturn * iOperant); case '/': return (iReturn / iOperant); default: throw new Exception("Error"); } } 

Ho bisogno del modo più veloce per ottenere un risultato.

Domanda: c’è un modo per rendere questo calcolo più veloce? Ho più thread ma ne uso solo uno.

Aggiornare:

Caso di prova: (Ho rimosso la divisione per 0 bug e rimosso StringBuilder.ToString() dalla misurazione di StopWatch )

 Random rand = new Random(); System.Text.StringBuilder input = new System.Text.StringBuilder(); string operators = "+-*/"; input.Append(rand.Next(0, 100)); for (int i = 0; i  0 ? 4 : 3)]; input.Append(" " + coperator + " " + number); } string calc = input.ToString(); System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch(); watch.Start(); int result = Calc(calc); watch.Stop(); 

La seguente soluzione è un automa finito. Calc (input) = O (n). Per prestazioni migliori, questa soluzione non utilizza IndexOf , Substring , Parse , concatenazione di stringhe o lettura ripetuta del valore (recupero input[i] più di una volta) … solo un processore di caratteri.

  static int Calculate1(string input) { int acc = 0; char last = ' ', operation = '+'; for (int i = 0; i < input.Length; i++) { var current = input[i]; switch (current) { case ' ': if (last != ' ') { switch (operation) { case '+': acc += last - '0'; break; case '-': acc -= last - '0'; break; case '*': acc *= last - '0'; break; case '/': acc /= last - '0'; break; } last = ' '; } break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': if (last == ' ') last = current; else { var num = (last - '0') * 10 + (current - '0'); switch (operation) { case '+': acc += num; break; case '-': acc -= num; break; case '*': acc *= num; break; case '/': acc /= num; break; } last = ' '; } break; case '+': case '-': case '*': case '/': operation = current; break; } } if (last != ' ') switch (operation) { case '+': acc += last - '0'; break; case '-': acc -= last - '0'; break; case '*': acc *= last - '0'; break; case '/': acc /= last - '0'; break; } return acc; } 

E un'altra implementazione. Legge il 25% in meno dall'input. Mi aspetto che abbia il 25% di prestazioni migliori.

  static int Calculate2(string input) { int acc = 0, i = 0; char last = ' ', operation = '+'; while (i < input.Length) { var current = input[i]; switch (current) { case ' ': if (last != ' ') { switch (operation) { case '+': acc += last - '0'; break; case '-': acc -= last - '0'; break; case '*': acc *= last - '0'; break; case '/': acc /= last - '0'; break; } last = ' '; i++; } break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': if (last == ' ') { last = current; i++; } else { var num = (last - '0') * 10 + (current - '0'); switch (operation) { case '+': acc += num; break; case '-': acc -= num; break; case '*': acc *= num; break; case '/': acc /= num; break; } last = ' '; i += 2; } break; case '+': case '-': case '*': case '/': operation = current; i += 2; break; } } if (last != ' ') switch (operation) { case '+': acc += last - '0'; break; case '-': acc -= last - '0'; break; case '*': acc *= last - '0'; break; case '/': acc /= last - '0'; break; } return acc; } 

Ho implementato un'altra variante:

  static int Calculate3(string input) { int acc = 0, i = 0; var operation = '+'; while (true) { var a = input[i++] - '0'; if (i == input.Length) { switch (operation) { case '+': acc += a; break; case '-': acc -= a; break; case '*': acc *= a; break; case '/': acc /= a; break; } break; } var b = input[i]; if (b == ' ') i++; else { a = a * 10 + (b - '0'); i += 2; } switch (operation) { case '+': acc += a; break; case '-': acc -= a; break; case '*': acc *= a; break; case '/': acc /= a; break; } if (i >= input.Length) break; operation = input[i]; i += 2; } return acc; } 

Risultati in punti astratti:

  • Calcola1 230
  • Calcola2 192
  • Calcola3 111

Modifica modifica: aggiornato con le ultime versioni di The General e Mirai Mann:

Se vuoi sapere quale cavallo è più veloce: corri con i cavalli. Ecco i risultati di BenchmarkDotNet confrontano varie risposte di questa domanda (non ho fuso il loro codice nel mio esempio completo, perché ciò sembra sbagliato – solo i numeri sono presentati) con input casuali ripetibili ma di grandi dimensioni, tramite:

 static MyTests() { Random rand = new Random(12345); StringBuilder input = new StringBuilder(); string operators = "+-*/"; var lastOperator = '+'; for (int i = 0; i < 1000000; i++) { var @operator = operators[rand.Next(0, 4)]; input.Append(rand.Next(lastOperator == '/' ? 1 : 0, 100) + " " + @operator + " "); lastOperator = @operator; } input.Append(rand.Next(0, 100)); expression = input.ToString(); } private static readonly string expression; 

con controlli di integrità (per verificare che facciano tutti la cosa giusta):

 Original: -1426 NoSubStrings: -1426 NoSubStringsUnsafe: -1426 TheGeneral4: -1426 MiraiMann1: -1426 

otteniamo i tempi (nota: l' Original è la versione dell'OP nella domanda; NoSubStrings[Unsafe] sono le mie versioni dal basso e altre due versioni da altre risposte per nome utente):

(inferiore "Media" è meglio)

(nota: c'è una versione più recente dell'implementazione di Mirai Mann, ma non ho più configurazione per eseguire un nuovo test, ma: è giusto presumere che dovrebbe essere migliore!)

Runtime: .NET Framework 4.7 (CLR 4.0.30319.42000), LegacyJIT-v4.7.2633.0 a 32 bit

  Method | Mean | Error | StdDev | ------------------- |----------:|----------:|----------:| Original | 104.11 ms | 1.4920 ms | 1.3226 ms | NoSubStrings | 21.99 ms | 0.4335 ms | 0.7122 ms | NoSubStringsUnsafe | 20.53 ms | 0.4103 ms | 0.6967 ms | TheGeneral4 | 15.50 ms | 0.3020 ms | 0.5369 ms | MiraiMann1 | 15.54 ms | 0.3096 ms | 0.4133 ms | 

Runtime: .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0

  Method | Mean | Error | StdDev | Median | ------------------- |----------:|----------:|----------:|----------:| Original | 114.15 ms | 1.3142 ms | 1.0974 ms | 114.13 ms | NoSubStrings | 21.33 ms | 0.4161 ms | 0.6354 ms | 20.93 ms | NoSubStringsUnsafe | 19.24 ms | 0.3832 ms | 0.5245 ms | 19.43 ms | TheGeneral4 | 13.97 ms | 0.2795 ms | 0.2745 ms | 13.86 ms | MiraiMann1 | 15.60 ms | 0.3090 ms | 0.4125 ms | 15.53 ms | 

Runtime: .NET Core 2.1.0-preview1-26116-04 (CoreCLR 4.6.26116.03, CoreFX 4.6.26116.01), RyuJIT a 64 bit

  Method | Mean | Error | StdDev | Median | ------------------- |----------:|----------:|----------:|----------:| Original | 101.51 ms | 1.7807 ms | 1.5786 ms | 101.44 ms | NoSubStrings | 21.36 ms | 0.4281 ms | 0.5414 ms | 21.07 ms | NoSubStringsUnsafe | 19.85 ms | 0.4172 ms | 0.6737 ms | 19.80 ms | TheGeneral4 | 14.06 ms | 0.2788 ms | 0.3723 ms | 13.82 ms | MiraiMann1 | 15.88 ms | 0.3153 ms | 0.5922 ms | 15.45 ms | 

Risposta originale di prima ho aggiunto BenchmarkDotNet :

Se ci provassi, sarei tentato di dare un'occhiata allo Span lavoro in 2.1 anteprime - il punto è che una Span può essere affettata senza allocare (e una string può essere convertita in una Span senza allocazione); questo consentirebbe di eseguire la stringa e l'analisi senza allocazioni. Tuttavia, la riduzione delle allocazioni non è sempre la stessa cosa delle prestazioni non elaborate (sebbene siano correlate), quindi per sapere se è più veloce: dovrai correre i tuoi cavalli (cioè confrontarli).

Se Span non è un'opzione: puoi ancora fare la stessa cosa rintracciando un int offset manualmente e semplicemente * mai usando SubString )

In entrambi i casi ( string o Span ): se l'operazione deve solo far fronte a un certo sottoinsieme di rappresentazioni di numeri interi, potrei essere tentato di assegnare a un ruolo un equivalente int.Parse personalizzato che non si applica a più regole ( culture, layout alternativi, ecc.) e che funziona senza bisogno di una Substring - per esempio potrebbe prendere una string e un ref int offset , dove l' offset viene aggiornato per essere dove l'analisi si è fermata (o perché ha colpito un operatore o uno spazio) e che ha funzionato

Qualcosa di simile a:

 static class P { static void Main() { string input = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34"; var val = Evaluate(input); System.Console.WriteLine(val); } static int Evaluate(string expression) { int offset = 0; SkipSpaces(expression, ref offset); int value = ReadInt32(expression, ref offset); while(ReadNext(expression, ref offset, out char @operator, out int operand)) { switch(@operator) { case '+': value = value + operand; break; case '-': value = value - operand; break; case '*': value = value * operand; break; case '/': value = value / operand; break; } } return value; } static bool ReadNext(string value, ref int offset, out char @operator, out int operand) { SkipSpaces(value, ref offset); if(offset >= value.Length) { @operator = (char)0; operand = 0; return false; } @operator = value[offset++]; SkipSpaces(value, ref offset); if (offset >= value.Length) { operand = 0; return false; } operand = ReadInt32(value, ref offset); return true; } static void SkipSpaces(string value, ref int offset) { while (offset < value.Length && value[offset] == ' ') offset++; } static int ReadInt32(string value, ref int offset) { bool isNeg = false; char c = value[offset++]; int i = (c - '0'); if(c == '-') { isNeg = true; i = 0; // todo: what to do here if `-` is not followed by [0-9]? } while (offset < value.Length && (c = value[offset++]) >= '0' && c <= '9') i = (i * 10) + (c - '0'); return isNeg ? -i : i; } } 

Successivamente, potrei considerare se vale la pena passare a unsafe per rimuovere i controlli di doppia lunghezza. Quindi lo implementerei in entrambi i modi , e testarlo con qualcosa come BenchmarkDotNet per vedere se ne vale la pena.


Modifica: qui è con l'aggiunta unsafe e l'utilizzo BenchmarkDotNet:

 using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Running; using System; static class P { static void Main() { var summary = BenchmarkRunner.Run(); System.Console.WriteLine(summary); } } public class MyTests { const string expression = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34"; [Benchmark] public int Original() => EvalOriginal.Calc(expression); [Benchmark] public int NoSubStrings() => EvalNoSubStrings.Evaluate(expression); [Benchmark] public int NoSubStringsUnsafe() => EvalNoSubStringsUnsafe.Evaluate(expression); } static class EvalOriginal { public static int Calc(string sInput) { int iCurrent = sInput.IndexOf(' '); int iResult = int.Parse(sInput.Substring(0, iCurrent)); int iNext = 0; while ((iNext = sInput.IndexOf(' ', iCurrent + 4)) != -1) { iResult = Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3), iNext - (iCurrent + 2)))); iCurrent = iNext; } return Operate(iResult, sInput[iCurrent + 1], int.Parse(sInput.Substring((iCurrent + 3)))); } public static int Operate(int iReturn, char cOperator, int iOperant) { switch (cOperator) { case '+': return (iReturn + iOperant); case '-': return (iReturn - iOperant); case '*': return (iReturn * iOperant); case '/': return (iReturn / iOperant); default: throw new Exception("Error"); } } } static class EvalNoSubStrings { public static int Evaluate(string expression) { int offset = 0; SkipSpaces(expression, ref offset); int value = ReadInt32(expression, ref offset); while (ReadNext(expression, ref offset, out char @operator, out int operand)) { switch (@operator) { case '+': value = value + operand; break; case '-': value = value - operand; break; case '*': value = value * operand; break; case '/': value = value / operand; break; default: throw new Exception("Error"); } } return value; } static bool ReadNext(string value, ref int offset, out char @operator, out int operand) { SkipSpaces(value, ref offset); if (offset >= value.Length) { @operator = (char)0; operand = 0; return false; } @operator = value[offset++]; SkipSpaces(value, ref offset); if (offset >= value.Length) { operand = 0; return false; } operand = ReadInt32(value, ref offset); return true; } static void SkipSpaces(string value, ref int offset) { while (offset < value.Length && value[offset] == ' ') offset++; } static int ReadInt32(string value, ref int offset) { bool isNeg = false; char c = value[offset++]; int i = (c - '0'); if (c == '-') { isNeg = true; i = 0; } while (offset < value.Length && (c = value[offset++]) >= '0' && c <= '9') i = (i * 10) + (c - '0'); return isNeg ? -i : i; } } static unsafe class EvalNoSubStringsUnsafe { public static int Evaluate(string expression) { fixed (char* ptr = expression) { int len = expression.Length; var c = ptr; SkipSpaces(ref c, ref len); int value = ReadInt32(ref c, ref len); while (len > 0 && ReadNext(ref c, ref len, out char @operator, out int operand)) { switch (@operator) { case '+': value = value + operand; break; case '-': value = value - operand; break; case '*': value = value * operand; break; case '/': value = value / operand; break; default: throw new Exception("Error"); } } return value; } } static bool ReadNext(ref char* c, ref int len, out char @operator, out int operand) { SkipSpaces(ref c, ref len); if (len-- == 0) { @operator = (char)0; operand = 0; return false; } @operator = *c++; SkipSpaces(ref c, ref len); if (len == 0) { operand = 0; return false; } operand = ReadInt32(ref c, ref len); return true; } static void SkipSpaces(ref char* c, ref int len) { while (len != 0 && *c == ' ') { c++;len--; } } static int ReadInt32(ref char* c, ref int len) { bool isNeg = false; char ch = *c++; len--; int i = (ch - '0'); if (ch == '-') { isNeg = true; i = 0; } while (len-- != 0 && (ch = *c++) >= '0' && ch <= '9') i = (i * 10) + (ch - '0'); return isNeg ? -i : i; } } 

NOTA

Per commenti, questa risposta non offre una soluzione performante. Lascerò qui perché ci sono punti da considerare / che potrebbero essere di interesse per gli altri che trovano questo thread in futuro; ma come si è detto in seguito, questo è lontano dalla soluzione più performante.


Risposta originale

Il framework .net fornisce già un modo per gestire le formule date come stringhe:

 var formula = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34"; var result = new DataTable().Compute(formula, null); Console.WriteLine(result); //returns 139.125490196078 

Feedback iniziale basato sui commenti

Per il thread dei commenti ho bisogno di evidenziare alcune cose:

Funziona come ho descritto?

No; questo segue le normali regole della matematica.

Presumo che le tue regole modificate semplificino la scrittura del codice per gestirle, piuttosto che perché vuoi supportare una nuova branca della matematica? In tal caso, controbatterei. Le persone si aspetteranno che le cose si comportino in un certo modo; quindi dovresti assicurarti che chiunque invii equazioni al tuo codice sia pronto con la consapevolezza di aspettarsi le regole di questa nuova matematica piuttosto che essere in grado di usare le loro aspettative esistenti.

Non c’è un’opzione per cambiare le regole qui; quindi se il tuo requisito è quello di cambiare le regole della matematica, questo non funzionerà per te.

È la soluzione più veloce

No. Comunque dovrebbe funzionare bene dato che MS spende un sacco di tempo per ottimizzare il proprio codice, e quindi probabilmente eseguirà più velocemente di qualsiasi codice rollato a mano per fare lo stesso (sebbene, ammettiamolo, questo codice faccia molto di più del semplice supporto dei quattro operatori principali ; quindi non sta facendo esattamente lo stesso).

Per specifico commento di MatthewWatson (vale a dire chiamare il costruttore DataTable comporta un sovraccarico significativo) che si desidera creare e quindi riutilizzare un’istanza di questo object. A seconda di come si presenta la tua soluzione, ci sono vari modi per farlo; eccone uno:

 interface ICalculator //if we use an interface we can easily switch from datatable to some other calulator; useful for testing, or if we wanted to compare different calculators without much recoding { T Calculate(string expression) where T: struct; } class DataTableCalculator: ICalculator { readonly DataTable dataTable = new DataTable(); public DataTableCalculator(){} public T Calculate(string expression) where T: struct => (T)dataTable.Compute(expression, null); } class Calculator: ICalculator { static ICalculator internalInstance; public Calculator(){} public void InitialiseCalculator (ICalculator calculator) { if (internalInstance != null) { throw new InvalidOperationException("Calculator has already been initialised"); } internalInstance = calculator; } public T Calculate(string expression) where T: struct => internalInstance.Calculate(expression); } //then we use it on our code void Main() { var calculator1 = new Calculator(); calculator1.InitialiseCalculator(new DataTableCalculator()); var equation = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34"; Console.WriteLine(calculator1.Calculate(equation)); //139.125490196078 equation = "1 + 2 - 3 + 4"; Console.WriteLine(calculator1.Calculate(equation)); //4 calculator1 = null; System.GC.Collect(); //in reality we'd pretty much never do this, but just to illustrate that our static variable continues fro the life of the app domain rather than the life of the instance var calculator2 = new Calculator(); //calculator2.InitialiseCalculator(new DataTableCalculator()); //uncomment this and you'll get an error; ie the calulator should only be initialised once. equation = "1 + 2 - 3 + 4 / 5 * 6 - 7 / 8 + 9"; Console.WriteLine(calculator2.Calculate(equation)); //12.925 } 

NB: la soluzione sopra riportata utilizza una variabile statica; alcune persone sono contro l’uso della statica. Per questo scenario (cioè dove durante la vita dell’applicazione si richiede solo un modo di fare calcoli) questo è un caso d’uso legittimo. Se si desidera supportare il passaggio della calcolatrice in fase di esecuzione, è necessario un approccio diverso.


Aggiornamento dopo test e confronto

Dopo aver eseguito alcuni test delle prestazioni:

  • Il problema più grande del metodo DataTable.Compute è che per le equazioni la cui dimensione si sta affrontando genera una StackOverflowException ; (cioè basato sul ciclo del generatore di equazioni for (int i = 0; i < 1000000; i++) .
  • Per una singola operazione con un'equazione più piccola ( i < 1000 ), il metodo di calcolo (incluso il costruttore e Convert.ToInt32 sul double risultato) richiede circa 100 volte di più.
  • per la singola operazione ho riscontrato anche eccezioni di overflow più spesso; cioè perché il risultato delle operazioni aveva spinto il valore fuori dai limiti dei tipi di dati supportati ...
  • Anche se spostiamo la chiamata del costruttore / inizializzazione al di fuori dell'area temporizzata e rimuoviamo la conversione in int (e giriamo per migliaia di iterazioni per ottenere una media), la tua soluzione arriva in 3,5 volte più velocemente della mia.

Link ai documenti: https://msdn.microsoft.com/en-us/library/system.data.datatable.compute%28v=vs.110%29.aspx?f=255&MSPPError=-2147217396

Aggiornare

La mia risposta originale era solo un po ‘divertente a tarda notte cercando di mettere questo in unsafe e ho fallito miseramente (in realtà non ha funzionato affatto ed è stato più lento). Comunque ho deciso di dare un altro colpo

La premessa era di rendere tutto in linea, di rimuovere quanto più ansible di IL , mantenere tutto in int o char* e rendere il mio codice carino. Ho ulteriormente ottimizzato questo rimuovendo l’interruttore, Ifs sarà più efficiente in questa situazione, inoltre possiamo ordinarli nel modo più logico. Infine, se rimuoviamo la quantità di controlli per le cose che facciamo e riteniamo che l’input sia corretto, possiamo rimuovere ulteriori overhead semplicemente assumendo cose come; se il char è> '0' deve essere un numero. se è uno spazio possiamo fare dei calcoli, altrimenti deve essere un operatore.

Questo è il mio ultimo tentativo con 10,000,000 calcoli eseguiti 100 volte per ottenere una media, ogni test fa un GC.Collect(); e GC.WaitForPendingFinalizers(); quindi non stiamo frammentando la memoria

risultati

 Test : ms : Cycles (rough) : Increase ------------------------------------------------------------------- OriginalCalc : 1,295 : 4,407,795,584 : MarcEvalNoSubStrings : 241 : 820,660,220 : 437.34%, * 5.32 MarcEvalNoSubStringsUnsafe : 206 : 701,980,373 : 528.64%, * 6.28 MiraiMannCalc1 : 225 : 765,678,062 : 475.55%, * 5.75 MiraiMannCalc2 : 183 : 623,384,924 : 607.65%, * 7.07 MyCalc4 : 156 : 534,190,325 : 730.12%, * 8.30 MyCalc5 : 146 : 496,185,459 : 786.98%, * 8.86 MyCalc6 : 134 : 455,610,410 : 866.41%, * 9.66 

Codice più veloce finora

 unsafe int Calc6(ref string expression) { int res = 0, val = 0, op = 0; var isOp = false; // pin the array fixed (char* p = expression) { // Lets not evaluate this 100 million times var max = p + expression.Length; // lets go straight to the source and just increment the pointer for (var i = p; i < max; i++) { // numbers are the most common thing so lets do a loose // basic check for them and push them in to our val if (*i >= '0') { val = val * 10 + *i - 48; continue; } // The second most common thing are spaces if (*i == ' ') { // not every space we need to calculate if (!(isOp = !isOp)) continue; // In this case 4 ifs are more efficient then a switch // do the calculation, reset out val and jump out if (op == '+') { res += val; val = 0; continue; } if (op == '-') { res -= val; val = 0; continue; } if (op == '*') { res *= val; val = 0; continue; } if (op == '/') { res /= val; val = 0; continue; } // this is just for the first op res = val; val = 0; continue; } // anything else is considered an operator op = *i; } if (op == '+') return res + val; if (op == '-') return res - val; if (op == '*') return res * val; if (op == '/') return res / val; throw new IndexOutOfRangeException(); } } 

Precedente

 unsafe int Calc4(ref string expression) { int res = 0, val = 0, op = 0; var isOp = false; fixed (char* p = expression) { var max = p + expression.Length; for (var i = p; i < max; i++) switch (*i) { case ' ': isOp = !isOp; if (!isOp) continue; switch (op) { case '+': res += val; val = 0; continue; case '-': res -= val; val = 0; continue; case '*': res *= val; val = 0; continue; case '/': res /= val; val = 0; continue; default: res = val; val = 0; continue; } case '+': case '-': case '*': case '/': op = *i; continue; default: val = val * 10 + *i - 48; continue; } switch (op) { case '+': return res + val; case '-': return res - val; case '*': return res * val; case '/': return res / val; default : return -1; } } } 

Come ho misurato i cicli del filo

 static class NativeMethods { public static ulong GetThreadCycles() { ulong cycles; if (!QueryThreadCycleTime(PseudoHandle, out cycles)) throw new System.ComponentModel.Win32Exception(); return cycles; } [DllImport("kernel32.dll", SetLastError = true)] private static extern bool QueryThreadCycleTime(IntPtr hThread, out ulong cycles); private static readonly IntPtr PseudoHandle = (IntPtr)(-2); } 

Post originale

Ho pensato che l'ID cercasse di essere intelligente e di usare fixed: / e massimizzare questo con milioni di calcoli

 public static unsafe int Calc2(string sInput) { var buf = ""; var start = sInput.IndexOf(' '); var value1 = int.Parse(sInput.Substring(0, start)); string op = null; var iResult = 0; var isOp = false; fixed (char* p = sInput) { for (var i = start + 1; i < sInput.Length; i++) { var cur = *(p + i); if (cur == ' ') { if (!isOp) { op = buf; isOp = true; } else { var value2 = int.Parse(buf); switch (op[0]) { case '+': iResult += value1 + value2; break; case '-': iResult += value1 - value2; break; case '*': iResult += value1 * value2; break; case '/': iResult += value1 / value2; break; } value1 = value2; isOp = false; } buf = ""; } else { buf += cur; } } } return iResult; } private static void Main(string[] args) { var input = "14 + 2 * 32 / 60 + 43 - 7 + 3 - 1 + 0 * 7 + 87 - 32 / 34"; var sb = new StringBuilder(); sb.Append(input); for (var i = 0; i < 10000000; i++) sb.Append(" + " + input); var sw = new Stopwatch(); sw.Start(); Calc2(sb.ToString()); sw.Stop(); Console.WriteLine($"sw : {sw.Elapsed:c}"); } 

I risultati sono stati 2 secondi più lenti dell'originale!

Ecco un fatto divertente di Java. Ho implementato la stessa cosa in Java e funziona circa 20 volte più velocemente dell’implementazione di Mirai Mann in C #. Sulla mia macchina, la stringa di input di 100M caratteri ha richiesto circa 353 millisecondi.

Di seguito è riportato il codice che crea e verifica il risultato.

Inoltre, si noti che mentre è un buon tester di prestazioni Java / C # questa non è una soluzione ottimale. Una prestazione migliore può essere ottenuta mediante il multithreading. È ansible calcolare parti della stringa e combinare il risultato.

 public class Test { public static void main(String...args){ new Test().run(); } private void run() { long startTime = System.currentTimeMillis(); Random random = new Random(123); int result = 0; StringBuilder input = new StringBuilder(); input.append(random.nextInt(99) + 1); while (input.length() < 100_000_000){ int value = random.nextInt(100); switch (random.nextInt(4)){ case 0: input.append("-"); result -= value; break; case 1: // + input.append("+"); result += value; break; case 2: input.append("*"); result *= value; break; case 3: input.append("/"); while (value == 0){ value = random.nextInt(100); } result /= value; break; } input.append(value); } String inputData = input.toString(); System.out.println("Test created in " + (System.currentTimeMillis() - startTime)); startTime = System.currentTimeMillis(); int testResult = test(inputData); System.out.println("Completed in " + (System.currentTimeMillis() - startTime)); if(result != testResult){ throw new Error("Oops"); } } private int test(String inputData) { char[] input; try { Field val = String.class.getDeclaredField("value"); val.setAccessible(true); input = (char[]) val.get(inputData); } catch (NoSuchFieldException | IllegalAccessException e) { throw new Error(e); } int result = 0; int startingI = 1; { char c = input[0]; if (c >= '0' && c <= '9') { result += c - '0'; c = input[1]; if (c >= '0' && c <= '9') { result += (c - '0') * 10; startingI++; } } } for (int i = startingI, length = input.length, value=0; i < length; i++) { char operation = input[i]; i++; char c = input[i]; if(c >= '0' && c <= '9'){ value += c - '0'; c = input[i + 1]; if(c >= '0' && c <= '9'){ value = value * 10 + (c - '0'); i++; } } switch (operation){ case '-': result -= value; break; case '+': result += value; break; case '*': result *= value; break; case '/': result /= value; break; } value = 0; } return result; } } 

Quando leggi il codice, puoi vedere che ho usato un piccolo hack per convertire la stringa in un array di caratteri. Ho mutato la stringa per evitare allocazioni di memoria aggiuntive per il char array.