... ТАК Я исправил это немного, но теперь он говорит ... Тест на ускорение: ограничение по времени программы ... Продолжительность: 5 секунд! (Предел 8 секунд)! ... Вот мой код, еслиу кого-нибудь были какие-то идеи ...
#ifndef __PROGTEST__
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#define MAX_TERRORISTS 32
typedef struct TImage
{
int m_W;
int m_H;
unsigned char ** m_Data;
} TIMAGE;
void TerroristHunter ( int databaseSize,
TIMAGE ** database,
int threads,
TIMAGE *(* scanner) ( void ),
void (* officer) ( TIMAGE *, int ) );
#endif /* __PROGTEST__ */
/* Vase implementace / your implementation here */
pthread_mutex_t m1;
typedef struct Par {
TIMAGE *(* scanner) ( void );
TIMAGE ** terrorist;
int number_of_terrorists;
void ( *officer) ( TIMAGE *, int );} PAR;
void * function ( void * arg ) {
PAR * a = ( PAR * ) arg;
TIMAGE * image;
int i1, i2, i3, i4, i5, result = 0;
while ( 1 ) {
pthread_mutex_lock ( & m1 );
if (( image = a->scanner()) == NULL ) {pthread_mutex_unlock ( & m1 );break;}
pthread_mutex_unlock ( & m1 );
for ( i5 = 0; i5 < a->number_of_terrorists; i5 ++ ) {
for ( i1 = 0; i1 <= ( image->m_H - a->terrorist[i5]->m_H ); i1 ++ ) {
for ( i2 = 0; i2 <= ( image->m_W - a->terrorist[i5]->m_W ); i2 ++ ) {
if ( ( a->terrorist[i5]->m_Data[0][0] == image->m_Data[i1][i2] ) || ( a->terrorist[i5]->m_Data[0][0] == 255 ) ) {
for ( i3 = 0; i3 < a->terrorist[i5]->m_H; i3 ++ ) {
for ( i4 = 0; i4 < a->terrorist[i5]->m_W; i4 ++ )
if ( ( a->terrorist[i5]->m_Data[i3][i4]!= image->m_Data[i1 + i3][i2 + i4] ) && ( a->terrorist[i5]->m_Data[i3][i4] != 255 ) )
break;
if ( i4 != a->terrorist[i5]->m_W )
break; }
if ( i3 == a->terrorist[i5]->m_H ) {
result = result + ( 1 << i5 );
break; } } }
if ( i3 == a->terrorist[i5]->m_H )
break; } }
a->officer ( image, result );
result = 0;}
return NULL;
}
void TerroristHunter ( int databaseSize,
TIMAGE ** database,
int threads,
TIMAGE *(* scanner) ( void ),
void (* officer) ( TIMAGE *, int ) ) {
PAR * pom = ( PAR * ) malloc ( sizeof ( * pom ) );
int i;
pthread_t * thr = ( pthread_t * ) malloc ( threads * sizeof( * thr ) );
pthread_attr_t Attr; pthread_attr_init ( & Attr ); pthread_attr_setdetachstate ( & Attr, PTHREAD_CREATE_JOINABLE );
pthread_mutex_init ( & m1, NULL );
pom->terrorist = database;
pom->number_of_terrorists = databaseSize;
pom->officer = officer;
pom->scanner = scanner;
for ( i = 0; i < threads; i ++ )
pthread_create ( & thr[i], & Attr, function, (void * ) pom );
for ( i = 0; i < threads; i ++ )
pthread_join (thr[i], NULL);
pthread_attr_destroy ( & Attr); pthread_mutex_destroy ( & m1 );
free ( pom );
return; }
#ifndef __PROGTEST__
unsigned char t0r0[] = { 255, 255, 255, 255, 255, 255, 255, 255 };
unsigned char t0r1[] = { 255, 50, 60, 70, 255, 255, 255, 255 };
unsigned char t0r2[] = { 255, 50, 60, 70, 255, 255, 255, 255 };
unsigned char t0r3[] = { 255, 255, 50, 60, 70, 80, 255, 255 };
unsigned char t0r4[] = { 255, 255, 50, 60, 70, 80, 255, 255 };
unsigned char t0r5[] = { 255, 255, 255, 255, 255, 255, 255, 255 };
unsigned char t0r6[] = { 255, 255, 255, 255, 255, 255, 255, 255 };
unsigned char * t0all[] = { t0r0, t0r1, t0r2, t0r3, t0r4, t0r5, t0r6 };
TIMAGE t0 = { 8, 7, t0all }; /* one sample */
unsigned char t1r0[] = { 10, 20, 30 };
unsigned char t1r1[] = { 20, 50, 255 };
unsigned char t1r2[] = { 80, 50, 255 };
unsigned char * t1all[] = { t1r0, t1r1, t1r2 };
TIMAGE t1 = { 3, 3, t1all }; /* another sample */
TIMAGE * terrorists[2] = { &t0, &t1};
unsigned char i0r0[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
unsigned char i0r1[] = { 2, 50, 60, 70, 6, 7, 8, 1 };
unsigned char i0r2[] = { 3, 50, 60, 70, 7, 10, 20, 30 };
unsigned char i0r3[] = { 4, 50, 60, 70, 8, 20, 50, 3 };
unsigned char i0r4[] = { 5, 6, 50, 60, 70, 80, 50, 4 };
unsigned char i0r5[] = { 6, 7, 50, 60, 70, 80, 4, 5 };
unsigned char i0r6[] = { 7, 8, 1, 2, 3, 4, 5, 6 };
unsigned char i0r7[] = { 8, 1, 2, 3, 4, 5, 6, 7 };
unsigned char * i0all[] = { i0r0, i0r1, i0r2, i0r3, i0r4, i0r5, i0r6, i0r7 };
TIMAGE i0 = { 8, 8, i0all }; /* t0 and t1 here */
unsigned char i1r0[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
unsigned char i1r1[] = { 2, 3, 4, 5, 6, 7, 8, 1 };
unsigned char i1r2[] = { 3, 4, 5, 6, 7, 8, 1, 2 };
unsigned char i1r3[] = { 10, 20, 30, 7, 8, 1, 2, 3 };
unsigned char i1r4[] = { 20, 50, 7, 8, 1, 2, 3, 4 };
unsigned char i1r5[] = { 80, 50, 8, 1, 2, 3, 4, 5 };
unsigned char i1r6[] = { 7, 8, 1, 2, 3, 4, 5, 6 };
unsigned char * i1all[] = { i1r0, i1r1, i1r2, i1r3, i1r4, i1r5, i1r6 };
TIMAGE i1 = { 8, 7, i1all }; /* t1 here */
unsigned char i2r0[] = { 1, 50, 60, 70, 5, 6 };
unsigned char i2r1[] = { 2, 50, 60, 70, 6, 7 };
unsigned char i2r2[] = { 3, 4, 50, 60, 70, 80 };
unsigned char i2r3[] = { 10, 20, 50, 50, 70, 81 };
unsigned char i2r4[] = { 20, 50, 7, 8, 1, 2 };
unsigned char * i2all[] = { i2r0, i2r1, i2r2, i2r3, i2r4 };
TIMAGE i2 = { 6, 5, i2all }; /* no terrorists here */
TIMAGE * scans[3] = { &i0, &i1, &i2 };
TIMAGE * dummyScanner ( void )
{
static int idx = 0;
if ( idx < 3 ) return ( scans[idx ++] );
return ( NULL );
}
void dummyOfficer ( TIMAGE * img, int found )
{
int i;
printf ( "Image: %d x %d ", img -> m_W, img -> m_H );
if ( found )
{
printf ( "TERRORISTS:" );
for ( i = 0; i < (int)sizeof ( found ) * 8; i ++ )
if ( found & ( 1 << i ) )
printf ( " %d", i );
printf ( "\n" );
}
else
printf ( "no terrorists found\n" );
}
int main ( int argc, char * argv[] )
{
TerroristHunter ( 2, terrorists, 20, dummyScanner, dummyOfficer );
return ( 0 );
}
#endif /* __PROGTEST__ */