Re[16]: Быстрый поиск свободного порта
От: AcidTheProgrammer Россия https://hts.tv/
Дата: 08.05.13 09:36
Оценка:
Здравствуйте, kaa.python, Вы писали:

По-моему вы просто хотите притянуть за уши хотелки к вашему решению. Человек же пишет, что не силен в алгоритмах, он не может точно сформулировать задачу, но, тем не менее, очень даже понятно чего он хочет. Свободный порт вы выдадите за О(1), а вернете вы его туда как, за O(1)?
Re[17]: Быстрый поиск свободного порта
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 08.05.13 09:40
Оценка:
Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>По-моему вы просто хотите притянуть за уши хотелки к вашему решению. Человек же пишет, что не силен в алгоритмах, он не может точно сформулировать задачу, но, тем не менее, очень даже понятно чего он хочет. Свободный порт вы выдадите за О(1), а вернете вы его туда как, за O(1)?

Добавлю в голову/хвост списка. А что не так? Добавление в голову/хвост так же делается за константное время.
Re[9]: Быстрый поиск свободного порта
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 08.05.13 09:52
Оценка:
Здравствуйте, kaa.python, Вы писали:

KP>Здравствуйте, -prus-, Вы писали:

P>>Как раз оптимизация по памяти тоже была бы к стати и поэтому представление диапазона в виде битового массива вариант подходящий.
P>>Остался поиск и изменение состояний портов.

KP>Если уж ты решил остановиться на битовой карте, то вот мои исследования на этот счет.

Тю, если не доступно __builtin_ffsll, то почему в этих исследованиях не расстатривается самое напрашивающееся решение для поиска первого установленного в единицу бита? 

const int magic64[64] = {
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6
};
 
int FirstOneIndex(uint64_t a) 
{
   assert (a != 0);
   return magic64[((a & -a) * 0x03f79d71b4cb0a89ull) >> 58];
}


Фактически имеем три битовые операции, одно умножение и обращение к таблице из 64-х чисел. Причем без всяких условий.
Re[10]: Быстрый поиск свободного порта
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 08.05.13 09:58
Оценка:
Здравствуйте, Mystic, Вы писали:

M>Тю, если не доступно __builtin_ffsll, то почему в этих исследованиях не расстатривается самое напрашивающееся решение для поиска первого установленного в единицу бита?

Потому что:

  1. Мне оно не пришло в голову;
  2. Итоговый набор операций в приведенном решении врятли будет быстрее чем 2.5 (в среднем) операции `&`.
Re[15]: Быстрый поиск свободного порта
От: Stanislav V. Zudin Россия  
Дата: 08.05.13 10:49
Оценка: 4 (1)
Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Здравствуйте, kaa.python, Вы писали:

KP>>Легко сделать O(1), если воспользоваться стеком/списком.

ATP>А как вы будете порт с заданным номером N удалять из списка или стека за O(1)?

Если не важен порядок получения свободных портов и не жалко 2х128К памяти, то получить О(1) очень легко.

Создаем два массива по 65К элементов (по числу доступных портов).

Первый массив (BusyArray) хранит номера портов, сгруппированные по занятости. Сперва идут свободные, затем занятые.
Переменная FirstBusy указывает на первый занятый порт.

Второй массив (PortPosition) хранит положение порта в массиве BusyArray. Получили элементарный хеш.


BusyArray:
  0   1   2   3   4   5   6   7   8   9  10  11  12
+---+---+---+---+---+---+---+---+---+---+---+---+---+...+
| 2 | 7 | 9 | 11| 4 | 1 | 3 | 12| 0 | 10| 8 | 5 | 6 |...|
+---+---+---+---+---+---+---+---+---+---+---+---+---+...+
                  ^
                  |
                  +---- FirstBusy

PortPosition:
  0   1   2   3   4   5   6   7   8   9  10  11  12
+---+---+---+---+---+---+---+---+---+---+---+---+---+...+
| 8 | 5 | 0 | 6 | 4 | 11| 12| 1 | 10| 2 | 9 | 3 | 7 |...|
+---+---+---+---+---+---+---+---+---+---+---+---+---+...+


Чтобы занять порт достаточно сделать декремент FirstBusy. 

ushort aquirePort()
{
   return BusyArray[--FirstBusy];
}



Чтобы освободить порт, нужно:
1. получить его положение в массиве занятых
2. переместить его на границу занятых и свободных.
3. инкрементировать FirstBusy


void releasePort(ushort port)
{
   ushort pos = PortPosition[port];
   if (pos != FirstBusy)
   {
      ushort portTmp = BusyArray[FirstBusy];
      swap(PortPosition[port], PortPosition[portTmp]);
      swap(BusyArray[FirstBusy], BusyArray[pos]);
      ++FirstBusy;
   }
}
_____________________
С уважением,
Stanislav V. Zudin
Re[16]: Быстрый поиск свободного порта
От: Stanislav V. Zudin Россия  
Дата: 08.05.13 11:21
Оценка:
Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Чтобы освободить порт, нужно:
SVZ>1. получить его положение в массиве занятых
SVZ>2. переместить его на границу занятых и свободных.
SVZ>3. инкрементировать FirstBusy

В предыдущем сообщении ошибочка. Инкремент нужно вынести из под if:
void releasePort(ushort port)
{
   ushort pos = PortPosition[port];
   if (pos != FirstBusy)
   {
      ushort portTmp = BusyArray[FirstBusy];
      swap(PortPosition[port], PortPosition[portTmp]);
      swap(BusyArray[FirstBusy], BusyArray[pos]);
   }

   ++FirstBusy;
}
_____________________
С уважением,
Stanislav V. Zudin
Re[11]: Быстрый поиск свободного порта
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 08.05.13 11:52
Оценка:
Здравствуйте, kaa.python, Вы писали:

KP>Потому что:

KP>

    KP>
  1. Итоговый набор операций в приведенном решении врятли будет быстрее чем 2.5 (в среднем) операции `&`.
    KP>
Условия и TLB-промахи могут кусаться, плюс обращения к памяти.
Re[16]: Быстрый поиск свободного порта
От: -prus-  
Дата: 13.05.13 06:39
Оценка:
Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Здравствуйте, AcidTheProgrammer, Вы писали:

Спасибо!
С уважением,
Евгений
Re[17]: Быстрый поиск свободного порта
От: Topknot Украина  
Дата: 22.11.13 01:42
Оценка:
Здоровский метод !

Для обработки случая когда все порты свободны (FirstBusy присвоено "запредельное" значение (= номер последнего + 1) ), нужно внести коррективы:

void releasePort(ushort port)
{
   ushort pos = PortPosition[port];

   if (pos >= FirstBusy)
   {
      if(pos != FirstBusy)
      {
         ushort portTmp = BusyArray[FirstBusy];
         swap(PortPosition[port], PortPosition[portTmp]);
         swap(BusyArray[FirstBusy], BusyArray[pos]);
      }
      ++FirstBusy;
   }
}




SVZ>Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>>Чтобы освободить порт, нужно:
SVZ>>1. получить его положение в массиве занятых
SVZ>>2. переместить его на границу занятых и свободных.
SVZ>>3. инкрементировать FirstBusy

SVZ>В предыдущем сообщении ошибочка. Инкремент нужно вынести из под if:
SVZ>
SVZ>void releasePort(ushort port)
SVZ>{
SVZ>   ushort pos = PortPosition[port];
SVZ>   if (pos != FirstBusy)
SVZ>   {
SVZ>      ushort portTmp = BusyArray[FirstBusy];
SVZ>      swap(PortPosition[port], PortPosition[portTmp]);
SVZ>      swap(BusyArray[FirstBusy], BusyArray[pos]);
SVZ>   }

SVZ>   ++FirstBusy;
SVZ>}

SVZ>
«Украина – это та Русь, которая осталась дома».
В. Новодворская.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.