MapReduce аркылуу медиананы кантип эсептейбиз?

MapReduce колдонуп медиананы эсептөө оңой эмес, анткени медиана бардык маалыматтарды глобалдык тартипке салууну талап кылат. Негизги идея:

1. Map: ар бир mapper маалыматтын бир бөлүгүн окуп, гистограмма же маанилердин таралышын түзөт (мисалы, белгилүү диапазондордогу элементтердин санын эсептейт).

2. Reduce: редукторлор бул гистограммаларды бириктирип, бардык маалыматтар топтому боюнча жалпы таралышын алат.

3. Медиананы аныктоо: топтолгон таралышты колдонуп, медиананын ордуна (жалпы элементтердин жарымы) эсептейт жана тиешелүү диапазонду табат.

4. Эгер керек болсо, бул диапазондо маалыматтарды фильтрлөө жана медиананы так аныктоо үчүн кошумча MapReduce ишке ашырылат.

Ошентип, медиана кайра-кайра эсептелип, маалыматтардын таралышын колдонуп издөө диапазону кыскарат, бүт топтомду сорттошпостон.

Алгоритм адатта мындай иштейт:

Map:
  ар бир элемент үчүн emit (диапазон_ключ, 1)

Reduce:
  ачкыч боюнча санды кошуу

Reduceтен кийин:
  кумулятивдүү таралышты эсептеп, медиананы камтыган диапазонду табуу

Эгер диапазон өтө чоң болсо:
  бул диапазондогу элементтер үчүн кайра MapReduce жүргүзүү

Итерациялар медиана так маанисин тапканга чейин улантылат.