كيف أكتب وظيفة حفظ عامة؟

Question

أنا أكتب وظيفة للعثور عليها أرقام المثلث والطريقة الطبيعية لكتابتها هي بشكل متكرر:

function triangle (x)
   if x == 0 then return 0 end
   return x+triangle(x-1)
end

لكن محاولة حساب أول 100000 رقم مثلث تفشل مع تجاوز سعة المكدس بعد فترة.هذه هي الوظيفة المثالية ل حفظ, ، لكني أريد حلاً يحفظ أي وظيفة أقوم بتمريرها إليها.

Answer 1

أراهن أن شيئًا كهذا يجب أن يعمل مع قوائم الوسائط المتغيرة في Lua:

local function varg_tostring(...)
    local s = select(1, ...)
    for n = 2, select('#', ...) do
        s = s..","..select(n,...)
    end
    return s
end

local function memoize(f)
    local cache = {}
    return function (...)
        local al = varg_tostring(...)
        if cache[al] then
            return cache[al]
        else
            local y = f(...)
            cache[al] = y
            return y
        end
    end
end

ربما يمكنك أيضًا القيام بشيء ذكي باستخدام الجداول التعريفية باستخدام __tostring بحيث يمكن تحويل قائمة الوسيطات باستخدام tostring().اه الاحتمالات

Answer 2

لدى Mathematica طريقة بارعة بشكل خاص للقيام بالحفظ، بالاعتماد على حقيقة أن التجزئات واستدعاءات الوظائف تستخدم نفس البنية:

triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]

هذا كل شيء.إنه يعمل لأن قواعد استدعاءات وظائف مطابقة الأنماط هي أنها تستخدم دائمًا تعريفًا أكثر تحديدًا قبل تعريف أكثر عمومية.

بالطبع، كما تمت الإشارة إليه، هذا المثال له حل مغلق: triangle[x_] := x*(x+1)/2.أرقام فيبوناتشي هي المثال الكلاسيكي لكيفية إضافة الحفظ إلى التذكير مما يؤدي إلى تسريع كبير:

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

على الرغم من أن هذا أيضًا له معادل مغلق، وإن كان أكثر فوضوية: http://mathworld.wolfram.com/FibonacciNumber.html

أنا لا أتفق مع الشخص الذي اقترح أن هذا غير مناسب للحفظ لأنه يمكنك "مجرد استخدام حلقة".الهدف من الحفظ هو أن أي استدعاءات دالة متكررة تكون O(1) مرة.هذا أفضل بكثير من O(n).في الواقع، يمكنك حتى إعداد سيناريو حيث يكون أداء التنفيذ المحفوظ أفضل من تنفيذ النموذج المغلق!

Answer 3

أنت أيضًا تطرح السؤال الخطأ لمشكلتك الأصلية ;)

هذه طريقة أفضل لهذه الحالة:

مثلث(ن) = ن * (ن - 1) / 2

علاوة على ذلك، بافتراض أن الصيغة لا تحتوي على مثل هذا الحل الأنيق، فإن الحفظ سيظل أسلوبًا سيئًا هنا.سيكون من الأفضل لك كتابة حلقة بسيطة في هذه الحالة.يرى هذه الإجابة لمناقشة أكمل.

Answer 4

في C# 3.0 - بالنسبة للوظائف العودية، يمكنك القيام بشيء مثل:

public static class Helpers
{
    public static Func<A, R> Memoize<A, R>(this Func<A, Func<A,R>,  R> f)
    {
        var map = new Dictionary<A, R>();
        Func<A, R> self = null;
        self = (a) =>
        {
            R value;
            if (map.TryGetValue(a, out value))
                return value;
            value = f(a, self);
            map.Add(a, value);
            return value;
        };
        return self;
    }        
}

ثم يمكنك إنشاء دالة فيبوناتشي محفوظة مثل هذا:

var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));

Answer 5

في سكالا (لم يتم اختباره):

def memoize[A, B](f: (A)=>B) = {
  var cache = Map[A, B]()

  { x: A =>
    if (cache contains x) cache(x) else {
      val back = f(x)
      cache += (x -> back)

      back
    }
  }
}

لاحظ أن هذا يعمل فقط مع وظائف arity 1، ولكن مع الكاري يمكنك جعله يعمل.المشكلة الأكثر دقة هي ذلك memoize(f) != memoize(f) لأي وظيفة f.إحدى الطرق المخادعة جدًا لإصلاح ذلك ستكون كما يلي:

val correctMem = memoize(memoize _)

لا أعتقد أن هذا سيجمع، لكنه يوضح الفكرة.

Answer 6

