Оптимизировать работу готового кода для задачи

Рейтинг: -3Ответов: 1Опубликовано: 11.03.2023

В строю отважной армии Сарумана друг за другом стоят n орков, рост i-го из них равен ai условных единиц. Новобранец-орк Гримморхус тоже собирается встать в этот строй, причём Саруману хочется поставить Гримморхуса на такую позицию p, чтобы f(p) = [количество орков левее Гримморхуса того же роста, что и Гримморхус] умножить на [количество орков правее Гримморхуса с ростом, не равным росту Гримморхуса] было максимально. Для этого Гримморхус может встать в начало строя, в её конец, или между любыми двумя соседними орками. К сожалению ни Гримморхус, ни Саруман не могут точно вспомнить рост Гримморхуса, у них есть только m предположений о том, каким он может быть, и для каждого из них они хотели бы знать оптимальную позицию, на которую Гримморхусу стоило бы встать.

Описание входных данных

В первой строке даны n целых чисел ai - рост орков, стоящих в строю Во второй строке даны m целых чисел xi - предполагаемый рост Гримморхуса

Описание выходных данных

В единственной строке выведите выведите m целых чисел - значение f(p) в оптимальной для данного роста позиции.

Формат ввода

1 1 2 2 2 2 1 1 1 1 2 1

Формат вывода

8 12 8

Вот мой код, но он не проходит тест по времени :

n = list(map(int, input().split()))
m = list(map(int, input().split()))


def f(a, p):
    left = sum(1 for i in range(p) if a[i] == a[p])
    right = sum(1 for i in range(p + 1, len(a)) if a[i] != a[p])
    return left * right


for x in m:
    max_val, max_pos = -1, -1
    for i in range(len(n) + 1):
        val = f(n[:i] + [x] + n[i:], i)
        if val > max_val:
            max_val, max_pos = val, i
    print(max_val, end=' ')
python алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 0

Что если 0) создать хеш таблицу если вдруг в m есть дубликаты чтобы повторно не считать

  1. создать структуру типа record для одного орка с полями рост и индекс в строю
  2. на входе отсортировать по росту 1го уровня и индексу встрою 2го уровня алг. быстрой сортировки она f(log/2)
  3. в цикле m ростов каждый отдельный рост найти в списке с п2. бинарным поиском
  4. полученый индекс с 3п. преобразовать в список одних ростов. цикл вверх пока рост<>List[i].рост i_min цикл вниз пока рост<>List[i].рост i_max
  5. сейчас у нас есть список всех одинаковых ростов причем мы знаем еще и их индексы в строю и они все одном списке отсортированы по индексу вверх пусть этот список завется Lsort
  6. далее пока не придумал как лучше узнать точную позицию т.к здесь уже магия математики но проход в лоб всегда спасет

    1. в цикле Lsort если поставить юнита в индекс Lsort[0].индекс то слева будет кол-во 0 т.к все одинаковые роста уже в списке и ниже Lsort[0].индекс-1 точно такого
      роста нет а справа кол-во (n.count - Lsort.Count) очевидно что умножение даст 0

      если поставить юнита в индекс Lsort1.индекс слева точно 1 а справа с = n.count - (Lsort1.индекс + (Lsort.Count - 1) ) умножение даст с

      если поставить юнита в индекс Lsort[2].индекс слева точно 2 а справа с2 = n.count - (Lsort[2].индекс + (Lsort.Count - 2) ) умножение даст с * 2

ну подумать о том какие ваши вызываемые методы могут оч долго работать мб это split мб sum мб ареей постоянно выделяет память по 1 элементу

в вашем коде сложность чутли ни кубическая тута линейная

сегодня еще немного покумекал и пришел к тому что можно уйти от линейной сложности и придти к логарифмической мб даже log(log(n-m))

если взять тест например рост 2 и прогнать по строю в котором 1млм а потом результаты позиций вывести на график то получится парабола с экстемумом в +- в центре. спрашивается зачем тогда весь цикл перебирать если ответ где-то в центре. Вот мне интересно эта откуда такие задачи берутся если люди идут искать ответы на форумах причем не в единичном случаи. Собес на работу что ли? вот лично у меня 520 строк кода правда не питоне и то не все сделано. Наверно еще стока же надо написать что бы m,n = 10млм за 0.015 решалось. Сама ржака если это новичкам задают.

Закину свой код мб кому интересно.

Результаты n = 100 000 m = 100 000 time 5ms

n = 1 000 000 m = 1 000 000 time 35ms

n = 10 000 000 m = 10 000 000 time 350ms

можно кончено с 350 до 250 оптимизировать если забить на читаемость а если на asm написать думаю будет 150-200ms сложность O(m+n)

в комментах я писал про срез, именно в этом коде он не особо помогает макс. 10-20 мс выигрывает на 3е тесте

unit uOrk;

interface

uses
  System.SysUtils,
  System.Classes,
  System.Diagnostics,
  Math;

type

  TDiagnosticTime = record
  private
    F: TStopwatch;
  public
    procedure Start;
    function Stop(): string;
  end;

  TArrayInt = TArray<integer>;

  // обычный список integer
  TListInt = class
  private
    FList: TArrayInt;
    FCount: integer;
    function CapacityGet: integer;
    procedure CapacitySet(const Value: integer);
    procedure ListSet(const Value: TArrayInt);
    function ItemsGet(Index: integer): integer; inline;
  public
    procedure Add(Value: integer);
    property Capacity: integer read CapacityGet write CapacitySet;
    property List: TArrayInt read FList write ListSet;
    property Items[index: integer]: integer read ItemsGet; default;
    property Count: integer read FCount;
    procedure Clear;
    procedure FillRandom(ACount, AMin, AMax: integer);
    procedure Fill(ACount: integer);
    procedure FillMod(ACount, AMod: integer);
    procedure SaveToFileTxt(FileName: string);
    procedure LoadFromFileTxt(FileName: string);
    procedure SaveToFile(FileName: string);
    procedure LoadFromFile(FileName: string);
    function SaveToString: string;
    constructor Create;
    destructor Destroy; override;
  end;

  // таблица по ключу роста
  TTabl = class
  private
    FList: TArray<TListInt>;
    function IndexsGet(const Height: byte): TListInt;
  public
    procedure Add(Height: byte; Index: integer);
    property Indexs[const Height: byte]: TListInt read IndexsGet;
    constructor Create;
    destructor Destroy; override;
  end;

  /// / кэщирование позиции ответа для повторяющихся ростов
  TTablCache = class
  private
    FList: TArrayInt;
    function IndexGet(const Height: byte): integer;
  public
    procedure Add(Height: byte; Index: integer);
    property Index[const Height: byte]: integer read IndexGet;
    constructor Create;
    destructor Destroy; override;
  end;

   // класс алгоритма
  TAlg = class
  private
    FTabl: TTabl;
    FTablCache: TTablCache;
    FTime: TDiagnosticTime;
    FTimeReturn: string;
    procedure InitTabl(Heights: TListInt);
    procedure ValueByteError;
    procedure ValueByteCheck(Value: integer);
    function GetPosInternal(Heights: TListInt; Height: byte): integer;
    function GetPosCaching(Heights: TListInt; Height: byte): integer;
  public
    procedure Main(Heights, Variants, VariantsReturn: TListInt);
    property Time: string read FTimeReturn;
    constructor Create;
    destructor Destroy; override;
  end;

implementation

{ TOrkAlgSplice }

constructor TAlg.Create;
begin
  inherited;
  FTabl := TTabl.Create;
  FTablCache := TTablCache.Create;
end;

destructor TAlg.Destroy;
begin
  FreeAndNil(FTabl);
  FreeAndNil(FTablCache);
  inherited;
end;

procedure TAlg.Main(Heights, Variants, VariantsReturn: TListInt);
var
  i, v: integer;
