巢狀式迴圈..效率..

2008-04-15

6328
0

巢狀式迴圈..效率..

許多大大一定有寫過..巢狀式迴圈..就是..下面這樣

for (int i = 0; i < 10; i++)
{
  for (int j = 0; j < 10; j++)
  {
      if(oo==xx)
      {
          .....
      }
  }
}

昨天就在寫這方面的class.發現..就算有加入break效率也不怎樣..
就寫了簡單的例子去改寫一下程式..把巢狀式迴圈..變成只有一層..

巢狀式

Stopwatch watch = new Stopwatch();
int count = 0;
List<int> nu = new List<int>();
List<int> nu1 = new List<int>();

for (int i = 0; i < 10000; i++)
{
  nu.Add(i);
}
for (int j = 0; j < 10000; j++)
{
  nu1.Add(j);
}

watch.Start();
foreach (int a in nu)
{
  foreach (int b in nu1)
  {
      if (a == b)
      {
          count++;
      }
  }
}
watch.Stop();

Response.Write(watch.ElapsedMilliseconds / 1000f + "<br />");
Response.Write(count);

單迴圈

Stopwatch watch = new Stopwatch();
int count = 0;
List<int> nu = new List<int>();
List<int> nu1 = new List<int>();

for (int i = 0; i < 10000; i++)
{
  nu.Add(i);
}
for (int j = 0; j < 10000; j++)
{
  nu1.Add(j);
}

watch.Start();
foreach (int a in nu)
{
  if (nu1.Contains(a))
  {
      count++;
  }
}
watch.Stop();

Response.Write(watch.ElapsedMilliseconds / 1000f +"<br />");
Response.Write(count);

結果..上面的測試..
巢狀式:平均1.35秒
單層式:平均0.46秒

上面兩個例子效果其實是一樣的..我把巢狀式改成單迴圈..然後用contains來代替..
查一下.net framework的contains的method..

bool IList.Contains(object value)
{
  return (IndexOf(this, value) >= this.GetLowerBound(0));
}

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public static int IndexOf(Array array, object value)
{
  if (array == null)
  {
      throw new ArgumentNullException("array");
  }
  int lowerBound = array.GetLowerBound(0);
  return IndexOf(array, value, lowerBound, array.Length);
}

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public static int IndexOf(Array array, object value, int startIndex, int count)
{
  int num2;
  if (array == null)
  {
      throw new ArgumentNullException("array");
  }
  int lowerBound = array.GetLowerBound(0);
  if ((startIndex < lowerBound) || (startIndex > (array.Length + lowerBound)))
  {
      throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  }
  if ((count < 0) || (count > ((array.Length - startIndex) + lowerBound)))
  {
      throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  }
  if (array.Rank != 1)
  {
      throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
  }
  if (TrySZIndexOf(array, startIndex, count, value, out num2))
  {
      return num2;
  }
  object[] objArray = array as object[];
  int num3 = startIndex + count;
  if (objArray != null)
  {
      if (value == null)
      {
          for (int i = startIndex; i < num3; i++)
          {
              if (objArray[i] == null)
              {
                  return i;
              }
          }
      }
      else
      {
          for (int j = startIndex; j < num3; j++)
          {
              object obj2 = objArray[j];
              if ((obj2 != null) && obj2.Equals(value))
              {
                  return j;
              }
          }
      }
  }
  else
  {
      for (int k = startIndex; k < num3; k++)
      {
          object obj3 = array.GetValue(k);
          if (obj3 == null)
          {
              if (value == null)
              {
                  return k;
              }
          }
          else if (obj3.Equals(value))
          {
              return k;
          }
      }
  }
  return (lowerBound - 1);
}

看起來也是要跑迴圈也沒有比直接if else簡單多少..可是效率好很多.. Dont tell anyone

..
所以個人的猜測就是.net framework一定有偷偷最佳化過啦.. Hot

..
還有在javascript也是一樣的情形..用巢狀式的效率也低於單層式的..

ps:小弟只是已微薄的知識去猜測的..各位大大如果不同的觀念..請給小弟多多指教..^^..

回首頁