(Добрый день!)

Имеется некое запоминающее устройство (ЗУ), позволяющее сохранять данные Д по адресам А.

Основное его свойство: определённые данные должны храниться только в одной ячейке (только одному адресу).

Поэтому, получив на входе данные Д и адрес А, ЗУ должно определить, не находятся ли уже Д в какой-нибудь ячейке. Если такая ячейка обнаружена, она очищается. А в ячейку с адресом А заносятся Д. (Если Д уже находятся по адресу А, то на ваш выбор — либо они перезаписываются, либо ничего не делается)

При чтении, на вход ЗУ поступают данные Д, по которым ЗУ должно обнаружить адрес А ячейки, где такие данные хранятся и возвратить этот адрес.

Требуется определить оптимальный алгоритм работы такого ЗУ.

PS1. Этих условий, имхо, достаточно для решения.
PS2. Не обязательно приводить готовую фотоматрицу для изготовления такого ЗУ.
Достаточно привести словестный алгоритм или программу-прототип.
PS3. Моя сама придумала.

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

M>Имеется некое запоминающее устройство (ЗУ), позволяющее сохранять данные Д по адресам А.

[остальное поскипано]

Если кроме сохранения данных ничего не нужно, то можно индексировать адреса A данными Д Тогда сохранение будет стоить O(1). Только чтение по адресу будет стоить O(|Д|)

А если серьезно, то что нужно оптимизировать? Время работы? Объем требуемой памяти? Какие операции с какой асимптотикой нужны?

Здравствуйте, m.a.g., Вы писали:

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

M>>Имеется некое запоминающее устройство (ЗУ), позволяющее сохранять данные Д по адресам А.

MAG>[остальное поскипано]

MAG>Если кроме сохранения данных ничего не нужно, то можно индексировать адреса A данными Д Тогда сохранение будет стоить O(1). Только чтение по адресу будет стоить O(|Д|)

MAG>А если серьезно, то что нужно оптимизировать? Время работы? Объем требуемой памяти? Какие операции с какой асимптотикой нужны?

Оптимизировать нужно всё! Время работы и объем требуемой памяти — одновременно.

Если серьёзно , то требуется предоставить оптимальные (я бы сказал наиболее оптимальные, но как меня уже раньше поправляли, оптимальные — это и есть наиболее) алгоритмы для тех операций, которые написаны в условии. См. также поскипанное PS1.

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


MAG>>А если серьезно, то что нужно оптимизировать? Время работы? Объем требуемой памяти? Какие операции с какой асимптотикой нужны?

M>Оптимизировать нужно всё! Время работы и объем требуемой памяти — одновременно.

Уточнение. Естественно, оптимизация по памяти не касается самого массива ячеек, а только описанных алгоритмов чтения и записи.

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

Еще до конца не въехал, но уже возникли вопросы:
1. Данные постоянной или пременной длины?
2. Какие опреации существуют над данными кроме сравнения (например, < >)?
3. Могут ли физически разные данные совпадать при сравнении? Например, сравнение строк в ignore case.

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

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

MP>Еще до конца не въехал, но уже возникли вопросы:
MP>1. Данные постоянной или пременной длины?

Можно считать, что постоянной. Т.е. размерность данных m бит, адреса n бит.

MP>2. Какие опреации существуют над данными кроме сравнения (например, < >)?

Сами данные можно считать целыми двоичными числами, с соответствующей арифметикой.

MP>3. Могут ли физически разные данные совпадать при сравнении? Например, сравнение строк в ignore case.

С учётом вышесказанного (данные — integer), нет, не могут.

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

M>PS2. Не обязательно приводить готовую фотоматрицу для изготовления такого ЗУ.

Уговорил, не буду.

Вот примерная схема — самая суть.
(Сравнение адресов рисовать не стал)

Ячейка памяти на 2 бита. (Один разряд адреса)
Наращиваешь — получаешь произвольную разрядность.



ЗЫ: Sorry за плохой C++

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

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

M>>PS2. Не обязательно приводить готовую фотоматрицу для изготовления такого ЗУ.

UgN>Уговорил, не буду.



UgN>Вот примерная схема — самая суть.
UgN>(Сравнение адресов рисовать не стал)

UgN>Ячейка памяти на 2 бита. (Один разряд адреса)
UgN>Наращиваешь — получаешь произвольную разрядность.

...

Красотишша какая!

Однако, извиняюсь, в этом решении есть некое излишество — оно решает больше задач, чем требовалось. Ещё раз извиняюсися.

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


M>Однако, извиняюсь, в этом решении есть некое излишество — оно решает больше задач, чем требовалось. Ещё раз извиняюсися.

В смысле излишество?

Тебе надо ЗУ, которое может записывать/читать данные по заданному адресу и получать адрес по заданным данным.
Вся остальная логика (чего там потереть) будет снаружи.
Или не так?

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

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

