Устройство для упорядочивания объектов

Авторы патента:

G06F7/24 - сортировка, т.е. отбор данных с одного или нескольких носителей информации, перегруппировка этих данных в определенную числовую или иную последовательность и перезапись отсортированных данных на этих же или других носителях информации (G06F 7/36 имеет преимущество)

ОПИСАЙИЕ

ИЗОБРЕТЕНИЯ «1 467346

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 25.05.73 (21) 1922675/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15.04.75. Бюллетень № 14

Дата опубликования описания 06.08,75 (51) М. Кл. б 06f 7/24

Государственный комитет

Совета Министров СССР ло делам изобретений и открытий (53) УДК 681.14-523.8 (088.8) (72) Авторы изобретения

В. ф. Жиров, В. Л, Ли, А. А. Соколов и В. И. Смирнов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧИВАНИЯ ОБЪЕКТОВ

Изобретение относится к области вычислительной техники и может быть использовано в схемах управления буферными регистрами, в схемах управления узлами коммутации, в мультиплексорных схемах и т. д.

Известны устройства, реализующие упорядочение объектов, содержащие регистры, схемы записи, подключенные к регистрам, схему выборки, подключенную к регистрам, и схему сравнения.

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

Целью изобретения является сокращение объема аппаратуры при построении устройства упорядочивания для большого числа объектов. ,Поставленная цель достигается тем, что выход входного регистра соединен с первым входом схемы выборки, со вторым входом которой соединены выходы регистров очереди. Выход схемы выборки соединен со входом выходного регистра, выход которого соединен с первым входом первой схемы записи в регистры очереди, со вторым входом которой соединен выход регистра совпадений. Выход первой схемы записи соединен со входами регистров очереди. Выход входного регистра соединен со входом регистра начала очереди и с первым входом второй схемы записи, со вторым входом которой соединен выход регистра начала очереди. Выход второй схемы записи соединен со входами регистров очереди. Выход входного регистра соединен с первым входом схемы сравнения, со вторым входом которой соединены выходы регистров очереди, с третьим входом вЂ” выход регистра начала очереди, с четвертым входом вЂ” выход регистра конца

10 очереди, вход которого соединен с выходом регистра совпадений. Выход схемы сравнения соединен со входом регистра совпадений.

На чертеже представлена блок-схема устройства.

15 Предлагаемое устройство содержит входной регистр 1, схему выборки 2, регистры очереди

3, выходной регистр 4, первую схему записи 5, регистр совпадений 6, вторую схему записи 7, регистр начала очереди 8, схему сравнения 9

20 и регистр конца очереди 10.

Количество элементов У предлагаемого устройства может быть приближенно равно:

N = n.log,ï, 25 в то же время для устройства фиксации приоритета информации и объектов:

N = nàj 2

Каждому объекту ставится в соответствие

З0 регистр очереди, т. е. номер объекта равен но10

0- 2- 3- 1.

60 меру регистра очереди. Для отображения упорядоченности объектов в регис;р очереди, соответствующий данному объекту, помещается номер того объекта, который в очереди непосредственно следует за данным объектом.

В двух регистрах указываются номера объектов, находящихся в начале и в конце очереди, эти регистры называются соответственно регистрами начала и конца очереди.

Для упрощения описания работы устройства принимаются некоторая конкретная очередь для четырех объектов.

Для этого упорядоченность объектов представляется следующей строкой 2 0 3 1, где целое число указывает номер объекта, т. е. в начале очереди стоит второй объект, затемвЂ” нулевой, затем вЂ” третий, а в конце вЂ” первый.

В таком случае регистры очереди РО; (где

i=0, 1, 2, 3) содержат следующие номера:

РО, 3) РО, Х,РО, 0>РО, 1) где Х вЂ” объект, находящийся в конце очереди, P O вЂ” регистр очереди.

Содержимое регистра конца очереди в данном случае равно: РК=1, содержимое регистра начала очереди вЂ” РН=2, где РК вЂ” регистр конца очереди, PH вЂ” регистр начала очереди. Перестройка очереди задается указанием номера объекта, который должен быть помещен в начало очереди, а упорядоченность остальных объектов сохраняется. Номер объекта, который должен быть помещен в начало очереди, устанавливается на входном регистре.

