Частое обновление массива.

[TOTAL]

nikvic в сообщении #697570 писал(а):

Работа с массивом" - три операции: читать элемент, записать значение в элемент, инициализировать всё значением.

Задача состоит в описании структуры, для которой все три укладываются в константу "времени", не зависящую от длины массива.

В каждый элемент массива (по каждому адресу) требуется записать новое число. Да или нет?

[venco]

nikvic в сообщении #697570 писал(а):

Или поясните, что значит "версия".

К каждому значению положить рядом ещё одно число - версию. Памяти да, понадобится больше, например в два раза, ну так это всегда так: хочется быстрее - добавь памяти.

[nikvic]

venco в сообщении #697572 писал(а):

К каждому значению положить рядом ещё одно число - версию.

Ок. Ещё и пару "значение-версия" рядом со всем массивом.
Осталось детализировать работу с такой структурой.

[TOTAL]

nikvic в сообщении #697574 писал(а):

Осталось детализировать работу с такой структурой.

Осталось признаться, что массив не обновляется.

[nikvic]

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

[TOTAL]

nikvic в сообщении #697671 писал(а):

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

Тогда ответьте на вопрос: каждый элемент массива должен измениться на новый или нет?

[nikvic]

(Оффтоп)

Вы хотите решение? ""Их есть у меня

Сама структура описана.

[TOTAL]

nikvic в сообщении #697685 писал(а):

(Оффтоп)

Вы хотите решение? ""Их есть у меня

Сама структура описана.

Что понимаете под инициализацией массива? Вы сами начали с инициализации, а теперь не хотите объяснять, что под ней понимаете. Так что задача Ваша выглядит так: сделай то, не скажу, что, но чтобы это не зависело от длины массаива.

[nikvic]

TOTAL в сообщении #697691 писал(а):

Вы сами начали с инициализации, а теперь не хотите объяснять, что под ней понимаете.

Под инциализацией "значением" я понимаю такое действие со структурой, что последующие операции "читать из места" дают это значение - если, конечно, в промежутке в это место не записано другое значение.

[TOTAL]

nikvic в сообщении #697695 писал(а):

Под инциализацией "значением" я понимаю такое действие со структурой, что последующие операции "читать из места" дают это значение - если, конечно, в промежутке в это место не записано другое значение.

Действия с какой структурой? Лично я в последний раз подожду вменяемой формулировки.

[nikvic]

(Оффтоп)

Собеседование в Yahoo Вы не прошли

[TOTAL]

nikvic в сообщении #697702 писал(а):

(Оффтоп)

Собеседование в Yahoo Вы не прошли

(Оффтоп)

Спросите в Yahoo, о чем задача, если сами не можете сформулировать.

[arseniiv]

Давайте я формализую структуру nikvic.

Есть структура данных, хранящая $n$ элементов (для удобства, а то и так много писать) с типом $A_n$ (у индексов тип $I_n$, у значений — $V$) и три операции:

• $\mathrm{init}(a : A_n, v : V) : A_n$,
• $\mathrm{set}(a : A_n, i : I_n, v : V) : A_n$,
• $\mathrm{get}(a : A_n, i : I_n) : V$.

Эти операции должны удовлетворять следующим соотношениям:

1. $\mathrm{get}(\mathrm{set}(a, i, v), j) = \mathop\mathbf{if} i=j \mathrel\mathbf{then} v \mathrel\mathbf{else} \mathrm{get}(a, j)$,
2. $\mathrm{get}(\mathrm{init}(a, v), j) = v$.

И даже вроде больше никаким.

И, конечно, каждая их них должна вычисляться за $O(1)$ времени относительно $n$.

Не обязательно такая структура должна иметь в своём воплощении какие-нибудь массивы.

Сразу видно, что способом venco любую структуру, реализующую $\mathrm{get}$ и $\mathrm{set}$ с временной сложностью $O(1)$ — а не только массив — можно превратить в искомую.

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

[TOTAL]

arseniiv в сообщении #697801 писал(а):

Есть структура данных, хранящая $n$ элементов (для удобства, а то и так много писать) с типом $A_n$ (у индексов тип $I_n$, у значений — $V$) и три операции:

• $\mathrm{init}(a : A_n, v : V) : A_n$,
• $\mathrm{set}(a : A_n, i : I_n, v : V) : A_n$,
• $\mathrm{get}(a : A_n, i : I_n) : V$.

Эти операции должны удовлетворять следующим соотношениям:

1. $\mathrm{get}(\mathrm{set}(a, i, v), j) = \mathop\mathbf{if} i=j \mathrel\mathbf{then} v \mathrel\mathbf{else} \mathrm{get}(a, j)$,
2. $\mathrm{get}(\mathrm{init}(a, v), j) = v$.

А теперь вместо этой лабуды условие русским языком.

[arseniiv]

То русское, что было в начале, из-за понятности мне я не могу перевести ещё раз.