ورود

View Full Version : سوال: مشکل در موازي سازي الگوريتم Pattern Matching در Visual C++‎‎



AmirGooran
چهارشنبه 18 فروردین 1389, 06:16 صبح
سلام،خسته نباشيد.مي خواهم با استفاده از تابع CreateThread يک الگوريتم Pattern Matching‌ بنويسم،يعني برنامه اي که يک فايل متني حجيم(مثلا 2 مگ) مي گيره،و بعد محل هاي وجود يک زيررشته را در اون گزارش مي ده.اما اين برنامه ام يه مشکلي داره،اونم اينه که تو فايل هاي بزرگ وقتي تعداد نخ هارو بيش از يکي مي کنم،برنامه همه محل هاي زيررشته را پيدا نمي کنه،البته هميشه اينطور نيست،يعني يک موقع الگوريتم با اين تعداد نخ معين جواب مي ده،و يه بار ديگه جواب نمي ده.کسي مي دوني دليلش چي مي تونه باشه؟ممکنه به خاطر متوقف نشدن Thread‌ها در هنگام اجراي کدهايي که ليست محل هاي زيررشته را نمايش مي ده،باشه؟
اين هم کد:(در Visual Studio 1998 و 2008 قابل کامپايل شدنه):


/*------------------------------------------------------------
PARALLELBF.CPP -- A Parallel Broute Force program for search into a pattern
(c) AmirGooran, 2010
(E-mail) Amir7687@yahoo.com
------------------------------------------------------------*/
#include <windows.h>
#include <process.h>

#define XSIZE 320
#define YSIZE 445

unsigned long int time,first_time;
HWND hWnd;
TCHAR openedfile[256];
char substring[256];
unsigned long int thread_size;
HWND childhwnd[10];
int subsize;//size of substring
unsigned long filesize;//size of file for search
HANDLE hFile;

class node{
public:
node* next;
long int data;
node( long int c=0){data=c,next=NULL;}
};

class queue{
node* front;
node* rear;
public:
queue(){front=rear=NULL;}
bool isempty(){return front==NULL;}
void enque(long int x){node* r=new node(x);
if(front==NULL)
front=rear=r;
else{
rear->next=r;
rear=r;
}
}
long int deque(){
long int m;
node* temp;
if(!isempty()){
m=front->data;
temp=front->next;
delete front;
front=temp;
return m;
}
else{
rear=NULL;
return -1;
}
}
}queue1;

//function definitions
DWORD WINAPI ParallelAlgo(PVOID pvoid);
LRESULT CALLBACK WndProc (HWND, UINT, WPARAM, LPARAM) ;
int openfile();
void ParallelBrouteForce(char* filename,unsigned long int thread_number);

int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
PSTR szCmdLine, int iCmdShow)
{
static TCHAR szAppName[] = TEXT ("PARALLELBF") ;
HWND hwnd ;
MSG msg ;
WNDCLASS wndclass ;

wndclass.style = CS_HREDRAW | CS_VREDRAW ;
wndclass.lpfnWndProc = WndProc ;
wndclass.cbClsExtra = 0 ;
wndclass.cbWndExtra = 0 ;
wndclass.hInstance = hInstance ;
wndclass.hIcon = LoadIcon (NULL, IDI_APPLICATION) ;
wndclass.hCursor = LoadCursor (NULL, IDC_ARROW) ;
wndclass.hbrBackground = (HBRUSH) GetStockObject (BLACK_BRUSH) ;
wndclass.lpszMenuName = NULL ;
wndclass.lpszClassName = szAppName ;

if (!RegisterClass (&wndclass))
{
MessageBox (NULL, TEXT ("This program requires Windows NT!"),
szAppName, MB_ICONERROR) ;
return 0 ;
}

hwnd = CreateWindow (szAppName, // window class name
TEXT ("The Parallel Broute Force Program"), // window caption
WS_BORDER |WS_SYSMENU |WS_CAPTION, // window style
CW_USEDEFAULT, // initial x position
CW_USEDEFAULT, // initial y position
XSIZE, // initial x size
YSIZE, // initial y size
NULL, // parent window handle
NULL, // window menu handle
hInstance, // program instance handle
NULL) ; // creation parameters
hWnd=hwnd;
ShowWindow (hwnd, iCmdShow) ;
UpdateWindow (hwnd) ;

while (GetMessage (&msg, NULL, 0, 0))
{
TranslateMessage (&msg) ;
DispatchMessage (&msg) ;
}
return msg.wParam ;
}

LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
HDC hdc ;
PAINTSTRUCT ps ;
RECT rect ;
unsigned long int thread_number;
long int x;
TCHAR matn[100];//for use as a buffer
int xwidth;
int ywidth;
switch (message)
{
case WM_CREATE:
SetWindowLong(hwnd,GWL_EXSTYLE,WS_EX_TOOLWINDOW);
xwidth=(GetSystemMetrics(SM_CXSCREEN)-XSIZE)/2;
ywidth=(GetSystemMetrics(SM_CYSCREEN)-YSIZE)/2;
MoveWindow(hwnd,xwidth,ywidth,XSIZE,YSIZE,true);
childhwnd[0]=CreateWindow(TEXT("edit"),NULL,WS_CHILD |ES_AUTOHSCROLL | WS_VISIBLE|WS_BORDER,2,25,250,30,hwnd,(HMENU)0,((L PCREATESTRUCT) lParam)->hInstance, NULL);
childhwnd[1]=CreateWindow(TEXT("button"),TEXT("..."), BS_FLAT |BS_DEFPUSHBUTTON |WS_CHILD | WS_VISIBLE|WS_BORDER,252,25,60,30,hwnd,(HMENU)1,(( LPCREATESTRUCT) lParam)->hInstance, NULL);
childhwnd[2]=CreateWindow(TEXT("button"),TEXT("Start Search"),BS_FLAT |BS_DEFPUSHBUTTON |WS_CHILD | WS_VISIBLE|WS_BORDER,2,385,310,30,hwnd,(HMENU)2,(( LPCREATESTRUCT) lParam)->hInstance, NULL);
childhwnd[3]=CreateWindow(TEXT("edit"),NULL,WS_CHILD | WS_VISIBLE|WS_BORDER,2,80,310,30,hwnd,(HMENU)3,((L PCREATESTRUCT) lParam)->hInstance, NULL);
childhwnd[4]=CreateWindow(TEXT("LISTBOX"),NULL,WS_CHILD|WS_VSCROLL |WS_VISIBLE|WS_BORDER,2,140,310,200,hwnd,(HMENU)4, ((LPCREATESTRUCT)lParam)->hInstance,NULL);
childhwnd[5]=CreateWindow(TEXT("edit"),TEXT("1"),WS_CHILD | WS_VISIBLE|WS_BORDER,215,335,30,30,hwnd,(HMENU)5,( (LPCREATESTRUCT) lParam)->hInstance, NULL);
return 0;
case WM_SETFOCUS:
SetFocus(childhwnd[3]);
return 0;
case WM_COMMAND:
if(childhwnd[1]==(HWND)lParam){//browse button
openfile();
SetWindowText(childhwnd[0],openedfile);
}
else if(childhwnd[2]==(HWND)lParam){
GetWindowText(childhwnd[3],substring,256);
GetWindowText(childhwnd[0],openedfile,256);
if(lstrcmp(openedfile,TEXT(""))!=0 && lstrcmp(substring,TEXT(""))!=0){
SendMessage(childhwnd[4],LB_RESETCONTENT,0,0);
GetWindowText(childhwnd[5],matn,3);
thread_number=atoi(matn);
first_time=GetTickCount();
ParallelBrouteForce(openedfile,thread_number);
time=GetTickCount()-first_time;
while(!queue1.isempty()){
x=queue1.deque();
wsprintf(matn,"match found at: %lu",x);
SendMessage(childhwnd[4],LB_ADDSTRING,0,(LPARAM)matn);
}
InvalidateRect(hWnd,NULL,true);
}
else
MessageBox(hwnd,TEXT("لطفا موارد مورد نياز را تکميل کنيد"),TEXT("اخطار"),MB_ICONEXCLAMATION);
}
return 0;
case WM_PAINT:
hdc = BeginPaint (hwnd, &ps) ;
GetClientRect (hwnd, &rect) ;
SetBkMode(hdc,TRANSPARENT);
SelectObject (hdc, CreateFont (0, 0, 0, 0, 0, 0, 0, 0,DEFAULT_CHARSET, 0, 0, 0, FIXED_PITCH, TEXT("NAZANIN"))) ;
SetTextColor(hdc,0xffffff);
lstrcpy(matn,TEXT(":لطفا فايلي براي جستجوي محتويات آن انتخاب کنيد"));
TextOut(hdc,52,0,matn,lstrlen(matn));
lstrcpy(matn,TEXT(":لطفا رشته اي براي جستجو در فايل وارد کنيد"));
TextOut(hdc,86,53,matn,lstrlen(matn));
lstrcpy(matn,TEXT(":ليست محل هايي که تطابق در آنها وجود دارد"));
TextOut(hdc,86,113,matn,lstrlen(matn));
wsprintf(matn,"%lu :مدت زمان انجام عمليات",time);
TextOut(hdc,86,360,matn,lstrlen(matn));
lstrcpy(matn,TEXT(":تعداد نخ ها"));
TextOut(hdc,250,337,matn,lstrlen(matn));
wsprintf(matn,"%lu :تعداد تطابق ها", SendMessage(childhwnd[4],LB_GETCOUNT,0,0));
TextOut(hdc,100,337,matn,lstrlen(matn));
EndPaint (hwnd, &ps) ;
return 0 ;
case WM_DESTROY:
PostQuitMessage (0) ;
return 0 ;
}
return DefWindowProc (hwnd, message, wParam, lParam) ;
}