begin
  FTime.Start;
  try
    VariantsReturn.Capacity := Variants.Count;
    InitTabl(Heights);
    for i := 0 to Variants.Count - 1 do
    begin
      v := Variants[i];
      ValueByteCheck(v); // если в  Variants только байты то можно закомментить строку
      VariantsReturn.Add(GetPosCaching(Heights, v));
    end;
  finally
    FTimeReturn := FTime.Stop;
  end;
end;

function TAlg.GetPosCaching(Heights: TListInt; Height: byte): integer;
begin
  Result := FTablCache.Index[Height];
  if Result < 0 then
  begin
    Result := GetPosInternal(Heights, Height);
    FTablCache.Add(Height, Result);
  end;
end;

function TAlg.GetPosInternal(Heights: TListInt; Height: byte): integer;
var
  Indexs: TListInt;
  i, mn, mx: integer;
  rw, left, rigth, max: int64;
  p: integer;
begin

  Result := 0;
  max := 0;

  Indexs := FTabl.Indexs[Height];
  if false then
  begin
    p := 10; // можно тут срезку еще сделать p процент срезки можно сделать динамическим со срезкой время 2 двое сократится
    p := Indexs.Count * p div 100;
    mn := Math.max((Indexs.Count - 1) div 2 - p, 0);
    mx := Math.Min((Indexs.Count - 1) div 2 + p, Indexs.Count - 1);
  end
  else
  begin
    mn := 0;
    mx := Indexs.Count - 1;
  end;

  for i := mn to mx do
  begin
    left := i + 1;
    rigth := Heights.Count - (Indexs[i] + 1 + (Indexs.Count - left));
    rw := left * rigth;
    // Test.Add(left.ToString +' '+ (POrk(Lbuf[i]).Index +1).Tostring);
    if rw > max then
    begin
      max := rw;
      Result := Indexs[i] + 1;
    end;
  end;
end;

procedure TAlg.InitTabl(Heights: TListInt);
var
  i, v: integer;
begin
  // этот метод на asm надо написать
  for i := 0 to Heights.Count - 1 do
  begin
    v := Heights[i];
    ValueByteCheck(v); // если в  Heights только байты то можно закомментить строку
    FTabl.Indexs[byte(v)].Add(i);
  end;
end;

procedure TAlg.ValueByteError;
begin
  raise Exception.Create
    ('Error TOrkAlgSplice.ValueByteError рост не может быть больше 255');
end;

procedure TAlg.ValueByteCheck(Value: integer);
begin
  if Value <> byte(Value) then
    ValueByteError;
end;









{ TdDiagnosticTime }

procedure TDiagnosticTime.Start;
begin
  F := TStopwatch.Create;
  F.Start;
end;

function TDiagnosticTime.Stop(): string;
begin
  F.Stop;
  Result := F.ElapsedMilliseconds.ToString + ' ms';

end;

{ TListInt }

constructor TListInt.Create;
begin
  inherited;
  FList := nil;
  FCount := 0;
end;

destructor TListInt.Destroy;
begin
  FList := nil;
  inherited;
end;

procedure TListInt.Add(Value: integer);
begin
  if FCount >= Capacity then
    Capacity := Capacity + 10000;
  FList[FCount] := Value;
  inc(FCount);
end;

function TListInt.CapacityGet: integer;
begin
  Result := Length(FList);
end;

procedure TListInt.CapacitySet(const Value: integer);
begin
  // if Value<0 then  raise Exception.Create('Error TListInt.CapacitySet Value<0');
  if Value > Length(FList) then
    setlength(FList, Value);
end;

procedure TListInt.Clear;
begin
  FCount := 0;
end;

procedure TListInt.ListSet(const Value: TArrayInt);
begin
  FList := Value;
  FCount := Capacity;
end;

procedure TListInt.FillRandom(ACount, AMin, AMax: integer);
var
  i: integer;
