Замечания и предложения

Среда PascalABC.NET
#2102

Он в этом режиме достаточно давно уже почти ничего не видит. Но со временем починят, думаю, это сейчас не самое главное.

#2103

А это кстати вообще не правда, я только сейчас понял - в паскале адрес это @, а & к адресам относится только в Си-подобных языках.

#2104

Вот и поговорили, вот и славно! )))

#2105

А, да, точно ))

#2106

Так должно быть?

image
image1920×1080 142 KB

#2107

Исправили

1 лайк
#2108

Предлагаю в стандартную библиотеку добавить кэш для мемоизации:

unit memoization;

type fCache<T,R> = class 
   private
     cache: Dictionary<T,R>;
     f: Func<T,R>;
     procedure setValue(key:T;value:R) := cache[key] := value;
     function getValue(key:T):R; begin
       if not cache.TryGetValue(key, Result) then begin
         Result := f(key);
         cache[key] := Result;
       end;
     end;
   public
     constructor(f:Func<T,R>); begin
       cache := new Dictionary<T,R>;
       Self.f := f;
     end;
     property Values[key:T]:R read getValue write setValue; default;
  end; 
end.

вызывать можно так:

uses memoization;

function fib(n:integer):integer;forward; // OldPascal-костыль 
var fibC := new fCache<integer,integer>(fib); // кэш
                    // ^^^^^^^ ^^^^^^^ нужен вывод типов
function fib(n:integer):integer :=
  n=0 ? 0 :
  n<=2 ? 1 :
  fibC[n-1] + fibC[n-2];  // << вызов через кэш
  
begin
  (0..46).Select(n->fib(n)).Print
end.

Обсуждение подходящего имени класса приветствуется

PS: я правильно понимаю, что этот код нужно писать из-за однопроходности компилятора, т.е. оптимизации под К580ВМ80?

function fib(n:integer):integer;forward; // OldPascal-костыль 
var fibC := new fCache<integer,integer>(fib); // кэш
                    // ^^^^^^^ ^^^^^^^ нужен вывод типов

и чтобы написать так:

var fibC := new fCache(fib); // кэш
function fib(n:integer):integer := ...

нужно менять архитектуру компилятора?

1 лайк
#2109

Вообще в идеале - сделать так:

uses memoization;

begin
  var c := new fCache<integer, integer>(n->
    n=0 ? 0 :
    n<=2 ? 1 :
      c[n-2] + c[n-1]
  );
end.

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

Ну а следующий лучший вариант это:

uses memoization;

begin
  var c: fCache<integer, integer>;
  c := new fCache<integer, integer>(n->
    n=0 ? 0 :
    n<=2 ? 1 :
      c[n-2] + c[n-1]
  );
  (0..46).Select(n->c[n]).Println;
end.
#2110

Да и, не могу не заметить, словарь из хеш-множества в данном случае совсем не подходит. Он эффективен когда хеш-коды ключей расположены не только равномерно, но и псевдо-случайно, иначе создание множества это лишняя работа.

Раз все числа (и равные им хеш-коды) идут последовательно - числа фибоначи это плохой пример для такого кэша. Их лучше сохранять в List<>.

Более хорошим примером будет, к примеру, любая задача где ключи - строки.

#2111

Вот такой пример есть. Это солвер для 19-21 ЕГЭ (Теория Игр). Для него и делалось. В качестве ключа используется кортеж двух целых

uses memoization;

type int2=(integer,integer);int=integer;

function moves(a,b:int):=|(a+1,b),(2*a,b),(a,b+1),(a,2*b)|;
function moves(heap:int2):=moves(heap[0],heap[1]);

function f(heap:int2):int;forward; 
var fc := new fCache<int2,int>(f); 

function f(heap:int2):int; begin 
  if (heap[0]+heap[1]<100) then begin
       var codes := moves(heap)
         .Select(el->fc[el]); 
       Result := 1 + if codes.Any(el->el.IsEven)
         then codes.Where(el->el.IsEven).Min
         else codes.Max;
  end;
end;

begin
  Range(90,1,-1).PrintLines(s->$'{s} : {f((9,s))}');
end.
#2112

А можно, пожалуйста, текст задачи?

#2113

не нашел именно эту задачу, но похожа на https://kpolyakov.spb.ru/school/ege/gen.php?action=viewTopic&topicId=3188 и солвер не полный. Далее нужно еще код дописывать. Этот солвер находит за сколько ходов можно выиграть (четные) или проиграть (нечетны значения функции).

#2114

Writeln ставит лишние переводы строк:

image
image1920×1040 32.8 KB

#2115

Это глюк IDE. Попробуйте Shift+F9 запускать. Не будет. Или нумерацию добавить в вывод и будет разрыв в разных местах.

#2116

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

#2117

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

#2118

Я отнюдь не утверждаю, что это все не нужно. Я лишь советую не напирать на то, что “Для него и делалось”, потому что это выглядит как частное решение.

#2119

Есть много фундаментальных вещей. Например, красно-чёрные деревья.

Для подобных вещей необходимо решить следующие вопросы:

  1. В каком модуле их описать
  2. Что ещё в этом модуле будет

Модуль ради одного класса делать - странно

#2120

2 сообщения было перемещено в эту тему: Помощь новичкам

#2121

У картинки гиперссылка неправильная.

image