int openfile(){
OPENFILENAME opn;
char szFile[260];
ZeroMemory(&opn,sizeof(opn));//tabe baraye zakhire faza baraye structure OPENFILENAME
opn.lStructSize=sizeof(OPENFILENAME);
opn.hInstance=NULL;
opn.hwndOwner=hWnd;
opn.lpstrTitle="لطفا فايلي انتخاب کنيد";
opn.Flags=OFN_HIDEREADONLY + OFN_FILEMUSTEXIST;
opn.lpstrFilter = "Text Files (*.txt)\0*.txt;*.text\0All Files(*.*)\0*.*\0";
opn.lpstrFile=szFile;
opn.nMaxFile=sizeof(szFile);
opn.lpstrFile[0] = '\0';
opn.lpstrFileTitle = NULL;
opn.lpstrInitialDir = NULL;
if(GetOpenFileNameA(&opn)==TRUE){
lstrcpy(openedfile,opn.lpstrFile);
return 1;
}
else
return 0;//error code
}

void ParallelBrouteForce(char* filename,unsigned long int thread_number){
HANDLE hThread[1000];
DWORD threadID;
unsigned long int i;
int j=0;
unsigned long int counter;
hFile = CreateFile(filename,GENERIC_READ,FILE_SHARE_READ,N ULL,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,NULL);
if(GetLastError()==ERROR_FILE_NOT_FOUND || GetLastError()==ERROR_PATH_NOT_FOUND){
MessageBox(hWnd,TEXT("فايل يافت نشد،لطفا موارد مورد نياز را دوباره بررسي کنيد"),TEXT("Error"),MB_ICONEXCLAMATION);
return;
}
filesize=GetFileSize(hFile,NULL);
subsize=lstrlen(substring);
thread_size=filesize/thread_number;
for(i=0;i<thread_number;i++)
hThread[i]=(HANDLE)CreateThread(NULL,0,&ParallelAlgo,(void*)thread_size,0,&threadID);
if(i*thread_size!=filesize){
hThread[i]=(HANDLE)CreateThread(NULL,0,&ParallelAlgo,(void*)(filesize-(i*thread_size)),0,&threadID);
thread_number++;
}
WaitForMultipleObjects(thread_number,hThread,true, INFINITE);
for(counter=0;counter<thread_number;counter++)//close added thread handles
CloseHandle(hThread[counter]);
CloseHandle(hFile);
}

DWORD WINAPI ParallelAlgo(PVOID pvoid){
unsigned long int filesize_nobat;
DWORD dwBytesRead;
char pattern[100000];
unsigned long int start;
unsigned long int bytes_readed=0;
int j=0;
unsigned long int thread_size=(unsigned long int)pvoid;
while(bytes_readed<thread_size){
start=SetFilePointer(hFile,NULL,NULL,FILE_CURRENT) ;
ReadFile(hFile,pattern,(thread_size-bytes_readed)>99999?99999:(thread_size-bytes_readed),&dwBytesRead,NULL);
filesize_nobat=dwBytesRead;
bytes_readed+=filesize_nobat;
pattern[filesize_nobat]=NULL;
for(unsigned long int i=0;i<filesize_nobat;i++){
if(pattern[i]==substring[0]){
j=1;
while(substring[j]!=NULL && pattern[i+j]==substring[j])
j++;
if(substring[j]==NULL)
queue1.enque(start+i);
}
}
}
return 0;
}



اگر مي دونيد مشکلش چيه،خواهشا جواب بدين،کارم بدجوري گيره.
مرسي.