ما هي الخريطة / تقليل؟

Question

أسمع الكثير عن الخريطة / الحد، خاصة في سياق نظام حساب Google الموازي Google. ما هو بالضبط؟

Answer 1

من مجردة Google mapreduce. صفحة منشور البحث:

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

ميزة MAPREDUC هي أن المعالجة يمكن إجراءها بالتوازي في عقد معالجة متعددة (خوادم متعددة) لذلك فهي نظام يمكن أن مقياس جيدا.

لأنه يعتمد من البرمجة الوظيفية نموذج، map و reduce لا تحتوي كل خطوات على أي آثار جانبية (الدولة والنتائج من كل القسم الفرعي map لا تعتمد العملية على آخر)، وبالتالي فإن تعيين البيانات التي يتم تعيينها وتقليلها يمكن فصل كل منها على عقد معالجة متعددة.

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

أنظر أيضا: ويكيبيديا: Mapreduce.

سؤال ذو الصلة: يرجى توضيح مابي فقط

Answer 2

وأوضح مابي.

يشرح أفضل مما أستطيع. هل يساعد؟

Answer 3

الخريطة هي وظيفة تنطبق وظيفة أخرى على جميع العناصر الموجودة في القائمة، لإنتاج قائمة أخرى مع جميع قيم الإرجاع عليه. (طريقة أخرى لقول "تطبيق F To X" هي "مكالمة F، تمريرها X". لذلك في بعض الأحيان يبدو أنه أجمل ليقول "تطبيق" بدلا من "الاتصال".)

هذه هي الطريقة التي ربما تكون بها الخريطة في C # (يطلق عليها Select وفي المكتبة القياسية):

public static IEnumerable<R> Select<T, R>(this IEnumerable<T> list, Func<T, R> func)
{
    foreach (T item in list)
        yield return func(item);
}

كما كنت المتأنق Java، ويحب جويل spolsky أن تخبر عن الأكاذيب غير العادلة بشكل صارخ حول كيفية قيادة Java Crappy (في الواقع، فهو لا يكذب، إنه كربي، لكنني أحاول الفوز بك)، وهنا محاولتي الخام للغاية نسخة جافا (ليس لدي مترجم جافا، وأنا أتذكر غامضة جافا الإصدار 1.1!):

// represents a function that takes one arg and returns a result
public interface IFunctor
{
    object invoke(object arg);
}

public static object[] map(object[] list, IFunctor func)
{
    object[] returnValues = new object[list.length];

    for (int n = 0; n < list.length; n++)
        returnValues[n] = func.invoke(list[n]);

    return returnValues;
}

أنا متأكد من أن هذا يمكن تحسينه في مليون طريقة. لكنها الفكرة الأساسية.

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

في C # تقليل يسمى Aggregate ومرة أخرى في المكتبة القياسية. سأتخطى مباشرة إلى إصدار Java:

// represents a function that takes two args and returns a result
public interface IBinaryFunctor
{
    object invoke(object arg1, object arg2);
}

public static object reduce(object[] list, IBinaryFunctor func)
{
    if (list.length == 0)
        return null; // or throw something?

    if (list.length == 1)
        return list[0]; // just return the only item

    object returnValue = func.invoke(list[0], list[1]);

    for (int n = 1; n < list.length; n++)
        returnValue = func.invoke(returnValue, list[n]);

    return returnValue;
}

تحتاج إصدارات Java هذه إلى أعمار إضافة إليهم، لكنني لا أعرف كيف أفعل ذلك في جافا. ولكن يجب أن تكون قادرا على نقلها فصول داخلية مجهولة إلى توفير Functors:

string[] names = getLotsOfNames();

string commaSeparatedNames = (string)reduce(names, 
   new IBinaryFunctor {
       public object invoke(object arg1, object arg2)
           { return ((string)arg1) + ", " + ((string)arg2); }
   }

نأمل أن تتخلص الأردن من المصابيح. ما يعادل المحاذاة في C # هو:

string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);

لماذا هذا "رائع"؟ طرق بسيطة لتقسيم الحسابات الكبيرة إلى قطع أصغر، حتى يتم وضعها معا بطرق مختلفة، هي دائما باردة. الطريقة التي تنطبق بها Google هذه الفكرة متوازية، لأن كلا الخطيين والحد منها يمكن تقاسمها عبر العديد من أجهزة الكمبيوتر.

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

Answer 4

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

ثم ذهبت إلى الأمام وجعلتها أكثر إيجازا من خلال ترجمة إلى سكالا، حيث قدمت أبسط القضية حيث يحدد المستخدم ببساطة فقط map و reduce أجزاء من التطبيق. في Hadoop / Spark، يتحدث بدقة، يتم استخدام نموذج أكثر تعقيدا للبرمجة الذي يتطلب من المستخدم تحديد 4 وظائف أخرى محددة هنا: http://en.wikipedia.org/wiki/mapreduceflow.

import scalaz.syntax.id._

trait MapReduceModel {
  type MultiSet[T] = Iterable[T]

