Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

очередь с приоритетом

19K
22 апреля 2007 года
пакахондас
21 / / 24.01.2007
Есть несколько отдельных потоков.Они дают свои запросы на сервер.Данные поступающие от клиентов помещаются в очередь с учётом их приоритета.Сервер их извлекает из очереди.Как организовать такую очередь? Если кто знает помогите.Кода не надо.Общие соображения и если не затруднит блок-схему.
Спасиба всем.
268
22 апреля 2007 года
Михаил
587 / / 25.06.2005
в очереди без приоритетов каждый элемент помещается в конец очереди, а тут будет помещаться за тем элементов у которого приоритет меньше
19K
23 апреля 2007 года
пакахондас
21 / / 24.01.2007
Всем спасиба.Всё понял.Нужно сформировать масив куда будут поступать запросы,и после каждого запроса каким ниб. методом сортировки масив сортировать.После сортировки сервер берёт первый елемент масива.
Тему можна закрыть.:)
240
23 апреля 2007 года
aks
2.5K / / 14.07.2006
Массив будет слишком накладно перераспределять память или сортировать. В данном случае очередь выгоднее организовывать списком и сразу формировать ее таким образом, чтобы вставлять элемент согласно ее приоритету. (Как понимаете преимущество списка в том, что его элемент можно без особых затрат вставить в любую позицию)
2.4K
23 апреля 2007 года
Lexogen
70 / / 18.05.2004
Для похожих целей использовали priority_queue. Вернее клас надстройку для даного контейнера с введением синхронизации доступа. Алгоритм сортироваки в данном контейнере устроил, по крайней мере написать что то такое же быстрое займет много времени.
3.3K
23 апреля 2007 года
GENA_DJ
123 / / 08.03.2005
Цитата: aks
В данном случае очередь выгоднее организовывать списком и сразу формировать ее таким образом, чтобы вставлять элемент согласно ее приоритету.



Поясни плиз, как быстро вставлять элемент согласно приоритету?

Как я понимаю, нужен поиск, а как реализовать поиск по списку кроме как просмотреть все элементы один за одним?

У примеру, держать массив сразу упорядоченными, применять сортировку вставками, для ускорения вставок - цепочечные комманды процессора. Поиск - применяя метод деления отрезка пополам. Как плюс - экономия памяти.

Или я в чем-то ошибаюсь?

240
23 апреля 2007 года
aks
2.5K / / 14.07.2006
GENA_DJ, даже в простом списке для добавления элемента на свое место достаточно просмотреть элементы от начала до его положения. Вставка - это еденичная опреация (поменять указатели грубо говоря). Какое будет быстродействие при N элементах в среднем?
А если добавить элемент в конец массива и произвести указанную сортировку какие надо произвести действия? И каково будет их сумарное быстродействие от количества элементов? Можешь посичтать? =))
3.3K
23 апреля 2007 года
GENA_DJ
123 / / 08.03.2005
Погоди, так быстро не надо делать выводы. Давай сначала модель построим. Будем исходить из следующих предпосылок.

1. В очереди в среднем на одну операцию добавления элемента приходится одна операция удаления элемента. - считаем, что система вышла в равновесный режим нагрузки.

2. Считаем что (в случае с массивами) элементы будут сортироваться от меньшего приоритета к большему. То есть если нужно будет добавить несколько элементов большого приоритета, а длина массива не позволит это сделать - достаточно перевыделить память. (на i386 читай: добавить еще несколько страниц). В случае со списками это ограничение не имеет значения.

3. Попробуем оценить объем памяти, необходимый для хранения одного элемента очереди.
а) массив: указатель на объект с приоритетом, число-приоритет
б) список: указатель на объект, число-приоритет, указатель на следующий элемент списка.
Для массива - 2 DWORD-а, для списка - 3 DWORD-а.

Вижу следующие сценарии работы системы:

1. Добавление этемента.
1.1 список
а) выделить память под элемент
б) пройти от начала до элемента, чей приоритет меньше приоритета добавляемого элемента. Поменять ссылки на элементы.
1.2 массив
а) зная фактическую длину массива, применить метод деления отреза пополам - найти пару элементов, такую что элемент слева имеет меньший или равный приоритет, а справа - больший или равный.
б) при необходимости - выделить страницу памяти.
в) цепочечной командой пересылки DWORD-ов сдвинуть подмассив больших элементов вправо на 1.
г) задать элемент массива

