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: <CA+mX7frj-M64F0Vzc09SV6nm0oRhP3TGEO4nX36VqTw8QS2VYg@mail.gmail.com>
References: <CA+mX7foyyLMV5miBKuvEQnCzKPufiETKHhDad2VPm9rrD+DWwQ@mail.gmail.com>
 <CA+5xAo3GuMezKkn=OJhqN_B4M_LxQJ9wK1xbOcveCAyWAniqWg@mail.gmail.com> <CA+mX7frj-M64F0Vzc09SV6nm0oRhP3TGEO4nX36VqTw8QS2VYg@mail.gmail.com>
From: Bright Chen <bright@datatorrent.com>
Date: Wed, 8 Mar 2017 09:54:41 -0800
Message-ID: <CACOUD7QL9dda-RZwjwXNYiyu7PLCgVJ9L3AjLUoznXKzYP2tHg@mail.gmail.com>
Subject: Re: Sort Accumulation
To: dev@apex.apache.org
Content-Type: multipart/alternative; boundary=001a113abd9cb4a767054a3bd224
archived-at: Wed, 08 Mar 2017 18:22:57 -0000

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

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
> > >
> >
>

--001a113abd9cb4a767054a3bd224--