تحديث:أشار المعلقون إلى أن الحفظ هو وسيلة جيدة لتحسين التكرار.من المسلم به أنني لم أفكر في هذا من قبل، لأنني أعمل عمومًا بلغة (C#) حيث لا يكون إنشاء الحفظ المعمم أمرًا تافهًا.خذ المنشور أدناه مع وضع حبة الملح هذه في الاعتبار.

أظن من المحتمل أن يكون لدى لوقا الحل الأنسب لهذه المشكلة، ولكن الحفظ ليس هو الحل بشكل عام لأي مشكلة تتعلق بتجاوز سعة المكدس.

عادةً ما يحدث تجاوز سعة المكدس بسبب التكرار بشكل أعمق مما يمكن للنظام الأساسي التعامل معه.اللغات تدعم في بعض الأحيان "العودية الذيل"، الذي يعيد استخدام سياق المكالمة الحالية، بدلاً من إنشاء سياق جديد للمكالمة العودية.لكن الكثير من اللغات/المنصات السائدة لا تدعم هذا.على سبيل المثال، ليس لدى لغة C# دعم متأصل للتكرار الخلفي.يمكن للإصدار 64 بت من .NET JITter تطبيقه كتحسين على مستوى IL، وهو أمر عديم الفائدة تمامًا إذا كنت بحاجة إلى دعم الأنظمة الأساسية 32 بت.

إذا كانت لغتك لا تدعم التكرار الخلفي، فإن أفضل خيار لك لتجنب تجاوزات المكدس هو إما التحويل إلى حلقة صريحة (أقل أناقة بكثير، ولكنها ضرورية في بعض الأحيان)، أو العثور على خوارزمية غير تكرارية مثل Luke المقدمة لهذه المشكلة.

Answer 7

function memoize (f)
   local cache = {}
   return function (x)
             if cache[x] then
                return cache[x]
             else
                local y = f(x)
                cache[x] = y
                return y
             end
          end
end

triangle = memoize(triangle);

لاحظ أنه لتجنب تجاوز سعة المكدس، سيظل المثلث بحاجة إلى البذر.

Answer 8

إليك شيء يعمل بدون تحويل الوسيطات إلى سلاسل.التحذير الوحيد هو أنه لا يمكنه التعامل مع حجة صفرية.لكن الحل المقبول لا يمكنه تمييز القيمة nil من السلسلة "nil", ، لذلك ربما يكون هذا جيدًا.

local function m(f)
  local t = { }
  local function mf(x, ...) -- memoized f
    assert(x ~= nil, 'nil passed to memoized function')
    if select('#', ...) > 0 then
      t[x] = t[x] or m(function(...) return f(x, ...) end)
      return t[x](...)
    else
      t[x] = t[x] or f(x)
      assert(t[x] ~= nil, 'memoized function returns nil')
      return t[x]
    end
  end
  return mf
end

Answer 9

لقد ألهمني هذا السؤال لتنفيذ وظيفة حفظ مرنة (أخرى) في Lua.

https://github.com/kikito/memoize.lua

المزايا الرئيسية:

• يقبل عددًا متغيرًا من الوسائط
• لا يستخدم tostring؛بدلاً من ذلك، يقوم بتنظيم ذاكرة التخزين المؤقت في بنية شجرة، باستخدام المعلمات لاجتيازها.
• يعمل بشكل جيد مع الوظائف التي تعود قيم متعددة.

لصق الكود هنا كمرجع:

local globalCache = {}

local function getFromCache(cache, args)
  local node = cache
  for i=1, #args do
    if not node.children then return {} end
    node = node.children[args[i]]
    if not node then return {} end
  end
  return node.results
end

local function insertInCache(cache, args, results)
  local arg
  local node = cache
  for i=1, #args do
    arg = args[i]
    node.children = node.children or {}
    node.children[arg] = node.children[arg] or {}
    node = node.children[arg]
  end
  node.results = results
end


-- public function

local function memoize(f)
  globalCache[f] = { results = {} }
  return function (...)
    local results = getFromCache( globalCache[f], {...} )

    if #results == 0 then
      results = { f(...) }
      insertInCache(globalCache[f], {...}, results)
    end

    return unpack(results)
  end
end

return memoize

Answer 10

فيما يلي تطبيق عام لـ C# 3.0، إذا كان من الممكن أن يساعد:

public static class Memoization
{
    public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
    {
        var cache = new Dictionary<T, TResult>();
        var nullCache = default(TResult);
        var isNullCacheSet = false;
        return  parameter =>
                {
                    TResult value;

                    if (parameter == null && isNullCacheSet)
                    {
                        return nullCache;
                    }

                    if (parameter == null)
                    {
                        nullCache = function(parameter);
                        isNullCacheSet = true;
                        return nullCache;
                    }

                    if (cache.TryGetValue(parameter, out value))
                    {
                        return value;
                    }

                    value = function(parameter);
                    cache.Add(parameter, value);
                    return value;
                };
    }
}

(نقلا عن أ المادة بلوق الفرنسية)

Answer 11

في سياق نشر المذكرات بلغات مختلفة، أود الرد على @onebyone.livejournal.com بمثال C++ لا يغير اللغة.

أولاً، مذكرة لوظائف وسيطة واحدة:

template <class Result, class Arg, class ResultStore = std::map<Arg, Result> >
class memoizer1{
public:
    template <class F>
    const Result& operator()(F f, const Arg& a){
        typename ResultStore::const_iterator it = memo_.find(a);
        if(it == memo_.end()) {
            it = memo_.insert(make_pair(a, f(a))).first;
        }
        return it->second;
    }
private:
    ResultStore memo_;
};

ما عليك سوى إنشاء مثيل للمذكرة، وإطعامها بوظيفتك ووسيطتك.فقط تأكد من عدم مشاركة نفس المذكرة بين وظيفتين مختلفتين (ولكن يمكنك مشاركتها بين تطبيقات مختلفة لنفس الوظيفة).

بعد ذلك، وظيفة السائق، والتنفيذ.فقط وظيفة السائق تحتاج إلى أن تكون FIB int العامة (int) ؛// driver int fib_ (int) ؛// تطبيق

مُنفّذ:

int fib_(int n){
    ++total_ops;
    if(n == 0 || n == 1) 
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

والسائق للحفظ

int fib(int n) {
    static memoizer1<int,int> memo;
    return memo(fib_, n);
}

الرابط الثابت يظهر الإخراج على codepad.org.يتم قياس عدد المكالمات للتحقق من صحتها.(أدخل اختبار الوحدة هنا...)

هذا يحفظ وظائف إدخال واحدة فقط.يتم ترك التعميم لوسائط متعددة أو حجج مختلفة كتمرين للقارئ.

Answer 12

من السهل الحصول على الحفظ العام في لغة Perl.تعد وحدة Memoize جزءًا من جوهر Perl وهي موثوقة للغاية ومرنة وسهلة الاستخدام.

المثال من صفحته manpage:

# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments);    # Is faster than it was before

يمكنك إضافة وإزالة وتخصيص حفظ الوظائف في وقت التشغيل! يمكنك توفير عمليات الاسترجاعات لحساب التذكارات المخصصة.

يحتوي Memoize.pm أيضًا على تسهيلات لجعل ذاكرة التخزين المؤقت للتذكار مستمرة، لذلك لا يلزم إعادة تعبئتها عند كل استدعاء لبرنامجك!

وهنا الوثائق: http://perldoc.perl.org/5.8.8/Memoize.html

Answer 13

يرى هذا بلوق وظيفة للحصول على حل Scala عام، ما يصل إلى 4 وسيطات.

Answer 14

لتوسيع الفكرة، من الممكن أيضًا حفظ الوظائف باستخدام معلمتين للإدخال:

function memoize2 (f)
   local cache = {}
   return function (x, y)
             if cache[x..','..y] then
                return cache[x..','..y]
             else
                local z = f(x,y)
                cache[x..','..y] = z
                return z
             end
          end
end

لاحظ أن ترتيب المعلمات مهم في خوارزمية التخزين المؤقت، لذلك إذا لم يكن ترتيب المعلمات مهمًا في الوظائف المراد حفظها، فستزداد احتمالات الحصول على نتيجة ذاكرة التخزين المؤقت عن طريق فرز المعلمات قبل التحقق من ذاكرة التخزين المؤقت.

ولكن من المهم ملاحظة أن بعض الوظائف لا يمكن حفظها بشكل مفيد.كتبت حفظ2 لمعرفة ما إذا كان العودي الخوارزمية الإقليدية لأنه يمكن تسريع عملية إيجاد القاسم المشترك الأكبر.

function gcd (a, b) 
   if b == 0 then return a end
   return gcd(b, a%b)
end

كما تبين، gcd لا يستجيب بشكل جيد للحفظ.الحساب الذي تقوم به أقل تكلفة بكثير من خوارزمية التخزين المؤقت.بالنسبة للأعداد الكبيرة، فإنها تنتهي بسرعة إلى حد ما.بعد فترة من الوقت، تصبح ذاكرة التخزين المؤقت كبيرة جدًا.من المحتمل أن تكون هذه الخوارزمية بأسرع ما يمكن.

Answer 15

العودية ليست ضرورية.رقم المثلث النوني هو n(n-1)/2، لذا...

public int triangle(final int n){
   return n * (n - 1) / 2;
}

Answer 16

من فضلك لا تكرار هذا.إما أن تستخدم الصيغة x*(x+1)/2 أو ببساطة تكرر القيم وتحفظها أثناء التقدم.

int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
  sum+=i;
  memo[i] = sum;
}
return memo[n];