一萬筆以上資料,排序 + 搜尋 |
尚未結案
|
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的網頁,但……
< href="http://www.cs.cf.ac.uk/user/C.L.Mumford/tristan/CountPage.html">http://www.cs.cf.ac.uk/user/C.L.Mumford/tristan/CountPage.html 除了感謝還是感謝 新手上路,請多指教 如果此文章違反版規
還請版主告知並刪除
------
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 一定夠了吧...
< class="code">
#include <iostream>
using namespace std; int compare( const void *arg1, const void *arg2 )
{
long double ret = *(long double*)(arg1)-*(long double*)(arg2);
if (ret>0) return 1;
if (ret<0) return -1;
return 0;
} void main()
{
long double test[5];
int i; test[0] = 0.257932167931;
test[1] = 0.597136798769;
test[2] = 0.166879313246;
test[3] = 1.267498764654;
test[4] = 0.649843143498; qsort(test,5,sizeof(long double),compare); for (i=0;i<5;i ) {
cout << test[i] <
|
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值希望是可以變動的 這樣做的到嗎? 謝謝指教~~ |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |