Решаю тут задачки, чтобы мозгами медленнее сохнуть. Нарешал уже мильйон. Но вот эту даже понять не могу условия.
Задачка программистская. Гуглить решения НЕ НАДО, именно поэтому я спрашиваю не у гугла, а у вас, уважаемые товарищи-братья.
Give a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space.
Что они хотят, блин?
Здравствуйте, Kore Sar, Вы писали:
KS>Здравствуйте, Nikkk2010, Вы писали:
N>>Здравствуйте, Kore Sar, Вы писали:
N>>Один из возможных вариантов перевода:
N>>Предоставте удовлетворительную структуру данных для представления n очередей (n не фиксировано) в конечном сегменте памяти.
N>>Любая очередь может быть представлена некоторой своей специфичной структурой данных.
N>>Попробуйте использовать не менее 90% объема памяти.
KS>Спасибо! Но теперь и на русском мало чего понимаю.
Это потому что перевод такой (не в обиду Нику будет сказано).
«Придумайте способ, которым можно организровать несколько очередей на базе одного заранее выделенного буфера памяти. Число очередей задаётся пользователем.
Вам разрешается разместить в этом же буфере, для каждой из очередей, структуру данных, описывающую очередь в целом. Постарайтесь использовать не менее 90% от доступного объёма памяти.
Ответом на задачу является описание разработанных структур данных. Методы работы с данными писать не требуется».
Здравствуйте, b-3, Вы писали:
b-3>Здравствуйте, Kore Sar, Вы писали:
KS>>Здравствуйте, Nikkk2010, Вы писали:
N>>>Здравствуйте, Kore Sar, Вы писали:
N>>>Один из возможных вариантов перевода:
N>>>Предоставте удовлетворительную структуру данных для представления n очередей (n не фиксировано) в конечном сегменте памяти.
N>>>Любая очередь может быть представлена некоторой своей специфичной структурой данных.
N>>>Попробуйте использовать не менее 90% объема памяти.
KS>>Спасибо! Но теперь и на русском мало чего понимаю.
b-3>Это потому что перевод такой (не в обиду Нику будет сказано).
b-3>b-3>«Придумайте способ, которым можно организровать несколько очередей на базе одного заранее выделенного буфера памяти. Число очередей задаётся пользователем.
b-3>Вам разрешается разместить в этом же буфере, для каждой из очередей, структуру данных, описывающую очередь в целом. Постарайтесь использовать не менее 90% от доступного объёма памяти.
b-3>Ответом на задачу является описание разработанных структур данных. Методы работы с данными писать не требуется».
Прекрасно! Теперь всё понятно.
Премного благодарствую. Надо, типа, файловую систему продумать.
Но, вот только, откуда вы взяли последние два предложения? Это, в принципе, не важно. Но интерес почему-то у меня возник.
Здравствуйте, Kore Sar, Вы писали:
KS>Здравствуйте, b-3, Вы писали:
b-3>>Здравствуйте, Kore Sar, Вы писали:
KS>>>Здравствуйте, Nikkk2010, Вы писали:
N>>>>Здравствуйте, Kore Sar, Вы писали:
N>>>>Один из возможных вариантов перевода:
N>>>>Предоставте удовлетворительную структуру данных для представления n очередей (n не фиксировано) в конечном сегменте памяти.
N>>>>Любая очередь может быть представлена некоторой своей специфичной структурой данных.
N>>>>Попробуйте использовать не менее 90% объема памяти.
KS>>>Спасибо! Но теперь и на русском мало чего понимаю.
b-3>>Это потому что перевод такой (не в обиду Нику будет сказано).
b-3>>b-3>>«Придумайте способ, которым можно организровать несколько очередей на базе одного заранее выделенного буфера памяти. Число очередей задаётся пользователем.
b-3>>Вам разрешается разместить в этом же буфере, для каждой из очередей, структуру данных, описывающую очередь в целом. Постарайтесь использовать не менее 90% от доступного объёма памяти.
b-3>>Ответом на задачу является описание разработанных структур данных. Методы работы с данными писать не требуется».
KS>Прекрасно! Теперь всё понятно. Премного благодарствую. Надо, типа, файловую систему продумать.
KS>Но, вот только, откуда вы взяли последние два предложения? Это, в принципе, не важно. Но интерес почему-то у меня возник.
Give a good data structure for X" = "Придумайте способ, которым можно X. Ответом на задачу является описание разработанных структур данных. Методы работы с данными писать не требуется".
Типа, литературный перевод, потому что "предложите структуру данных для" в русских задачниках в данном смысле не встречается. Под "data structure" имеется в виду организация данных целиком, с учётом стратегий аллокации, резервирования и т.д., а русский дословный перевод, "структура данных", можно понять как "написали struct A { A* next; }; и успокоились". Соотвественно при дословном переводе этот смысл терялся, и я его восстановил добавлением последних двух предложений.
Здравствуйте, Kore Sar, Вы писали:
KS>Прекрасно! Теперь всё понятно. Премного благодарствую. Надо, типа, файловую систему продумать.
Зачем файловую систему?
Отображение номер -> очередь. Это может быть вектор, мап или даже список (если n невелико, то линейный забег по списку будет стоить дёшево).
Кстати, смотря какая задача ставится. Упор на скорость, память, простоту кодирования...
Можно, например, сделать мап (номер,время)->данные.
Добавление в очередь K — это добавление нового элемента с ключом (K,T++), где T — глобальный счётчик.
Извлечение из очереди K — это поиск lower bound для (K,+oo) и проверка, что ключ найденного элемента — это (K,_).
Для полноценной утилизации памяти — хранить мап не в бинарном дереве, а в B-дереве.
А можно сделать двухслойное B-дерево, в котором верхний слой — это мап номер->очередь, а нижний — собственно очередь.
Единственная проблема здесь в том, что хвосты блоков, отведённых под мап, являются балластом и не могут использоваться для хранения данных очередей.
То есть, при известной ловкости рук, у нас может получиться не заявленное 90%, а близко к 0%.
Из задачи неясно, определяется ли n на стадии инициализации или может меняться в ходе работы.
Если на стадии инициализации — так вообще конфета: создаём в начале блока памяти массив очередей, а оставшееся место отводим под общую для этих очередей кучу.
Перекуём баги на фичи!
