优化表达式评价挑战
优化表达式评价挑战
提问于 2013-03-28 20:06:30
我试图用6个数字数组和所有基本运算符(+-*/)来计算总价值。
假设你有: 1，2，3，4，5，6，而你想拥有10。
下面是我的函数调用结果的一部分：
10 =4- (2 - (5 + 6) + (3 * 1)) 10 =( (6 - 4) - 1) - (2 - 3) *5 10 =(2*3)- ((1 + (5 -4)-6) : 10 =3- (5 -(6* 2)) 10 = (3 - 2) *(1**( 5) *(6-4) 10 = (4 + (6 + 3)) -(5+ 1) / 2)解决方案数量= 252676 3/28/201312:28:25 PM 3/28/201312:28:44 PM 00:00:19.7425257
我的老四CPU Q8200 2.33Ghz花了19秒钟才处理了105164223可能的表达式。我将所有可能的表达式放入Hashtable中。最后，我打印所有的有效表达式。应该有办法加快这一进程。
我试着把所有的结果都放在一个文件里，比如：(C )* ((A * E) * (F ))
在此之后，我处理文件并将字母更改为正确的编号。但是这个文件的大小约为2GB，只需35秒就可以读取该文件，而不会有任何进展。
我想听听你对密码的意见。我能加速这段代码吗？我们如何加快进程，可能是:(并行、任务、异步/等待等)。)这一切我都不习惯。
对于计算，你有其他的想法吗，比如把所有的方程放在一个表格中(比如：(C )* ((A * E) *( and )并处理这个表。
using System;
using System.Collections;
/// <summary>
/// Class to Find all the possible value to reach a number
///from an number array with the basic operators
/// </summary>
class PossibleExpression
{
public DateTime mStartDateTime;
public DateTime mEndDateTime;
public TimeSpan mTimeSpan;
// all the solutions are stored in an Hachtable
public Hashtable mSolutionHashtable = new Hashtable();
// NbEvaluate
public int mNbEvaluate = 0;
// calculate the AbsValue, if we are not able to reach the total, we kept the nearest total
public int mAbsValue = int.MaxValue;
public PossibleExpression()
{
}
/// <summary>
/// Evaluate all the possibility to reach the total with this numbers
/// </summary>
/// <param name="Numbers"></param>
/// <param name="total"></param>
private void Evaluate(Number[] Numbers, int total)
{
mNbEvaluate++;
if (Numbers.Length == 1)
{
int absValue = Math.Abs(Numbers[0].Value - total);
// if the abolute value is less then the one before
if (absValue < mAbsValue)
{
mAbsValue = absValue;
}
// if it was the right absolute value store the ValueString and the Value in the SolutionHashtable
if (mAbsValue == absValue)
{
string valueString = Numbers[0].ValueString.ToString();
if (mSolutionHashtable.ContainsKey(valueString) == false)
{
mSolutionHashtable.Add(valueString, Numbers[0].Value);
}
}
}
else
{
{
// we prepare to call back the function with a smaller array size
Number[] NextNumbers = new Number[Numbers.Length - 1];
{
// allocate Number for this new array
int i = 0;
while (i < NextNumbers.Length)
{
NextNumbers[i] = new Number();
i++;
}
}
// get the right Mix Array
int[][] Mix = AllMix[Numbers.Length];
// for all the possible Mix
int indexMixOperand = 0;
while (indexMixOperand < Mix.Length)
{
// copy all the numbers that was not in the Mix index
if ((Numbers.Length - 1 > 1))
{
int indexNextNumbers = 1; // we kept the index 0 for the Mix result
int i = 0;
while (i < Numbers.Length)
{
if ((i != Mix[indexMixOperand][0])
&& (i != Mix[indexMixOperand][1]))
{
NextNumbers[indexNextNumbers++] = Numbers[i];
}
i++;
}
}
// for all the operators
for (int indexOperator = 0; indexOperator < 4; indexOperator++)
{
// set the number 0 to the total of the expression composed of this two number and operator
if (NextNumbers[0].Set(Numbers[Mix[indexMixOperand][0]], Numbers[Mix[indexMixOperand][1]], indexOperator) == true)
{
// call to evaluate
Evaluate(NextNumbers, total);
}
//next operator
}
// next MixPermutation
indexMixOperand++;
}
}
}
}
public bool Find(int[] numbers, int total)
{
if( numbers.Length == 6)
{
mStartDateTime = DateTime.Now;
mSolutionHashtable = new Hashtable();
mNbEvaluate = 0;
mAbsValue = int.MaxValue;
Number[] Numbers = new Number[6];
Numbers[0] = new Number();
Numbers[1] = new Number();
Numbers[2] = new Number();
Numbers[3] = new Number();
Numbers[4] = new Number();
Numbers[5] = new Number();
Numbers[0].Set(numbers[0]);
Numbers[1].Set(numbers[1]);
Numbers[2].Set(numbers[2]);
Numbers[3].Set(numbers[3]);
Numbers[4].Set(numbers[4]);
Numbers[5].Set(numbers[5]);
foreach (int[] index in m_Index)
{
Number[] CurrentNumbers = new Number[index.Length];
for (int i = 0; i < index.Length; i++)
{
CurrentNumbers[i] = Numbers[index[i]];
}
Evaluate(CurrentNumbers, total);
}
mEndDateTime = DateTime.Now;
mTimeSpan = mEndDateTime - mStartDateTime;
}
return (numbers.Length == 6);
}
// possible index for indirection table
static private int[][] m_Index = new int[][]
{
// with one number
new int[] {0},
new int[] {1},
new int[] {2},
new int[] {3},
new int[] {4},
new int[] {5},
// with two numbers
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {0,4},
new int[] {0,5},
new int[] {1,2},
new int[] {1,3},
new int[] {1,4},
new int[] {1,5},
new int[] {2,3},
new int[] {2,4},
new int[] {2,5},
new int[] {3,4},
new int[] {3,5},
new int[] {4,5},
// with three numbers
new int[] {0,1,2},
new int[] {0,1,3},
new int[] {0,1,4},
new int[] {0,1,5},
new int[] {0,2,3},
new int[] {0,2,4},
new int[] {0,2,5},
new int[] {0,3,4},
new int[] {0,3,5},
new int[] {0,4,5},
new int[] {1,2,3},
new int[] {1,2,4},
new int[] {1,2,5},
new int[] {1,3,4},
new int[] {1,3,5},
new int[] {1,4,5},
new int[] {2,3,4},
new int[] {2,3,5},
new int[] {2,4,5},
new int[] {3,4,5},
// with four numbers
new int[] {0,1,2,3},
new int[] {0,1,2,4},
new int[] {0,1,2,5},
new int[] {0,1,3,4},
new int[] {0,1,3,5},
new int[] {0,1,4,5},
new int[] {0,2,3,4},
new int[] {0,2,3,5},
new int[] {0,2,4,5},
new int[] {0,3,4,5},
new int[] {1,2,3,4},
new int[] {1,2,3,5},
new int[] {1,2,4,5},
new int[] {1,3,4,5},
new int[] {2,3,4,5},
// with five numbers
new int[] {0,1,2,3,4},
new int[] {0,1,2,3,5},
new int[] {0,1,2,4,5},
new int[] {0,1,3,4,5},
new int[] {0,2,3,4,5},
new int[] {1,2,3,4,5},
// with six numbers
new int[] {0,1,2,3,4,5},
};
static private int[][] Mix0 = new int[][]
{
};
static private int[][] Mix1 = new int[][]
{
};
static private int[][] Mix2 = new int[][]
{
new int[] {0,1},
new int[] {1,0}
};
static private int[][] Mix3 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {1,0},
new int[] {1,2},
new int[] {2,0},
new int[] {2,1}
};
static private int[][] Mix4 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {1,0},
new int[] {1,2},
new int[] {1,3},
new int[] {2,0},
new int[] {2,1},
new int[] {2,3},
new int[] {3,0},
new int[] {3,1},
new int[] {3,2}
};
static private int[][] Mix5 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {0,4},
new int[] {1,0},
new int[] {1,2},
new int[] {1,3},
new int[] {1,4},
new int[] {2,0},
new int[] {2,1},
new int[] {2,3},
new int[] {2,4},
new int[] {3,0},
new int[] {3,1},
new int[] {3,2},
new int[] {3,4},
new int[] {4,0},
new int[] {4,1},
new int[] {4,2},
new int[] {4,3}
};
static private int[][] Mix6 = new int[][]
{
new int[] {0,1},
new int[] {0,2},
new int[] {0,3},
new int[] {0,4},
new int[] {0,5},
new int[] {1,0},
new int[] {1,2},
new int[] {1,3},
new int[] {1,4},
new int[] {1,5},
new int[] {2,0},
new int[] {2,1},
new int[] {2,3},
new int[] {2,4},
new int[] {2,5},
new int[] {3,0},
new int[] {3,1},
new int[] {3,2},
new int[] {3,4},
new int[] {3,5},
new int[] {4,0},
new int[] {4,1},
new int[] {4,2},
new int[] {4,3},
new int[] {4,5},
new int[] {5,0},
new int[] {5,1},
new int[] {5,2},
new int[] {5,3},
new int[] {5,4}
};
static private int[][][] AllMix = { Mix0, Mix1, Mix2, Mix3, Mix4, Mix5, Mix6 };
using System.Text;
/// <summary>
/// allways have the value and the Value in String format
/// </summary>
public class Number
{
// the int value
public int Value = 0;
// the string value
public StringBuilder ValueString = new StringBuilder(40);
// the operator
public int m_Operator = -1;
/// <summary>
/// Set the value
/// </summary>
/// <param name="value"></param>
public void Set(int value)
{
Value = value;
ValueString.Clear();
ValueString.Append(value);
}
/// <summary>
/// Build the Value String depending on the operand and the operator
/// </summary>
/// <param name="Operande1"></param>
/// <param name="Operande2"></param>
/// <param name="Operator"></param>
private void BuildValueString(Number Operande1, Number Operande2, int Operator)
{
ValueString.Clear();
// int Operande1OperatorFamily = Operande1.m_Operator / 2;
// int Operande2OperatorFamily = Operande2.m_Operator / 2;
// int OperatorFamily = Operator / 2;
if ((Operande1.m_Operator != -1)
// && ( (Operande1OperatorFamily != OperatorFamily)
// || (Operator == 1)
// || (Operator == 2)
// || (Operator == 3)
// )
)
{
ValueString.Append("(");
}
ValueString.Append(Operande1.ValueString);
if ((Operande1.m_Operator != -1)
// && ((Operande1OperatorFamily != OperatorFamily)
// || (Operator == 1)
// || (Operator == 2)
// || (Operator == 3)
// )
)
{
ValueString.Append(")");
}
switch (Operator)
{
case 0:
ValueString.Append(" + ");
break;
case 1:
ValueString.Append(" - ");
break;
case 2:
ValueString.Append(" * ");
break;
case 3:
ValueString.Append(" / ");
break;
}
if ((Operande2.m_Operator != -1)
// && ( (Operande2OperatorFamily != OperatorFamily)
// || (Operator == 1)
// || (Operator == 2)
// || (Operator == 3)
// )
)
{
ValueString.Append("(");
}
ValueString.Append(Operande2.ValueString);
if ((Operande2.m_Operator != -1)
// && ((Operande2OperatorFamily != OperatorFamily)
// || (Operator == 1)
// || (Operator == 2)
// || (Operator == 3)
// )
)
{
ValueString.Append(")");
}
}
/// <summary>
/// Set the number for these operands and operator
/// </summary>
/// <param name="Operande1"></param>
/// <param name="Operande2"></param>
/// <param name="Operator"></param>
/// <returns></returns>
public bool Set(Number Operande1, Number Operande2, int Operator)
{
bool returnValue = true;
m_Operator = Operator;
Value = Operande1.Value;
switch (Operator)
{
case 0:
Value += Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case 1:
Value -= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case 2:
Value *= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case 3:
if ((Operande2.Value != 0)
&& (Value % Operande2.Value) == 0)
{
Value /= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
}
else
{
returnValue = false;
}
break;
}
return returnValue;
}
}
}回答 1
Code Review用户
发布于 2013-03-28 20:49:17
我将评论代码的C#ness，然后我们就可以考虑逻辑了。
总的来说，还不错。我喜欢机壳和空白。
不过，我看到了一些需要改进的地方：
- 在C#中，类级成员的一般标准是以_作为前缀。即
_solutionHasTable，或者如果您喜欢m_solutionHasTable。关于哪一个更好，大家都在讨论，我让你决定。 - 不需要包含空的默认构造函数。如果没有声明，C#将添加它。
- 在声明明显的变量时使用var。var是强类型的，使用它只会消除代码中不必要的杂乱。即
var absValue = Math.Abs(Numbers[0].Value - total); - 总的来说，我认为你的方法太长了，而且试图做的太多了。最优情况下，整个方法应该安装在一个屏幕上。如果没有，则将其重构为更小的函数。这对#5也有帮助。
- 我想代码已经过时了。像
// for all the operators或// call to evaluate这样的评论只是在重复我在代码中可以读到的内容。应该保存注释来描述为什么要做某件事，或者是为了增强代码，而不是解释它正在做什么。好的代码解释了它在做什么。 - 魔法数字太多了。使用
private const int MeaningOfNumber = 1代替。 foreach是一个比for (var i=0;i<4;i++)更容易使用的循环结构。你应该调查一下- m_Index不是C#的正确命名约定。我想我们可以找到一个更好的名字。
- 同样，m_Index中的操作可以使用循环和常量(或app.confg文件中的一个值)来完成。这样，如果将来数字发生变化，您可以在一个地方更改它，然后程序继续运行。
- 如果可以的话，可以使用枚举。您的操作符应该是enum，这将使switch语句更易于阅读：
switch (Operator)
{
case Operator.Add:
Value += Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case Operator.Subtract:
Value -= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case Operator.Multiple:
Value *= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
break;
case Operator.Divide:
if ((Operande2.Value != 0)
&& (Value % Operande2.Value) == 0)
{
Value /= Operande2.Value;
BuildValueString(Operande1, Operande2, Operator);
}
else
{
returnValue = false;
}
break;
}页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/24485
复制相关文章
相似问题
腾讯云开发者
