Чӣ гуна медиа бо истифода аз MapReduce ҳисоб карда мешавад?

MapReduce-ті пайдаланып медиананы есептеу оңай емес, себебі медиана барлық деректерді ғаламдық сұрыптауды талап етеді. Негізгі идея:

1. Map: әрбір mapper деректердің бір бөлігін оқиды және гистограмма немесе мәндердің таралуын құрады (мысалы, белгілі бір диапазондардағы элементтердің санын есептейді).

2. Reduce: редукторлар бұл гистограммаларды біріктіреді, осылайша барлық деректер жиынтығы бойынша жалпы таралу алынады.

3. Медиананы анықтау: жинақталған таралу негізінде, олар медиана позициясын (жалпы элементтердің жартысы) есептейді және сәйкес диапазонды табады.

4. Қажет болса, бұл диапазонда деректерді сүзу және медиананы дәлірек анықтау үшін қосымша MapReduce іске қосылады.

Осылайша, медиана қайталанатын түрде есептеледі, деректердің таралуын пайдалана отырып, іздеу диапазонын тарылтады, барлық жиынтықты сұрыптамай.

Әдетте алгоритм келесідей жұмыс істейді:

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

Reduce:
  кілт бойынша санды қосу

Reduce-тан кейін:
  кумулятивті таралуды есептеу және медиананы қамтитын диапазонды табу

Егер диапазон тым үлкен болса:
  осы диапазонда элементтер үшін MapReduce қайталау

Итерациялар медиана нақты мәнін табуға дейін жалғасады.