一個a[30000]的陣列,可是其中的10000個位置不要作動作~要如何實現呢? |
尚未結案
|
黑輪
中階會員 發表:135 回覆:188 積分:64 註冊:2004-01-29 發送簡訊給我 |
有一個陣列a[i],i=30000,有3萬筆資料,要做一些動作,可是其中某10000個位置,不要作動,要如何來做呢?
不可能用:
if(i==某特定位置)
{
不要作動;
}
不可能用這樣吧!!因為有10000特定位置啊~不可能寫10000次吧!!! for(int j=0;j<=30000;j )
{
for(int k=0;k<=10000;k ) //c[]儲存不要作動的位置
{
if(a[i]==c[k])
{
不要作動;
}
}
}
也不可能用這樣吧~這樣做完~最多會做到30000*10000次啊~~會花很久的時間~~ 有沒有別的方法啊~~
請教各位前輩~~
感謝各位哦~~
|
taishyang
站務副站長 發表:377 回覆:5490 積分:4563 註冊:2002-10-08 發送簡訊給我 |
黑輪您好:
引言: 有一個陣列a[i],i=30000,有3萬筆資料,要做一些動作,可是其中某10000個位置,不要作動,要如何來做呢? 不可能用:改成上面紅色部分應該就可以了 發表人 -if(i==某特定位置) { 不要作動; } 不可能用這樣吧!!因為有10000特定位置啊~不可能寫10000次吧!!! for(int j=0;j<=30000;j ) { if (j>10000) 做您要做的事(或是改變for迴圈的起始值) /* for(int k=0;k<=10000;k ) //c[]儲存不要作動的位置 { if(a[i]==c[k]) { 不要作動; } }*/ } |
黑輪
中階會員 發表:135 回覆:188 積分:64 註冊:2004-01-29 發送簡訊給我 |
|
shinnuei
一般會員 發表:32 回覆:48 積分:21 註冊:2002-03-13 發送簡訊給我 |
|
JerryKuo
版主 發表:42 回覆:571 積分:322 註冊:2003-03-10 發送簡訊給我 |
引言: 我知道"改變for迴圈的起始值",可是這樣要改變很次,會使程式執行很久, 有沒有什麼方法可以使不要執行的位置,例如a[3]、a[99]、a[2000]...,程式預先知道這些位置不要執行,不要等執行到這些位置才來判別,而是事先把這些位置砍掉~~可以這樣嗎?黑輪你好: 建議是建立同樣大小的布林陣列,決定是否要處理這筆資料: int Array[30000]; bool bArray[30000]; for (i;;) { ... if(bArra[i]) { do it.... } else { undo it.... } .... } 或著,新宣告一個結構(structure),在建立資料就決定是否處理。 typedef struct tArry { int value; bool do; }tData; void main() { tData arry[30000] for (i;;) { ... if(arry[i].do) { do it.... } else { undo it.... } .... } }為了讓程式更容易解讀,發表程式時,請參考版規說明 問題 |
jest0024
高階會員 發表:11 回覆:310 積分:224 註冊:2002-11-24 發送簡訊給我 |
引言: 有一個陣列a[i],i=30000,有3萬筆資料,要做一些動作,可是其中某10000個位置,不要作動,要如何來做呢? 不可能用: if(i==某特定位置) { 不要作動; } 不可能用這樣吧!!因為有10000特定位置啊~不可能寫10000次吧!!! for(int j=0;j<=30000;j ) { for(int k=0;k<=10000;k ) //c[]儲存不要作動的位置 { if(a[i]==c[k]) { 不要作動; } } } 也不可能用這樣吧~這樣做完~最多會做到30000*10000次啊~~會花很久的時間~~ 有沒有別的方法啊~~ 請教各位前輩~~ 感謝各位哦~~for(int k=0;k<=10000;k ) //c[]儲存不要作動的位置 { if(a[i]==c[k]) { 不要作動; } } 這迴圈好像是種循序搜尋,可將c陣列做遞增排序後再用二分搜尋會更快八? |
mkbobo
一般會員 發表:4 回覆:68 積分:19 註冊:2003-04-10 發送簡訊給我 |
您好
假設
1. for(i=0;i<30000;i ) a[i]=?; <== 執行30000次 共三萬次 2. bChk改變點為 10000 個 bChk[i為30000個] 型態為bool for(i=0;i<30000;i ) { if(bChk[i]) <== 執行30000次 a[i]=?; <== 執行10000次 else a[i]=0; <== 執行20000次 } 共六萬次 3. chk改變點為 10000 個 chk[i為10000個] 型態為 int iChk[10000] 儲存所有需要變的點 for(i=0;i<10000;i ) { a[iChk[i]]=?; <== 執行10000次 } 共一萬次發表人 - mkbobo 於 2004/03/22 11:28:07 |
JerryKuo
版主 發表:42 回覆:571 積分:322 註冊:2003-03-10 發送簡訊給我 |
引言: 您好 假設因為黑輪提出的問題是: 有一個陣列a[i],i=30000,有3萬筆資料,要做一些動作,可是其中某10000個 位置,不要作動,要如何來做呢? 第三種方法好像不是使用在這種問題,應該不能這樣比? 如果硬要用第三種方法,就會出現下面的問題,只會增加程式複雜度。 30000x10000 = 300000000次1. for(i=0;i<30000;i ) a[i]=?; <== 執行30000次 共三萬次 2. bChk改變點為 10000 個 bChk[i為30000個] 型態為bool for(i=0;i<30000;i ) { if(bChk[i]) <== 執行30000次 a[i]=?; <== 執行10000次 else a[i]=0; <== 執行20000次 } 共六萬次 3. chk改變點為 10000 個 chk[i為10000個] 型態為 int iChk[10000] 儲存所有需要變的點 for(i=0;i<10000;i ) { a[iChk[i]]=?; <== 執行10000次 } 共一萬次 for(i=0;i<30000;i ) { ...do something.. //因為這3萬次也是要有相同的步驟 boolean bchk = true; //假設一開始是要執行; for(int j=0;j<10000;j ) { if (i == iChk[j]) //查詢是否在不執行的列表中; { bchk = false; //有查詢到,表示不用執行; } } if(bchk) { ...do something } else { don't do something } }^^ |
aquarius
資深會員 發表:3 回覆:347 積分:330 註冊:2003-05-21 發送簡訊給我 |
|
mkbobo
一般會員 發表:4 回覆:68 積分:19 註冊:2003-04-10 發送簡訊給我 |
引言: 第三種方法好像不是使用在這種問題,應該不能這樣比? 如果硬要用第三種方法,就會出現下面的問題,只會增加程式複雜度。 30000x10000 = 300000000次 引言: 若是不要處理的陣列索引是已經知道的, 那麼使用 TList 來記錄要執行的陣列索引即可. 在程式啟動時, 把要處理的索引值加到 TList 中, 然後以後只要從 TList 中取出要動作的值即可. 若在程式中要處理或不處理的陣列索引值會變動, 也只要更新 TList 的內容. 使用 TList 的好處是彈性大, 也容易知道現在有多少個待處理的項目.JerryKuo版主 您好 我寫的第三種方法的意思~~跟aquarius說的是接近的 可能我有些誤導 因為黑輪說的是10000個不動作 但我第三題的例子是20000不動作 只動10000個 以例二 跟例三 來說都是需要前置作業chk陣列設定好 而我覺得這些前置作業一定要做的 我想說的事後來怎麼將減少判斷的資料 就是利用另一個陣列當索引值 a[iChk[i]]=?; iChk[i]就是他的索引值 這樣便會使需要被修改的資料才會被提取出來 做修改 而aquarius所提出的就是實用上比較好的方法 以下綜合aquarius說的的程式碼 ///////////////////////////////// 前置作業 TList *pList = new |
JerryKuo
版主 發表:42 回覆:571 積分:322 註冊:2003-03-10 發送簡訊給我 |
mkbobo你好: 抱歉,小弟無意冒犯,只是看到你的評論,有點疑問。畢竟這只是資料的處理
並不是排序,所以程式的時間複雜度不應該差這麼多。 根據你的計算,當下我只覺得可能有算錯或是用法不同。就問題來說,3萬筆
資料都要執行,基本時間複雜度就已經3萬囉,(怎麼可能變成1萬呢),又因為
其中有1萬筆資料不需要做某些動作,所以我們要知道是哪1萬筆不需要執行
某些動作,一般是加個判斷式if來分要不要執行。如果我們已事先知道有哪
些不需要執行,每個索引值只要花一個時間複雜度判斷,所以這個if判斷式
會加上一倍的時間複雜度。最小時間總複雜度是2x3萬=6萬。就如你所算的。 而你的作法是用另一個陣列(1萬個),紀綠不要做某些動作的索引,一般會認
為這個陣列只要花1萬的時間複雜度去計算,比上面的6萬快了6倍。但其實不
是,因為我們都已經註明不用執行了,所以事實上這一萬個索引是不用執行的
,怎麼會有時間複雜度呢? 如果反過來,我們用另一個陣列去紀錄要執行的兩萬個索引值,我們只會用兩萬
時間複雜度去執行某一段程式,還是比6萬快3倍,想想這樣還是很快,但我們忘
了有一萬筆資料還是要執行某些程式,只是這一萬筆跟那二萬筆資料有一些地
方不用執行,為執行這剩下的一萬筆資料,我們要比照那二萬筆資料一樣,另外
再做一個迴圈執行,還是要執行一萬次,加上之前的時間複雜度總共3萬,還是比
6萬快一倍。如果1萬和2萬筆資料互不相干,這樣做真會比較快,只是程式碼變
多一倍。 想想如果3萬筆資料要分為2萬筆和1萬筆互不相干資料,那當初為何不在建立時,
就分為兩個陣列呢?還要合在一起做什麼,又建立2個陣列去紀錄,是不是多此一
舉?原因不外乎是這3萬筆資料互有關聯,不能獨立處理,互有引用,所以必須合
在一起執行,這樣我們才不會突然要引用對方時,還要去找資料。就像下面程式
一樣,增加更多程式複雜度。 請再多指教
for(int j=0;j<10000;j ) { if (i == iChk[j]) //查詢是否在不執行的列表中; { bchk = false; //有查詢到,表示不用執行; } }^^ |
mkbobo
一般會員 發表:4 回覆:68 積分:19 註冊:2003-04-10 發送簡訊給我 |
|
黑輪
中階會員 發表:135 回覆:188 積分:64 註冊:2004-01-29 發送簡訊給我 |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |