Не силен в алгоритмах...
Есть диапазон сетевых портов 0-65535 или, например, 5000-5500 или 16300-49400.
Во время сетевого обмена порты помечаются как занятые — 1 и свободные — 0.
Например,
Подскажите плиз (может уже обсуждалось) чего почитать или механизм, который позволит максимально быстро ваще прям за минимум тактов искать свободный порт в диапазоне? Фактически искать 0 в крупном таком битовом массиве получается чтоль...
Заранее прям благодарен!
Здравствуйте, -prus-, Вы писали:
P>Подскажите плиз (может уже обсуждалось) чего почитать или механизм, который позволит максимально быстро ваще прям за минимум тактов искать свободный порт в диапазоне?
Непонятно. Диапазон считается известным изначально и не меняется во время работы? Или каждый запрос на поиск содержит свой уникальный диапазон (то есть сначала идёт запрос на поиск свободного порта только из диапазона [a, b], а затем только из диапазона [c, d] для произвольных значений переменных a-d)?
В первом случае стек (или очередь) со всеми свободными адресами хорошо подойдет. Операция Pop — взять и пометить как занятый, Push — пометить как свободный.
Во втором случае можно использовать древовидные структура данных — trie или дерево сегментов (вот похожий пример использования). Разумеется так как максимальное значение адреса известно и ограничено небольшим числом, то вся структура просто делается статической и занимает чуть больше битового массива соответствующей длины.
Вообще, вариантов много. Исходных данных ты привел маловато. Как я понял, у тебя уже есть некий массив портов, на основании которого ты определяешь свободен порт или занят. Так вот, если у тебя нет ограничений по дополнительной памяти, можно завести параллельную структуру типа списка/стека, куда добавлять номера свободных портов.
Если у тебя ограничения по дополнительной памяти есть, можно разбить твой массив с портами на ряд диапазонов и вспомогательный массив говорящий о том, есть ли в конкретном диапазоне свободный порт. Ну и при выдаче, не переходить к следующему диапазону до тех пор, пока не заполнишь текущий.
Здравствуйте, -prus-, Вы писали:
P>Всем привет!
P>Не силен в алгоритмах... P>Есть диапазон сетевых портов 0-65535 или, например, 5000-5500 или 16300-49400. P>Во время сетевого обмена порты помечаются как занятые — 1 и свободные — 0. P>Например, P>
P>Подскажите плиз (может уже обсуждалось) чего почитать или механизм, который позволит максимально быстро ваще прям за минимум тактов искать свободный порт в диапазоне? Фактически искать 0 в крупном таком битовом массиве получается чтоль... P>Заранее прям благодарен!
Заведи массив, битовую карту, каждый байт — 8 портов. С точки зрения скорости — будет самое быстрое.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Заведи массив, битовую карту, каждый байт — 8 портов. С точки зрения скорости — будет самое быстрое.
Ты, наверное, хотел сказать "с точки зрения потребления памяти будет самое экономное"? Каким образом подобное решение может быть самым быстрым? Оно будет зависеть как минимум от набора инструкций процессора, на котором выполняется. Все же, быстрей всего, организуется доступ к выровненным данным.
Здравствуйте, kaa.python, Вы писали:
KP>Ты, наверное, хотел сказать "с точки зрения потребления памяти будет самое экономное"? Каким образом подобное решение может быть самым быстрым? Оно будет зависеть как минимум от набора инструкций процессора, на котором выполняется. Все же, быстрей всего, организуется доступ к выровненным данным.
С точки зрения памяти, как раз, нет. Я имел ввиду с точки зрения алгоритмической сложности (форум — алгоритмы), O(1) — куда быстрее?!
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>С точки зрения памяти, как раз, нет. Я имел ввиду с точки зрения алгоритмической сложности (форум — алгоритмы), O(1) — куда быстрее?!
Стесняюсь спросить... А ты вопрос ТС читал?
механизм, который позволит максимально быстро ваще прям за минимум тактов искать свободный порт в диапазоне?
Как тебе битовая карта поможет искать, да еще и с константным временем?
Здравствуйте, kaa.python, Вы писали:
KP>Как тебе битовая карта поможет искать, да еще и с константным временем?
Наверное, можно представить диапазон портов 16300-49400 в виде битового массива, где первый бит будет соответствовать порту 16300, а последний — 49400. И, соответственно, 0 — порт свободен, 1 — порт занят. Может про это имелось ввиду примерно?
Здравствуйте, -prus-, Вы писали:
P>Наверное, можно представить диапазон портов 16300-49400 в виде битового массива, где первый бит будет соответствовать порту 16300, а последний — 49400. И, соответственно, 0 — порт свободен, 1 — порт занят. Может про это имелось ввиду примерно?
Именно. И как ты в таком массиве найдешь что-то за константное время?
Здравствуйте, kaa.python, Вы писали:
KP>Именно. И как ты в таком массиве найдешь что-то за константное время?
Ну да...
Вот собственно и хотел спросить, как лучше
Как раз оптимизация по памяти тоже была бы к стати и поэтому представление диапазона в виде битового массива вариант подходящий.
Остался поиск и изменение состояний портов.
Здравствуйте, -prus-, Вы писали:
P>Как раз оптимизация по памяти тоже была бы к стати и поэтому представление диапазона в виде битового массива вариант подходящий. P>Остался поиск и изменение состояний портов.
Здравствуйте, -prus-, Вы писали:
P>Как раз оптимизация по памяти тоже была бы к стати и поэтому представление диапазона в виде битового массива вариант подходящий. P>Остался поиск и изменение состояний портов.
В таком случае всё же посоветую использовать segment tree. Детали реализации для разных процессоров могут немного отличаться, но, например, на x86-64 эта структура данных требует аж на 1.75% больше памяти чем соответствующий битовый массив. Зато позволяет находить положение бита за три обращения к памяти и за три вызова инструкции типа bsf (+немного битовой магии) в худшем случае. Разумеется изменение бита делается за те же три обращения. А тест — за одно — так же как и в битовом массиве (что неудивительно, ибо segment tree и строит индекс вокруг этого массива).
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>А какое вам нужно ограничение по памяти, если 128К — это приемлимо?
Вполне хватит, думаю . Даже много...
Вообще если брать весь диапазон от 0 до 65535, то это получается 65536 бит = 8192 байт = 8 кбайт. Т.е.
8 кбайт получается за глаза.
Здравствуйте, -prus-, Вы писали:
P>Вполне хватит, думаю . Даже много... P>Вообще если брать весь диапазон от 0 до 65535, то это получается 65536 бит = 8192 байт = 8 кбайт. Т.е. P>8 кбайт получается за глаза.
— это понятно. А можно еще Zip-ом пройтись и еще меньше будет... Я просто думаю можно ли в вашем случае быстрее чем log(N) сделать, за счет памяти. Вам же вроде скорость важна.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP> — это понятно. А можно еще Zip-ом пройтись и еще меньше будет... Я просто думаю можно ли в вашем случае быстрее чем log(N) сделать, за счет памяти. Вам же вроде скорость важна.
Легко сделать O(1), если воспользоваться стеком/списком.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>А как вы будете порт с заданным номером N удалять из списка или стека за O(1)?
Я начну с чтения хотелки ТС. В ней сказано: "механизм, который позволит максимально быстро ваще прям за минимум тактов искать свободный порт в диапазоне?". Из чего сделаю вывод — нужен любой (в моем решении самый первый) свободный порт в диапазоне, так как необходимость поиска конкретного порта в хотелке никак не обозначена. А доступ к первому элементу списка/стека константный
искать свободный порт в диапазоне? Фактически искать 0 в крупном таком битовом массиве получается чтоль...
А ты вопрос ТС читал?
