全國最多中醫師線上諮詢網站-台灣中醫網
發文 回覆 瀏覽次數:867
推到 Plurk!
推到 Facebook!

一個a[30000]的陣列,可是其中的10000個位置不要作動作~要如何實現呢?

尚未結案
黑輪
中階會員


發表:135
回覆:188
積分:64
註冊:2004-01-29

發送簡訊給我
#1 引用回覆 回覆 發表時間:2004-03-13 18:11:45 IP:140.124.xxx.xxx 未訂閱
有一個陣列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

發送簡訊給我
#2 引用回覆 回覆 發表時間:2004-03-13 18:38:18 IP:61.231.xxx.xxx 未訂閱
黑輪您好:
引言: 有一個陣列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

發送簡訊給我
#3 引用回覆 回覆 發表時間:2004-03-15 07:57:10 IP:140.124.xxx.xxx 未訂閱
我知道"改變for迴圈的起始值",可是這樣要改變很次,會使程式執行很久, 有沒有什麼方法可以使不要執行的位置,例如a[3]、a[99]、a[2000]...,程式預先知道這些位置不要執行,不要等執行到這些位置才來判別,而是事先把這些位置砍掉~~可以這樣嗎?
shinnuei
一般會員


發表:32
回覆:48
積分:21
註冊:2002-03-13

發送簡訊給我
#4 引用回覆 回覆 發表時間:2004-03-15 13:25:40 IP:61.221.xxx.xxx 未訂閱
你可以另外開一個陣列,把要執行的都放進去,就可以去處理這個陣列了.
JerryKuo
版主


發表:42
回覆:571
積分:322
註冊:2003-03-10

發送簡訊給我
#5 引用回覆 回覆 發表時間:2004-03-15 15:37:20 IP:61.230.xxx.xxx 未訂閱
引言: 我知道"改變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

發送簡訊給我
#6 引用回覆 回覆 發表時間:2004-03-22 01:28:34 IP:210.66.xxx.xxx 未訂閱
引言: 有一個陣列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

發送簡訊給我
#7 引用回覆 回覆 發表時間:2004-03-22 11:24:08 IP:61.222.xxx.xxx 未訂閱
您好 假設 
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

發送簡訊給我
#8 引用回覆 回覆 發表時間:2004-03-22 14:25:02 IP:61.230.xxx.xxx 未訂閱
引言: 您好 假設
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次
}
共一萬次    
因為黑輪提出的問題是: 有一個陣列a[i],i=30000,有3萬筆資料,要做一些動作,可是其中某10000個 位置,不要作動,要如何來做呢? 第三種方法好像不是使用在這種問題,應該不能這樣比? 如果硬要用第三種方法,就會出現下面的問題,只會增加程式複雜度。 30000x10000 = 300000000次
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

發送簡訊給我
#9 引用回覆 回覆 發表時間:2004-03-22 14:29:06 IP:211.23.xxx.xxx 未訂閱
若是不要處理的陣列索引是已經知道的, 那麼使用 TList 來記錄要執行的陣列索引即可. 在程式啟動時, 把要處理的索引值加到 TList 中, 然後以後只要從 TList 中取出要動作的值即可. 若在程式中要處理或不處理的陣列索引值會變動, 也只要更新 TList 的內容. 使用 TList 的好處是彈性大, 也容易知道現在有多少個待處理的項目. ...Aquarius
------
水瓶男的blog: http://791909.blogspot.com
mkbobo
一般會員


發表:4
回覆:68
積分:19
註冊:2003-04-10

發送簡訊給我
#10 引用回覆 回覆 發表時間:2004-03-23 00:47:05 IP:61.229.xxx.xxx 未訂閱
引言: 第三種方法好像不是使用在這種問題,應該不能這樣比? 如果硬要用第三種方法,就會出現下面的問題,只會增加程式複雜度。 30000x10000 = 300000000次
引言: 若是不要處理的陣列索引是已經知道的, 那麼使用 TList 來記錄要執行的陣列索引即可. 在程式啟動時, 把要處理的索引值加到 TList 中, 然後以後只要從 TList 中取出要動作的值即可. 若在程式中要處理或不處理的陣列索引值會變動, 也只要更新 TList 的內容. 使用 TList 的好處是彈性大, 也容易知道現在有多少個待處理的項目.
JerryKuo版主 您好 我寫的第三種方法的意思~~跟aquarius說的是接近的 可能我有些誤導 因為黑輪說的是10000個不動作 但我第三題的例子是20000不動作 只動10000個 以例二 跟例三 來說都是需要前置作業chk陣列設定好 而我覺得這些前置作業一定要做的 我想說的事後來怎麼將減少判斷的資料 就是利用另一個陣列當索引值 a[iChk[i]]=?; iChk[i]就是他的索引值 這樣便會使需要被修改的資料才會被提取出來 做修改 而aquarius所提出的就是實用上比較好的方法
以下綜合aquarius說的的程式碼
/////////////////////////////////
前置作業
TList *pList = new ();
if(某判斷成立)
    pList->Add(需要加入的索引值);
/////////////////////////////////    for(i=0;iCount;i  )
{
    a[pList->Items[i]] 利用pList->Items[i]將要改變的資料提取出來;
}    
JerryKuo
版主


發表:42
回覆:571
積分:322
註冊:2003-03-10

發送簡訊給我
#11 引用回覆 回覆 發表時間:2004-03-23 14:51:39 IP:61.230.xxx.xxx 未訂閱
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

發送簡訊給我
#12 引用回覆 回覆 發表時間:2004-03-23 16:32:52 IP:61.222.xxx.xxx 未訂閱
JerryKuo版主 您好 我想了又想 可能是我想的太單純了 如果只要動到兩萬筆 哪就是將兩萬筆的索引值紀錄下來 跑一個兩萬筆的迴圈 就可以將所有要動作的資料改變了    不需要跑到三萬筆資料 然後在判斷是否需要改變    我順便將我的上面的文章做一些修改 就這樣拉 我想我還是說我的想法跟 Aquarius是一樣的 可能是我看不清題意吧 請見諒
黑輪
中階會員


發表:135
回覆:188
積分:64
註冊:2004-01-29

發送簡訊給我
#13 引用回覆 回覆 發表時間:2004-03-25 17:49:47 IP:140.124.xxx.xxx 未訂閱
不好意思哦~~回去南部好幾天了~都沒上網 這麼久才回~~ 我來試試~感謝大家哦~
系統時間:2024-05-18 20:30:27
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!