Предположим, что содержимое входного регистра 1 равно «О», т. е. очередь должна стать следующей:

Содержимое регистров также должно измениться:

PO,=2, РО,=Х, РО,=Ç, РО,=1, РН=О, РК=1.

Для рассматриваемого примера в начальный момент состояние регистров следующее:

РО,=З,РО,=Х,РО,= вЂ” О,Р0,=-1, РК=1, РН =2, и содержимое входного регистра 1 равно «О», следовательно, на выходной регистр выдается содержимое нулевого регистра очереди, т. е.

«3». Содержимое регистра совпадений равно

«2», так как «О» на входном регистре совпадает с «О» во втором регистре очереди (РО ).

Входной регистр 1 соединен со второй схемой записи 7, так что содержимое регистра начала очереди 8 записывается в тот регистр очереди

3, номер которого находится на входном регистре, так как объект, помер которого находится на входном регистре 1, должен быть поставлен в начало очереди, и содержимое любого данного регистра очереди указывает на объект, непосредственно следующий за данным объектом.

Для рассматриваемого примера регистр начала содержит «2», а входной регистр вЂ” «О», таким образом, в нулевой регистр очереди 3 записывается число «2» (РОС вЂ” вЂ” 2) .

Первая схема записи 5, записывая содержимое выходного регистра 4, равное «3», в регистр очереди 3, номер которого указан на регистре совпадений 6, равным «2», изменяет содержимое второго регистра очереди PO> вЂ” вЂ” 3.

Общая картина измененных регистров очереди выглядит следующим образом:

PO,=2, РО,=,Х, РО,=З, PO,=1.

Остается изменить содержимое регистра начала очереди 8, куда помещается содержимое входного регистра 1

РН= О.

Необходимость регистра конца очереди 10 ясна из следующей ситуации: пусть на каждом регистре появляется номер объекта, который состоит в конце очереди. Например, для очереди 203 вЂ” 1 появление на входном регистре «1» вызывает некоторые дополнительные действия. Регистр совпадений содержит вместе с номером регистра очереди 3, в котором содержится ссылка на конец очереди, и признак конца очереди, как результат сравнения входного регистра 1 с регистром конца очереди 10.

Под управлением признака конца очереди в регистр конца очереди 10 записывается содержимое регистра совпадений 6, равное «3».

Остальные действия выполняются как в предыдущем примере, так что от состояния регистров, представляемого:

РО,=З, РО,=Х, РО,=О, РО,=1, РН=2, РК =1, переходим к состоянию, представленному:

РОю =3 РО =2 РОа =О, РОз = Х, РН=1, РК=З.

Регистр начала очереди 8 также соединен схемой сравнения 9 с входным регистром 1 (при фиксации совпадения с регистром начала никаких действий по перестройке очереди не выполняется).

Предмет изобретения

Устройство для упорядочивания объектов, содержащее регистры, схемы записи, подключенные к регистрам, схему выборки, подключенную к регистрам, и схему сравнения, отл и ч а ю щ е е с я тем, что, с целью сокращения объема аппаратуры, выход входного регистра соединен с первым входом схемы выборки, со вторым входом которой соединены выходы регистров очереди, выход схемы выборки соединен со входом выходного регистра, выход которого соединен с первым входом первой схемы записи в регистры очереди, со вторым входом которой соединен выход регистра совпа467346

Составитель А. Козлин

Техред Т, Миронова

Редактор Е. Семанова

Корректор А. Степанова

Заказ 1810!2 Изд, Ко 1364 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5

Типография, пр. Сап нова, 2 дений, причем выход первой схемы записи соединен со входами регистров очереди, выход входного регистра вЂ” со входом регистра начала очереди и с первым входом второй схемы записи, со вторым входом которой соединен выход регистра начала очереди, выход второй схемы записи соединен со входами регистров очереди, выход входного регистра вЂ” с первым входом схемы сравнения, со вторым входом которой соединены выходы регистров очереди, с третьим входом вЂ” выход регистра начала очереди, с четвертым входом вЂ” выход регистра конца очереди, вход которого соединен с выходом регистра совпадений, причем выход схемы сравнения соединен со входом регистра совпадений.

Устройство для преобразования статистической информации, вводимой в запоминающее устройство // 398944

Преобразователь цифрового кода в единичный // 269602

Патент 259958 // 259958

