Re: Support loser tree for k-way merge

Поиск
Список
Период
Сортировка
Искать
От
cca5507
Тема
Re: Support loser tree for k-way merge
Дата
Msg-id
tencent_BCDD766860E1776D510A9F8C331EECC18306@qq.com
Ответ на
Re: Support loser tree for k-way merge (John Naylor)
Список
Дерево обсуждения
Support loser tree for k-way merge "cca5507" <cca5507@qq.com>
Re: Support loser tree for k-way merge Heikki Linnakangas <hlinnaka@iki.fi>
Re: Support loser tree for k-way merge "cca5507" <cca5507@qq.com>
Re: Support loser tree for k-way merge "cca5507" <cca5507@qq.com>
Re: Support loser tree for k-way merge Sami Imseih <samimseih@gmail.com>
Re: Support loser tree for k-way merge John Naylor <johncnaylorls@gmail.com>
Re: Support loser tree for k-way merge "cca5507" <cca5507@qq.com>
Re: Support loser tree for k-way merge "cca5507" <cca5507@qq.com>
Re: Support loser tree for k-way merge John Naylor <johncnaylorls@gmail.com>
Re: Support loser tree for k-way merge "cca5507" <cca5507@qq.com>
Re: Support loser tree for k-way merge Andreas Karlsson <andreas@proxel.se>
Re: Support loser tree for k-way merge Xuneng Zhou <xunengzhou@gmail.com>
Re: Support loser tree for k-way merge "cca5507" <cca5507@qq.com> 
Hi,

I summarized the number of comparisons needed for different 'k':

k = 2, heap: 1, loser tree: 1
k = 3, heap: 2, loser tree: [1, 2]
k = 4, heap: [2, 3], loser tree: 2
k = 5, heap: [2, 4], loser tree: [2, 3]

So if k < 5, the loser tree is never worse than the heap for any input data. 

Thoughts?

--
Regards,
ChangAo Chen
В списке pgsql-hackers по дате отправления
Предыдущее
От: shveta malik
Дата:
Следующее
От: Amit Kapila
Дата:
FAQ