UgN>
M>>Однако, извиняюсь, в этом решении есть некое излишество — оно решает больше задач, чем требовалось. Ещё раз извиняюсися.

UgN>В смысле излишество?

UgN>Тебе надо ЗУ, которое может записывать/читать данные по заданному адресу и получать адрес по заданным данным.

Не совсем так.
Достаточно, чтобы при записи и при чтении, ЗУ вело себя так как описано.

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

M>Уточнение. Естественно, оптимизация по памяти не касается самого массива ячеек, а только описанных алгоритмов чтения и записи.

Оптимальным будет хранить не только данные по адресу, но и адрес по данным.

Пусть у нас есть массивы data и addr, размером, соответственно |addr| и |data|.

set(addr_, data_) = 
(
  data[addr[data_]] = null;
  addr[data_] = addr_;
  data[addr_] = data_;
)

get(addr_)
{
  return data[addr_];
}

Асимптотика операций: O(1)!

Здравствуйте, m.a.g., Вы писали:

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

M>>Уточнение. Естественно, оптимизация по памяти не касается самого массива ячеек, а только описанных алгоритмов чтения и записи.

MAG> Оптимальным будет хранить не только данные по адресу, но и адрес по данным.

Ну вот, подсказал.

Интересно, если б в условии ещё стояло: "несколько различных данных могут находиться по одному адресу" — это облегчило решение или только усложнило?

"Оптимальным будет хранить не только данные по адресу, но и адрес по данным."

Ещё оптимальнее будет хранить только адрес по данным! В условии ведь не сказано, что ЗУ должно уметь извлекать данные по адресу!

Вот ведь как бывает — достаточно поменять названия входов у самого обычного устройства, как оно начинает приобретать загадочные и запутанные свойства.

Итого:
Запись М[Д] <- А
Чтение Result <- М[Д]

MAG>Асимптотика операций: O(1)!

Атож!

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

M>Ещё оптимальнее будет хранить только адрес по данным! В условии ведь не сказано, что ЗУ должно уметь извлекать данные по адресу!

Только решение я написал еще вот тут

Автор: m.a.g.
Дата: 16.04.03

:

Если кроме сохранения данных ничего не нужно, то можно индексировать адреса A данными Д Тогда сохранение будет стоить O(1). Только чтение по адресу будет стоить O(|Д|)

Здравствуйте, m.a.g., Вы писали:

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

M>>Ещё оптимальнее будет хранить только адрес по данным! В условии ведь не сказано, что ЗУ должно уметь извлекать данные по адресу!

MAG> Только решение я написал еще вот тут

Автор: m.a.g.
Дата: 16.04.03

:

MAG>

MAG>Если кроме сохранения данных ничего не нужно, то можно индексировать адреса A данными Д Тогда сохранение будет стоить O(1). Только чтение по адресу будет стоить O(|Д|)

Ага. Та ещё было:
MAG>

MAG>А если серьезно, то что нужно оптимизировать? Время работы? Объем требуемой памяти? Какие операции с какой асимптотикой нужны?

Получается, что сам ответ был дан несерьёзно?

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

MAG>

MAG>А если серьезно, то что нужно оптимизировать? Время работы? Объем требуемой памяти? Какие операции с какой асимптотикой нужны?

M>Получается, что сам ответ был дан несерьёзно?

Ага. Просто думал, что задача не может быть такой легкой.

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

M>Итого:
M>Запись М[Д] <- А
M>Чтение Result <- М[Д]

Замечательно!
А теперь я, обычный юзер, прошу записать число 0xFFFFFFFF по адресу 0x00000000... И с удивлением обнаруживаю, что мне не хватает моих 512МБ!

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

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

M>>Итого:
M>>Запись М[Д] <- А
M>>Чтение Result <- М[Д]

MP>Замечательно!
MP>А теперь я, обычный юзер, прошу записать число 0xFFFFFFFF по адресу 0x00000000... И с удивлением обнаруживаю, что мне не хватает моих 512МБ!

Почему с удивлением?

"Всего на всех не хватает, потому, что всех — много, а всего — мало."

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


M>Почему с удивлением?

M>"Всего на всех не хватает, потому, что всех — много, а всего — мало."

Производители памяти должны тебе памятник при жизни поставить за такое решение!

M>Итого:
M>Запись М[Д] <- А
M>Чтение Result <- М[Д]

MP>Замечательно!
MP>А теперь я, обычный юзер, прошу записать число 0xFFFFFFFF по адресу 0x00000000... И с удивлением обнаруживаю, что мне не хватает моих 512МБ!

512МБ хватит! Т.к. нам адрес абсолютно не нужен, достаточно 1 бит выставлять!

Кстати, а зачем требовать от пользователя адрес передавать? Чтобы он окончательно запутался?

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

M>Имеется некое запоминающее устройство (ЗУ), позволяющее сохранять данные Д по адресам А.

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

ret