Привет всем! Дали мне тут задачу по оптимизации кода, а я такими вещами никогда раньше не занималась, поэтому решила спросить у коллег. Код дан ниже. Условия такие: есть межсетевой экран, через который проходит трафик, по этому трафику собирается статистика в определенный массив. Функция GetUserShow, которую надо оптимизировать, как раз собирает эту статистикиу. Но в соединении может участвовать не только компьютер, характеризующийся IP-адресом, но и так называемый VPN-клиент, который характеризуется определенным номером, а не IP-адресом (либо с той, либо с другой стороны соединения). Таким образом, есть 3 варианта соединения: IP-адрес — IP-адрес IP-адрес — VPN-клиент VPN-клиент — IP-адрес Так вот, эта функция получает данные о трафике и проверяет полным перебором по массиву usershow; если нет записи для данной пары отправитель-получатель, то она добавляется в массив; если массив полон (максимальная длина — MAXABONENT), то удаляется самая старая, добавляется новая; если такая запись уже есть, то не добавляется. Кстати, надо учесть, что может придти такая пара (адреса условно обозначены цифрами): 100 — 101 и такая пара 101 — 100 И они считаются одинаковыми, это тоже надо учитывать. Так вот, надо постараться оптимизировать код функции как можно лучше. Я, конечно, понимаю, что полный перебор — это плохо, и можно взять какой-то другой алгоритм поиска и получить выигрыш в скорости, но хотелось бы услышать мнение более опытных людей, какой именно алгоритм можно было бы задействовать и почему(!) — обязательно аргументируйте. Может, в коде еще что-то можно оптимизировать. Любым предложениям по потимизации буду рада, потому что не знаю пока, с какого ркая грызть эту задачу. Кстати, многие поля структур можно игнорировать, они несущественны, имеют значение только вот эти 4 поля (по крайней мере, так мне объяснили): Код (Text): saddr =acc->ac_souraddr; daddr =acc->ac_destaddr; sclient=acc->ac_localclient; dclient=acc->ac_remoteclient; Эти поля выступают также как флаги, показывающие, какой из трех случаев имеет место. Примерный код ниже (примерный, потому что некоторые вещи не существенны): Код (Text): typedef void guardworktype; typedef void clientworktype; typedef unsigned char BYTE; // 8 бит typedef unsigned short WORD; // 16 бит typedef unsigned long DWRD; // 32 бита typedef struct _ptype_ { WORD pt_portnumber; }; DWRD curftime; DWRD curtick; const static int TIMELIVEABONENT = 20; typedef struct { DWRD ac_souraddr; // адрес отправителя (в глобальном формате) struct _gwtype_ *ac_localguard; // ссылка на гадюку отправителя(0-нет) struct _ptype_ *ac_recvport; // порт откуда принят пакет struct _cliwrk_ *ac_localclient; DWRD ac_destaddr; // адрес получателя struct _gwtype_ *ac_destguard; // ссылка на гадюку получателя(0-нет) struct _ptype_ *ac_linkport; // порт куда необходимо послать пакет struct _cliwrk_ *ac_remoteclient; DWRD ac_lendata; // размер данных в принятом пакете BYTE ac_ipheadlen; // размер IP заголовка в данном пакете BYTE ac_ipprotocol; // протокол в IP BYTE ac_direct; BYTE ac_ipflags; // флаги из IP пакета WORD ac_sourport; // TCP/UDP порты (должны быть вместе) WORD ac_destport; // *(DWRD*)&ac_sourport==0 - не определены DWRD ac_reccrylendata; // размер данных до преобразования на приеме DWRD ac_reclendata; // размер данных после преобразования на приеме DWRD ac_senlendata; // размер открытых данных на передачу DWRD ac_sencrylendata; // размер закрытых данных на передачу BYTE ac_ipuserprotocol; // протокол в IP оригинальный (как пришел) BYTE ac_routeraccess; // 0/1/2-абоненты/к рутеру/от рутера BYTE ac_statdontupdate; // ACSDU.. не отписывать в статистику и //отображение // на экране - ICMP ERROR MESSAGE BYTE ac_state; // ACS_... DWRD ac_sendmtu; // MTU с каким передавить пакеты в линк // DWRD ac_specialsendmtu; // если длинный пакет с DONTFRAGMENT // // был принят через фпсу то попытайся // // передать пакет с таким mtu //ipheadertype *ac_pack; // сам IP пакет с заголовком DWRD ac_sendtoipaddr; // IP в который отправлять далее // =0 - отправь broadcast //DWRD ac_tcpudpiface[MAXACC/32]; // для TCP/UDP каким группам он //должен удовлетворить //useritemtype *ac_localuser; // ссылка на юзера отправителя //useritemtype *ac_remoteuser; // ссылка на юзера получателя (0-нет) struct _gawwrk_ *ac_localgate; // ссылка на рутер со стороны приема struct _gawwrk_ *ac_remotegate; // ссылка на рутер со стороны передачи BYTE ac_backhaddr[6]; // Hardware Address откула пришел BYTE ac_align[2]; } accesstype; #define MAXABONENT (2048) // биты в поле ab_status #define ABS_DECLARED 0x01 // запись заполнена #define ABS_CLOSED 0x02 // запись закрыта #define ABS_INVRSB 0x04 // счетчик ab_recvsourbytes перехлестнулся #define ABS_INVRDB 0x08 // счетчик ab_recvdestbytes перехлестнулся #define ABS_INVRSP 0x10 // счетчик ab_recvsourpack перехлестнулся #define ABS_INVRDP 0x20 // счетчик ab_recvdestpack перехлестнулся #define ABS_INVISP 0x40 // счетчик ab_ignoresourpack перехлестнулся #define ABS_INVIDP 0x80 // счетчик ab_ignoredestpack перехлестнулся typedef struct { BYTE ab_status; // 0 состояние (ABS_...) BYTE ab_port; // 1 LAN порт источника (0-не определен) BYTE ab_linkport; // 2 LAN порт получателя(0-не определен) BYTE ab_nextlist; // 3 DWRD ab_souripaddr; // 4 IP адрес по стороне ab_port DWRD ab_destipaddr; // 8 IP адрес по стороне ab_linkport guardworktype *ab_guard; // 12 гадюка по стороне ab_port (0-открытое) guardworktype *ab_linkguard; // 16 гадюка по стороне ab_linkport (0-открытое) clientworktype *ab_client; // клиент по стороне ab_port clientworktype *ab_linkclient; // клиент по стороне ab_linkport DWRD ab_lasttime; // 20 время прошлого обмена (ftime) DWRD ab_closetime; // 24 время закрытия записи (ftime) // (если не закрыта-тики когда сессия закроется) DWRD ab_recvsourbytes; // 28 кол-во принятых байт от ab_port DWRD ab_recvdestbytes; // 32 кол-во принятых байт от ab_linkport DWRD ab_recvsourpack; // 36 кол-во принятых пакетов от ab_port DWRD ab_recvdestpack; // 40 кол-во принятых пакетов от ab_linkport DWRD ab_ignoresourpack; // 44 кол-во принятых пакетов от ab_port DWRD ab_ignoredestpack; // 48 кол-во принятых пакетов от ab_linkport DWRD ab_timesave; // 52 время на сохранение DWRD ab_initipaddr; // ip инициатора соединения //BYTE ab_statrec[SIZEUSERSTAT]; // userfpsuworktype ab_statrec; // 56 запись статистики (набольшая по длине) //histlisttype ab_errlist[MAXHLIST];// история ошибок передачи/приема } usershowtype; // usershowtype usershow[MAXABONENT]; static usershowtype *GetUserShow(accesstype *acc) { DWRD minlast=0xFFFFFFFF,minclose=0xFFFFFFFF; usershowtype *uslast=0; usershowtype *usclosed=0; usershowtype *us=&usershow[0]; DWRD saddr,daddr; clientworktype *sclient,*dclient; int swithaddr=0; saddr =acc->ac_souraddr; daddr =acc->ac_destaddr; sclient=acc->ac_localclient; dclient=acc->ac_remoteclient; if (acc->ac_recvport->pt_portnumber) { // порт 2-LAN карты saddr =daddr; daddr =acc->ac_souraddr; dclient=sclient; sclient=acc->ac_remoteclient; swithaddr=1; } if (sclient) { if (dclient==0) { // поиск по клиенту источнику do { if (us->ab_status==0) goto setnew; // чистая if (us->ab_client==sclient) { if (us->ab_linkclient) goto checkmindc; if (us->ab_destipaddr!=daddr) goto checkmindc; us->ab_souripaddr=saddr; // если изменится адрес goto settime; } // найден if (us->ab_linkclient==sclient) { if (us->ab_client) goto checkmindc; if (us->ab_souripaddr!=daddr) goto checkmindc; us->ab_destipaddr=saddr; swithaddr^=1; goto settime; } // найден checkmindc: if (us->ab_status&ABS_CLOSED) { if (us->ab_closetime<minclose) { usclosed=us; minclose=us->ab_closetime; } continue; } if (us->ab_lasttime<minlast) { uslast=us; minlast=us->ab_lasttime; } } while((++us)<&usershow[MAXABONENT]); goto getlast; } // поиск для пары клиентов do { if (us->ab_status==0) goto setnew; // чистая if ((us->ab_client==sclient)&&(us->ab_linkclient==dclient)) { us->ab_souripaddr=saddr; us->ab_destipaddr=daddr; // если изменится адрес goto settime; } if ((us->ab_client==dclient)&&(us->ab_linkclient==sclient)) { us->ab_souripaddr=daddr; us->ab_destipaddr=saddr; // если изменится адрес swithaddr^=1; goto settime; } if (us->ab_status&ABS_CLOSED) { if (us->ab_closetime<minclose) { usclosed=us; minclose=us->ab_closetime; } continue; } if (us->ab_lasttime<minlast) { uslast=us; minlast=us->ab_lasttime; } } while((++us)<&usershow[MAXABONENT]); goto getlast; } if (dclient) { // sclient==0 - поиск по клиенту получателю do { if (us->ab_status==0) goto setnew; // чистая if (us->ab_linkclient==dclient) { if (us->ab_client) goto checkminsc; if (us->ab_souripaddr!=saddr) goto checkminsc; us->ab_destipaddr=daddr; // если изменится адрес goto settime; } if (us->ab_client==dclient) { if (us->ab_linkclient) goto checkminsc; if (us->ab_destipaddr!=saddr) goto checkminsc; us->ab_souripaddr=daddr; // если изменится адрес swithaddr^=1; goto settime; } checkminsc: if (us->ab_status&ABS_CLOSED) { if (us->ab_closetime<minclose) { usclosed=us; minclose=us->ab_closetime; } continue; } if (us->ab_lasttime<minlast) { uslast=us; minlast=us->ab_lasttime; } } while((++us)<&usershow[MAXABONENT]); goto getlast; } do { if (us->ab_status==0) goto setnew; // чистая if (((DWRD)us->ab_linkclient|(DWRD)us->ab_client)==0) { if ((us->ab_souripaddr==saddr)&&(us->ab_destipaddr==daddr)) goto settime; if ((us->ab_souripaddr==daddr)&&(us->ab_destipaddr==saddr)) { swithaddr^=1; goto settime; }} if (us->ab_status&ABS_CLOSED) { if (us->ab_closetime<minclose) { usclosed=us; minclose=us->ab_closetime; } continue; } if (us->ab_lasttime<minlast) { uslast=us; minlast=us->ab_lasttime; } } while((++us)<&usershow[MAXABONENT]); getlast: // не найдена - выбираю подходящую us=uslast; if (usclosed) us=usclosed; CloseUserStat(us); setnew: _MemClearMacro(us,sizeof(usershowtype)); us->ab_souripaddr=saddr; // IP адрес по стороне ab_port us->ab_destipaddr=daddr; // IP адрес по стороне ab_port us->ab_client =sclient; us->ab_linkclient=dclient; settime: if (swithaddr) { us->ab_port =0; if (acc->ac_linkport) us->ab_port=acc->ac_linkport->pt_portnumber+1; us->ab_linkport =acc->ac_recvport->pt_portnumber+1; us->ab_guard =acc->ac_destguard; us->ab_linkguard=acc->ac_localguard; } else { us->ab_linkport =0; if (acc->ac_linkport) us->ab_linkport=acc->ac_linkport->pt_portnumber+1; us->ab_port =acc->ac_recvport->pt_portnumber+1; us->ab_linkguard=acc->ac_destguard; us->ab_guard =acc->ac_localguard; } us->ab_lasttime =curftime; // время прошлого обмена (ftime) us->ab_closetime =curtick+TIMELIVEABONENT; us->ab_status &=~ABS_CLOSED; us->ab_status |=ABS_DECLARED; return us; } Кстати, какими функциями в программе можно замерить производительность?
XJess Надо писать что оптимизируем. Насколько понял по скорости. Второе надо указывать объем обробатываемых данных. Для быстрого поиска можно использовать бинарный. А структуру представления зависит от многих факторов. Как часто пользователи добавляются в систему и удоляются из нее. Можно представить массивом или в виде дерева. Если в виде дерева то AVL (сбаланосированные деревья). Для этого есть профайлы или как-то так. А если дедовским методом то через функцию получения времени. Я бы функцию назвал только не знаю какая у вас система?
Система - Windows, оптимизация - да, по времени, но можно и не только, если есть что улучшить в плане чего-то другого.
А что скажете о хэш-таблице как средстве для поиска в данном случае? Насчет объема обрабатываемых данных - а что от этого будет зависеть? Кстати, насколько часто добавляются/удаляются данные, не знаю - не сказано.
XJess в любом случае нужно постараться снизить кол-во переборов. определись с условием равенства/неравенства данных, и ты увидишь решение. короче, в каком случае у тебя элементы считаются равными, а в каком - нет? а со структурой данных для поиска далее определишься, это несложно.
IMHO, лучший вариант для таблицы (usershow) фиксированного размера. Только подобрать хорошую хэширующую функцию.