2.Удаление элемента.
2.1. список.
а) обновить головной элемент списка
б) освободить память
2.2 массив
а) уменьшить значение переменной фактической длины массива на 1

Теперь анализ.

На этапе удаления массива имеем небольшой выигрыш по времени при приминении массива в связи с тем, что не нужно каждый раз освобождать память. Можно пренебречь.

На этапе добавления ситуация сложнее. Дело в том, что операции 1.1-б) и 1.2-в) - обе в среднем линейные с ростом длины очереди. Но время выполнения операции 1.1-б) как правило растет быстрее с ростом длины очереди по сравнению с операцией 1.2-в), (последняя - цепочечная команда). Тогда 1.1-б займет время =k1*L, L - длина массива, а 1.2-в) займет время =k2*L, причем k2<k1. Но когда работаем с массивом, мы должны еще выполнить 1.а-а). Время выполнения этой операции логарифмически растет с ростом L. Поясню. Нужно выполнить N итераций, причем после каждой итерации множество элементов сокращается вдвое. Итак до тех пор, пока не останется один элемент. То есть L*(1/2)^N=1, откуда число итераций N~ln(L), следовательно время выполнения =k3*ln(L).

Ну и итог.

Когда мы используем массивы, мы тратим на добавление одного элемента время k2*L+k3*ln(L), а когда используем списки, то тратим время k1*L. Причем k2<k1, все k - положительные.

И странно, на первый взгяд списки эффективнее, там нет логарифмической добавки. Однако я считаю, что наоборот. Сейчас докажу.

Нужно решить неравенство k1*L > k2*L+k3*ln(L). - этим мы докажем, что массивы эффективнее.

Перенесем k2*L в левую часть.

(k1-k2)*L > k3 * ln(L). Не забудем, что левая часть линейно растет с ростом L. А павая растет логарифмически.

Дальше можно не читать, думаю, что все уже всё поняли.

На всякий случай.

Ни для кого не секрет, что начиная с некоторого L правая часть будет меньше чем левая. С ростом L различие будет только увеличиваться, поскольку ни для кого не секрет, что логарифм растет медленнее линейной функции (доказательство - экспонента растет быстрее линейной функции).

Кто не верит - строит графики.
5
23 апреля 2007 года
hardcase
4.5K / / 09.08.2005
Всё это конечно круто.... с графиками особенно, представляю.

Но, я как-то реализовывал очередь с N приоритетами через кольцевой массив длины N + 1. (1 - высший приоритет, N - низший)

У нас есть N + 1 обычных очередей (возможно пустых). очередь с индексом 0 - это "текущая" очередь, из которой происходит последовательная выборка запросов (в неё нельзя вставлять). с индексом N - это очередь для запросов с приоритетом N.

Когда в текущей очереди заканчиваются элементы, мы "поворачиваем" буфер на 1 позицию, и "текущей" станет очередь, у которой индекс до этого был 1, в случае если она пустая - повторяем поворот.

Вставка запросов элементарна: Если запрос имеет приоритет K, то мы вставляем его в конец очереди, находящейся позиции K нашего кольцевого массива.
240
24 апреля 2007 года
aks
2.5K / / 14.07.2006
Цитата: GENA_DJ

3. Попробуем оценить объем памяти, необходимый для хранения одного элемента очереди.


Ну вобщето речь была об оптимизации по количеству операций, а не памяти. Известно, что обычно оптимизация времени наоборот менее оптимальна по памяти.

Цитата: GENA_DJ

1.2 массив
а) зная фактическую длину массива, применить метод деления отреза пополам - найти пару элементов, такую что элемент слева имеет меньший или равный приоритет, а справа - больший или равный.
б) при необходимости - выделить страницу памяти.
в) цепочечной командой пересылки DWORD-ов сдвинуть подмассив больших элементов вправо на 1.
г) задать элемент массива


По поводу пунктов б и в - речь шла о задаче на высокоуровневом языке (я так понимаю) и безо всякой привязки к архитектуре процессора и ОС.
Так что пункты эти некорректны. Да и не самая лучшая тенденция делать такой зависимый код. А вот как раз операция сдвига "подмассив больших элементов вправо на 1" как раз таки трудоемкая в общем случае, особенно при большой длине массива.

3.3K
24 апреля 2007 года
GENA_DJ
123 / / 08.03.2005
Цитата:
Ну вобщето речь была об оптимизации по количеству операций, а не памяти. Известно, что обычно оптимизация времени наоборот менее оптимальна по памяти.



Данный пример - исключение. Выигрыш по быстродействию - сама цель. Выигрыш по памяти - бонус.

Цитата:

По поводу пунктов б и в - речь шла о задаче на высокоуровневом языке (я так понимаю) и безо всякой привязки к архитектуре процессора и ОС.
Так что пункты эти некорректны. Да и не самая лучшая тенденция делать такой зависимый код. А вот как раз операция сдвига "подмассив больших элементов вправо на 1" как раз таки трудоемкая в общем случае, особенно при большой длине массива.


Операция сдвига (как MoveMemory(), так и простой цикл) менее трудоемкая чем циклический переход от одного элемента очереди к следующему. Можете поверить, можете проверить.

19K
29 апреля 2007 года
пакахондас
21 / / 24.01.2007
Здрасте.Тут сделал прогу небольшую по очереди с приоритетом.Вроде Работает ,хотя кто его знает.....


Код:
#include <windows.h>
DWORD countThread,simbols; // переменная для сохранения к-ва потоков
HANDLE hInput,hOutput,semafor,semafor1; // хендлы буфера вводы-вывода консои,хендлы семафоров
char NameSemaphore1[]="port1"; // имя первого семафора
char NameSemaphore2[]="port2"; // имя второго семафора

SYSTEMTIME sysTime;

struct iTread{      //основная структура
    DWORD id; //идентификатор потока
    DWORD time; //время отправки сообщения
    DWORD ticet; // время ожидания в милисикундах
    DWORD prioriti; //приоритет потока
} masiv[11];

struct iPriority{   //дополнительная структура.При помощи даной структуры каждый поток узнаёт свой приоритет   
    DWORD prioritet; //Также если доработать программу даная структура может использоватся для
    DWORD id;       // динамического изменения приоритета потока.Поток ищет свой идентификатор
} masiv1[10];           // и присваивает себе приоритет.

bool FLAG=true;
DWORD WINAPI client(LPVOID);    // обявление клиентской процедуры
DWORD  WINAPI server(LPVOID);   //Обявлени серверной процедуры


int main(int argc,char* argv[]) // главная процедура
{
    char mes1[]="Введите количество потоков(не больше 9) \n";   //текстовые сообщения
    char mes3[]="Тестовая Программа";
    char mes4[]="Превышен лимит потоков,завершение программы!!!!";
    char mes5[]="Для выхода нажмите ESC \n";
    char mes2[10];  //буфер для ввода к-ва потоков
    INPUT_RECORD ir; //структура для обработки сообщений приходящих на консоль
   
    FreeConsole();  // освобождаем консоль по умолчанию
    AllocConsole(); //выделяем свою консоль
    hInput=GetStdHandle(STD_INPUT_HANDLE);  //получаем хендл буфера ввода консоли
    hOutput=GetStdHandle(STD_OUTPUT_HANDLE); //получаем хендл буфера вывода
    CharToOem(mes1,mes1); //перекодируем выводимые текстовые сообщения
    CharToOem(mes3,mes3);
    CharToOem(mes4,mes4);
    CharToOem(mes5,mes5);
    SetConsoleTitle(mes3); //устанавливаем заголовок консоли
    WriteConsole(hOutput,mes5,lstrlen(mes5),&simbols,0); // пишем в консоль
    WriteConsole(hOutput,mes1,lstrlen(mes1),&simbols,0);
    ReadConsole(hInput,mes2,9,&simbols,0); //читаем из консоли к-во создаваемых потоков
    countThread=atol(mes2); //перекодируем строку в число и сохраняем к-во потоков в переменной
    if (countThread>=10)    // проверяем не привышен ли лимит запрошеных потоков
    {
        WriteConsole(hOutput,mes4,lstrlen(mes4),&simbols,0); //если привышен-на выход
        Sleep(5000);
        return(0);
    }
    semafor=CreateSemaphore(0,1,1,NameSemaphore1); //создаём первый семафор
    semafor1=CreateSemaphore(0,1,1,NameSemaphore2); //создаём второй семафор
    //даные семафоры будут работать по принцыпу обратной связм что позволит жостко синхронизировать работу\
    //сервера и клиентов

   
    int pvParam=0,i=1;
    CreateThread(NULL,0,server,(LPVOID) &pvParam,0,NULL); //создаём серверную процедуру

    while (countThread) {       //при помощи цикла создаём заказаное количество клиентов
    --countThread;              // и устанавливаем их приоритет
    CreateThread(NULL,0,client,(LPVOID) &pvParam,0,&masiv1.id);
    masiv1.prioritet=i; //формируем масив структур по соотношению: идентификатор/приоритет
    ++i;
    }
   
   
   
   
    while (1)       //процедура обработки сообщений консоли
    {
        ReadConsoleInput(hInput,&ir,1,&simbols); //функция чтения сообщений
        if(ir.EventType==KEY_EVENT)             // идентификация типа сообщения
        {
            if(ir.Event.KeyEvent.bKeyDown)      // идентификация нажатия клавишы
                switch(ir.Event.KeyEvent.uChar.AsciiChar) //проверка кода клавишы
            {
                case (0x1b):
                    FLAG=false;  //выход по нажатию ESC
                    CloseHandle(semafor);
                    CloseHandle(semafor1);
                    Sleep(1000);
                    return(0);
                   
            }
        }
    }
}



   

DWORD WINAPI client(LPVOID pvParam) //клиентская процедура
{
   
    DWORD amon=50;
   

    while(amon>0)
    {
   
        masiv[0].ticet=GetTickCount();
        GetLocalTime(&sysTime); //получаем локальное время
        masiv[0].time=sysTime.wMilliseconds; //записываем милисикунды         
        masiv[0].id=GetCurrentThreadId(); //получаем идентификатор потока
       
        for(int i=10;i>0;i--) // цикл ищет приоритет потока по его идентификатору
        {
            if(masiv[0].id==masiv1.id)
                masiv[0].prioriti=masiv1.prioritet;
        }

   
       
               
            --amon;
        ReleaseSemaphore(semafor1,1,NULL); // разрешаем работу серверу       
        WaitForSingleObject(semafor,INFINITE);  // ждём разрешения на продолжение работы
    }
    ReleaseSemaphore(semafor1,1,NULL);
    FLAG=false;
    return(0);
}



DWORD  WINAPI server(LPVOID pvParam)  // серверная процедура

{
   
    DWORD size,simbols,i,j,sizeM=10; //временные переменные
   
    char buf1[100];     // буфер форматирования
    char mes[]="Идентификатор: %u            Время: %u      Приоритет: %u  Тики: %u \x0d\x0a ";
    HANDLE fHandle=CreateFile("LOG.txt",GENERIC_WRITE,0,0,OPEN_ALWAYS,0,0); //открываем лог файл \
    //если файла небыло то он создаётся.
     
    if( fHandle==INVALID_HANDLE_VALUE) // проверка создания файла
    {
        MessageBox(0,"Немогу создать файл,перезапустите программу","Ошибка",0);
        return(0);
    }
    while (FLAG)
    {
       
        WaitForSingleObject(semafor1,INFINITE); //ждём разрешения на работу от клиента
        for(i=10;i>0;i--)
       
        {
            if(masiv.prioriti==0) // в даном цикле мы заполняем очередь просматривая пустые \
                                    //  ячейки масива
            {
                masiv=masiv[0]; //находим пустую ячейку масива и заполняем её
                goto a;             // идём за новой порцией данных
            }
                                // очередь сформирована-идём на сортировку
        }
        for(i=0;i<sizeM;i++)  // организуем простейшую пузырьковую сортировку (масив небольшой)
        {
            for(j=sizeM-1;j>i;j--)
            {
                if(masiv[j-1].prioriti > masiv[j].prioriti)
                {
                    masiv[11]=masiv[j-1];masiv[j-1]=masiv[j];masiv[j]=masiv[11];
                }
            }
        }
   



       
        wsprintf(buf1,&mes[0],masiv[0].id,masiv[0].time,masiv[0].prioriti); // форматируем первый элемент масива 
        size=GetFileSize(fHandle,0); //получаем размер файла
        SetFilePointer(fHandle,size,0,FILE_BEGIN);  //устанавливаем файловый указатель в конец файла
        WriteFile(fHandle,buf1,lstrlen(buf1),&simbols,0); //пишем в файл
a:
        ReleaseSemaphore(semafor,1,NULL); //разрешаем работу клиенту
    }
    CloseHandle(fHandle); //закрываем хендл файла
   
   
    return(0); //выходим
}
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог