تم النشر اليوم 2024/05/12 | نموذج الهيكلة والتجميع

تعريف اقتران الهيكلة والتجميع

يقوم اقتران الهيكلة والتجميع بتحويل قائمة من المدخلات إلى قائمة من المخرجات، وكل قائمة-المدخلات والمخرجات- تتكون من قيم ومفتاح لكل قيمة، كما هو الحال في دوال التجزئة أو ال دالة تجزئة.
M
a
p
R
e
d
u
c
e :
(
K
×
V ) ∗ →
(
L
×
W ) ∗ [
( k 1
, v 1
)
,
…
,
( k n
, v n
)
]
↦
[
( l 1
, w 1
)
,
…
,
( l m
, w m
)
]
{displaystyle {begin{aligned}mathrm {MapReduce} :(Ktimes V)^{*}&to (Ltimes W)^{*}\{lbrack (k_{1},v_{1}),ldots ,(k_{n},v_{n})rbrack }&mapsto lbrack (l_{1},w_{1}),ldots ,(l_{m},w_{m})rbrack end{aligned}}}
شرح اقتران الهيكلة والتجميع
المجموعات K
{displaystyle K} و L
{displaystyle L} تحوي على المفاتيح، بينما تحوي المجموعات V
{displaystyle V} و W
{displaystyle W} على القيم.
كل المفاتيح k
∈
K
{displaystyle kin K} هي من نفس النوع، مثلاً: نص أو String.
كل المفاتيح l
∈
L
{displaystyle lin L} هي من نفس النوع، مثلاً: عدد صحيح.
كل القيم v
∈
V
{displaystyle vin V} هي من نفس النوع، مثلاً: عدد عشري.
كل القيم w
∈
W
{displaystyle win W} هي من نفس النوع، مثلاً: عدد حقيقي.
إذا كانت A
{displaystyle A} و B
{displaystyle B} هي مجموعات، فإن A
×
B
{displaystyle Atimes B} هي مجموعة كل الأزواج (
a
,
b
)
{displaystyle (a,b)} , بحيث أن a
∈
A
{displaystyle ain A} و b
∈
B
{displaystyle bin B} (الضرب الديكارتي).
إذا كانت M
{displaystyle M} هي مجموعة، فإن
M ∗
{displaystyle M^{*}} هي مجموعة كل المجموعات التي يمكن تكوينها من عناصر M
{displaystyle M} , أو ما تسمى بنجمة كلين.
تعريف اقتران الهيكلة Map واقتران التجميع Reduce M
a
p :
K
×
V →
(
L
×
W ) ∗
(
k
,
v
) ↦
[
( l 1
, x 1
)
,
…
,
( l
r k
, x
r k
)
]
{displaystyle {begin{aligned}mathrm {Map} :Ktimes V&to (Ltimes W)^{*}\(k,v)&mapsto lbrack (l_{1},x_{1}),ldots ,(l_{r_{k}},x_{r_{k}})rbrack end{aligned}}}
أو
R
e
d
u
c
e :
L
× W ∗ →
∗ ( l
, [ y 1
,
…
, y
s l
]
)
↦
[ w 1
,
…
, w
m l
]
{displaystyle {begin{aligned}mathrm {Reduce} :Ltimes W^{*}&to X^{*}\left(l,{lbrack y_{1},ldots ,y_{s_{l}}rbrack }right)&mapsto lbrack w_{1},ldots ,w_{m_{l}}rbrack end{aligned}}}

طريقة العمل

MapReduce Zwischen Ergebnisse: نتائج غير نهائية
الصورة (MapReduce) توضح كيفية حساب البيانات في تقنية الهيكلة والتجميع وهي كالتالي: في البداية لدينا البيانات (D,A,T,A) المُراد حسابها، ويتم توزيع هذه البيانات على مجموعة من عمليات الهيكلة Map, وكل عملية تقوم بوظيفة معينة يتم تحديدها من قِبَل المستخدم.
يتم تنفيذ هذه العمليات بشكل متوازي.
كل عملية من هذه العمليات تقوم بطرح مخرجاتها الأولية (هذه المخرجات ممثلة باللون الزهري), مع العلم أن العملية الواحدة يمكنها توزيع مخرجاتها على أكثر من مكان تخزين.
هنا نأتي إلى مرحلة الخلط، حيث يتم خلط هذه البيانات مع بعضها البعض، وهنا أيضاً يتم تبادل البيانات بشكل كبير بين الأجهزة (الأماكن التي تتواجد فيها النتائج الأولية).
عندما تنتهي مرحلة الخلط فإنه يمكننا القول أنها بداية مرحلة التجميع Reduce (باللون الأزرق).
يتم هنا إجراء عملية تجميع واحدة لكل مكان تخزين (اللون الزهري) وتتم أيضاً هذه العمليات بشكل متواز، ومن ثم تطرح كل عملية من هذه العمليات مخرجاتها على حدا، وهي (X,Y,Z).

شرح مبسط

نموذج الهيكلة والتجميع
(بالإنجليزية: نموذج الهيكلة والتجميع) هو نموذج برمجي، طورته شركة جوجل لإجراء عمليات حسابية بشكل متزامن على كمية كبيرة جداً من البيانات (عدة بيتابايت[1]), وتتم هذه العمليات على عدة حواسيب تسمى بالعناقيد الحاسوبية.
كما يطلق اسم MapReduce على اسم المكتبة البرمجية لهذا النموذج وليس فقط على النموذج نفسه.
باستخدام طريقة الهيكلة والتجميع سيتم معالجة البيانات على ثلاثة مراحل (التجزئة، الخلط، التجميع) وبالانجليزية على التوالي
(Map, shuttle ,reduce), اثنتان منهم تتم من قِبَل المستخدم وهما التجزئة والتجميع.
— وبالتالي يمكن إجراء العمليات الحسابية على عدة حواسيب وفي الوقت نفسه، أي بشكل متواز.
تكمن أهمية هذه التقنية في الدور الذي تلعبه في توزيع العمليات على عدة حساب وإجرائها بشكل متزامن، ومن ثم جمع النتائج
في المرحلة الثانية (الخلط). بصورة أوضح يمكننا القول أننا نقسم المشكلة الكبيرة إلى عدة أجزاء ونحل كل جزء منها على حدا ومن ثم
نجمع هذه الحلول مع بعضها لتشكل في النهاية الحل للمشكلة الكبيرة. فكرة هذا النموذج مستوحاة من الدوال Map و Reduce, اللذان يستخدمان بكثرة في البرمجة الوظيفية.[2]