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

[TOTAL]

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

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

Будем считать, что не было никакой проблемы.

[nikvic]

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

Сразу видно, что способом venco ...— можно превратить в искомую.

У него не было отдельной записи для сохранения последней инициализации и не хватает детализации.

[_Ivana]

У него все было и всего хватает. И идея высказана в одной фразе - и всего достаточно, и все все понятно (и было понятно сразу без дополнительных пояснений). Единственные претензии к его предложению могут быть только насчет ограничения максимальной версии, и то можно себе позволить в такой модели один раз за $2^{32}$ версий и пробежаться по всему массиву - обнулить версии.

[Dave]

Вот реализация идеи venco в виде модуля Delphi:

Используется синтаксис Delphi

unit OftenInitArray;

interface

type
  TOftenInitArray<TElement> = class
  type
    TVersionedValue = record
      Value: TElement;
      Version: Cardinal;
    end;
  private
    FSize: Integer;
    FGlobalState: TVersionedValue;
    FArray: array of TVersionedValue;
    procedure ZeroVersions;
    procedure CheckIndex(Index: Integer);
    function GetElement(Index: Integer): TElement;
    procedure SetElement(Index: Integer; const NewValue: TElement);
  public
    constructor Create(Size: Integer; const InitialValue: TElement);
    property Element[Index: Integer]: TElement read GetElement write SetElement; default;
    procedure Initialize(const Value: TElement);
  end;

implementation

uses SysUtils;

procedure TOftenInitArray<TElement>.ZeroVersions;
var i:Integer;
begin
  for i:=0 to FSize-1 do
    FArray[i].Version:=0;
  FGlobalState.Version:=0;
end;

procedure TOftenInitArray<TElement>.CheckIndex(Index: Integer);
begin
  if (Index<0) or (Index>=FSize) then
    raise Exception.CreateFmt('Неправильный индекс массива: %d',[Index]);
end;

procedure TOftenInitArray<TElement>.Initialize(const Value: TElement);
begin
  FGlobalState.Value:=Value;
  try
    Inc(FGlobalState.Version);
  except
    on EIntOverflow do
    begin
      ZeroVersions;
      Inc(FGlobalState.Version);
    end;
  end;
end;

constructor TOftenInitArray<TElement>.Create(Size: Integer; const InitialValue: TElement);
begin
  FSize:=Size;
  SetLength(FArray, Size);
  ZeroVersions; // Можно удалить этот вызов отсюда в целях ускорения
  Initialize(InitialValue);
end;

function TOftenInitArray<TElement>.GetElement(Index: Integer): TElement;
begin
  CheckIndex(Index);
  with FArray[Index] do
    if Version=FGlobalState.Version then Result:=Value
                                    else Result:=FGlobalState.Value;
end;

procedure TOftenInitArray<TElement>.SetElement(Index: Integer;
  const NewValue: TElement);
begin
  CheckIndex(Index);
  with FArray[Index] do
  begin
    Value:=NewValue;
    Version:=FGlobalState.Version;
  end;
end;

end.

[arseniiv]

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

У него не было отдельной записи для сохранения последней инициализации

Как не было? Он сказал:

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

Надо увеличить версию массива на 1 и сохранить новое значение по умолчанию. При записи элемента ему присваивается версия массива и новое значение. При чтении если версия элемента меньше версии массива, значит берём дефолтное значение массива, иначе значение из самого элемента.

Т. е. хранятся массив пар (элемент, версия), значение по умолчанию, версия. Всё упомянуто. Я неправильно прочитал?

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

и не хватает детализации.

Какой ещё? Разве что при создании массива надо спрашивать и значение по умолчанию, и провести им инициализацию как описано. Это добавление должно бы закрыть все возможности неопределённого поведения; если вы не согласны, пожалуйста, скажите, почему.

[nikvic]

_Ivana в сообщении #697845 писал(а):

У него все было и всего хватает.

Перечитал и согласился

[cepesh]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.