星期二, 4月 15, 2008

巢狀式迴圈..效率..

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

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:小弟只是已微薄的知識去猜測的..各位大大如果不同的觀念..請給小弟多多指教..^^..

2 則留言:

匿名 提到...

不好意思, 我在blueshop 問過問題, 怕你看不到...所以借空位post在這裡.

因為我不知道接受答案之後, 就會自動關帖 XD
所以只好直接找你.
我按你的方法做了, 但還是有別的問題.
以下是修改後的code.

function LoadSpare(combo, eventargs) { <--
var countriesCombot = Content1($find("RadComboBox2"));
var itemt = Content1(eventargs.get_item());
var countriesCombo = countriesCombot;
var item = itemt;
(下略...)
}
但現在在runtime 出現的error為"必需要有物件" (被指的那行)
可能我沒有寫... 其實這個js是當我選擇combobox的item 之後, 就
會call 這個js. 而call的方法只是在combobox中,
加上 OnClientSelectedIndexChanging="LoadSpare"
所以我自己根本不會pass入value...
想問一下有什麼方法解決?
可以的話, 可以加個msn 嗎, 這樣討論比較方便.
我的msn為: paymok@hotmail.com
先再一次多謝你為我解答問題...

Bibby 提到...

function LoadSpare(combo, eventargs)
combo跟eventargs這兩個參數~你從哪來低阿~"必需要有物件"表示跟找不到這東東阿~你先搞清楚那兩個東西你怎寫的


還有如果你是用我低方法去做的話..你這行因該改成var countriesCombot = $find(ContentPlaceHolder1("RadComboBox2"));
才可以跑ㄅ..你在仔細看一下我的文章ㄟ..

這樣才對..試試ㄅ..