| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Как оптимизировать работу в данном случае?
Cooller © (2006-10-11 09:32:00)Есть серверное приложение (активная одновременная работа с 1000+ клиентами). Пишется "навес" ввиде DLL, перехватывающий и анализирующий весь входящий траффик (функции send/recv). Для каждого соединения необходимо хранить некую информацию:
TClientData=record
...
end;
Уникальным идентификатором получается может быть только TSocket. Как быстро находить и изменять нужную информацию для каждого клиента? С одной стороны хорошо бы было использовать TSocket в качестве индекса. В модуле WinSock:TSocket = u_int;
Получается нужно объявить вот такой массив:
aClientData:array [integer] of TClientData
В итоге:
[Error] Unit1.pas(21): Data type too large: exceeds 2 GB
В принципе ничего удивительного
Можно конечно создать динамический массив:
aClientData:array of record
s:integer;
data:TClientData;
end;
Но при получении каждого пакета производить поиск по такому массиву - слишком накладное занятие (повторюсь - активная одновременная работа с 1000+ клиентами).
Как быть, что посоветуете?
Сергей М. (2006-10-11 12:14:00) [21]
> выбора алгоритма имеет огромное значение
Конечно имеет.
Но ведь вопрос твой был не о выборе алгоритма поиска в упорядоченном списке, а об организации такого списка ...
Cooller (2006-10-11 12:04:00) [22]Просто если в секунду необходимо производить поиск около трех тысяч раз... то выбора алгоритма имеет огромное значение.
Сергей М. (2006-10-11 11:58:00) [23]
> как обстоят дела с быстродействием?
Дело не в быстродействии (оно сравнимо с вариантом для стат.массива), а в удобстве.
TList имеет готовый метод Sort, реализующий алгоритм быстрой сортировки списка.
После добавления в список нового элемента достаточно вызвать Sort(), после чего список становится упорядоченным и для него тут же можно применять любые высокоэффективные алгоритмы поиска.
Cooller (2006-10-11 11:34:00) [24]
> 3. Использовать TList
А как обстоят дела с быстродействием?
---
Вообщем мне надо выбрать и трёх вариантов =)
Сергей М. (2006-10-11 10:55:00) [25]3. Использовать TList
Cooller (2006-10-11 10:46:00) [26]И какой алгоритм хеширования посоветуете (чтобы бы проще искать)?
Cooller (2006-10-11 10:38:00) [27]Мне кажется, что хеширование выиграет в скорости
Cooller (2006-10-11 10:35:00) [28]В итоге есть два метода реализации:
1. Использовать динамический массив. При добавлении нового сокета - вставлять его в нужную ячейку, чтобы список был упорядоченным (как это реализовать? move?)
2. Использовать статический массив и хеширование (сейчас займусь поиском исходников).
Какой вариант выбрали бы Вы?
MBo (2006-10-11 10:24:00) [29]>Номера назначаются сокетам по порядку или абсолютно случайно?
Этого я не знаю.
В примере ты используешь простейшее хэширование по младшему слову и линейный поиск. Это будет приводить к конфликтам, да и поиск медленный, так что лучше все же использовать настояще хэширование, исходники найти нетрудно.
Принцип - заводится массив размером N раза в полтора больше количества ключей
Ключ (у тебя номер сокета) хэшируется - по некоему алгоритму кодируется, приводится к диапазону 0..N-1
Поиск требует очень малого количества операций - обычно одну, при возможных конфликтах (которые разруливаются хэш-алгоритмом) - пару-тройку, добавление - тоже.
Сергей М. (2006-10-11 10:22:00) [30]
> Номера назначаются сокетам по порядку или абсолютно случайно?
Неважно как они назначаются, никаких предположений на эту тему делать не следует.
Важно чтобы на момент необходимости поиска эти "номера" были упорядочены.
Сергей М. (2006-10-11 10:20:00) [31]
> входящий траффик (функции send/recv)
Send - это исходящий траффик.
> производить поиск по такому массиву - слишком накладное
> занятие
Немногим накладнее чем при стат.массиве.
Массив д.б. упорядочен по полю s, тогда для поиска можно будет применить любой из подходящих высокоэффективных алгоритмов. оперирующих именно упорядоченным (а не произвольно сформированным) списком.
Cooller (2006-10-11 10:10:00) [32]2 MBo
Насколько сложный алгоритм необходимо использовать в данном случае? Номера назначаются сокетам по порядку или абсолютно случайно?
К примеру может ли подойти такой метод?
function FindSock(s:TSocket):integer;
var
i:0..$FFFF;
begin
Result:=-1;
i:=s mod $FFFF;
while aCD[i].s<>0 do
begin
if aCD[i].s=s then
begin
Result:=i;
break;
end;
i:=i-1;
end;
end;
function AddSock(s:TSocket):integer;
var
i:0..$FFFF;
begin
Result:=-1;
i:=s mod $FFFF;
while aCD[i].s<>0 do
begin
if aCD[i].s=s then
begin
Result:=i;
exit;
end;
i:=i-1;
end;
result:=i;
end;
MBo (2006-10-11 09:38:00) [33]1. хэширование
2. дерево поиска (простое бинарное, красно-черное, AVL)
3. сортированный по ключу поиска массив + бинарный поиск
| |
Страницы: 