Mailing-List: contact dev-help@apex.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@apex.apache.org
MIME-Version: 1.0
In-Reply-To: <CACOUD7QL9dda-RZwjwXNYiyu7PLCgVJ9L3AjLUoznXKzYP2tHg@mail.gmail.com>
References: <CA+mX7foyyLMV5miBKuvEQnCzKPufiETKHhDad2VPm9rrD+DWwQ@mail.gmail.com>
 <CA+5xAo3GuMezKkn=OJhqN_B4M_LxQJ9wK1xbOcveCAyWAniqWg@mail.gmail.com>
 <CA+mX7frj-M64F0Vzc09SV6nm0oRhP3TGEO4nX36VqTw8QS2VYg@mail.gmail.com> <CACOUD7QL9dda-RZwjwXNYiyu7PLCgVJ9L3AjLUoznXKzYP2tHg@mail.gmail.com>
From: AJAY GUPTA <ajaygit158@gmail.com>
Date: Thu, 9 Mar 2017 12:24:18 +0530
Message-ID: <CA+mX7frvb5H1M820+t6d1XfFJgtiShuefcWZ0OXooXVVADC3kw@mail.gmail.com>
Subject: Re: Sort Accumulation
To: dev@apex.apache.org
Content-Type: multipart/alternative; boundary=001a114832d6d1e464054a46b69e
archived-at: Thu, 09 Mar 2017 06:54:25 -0000

--001a114832d6d1e464054a46b69e
Content-Type: text/plain; charset=UTF-8

Hi Bright,

I couldnot completely understand the bucketing approach you mentioned. How
would we bucket the data considering we have no idea what the data will be?

How about using a TreeMultiSet?


Thanks,
Ajay

On Wed, Mar 8, 2017 at 11:24 PM, Bright Chen <bright@datatorrent.com> wrote:

> Hi Ajay,
> I think sort at getOutput() probably will get this method stuck due to very
> high volume of computation.
> And as we still need to persistent the data, it will not very helpful to
> increase the performance of processing tuple. Probably we can bucket the
> data with range of value. Such as following:
> - process tuple in one window: sort data of current window in memory
> - end window: merge the sorted memory data into buckets.
>
> thanks
> Bright
>
> On Wed, Mar 8, 2017 at 8:51 AM, AJAY GUPTA <ajaygit158@gmail.com> wrote:
>
> > Hi Thomas,
> >
> > I looked at TopN. The accumulate() of TopN is an O(n*k). Using similar
> > approach for Sort will lead to an O(n^2) complexity.
> > Since we have to sort all elements, we can do it in a single sort call in
> > getOutput().
> >
> >
> > On Wed, Mar 8, 2017 at 10:09 PM, Thomas Weise <thw@apache.org> wrote:
> >
> > > Look at the existing topN accumulation. It should be a generalization,
> > > where you don't have a limit.
> > >
> > >
> > > On Wed, Mar 8, 2017 at 8:05 AM, AJAY GUPTA <ajaygit158@gmail.com>
> wrote:
> > >
> > > > Hi,
> > > >
> > > > I would like to propose the Sort Accumulation. The accumulation will
> be
> > > > responsible for sorting the input POJO stream. The accumulation will
> > > > require a comparator to compare and sort the input tuples. Another
> > > boolean
> > > > parameter "sortDesc" will be used to decide sorting order.
> > > >
> > > > Let me know your views.
> > > >
> > > > Thanks,
> > > > Ajay
> > > >
> > >
> >
>

--001a114832d6d1e464054a46b69e--