كيف أكتب وظيفة حفظ عامة؟
-
02-07-2019 - |
سؤال
أنا أكتب وظيفة للعثور عليها أرقام المثلث والطريقة الطبيعية لكتابتها هي بشكل متكرر:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
لكن محاولة حساب أول 100000 رقم مثلث تفشل مع تجاوز سعة المكدس بعد فترة.هذه هي الوظيفة المثالية ل حفظ, ، لكني أريد حلاً يحفظ أي وظيفة أقوم بتمريرها إليها.
المحلول
أراهن أن شيئًا كهذا يجب أن يعمل مع قوائم الوسائط المتغيرة في 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().اه الاحتمالات
نصائح أخرى
لدى 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).في الواقع، يمكنك حتى إعداد سيناريو حيث يكون أداء التنفيذ المحفوظ أفضل من تنفيذ النموذج المغلق!
أنت أيضًا تطرح السؤال الخطأ لمشكلتك الأصلية ;)
هذه طريقة أفضل لهذه الحالة:
مثلث(ن) = ن * (ن - 1) / 2
علاوة على ذلك، بافتراض أن الصيغة لا تحتوي على مثل هذا الحل الأنيق، فإن الحفظ سيظل أسلوبًا سيئًا هنا.سيكون من الأفضل لك كتابة حلقة بسيطة في هذه الحالة.يرى هذه الإجابة لمناقشة أكمل.
في 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));
في سكالا (لم يتم اختباره):
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 _)
لا أعتقد أن هذا سيجمع، لكنه يوضح الفكرة.
تحديث:أشار المعلقون إلى أن الحفظ هو وسيلة جيدة لتحسين التكرار.من المسلم به أنني لم أفكر في هذا من قبل، لأنني أعمل عمومًا بلغة (C#) حيث لا يكون إنشاء الحفظ المعمم أمرًا تافهًا.خذ المنشور أدناه مع وضع حبة الملح هذه في الاعتبار.
أظن من المحتمل أن يكون لدى لوقا الحل الأنسب لهذه المشكلة، ولكن الحفظ ليس هو الحل بشكل عام لأي مشكلة تتعلق بتجاوز سعة المكدس.
عادةً ما يحدث تجاوز سعة المكدس بسبب التكرار بشكل أعمق مما يمكن للنظام الأساسي التعامل معه.اللغات تدعم في بعض الأحيان "العودية الذيل"، الذي يعيد استخدام سياق المكالمة الحالية، بدلاً من إنشاء سياق جديد للمكالمة العودية.لكن الكثير من اللغات/المنصات السائدة لا تدعم هذا.على سبيل المثال، ليس لدى لغة C# دعم متأصل للتكرار الخلفي.يمكن للإصدار 64 بت من .NET JITter تطبيقه كتحسين على مستوى IL، وهو أمر عديم الفائدة تمامًا إذا كنت بحاجة إلى دعم الأنظمة الأساسية 32 بت.
إذا كانت لغتك لا تدعم التكرار الخلفي، فإن أفضل خيار لك لتجنب تجاوزات المكدس هو إما التحويل إلى حلقة صريحة (أقل أناقة بكثير، ولكنها ضرورية في بعض الأحيان)، أو العثور على خوارزمية غير تكرارية مثل Luke المقدمة لهذه المشكلة.
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);
لاحظ أنه لتجنب تجاوز سعة المكدس، سيظل المثلث بحاجة إلى البذر.
إليك شيء يعمل بدون تحويل الوسيطات إلى سلاسل.التحذير الوحيد هو أنه لا يمكنه التعامل مع حجة صفرية.لكن الحل المقبول لا يمكنه تمييز القيمة 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
لقد ألهمني هذا السؤال لتنفيذ وظيفة حفظ مرنة (أخرى) في 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
فيما يلي تطبيق عام لـ 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;
};
}
}
(نقلا عن أ المادة بلوق الفرنسية)
في سياق نشر المذكرات بلغات مختلفة، أود الرد على @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.يتم قياس عدد المكالمات للتحقق من صحتها.(أدخل اختبار الوحدة هنا...)
هذا يحفظ وظائف إدخال واحدة فقط.يتم ترك التعميم لوسائط متعددة أو حجج مختلفة كتمرين للقارئ.
من السهل الحصول على الحفظ العام في لغة 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
يرى هذا بلوق وظيفة للحصول على حل Scala عام، ما يصل إلى 4 وسيطات.
لتوسيع الفكرة، من الممكن أيضًا حفظ الوظائف باستخدام معلمتين للإدخال:
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 لا يستجيب بشكل جيد للحفظ.الحساب الذي تقوم به أقل تكلفة بكثير من خوارزمية التخزين المؤقت.بالنسبة للأعداد الكبيرة، فإنها تنتهي بسرعة إلى حد ما.بعد فترة من الوقت، تصبح ذاكرة التخزين المؤقت كبيرة جدًا.من المحتمل أن تكون هذه الخوارزمية بأسرع ما يمكن.
العودية ليست ضرورية.رقم المثلث النوني هو n(n-1)/2، لذا...
public int triangle(final int n){
return n * (n - 1) / 2;
}
من فضلك لا تكرار هذا.إما أن تستخدم الصيغة 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];