Устройство для приел1а и регистрации информации // 249981

Устройство для выборки групп разрядов числа и сдвига этих групп или всего числа на заданное // 217719

Патент 174801 // 174801

Оптико-механическое устройство для расшифровки осциллограмм с применением регистратора цифровых значений расшифровываемых величин, каретки, несущей перо, и системы зеркал для отражения освещенной щели на расшифровываемую осциллограмму // 124154

Универсальный прибор для обработки эхограмм и записей показаний на рулонной бумаге // 119683

Устройство обращения циклического сдвига и обращенного перемежения данных // 2189629

Изобретение относится к устройству обращения циклического сдвига и/или обращенного перемежения данных

Устройство для выбора оптимальных решений методом наименьших расстояний // 2234732

Изобретение относится к области вычислительной техники и может быть использовано для выбора оптимальных решений из ряда возможных вариантов

Устройство и способ редактирования // 2252448

Изобретение относится к устройству и способу редактирования

Способ и устройство сортировки на основе в-дерева для больших объемов сейсмических данных // 2285276

Изобретение относится к области геофизики и может быть использовано при обработке больших объемов сейсмических данных в нефтяной промышленности

Устройство управляемой перестановки информации, хранимой в эвм // 2405187

Многоканальное устройство для выбора минимального значения средней величины // 744610

Многоканальное устройство для выбора минимального значения средней величины // 920740

Конвейер классификации данных, включающий в себя правила автоматической классификации // 2544752

Изобретение относится к средствам управления данными. Технический результат заключается в уменьшении времени обработки элементов данных. Обнаруживают элемент данных. Классифицируют элемент данных с использованием одного или более свойств, связанных с элементом данных, для формирования связанного с ним набора свойств классификации, причем эти одно или более свойств включают в себя имеющиеся свойства классификации, связанные с элементом данных, при этом элемент данных классифицируется одним или более компонентами классификации. Агрегируют наборы свойств классификации, когда элемент данных классифицируется двумя или более компонентами классификации. Применяют политику к элементу данных на основе по меньшей мере одного из набора свойств классификации и агрегированных наборов свойств классификации. 3 н. и 17 з.п. ф-лы, 6 ил., 1 табл.

Способ предоставления информационной поддержки разработчика программного обеспечения для микроконтроллеров и реализующая его система // 2553067

Изобретение относится к вычислительной технике. Технический результат заключается в ускорении процесса производства программного обеспечения для микроконтроллеров за счет повышения качества и скорости предоставления разработчику информационной поддержки. Способ предоставления информационной поддержки, в котором предоставляют поиск по техническим описаниям микроконтроллеров, по серверам RSS, по веб-серверам, предоставляют контекстную справку по элементам графического интерфейса среды разработки программного обеспечения, при этом из каждого файла технического описания микроконтроллера извлекается его структура, и элементы этой структуры объединяются по заранее заданным правилам в обобщающие разделы, после чего создают запись в базе данных, затем создают индексный файл, при этом структуру технического описания микроконтроллера и индекс его текстового содержимого хранят раздельно на сервере базы данных и сервере индексации соответственно. 2 н. и 1 з.п. ф-лы, 1 ил.

Способ и устройство для отображения прикладного программного обеспечения // 2636133

Изобретение относится к средствам для отображения прикладного программного обеспечения. Технический результат заключается в повышении точности ранжирования прикладного программного обеспечения. Получают по меньшей мере два параметрических коэффициента, указывающих информацию о прикладном программном обеспечении в течение установленного периода. Выводят индекс сортировки прикладного программного обеспечения в результате вычисления на основе по меньшей мере двух полученных параметрических коэффициентов. Сортируют прикладное программное обеспечение в соответствии с индексом сортировки и представление отсортированного прикладного программного обеспечения. При этом получение по меньшей мере двух параметрических коэффициентов, указывающих информацию о прикладном программном обеспечении в течение установленного периода, представляет собой: получение значения количества загрузок прикладного программного обеспечения в течение установленного периода и выполнение обработки значения количества загрузок путем умножения значения количества загрузок на (1/2)T, где Т - установленный период времени, с получением таким образом коэффициента количества загрузок, указывающего информацию о прикладном программном обеспечении в течение установленного периода. 2 н. и 14 з.п. ф-лы, 6 ил.