一萬筆以上資料，排序 + 搜尋 |
|
尚未結案
|
|
clarkkent
初階會員   發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
各位先進好
不好意思又來打擾各位了 以下為小弟遭遇的問題
有一連續座標資料(例如：X=0~320,Y=0~240)，稱為A
每一點(X,Y)經過一些運算會得到一些未經排序的數據，稱為B
若將這些資料排序後，稱為C 我現在做到的是
開一個FILE 將B存成1.txt
然後再用 RaynorPao大哥 的氣泡排序法去排序，將C存成2.txt
......後續還沒有做完，因為這樣就花了好久好久 問題來了
假若我要取C中的前100筆，且要知道其原始座標資料
那麼我該如何下手呢？
可否不需要存成.txt檔再排序、搜尋呢？
或者各位大大有較為精簡的流程？ 新手上路，請多指教 如果此文章違反版規
還請版主告知並刪除
Just do it 發表人 - clarkkent 於 2003/04/08 21:38:32
------
JUST DO IT |
|
taishyang
站務副站長  發表：377 回覆：5490 積分：4563 註冊：2002-10-08 發送簡訊給我 |
|
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
感謝各位大大的回應 小弟所要的結果就如同上述所說明的，不好意思可能沒有說明白
我再補充一下 我要針對一張灰階256色(320x240)的圖做處理
首先會先設定一個範圍(最大就是跟圖一樣大，這樣就有76800點嘍！)
再針對範圍內的每一個點做一些數值上的處理
亦即每個點會得到一個處理後的值(大小當然不盡相同啦！) 我想把處理後比較大的值，該點座標再畫回圖去
所以必需先知道那個點算出來的值較大(可能選前100筆左右...還不確定)
才能畫回去 不知道我這樣表達可以嗎？
還煩請各位大大多多指教
PS.一、資料庫我沒有接觸過，這樣的例子需要用到它嗎？
二、我是想要以速度為優先，當然不存成.txt再叫出也是可以的
因為我這個死腦筋，我只會這樣
------
JUST DO IT |
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
|
|
dan59314
中階會員 發表：121 回覆：107 積分：86 註冊：2002-08-16 發送簡訊給我 |
|
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
1.驗證資料的正確性在 Console 模式下（就是 DOS 的畫面啦），你可以寫一個迴圈，用 printf 的方式把他列出來看，如果有 FORM 的話則可以拉一個 memo 或是 任何一個表格元件來用。 2.當然是資料庫會比較快，而且可以要求資料庫幫你依某個欄位排序，但是如果資料量很小的話，用 TXT 來輸出就可以了省得開啟資料庫的時間和麻煩。 其實 TXT 輸出也不是完全沒有好處，很多資料庫在作資料交換的時候，都會先輸出 TXT 再行轉換，所以 TXT 的自由度比較高，而且攜帶又方便，如果是資料庫的話可能還要裝一些介面程式才能用。 你前一篇文章有提到排序的方法我幫你試了一下： 你可以用基本函數庫提供的快速搜尋排序法來作： #include
|
|
brant
一般會員  發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
如果您算出來的 B 的 data type 是整數型態
有些偷雞的排序演算法的 time complexity 是 O(n) ex: bucket sort
不過這些 tricky 的演算法，要找演算法的書，一般 data structure 的書不會有。
參考一下，或許會對您有幫助。
ps:dan59314所提的方法也是O(n)的一種，叫Counting sort，如果B值的range在0~255之間，那這個方法應該是最好的方法。 我的回答只給一個方向，剩下的就靠你自己了!!!
～～不喜歡大大來大大去的，沒事不要往我臉上塗奶油～～ 發表人 - brant 於 2003/04/09 11:33:03 發表人 - brant 於 2003/04/09 11:57:18
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
再次感謝各位先進的協助 看了各位所提供的方法，小弟都會去試試的！ 題外話：
我運算結果的數值資料是小數點後面19位數且有正負
這樣子用qsort要改那邊呢？(我剛才將int 改成 float無法執行) 另外對於dan59314大哥所建議的方法
可以舉個範例嗎？
雖然說可能不適用(因為是要整數值嗎？而我的是小數)，但還是想長知識！
我找到了介紹Counting Sort的網頁，但……
------
JUST DO IT |
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
引言: 上面 Post 的那篇，刮號裡面的東西被刪掉了 ... 首先你要在開頭 #include 以下三個檔 stdlib.h stdio.h string.h 然後將 printf("%s\n", list[x]); 改成 printf("%f\n", list[x]);謝謝您的回應，我寫了以下的程式，但無法執行 include三個檔，我有加 float sort_function( const void *a, const void *b); //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- void __fastcall TForm1::Button1Click(TObject *Sender) { float list[5] = { 3.0,-1.5,7.7,1.51,8.1 }; qsort((void *)list, 5, sizeof(list[0]), sort_function); for (int x = 0; x < 5; x ) Memo1->Lines->Add(list[x]); } //--------------------------------------------------------------------------- float sort_function( const void *a, const void *b) { return( strcmp((char *)a,(char *)b) ); } //--------------------------------------------------------------------------- 是哪兒需要改呢？謝謝您 新手上路，請多指教 如果此文章違反版規 還請版主告知並刪除 Just do it
------
JUST DO IT |
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
給你一個 sample code ，比 float 用 strcmp 去比也許會容易讓人搞不清楚：
小數點以下19位，用 long double 一定夠了吧...
|
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
請修改紅色的地方，int 是固定的傳入值請勿修改！ int sort_function( const void *a, const void *b);
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//--------------------------------------------------------------------------- void __fastcall TForm1::Button1Click(TObject *Sender)
{
float list[5] = { 3.0,-1.5,7.7,1.51,8.1 };
qsort((void *)list, 5, sizeof(list[0]), sort_function);
for (int x = 0; x < 5; x )
Memo1->Lines->Add(list[x]); }
//---------------------------------------------------------------------------
int sort_function( const void *a, const void *b)
{
return( strcmp((char *)a,(char *)b) );
}
//---------------------------------------------------------------------------
|
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
|
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
|
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
|
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
|
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
引言:謝謝您的回應 那這樣子有辦法得到最原始的座標位置嗎？排序完都亂了！ 雖然說小數十九位數要一樣是很難的 新手上路，請多指教 如果此文章違反版規 還請版主告知並刪除 Just do it引言: 各位先進討論真是熱烈 小弟突然想到 qsort是穩定還是不穩定排序呢？ 謝謝您 新手上路，請多指教 如果此文章違反版規 還請版主告知並刪除 Just do itqsort 是 unstable sorting [blue]我的回答只給一個方向，剩下的就靠你自己了!!! ～～不喜歡大大來大大去的，沒事不要往我臉上塗奶油～～
------
JUST DO IT |
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
|
|
China Join
中階會員 發表：81 回覆：242 積分：89 註冊：2003-03-12 發送簡訊給我 |
|
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
引言: 謝謝您的回應 那這樣子有辦法得到最原始的座標位置嗎？排序完都亂了！ 雖然說小數十九位數要一樣是很難的 新手上路，請多指教 如果此文章違反版規 還請版主告知並刪除 Just do it您可以用一個 structure 來存放計算完的值跟座標 在 qsort 的第三個參數傳入整個 structure 的大小 qsort 會依據第三個參數的大小來搬動資料 在 compare 的函式裡面把傳入的指標轉型為此 structure 依據裡面的值比較後回傳大於0，小於0或是等於0 不用理會 structure 裡的座標值 這樣就可以連同座標值一起 sort 了。 我的回答只給一個方向，剩下的就靠你自己了!!! ～～不喜歡大大來大大去的，沒事不要往我臉上塗奶油～～ |
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
|
|
dan59314
中階會員 發表：121 回覆：107 積分：86 註冊：2002-08-16 發送簡訊給我 |
Counting Sort 假設有 123.21 , 3.32, 6.43, 5.12, 3242.32, 322.23 共六個資料，其中3242.32 最大，因此可以配置維度 324232 的陣列:
ary:Array [0..324232] of double; 然後， ary[12321]=123.21,
ary[332]=3.32,
ary[643]=6.43........就完成排序了。 也可以用tolerance 作粗排序，配置二維陣列，然後再逐一針對第二維作細排序。
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
|
|
clarkkent
初階會員 發表：29 回覆：83 積分：32 註冊：2003-01-23 發送簡訊給我 |
引言: Counting Sort 假設有 123.21 , 3.32, 6.43, 5.12, 3242.32, 322.23 共六個資料，其中3242.32 最大，因此可以配置維度 324232 的陣列: ary:Array [0..324232] of double; 然後， ary[12321]=123.21, ary[332]=3.32, ary[643]=6.43........就完成排序了。 也可以用tolerance 作粗排序，配置二維陣列，然後再逐一針對第二維作細排序。感謝您的回應 請教您， 如果數據資料太大(例如20位數< >) 有負值< > 有相同值
------
JUST DO IT |
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
引言: Counting Sort 假設有 123.21 , 3.32, 6.43, 5.12, 3242.32, 322.23 共六個資料，其中3242.32 最大，因此可以配置維度 324232 的陣列: ary:Array [0..324232] of double; 然後， ary[12321]=123.21, ary[332]=3.32, ary[643]=6.43........就完成排序了。 也可以用tolerance 作粗排序，配置二維陣列，然後再逐一針對第二維作細排序。紅色的部份屬於 bucket sort 的做法了。 有相同值的話，可用 array of pointer 的做法，指向同值的一個 link list 需要的話記錄其 list item 的個數，負值就要想對應的方式。 但是 counting sort 若是維度太大，資料分佈又不平均的話 會造成非常大的浪費，其中的 trade off 就要去評估了。 我的回答只給一個方向，剩下的就靠你自己了!!! ～～不喜歡大大來大大去的，沒事不要往我臉上塗奶油～～ 發表人 - brant 於 2003/04/10 10:10:44 |
|
brant
一般會員 發表：1 回覆：64 積分：23 註冊：2003-04-07 發送簡訊給我 |
|
|
Cafia
一般會員 發表：6 回覆：12 積分：3 註冊：2003-03-17 發送簡訊給我 |
引言: 您可以用一個 structure 來存放計算完的值跟座標 在 qsort 的第三個參數傳入整個 structure 的大小 qsort 會依據第三個參數的大小來搬動資料 在 compare 的函式裡面把傳入的指標轉型為此 structure 依據裡面的值比較後回傳大於0，小於0或是等於0 不用理會 structure 裡的座標值 這樣就可以連同座標值一起 sort看了各位的討論..有個問題想請教一下 如brant所說的..若是以structure為傳入值 能否使compare根據structure內的某個陣列的某欄來排序 譬如
struct test{
int dir[3];
};
如果要以dir[i]的值來排序.而這個i值希望是可以變動的
這樣做的到嗎？ 謝謝指教～～
|
發表時間：2003-04-08 21:37:06
IP:61.59.xxx.xxx 未訂閱
系統時間：2024-04-29 23:54:29
聯絡我們 | Delphi K.Top討論版
| 本站聲明 |
|
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！ |