  // `map` must be a pure function
  def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                              (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = 
    data.flatMap(map)

  def shufflePhase[K2, V2](mappedData: MultiSet[(K2, V2)]): Map[K2, MultiSet[V2]] =
    mappedData.groupBy(_._1).mapValues(_.map(_._2))

  // `reduce` must be a monoid
  def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.flatMap(reduce).map(_._2)

  def mapReduce[K1, K2, V1, V2, V3](data: MultiSet[(K1, V1)])
                                   (map: ((K1, V1)) => MultiSet[(K2, V2)])
                                   (reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]): MultiSet[V3] =
    mapPhase(map)(data) |> shufflePhase |> reducePhase(reduce)
}

// Kinda how MapReduce works in Hadoop and Spark except `.par` would ensure 1 element gets a process/thread on a cluster
// Furthermore, the splitting here won't enforce any kind of balance and is quite unnecessary anyway as one would expect
// it to already be splitted on HDFS - i.e. the filename would constitute K1
// The shuffle phase will also be parallelized, and use the same partition as the map phase.  
abstract class ParMapReduce(mapParNum: Int, reduceParNum: Int) extends MapReduceModel {
  def split[T](splitNum: Int)(data: MultiSet[T]): Set[MultiSet[T]]

  override def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                                       (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = {
    val groupedByKey = data.groupBy(_._1).map(_._2)
    groupedByKey.flatMap(split(mapParNum / groupedByKey.size + 1))
    .par.flatMap(_.map(map)).flatten.toList
  }

  override def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.map(g => split(reduceParNum / shuffledData.size + 1)(g._2).map((g._1, _)))
    .par.flatMap(_.map(reduce))
    .flatten.map(_._2).toList
}

Answer 5

Mapreduce و / أو SQL:

http://www.data-miners.com/blog/2008/01/mapreduce-and-sql-aggregations.html.

http://www.data-miners.com/blog/

انتقاد ميثادس

http://www.databasecolumn.com/2008/01/mapreduce-a-major-step-back.html.

http://www.databasecolumn.com/2008/01/mapreduce-continued.html.

Answer 6

الخريطة هي طريقة JS الأصلية التي يمكن تطبيقها على صفيف. يقوم بإنشاء مجموعة جديدة نتيجة لبعض الوظائف المعينة إلى كل عنصر في الصفيف الأصلي. لذلك إذا قمت بتعيين وظيفة (عنصر) {إرجاع عنصر * 2؛}، سيعود مجموعة جديدة تضاعفت كل عنصر. المصفاة الأصلية سوف تذهب غير مصطوم.

https:/developer.mozilla.org/en-us/docs/web/javascript/Reference/global_Objects/arriay/map.

تقليل هي طريقة JS الأصلية التي يمكن أيضا تطبيقها على صفيف. يطبق وظيفة إلى صفيف ولديها قيمة إخراج أولية تسمى تراكم. تحلقها من خلال كل عنصر في الصفيف، وتطبق وظيفة، ويقلل منهم إلى قيمة واحدة (والتي تبدأ كمكرر). من المفيد لأنه يمكنك الحصول على أي إخراج تريده، عليك فقط أن تبدأ بهذا النوع من تراكم. لذلك إذا أردت تقليل شيء إلى كائن، فسأبدأ بمسكرات {}.

https://developer.mozilla.org/en-us/docs/web/javascript/Reference/global_Objects/arriay/reduce؟v=a.

Answer 7

mapreduce:

لتشغيل شيء كبير، يمكننا استخدام قوة حساب الكمبيوتر المختلفة في مكتبنا. الجزء الصعب هو تقسيم المهمة بين أجهزة الكمبيوتر المختلفة. تم ذلك بواسطة مكتبة Mapreduce.

الفكرة الأساسية هي أن تقسم الوظيفة إلى قسمين: خريطة، وتقليل. تأخذ الخريطة المشكلة بشكل أساسي، وتشبعها في الأجزاء الفرعية، ويرسل الأجزاء الفرعية إلى آلات مختلفة - لذلك تشغيل جميع القطع في نفس الوقت. الحد من النتائج من الأجزاء الفرعية وتجمع بينها معا للحصول على إجابة واحدة.

الإدخال هي قائمة من السجلات. Result of خريطة الخريطة هي قائمة بأزواج المفتاح / القيمة. الحد من كل مجموعة من القيم التي لها نفس المفتاح، وتجمع بينها في قيمة واحدة. لا يمكنك معرفة ما إذا كانت المهمة تم تقسيمها إلى 100 قطعة أو قطعتين؛ تبدو النتيجة النهائية كثيرا مثل نتيجة خريطة واحدة.

يرجى النظر في خريطة بسيطة وتقليل البرنامج:

يتم استخدام وظيفة الخريطة لتطبيق بعض الوظائف على قائمةنا الأصلية وقائمة جديدة هي وبالتالي تم إنشاؤها. تأخذ وظيفة الخريطة () في Python في وظيفة وقائمة كوسيطة. يتم إرجاع قائمة جديدة عن طريق تطبيق وظيفة إلى كل عنصر من القائمة.

li = [5, 7, 4, 9] 
final_list = list(map(lambda x: x*x , li)) 
print(final_list)  #[25, 49, 16, 81]

تستغرق الدالة تقليل () في Python في وظيفة وقائمة كوسيطة. يتم استدعاء الوظيفة بوظيفة Lambda وقائمة ويتم إرجاع نتيجة مخفضة جديدة. هذا يؤدي عملية متكررة على أزواج القائمة.

#reduce func to find product/sum of list
x=(1,2,3,4)
from functools import reduce
reduce(lambda a,b:a*b ,x) #24