begin
  self.Clear;
  self.Capacity := ACount;
  for i := 0 to ACount - 1 do
    Add(Math.RandomRange(AMin, AMax));
end;

procedure TListInt.Fill(ACount: integer);
var
  i: integer;
begin
  self.Clear;
  self.Capacity := ACount;
  for i := 0 to ACount - 1 do
    Add(i);
end;

procedure TListInt.FillMod(ACount, AMod: integer);
var
  i: integer;
begin
  self.Clear;
  self.Capacity := ACount;
  for i := 0 to ACount - 1 do
    Add(i mod AMod);
end;

function TListInt.ItemsGet(Index: integer): integer;
begin
  Result := List[index];
end;

procedure TListInt.LoadFromFile(FileName: string);
var
  F: TFileStream;
  ACount: integer;
begin
  self.Clear;
  F := TFileStream.Create(FileName, fmOpenRead);
  try
    F.Position := 0;
    if F.Size mod sizeof(integer) <> 0 then
      raise Exception.Create
        ('Error TListInt.LoadFromFile F.Size mod  sizeof(integer) <> 0 не валидный файл');
    ACount := F.Size div sizeof(integer);
    self.Capacity := ACount;
    if ACount > 0 then
      F.ReadBuffer(FList[0], sizeof(integer) * ACount);
    FCount := ACount;
  finally
    F.Free;
  end;
end;

procedure TListInt.SaveToFile(FileName: string);
var
  F: TFileStream;
begin
  F := TFileStream.Create(FileName, fmCreate);
  try
    F.Size := 0;
    if FCount > 0 then
      F.WriteBuffer(FList[0], sizeof(integer) * FCount);
  finally
    F.Free;
  end;
end;

procedure TListInt.LoadFromFileTxt(FileName: string);
var
  F: TStringlist;
  i: integer;
begin
  F := TStringlist.Create;
  try
    F.LoadFromFile(FileName);
    self.Capacity := F.Count;
    for i := 0 to F.Count - 1 do
      Add(StrToIntDef(F[i], 0));
  finally
    F.Free;
  end;
end;

procedure TListInt.SaveToFileTxt(FileName: string);
var
  F: TStringlist;
  i: integer;
begin
  F := TStringlist.Create;
  try
    for i := 0 to Count - 1 do
      F.Add(Items[i].ToString);
    F.SaveToFile(FileName);
  finally
    F.Free;
  end;
end;

function TListInt.SaveToString: string;
var
  P: TStringBuilder;
  i: integer;
begin
  P := TStringBuilder.Create;
  try
    for i := 0 to Count - 1 do
      P.Append(Items[i].ToString).Append(' ');
    Result := P.ToString;
  finally
    P.Free;
  end;
end;

{ TTablItem }

constructor TTabl.Create;
var
  i: integer;
begin
  inherited;
  setlength(FList, byte.MaxValue + 1);
  for i := 0 to Length(FList) - 1 do
    FList[i] := TListInt.Create;
end;

destructor TTabl.Destroy;
var
  i: integer;
begin
  for i := 0 to Length(FList) - 1 do
    FreeAndNil(FList[i]);
  FList := nil;
  inherited;
end;

procedure TTabl.Add(Height: byte; Index: integer);
begin
  FList[Height].Add(Index);
end;

function TTabl.IndexsGet(const Height: byte): TListInt;
begin
  Result := FList[Height];
end;

{ TTablCache }
constructor TTablCache.Create;
var
  i: integer;
begin
  inherited;
  setlength(FList, byte.MaxValue + 1);
  for i := 0 to Length(FList) - 1 do
    FList[i] := -1;
end;

destructor TTablCache.Destroy;
begin
  FList := nil;
  inherited;
end;

procedure TTablCache.Add(Height: byte; Index: integer);
begin
  FList[Height] := Index;
end;

function TTablCache.IndexGet(const Height: byte): integer;
begin
  Result := FList[Height];
end;

end.

введите сюда описание изображения