[FFmpeg-devel] [PATCH 3/8] avfilter: keep a list of sink links by age.

[Michael Niedermayer]

On Sat, Apr 21, 2012 at 05:56:31PM +0200, Michael Niedermayer wrote:
> On Sat, Apr 21, 2012 at 02:25:07PM +0200, Nicolas George wrote:
> > Le tridi 3 floréal, an CCXX, Michael Niedermayer a écrit :
> > > LGTM, a binary heap would of course be more ideal, especially with
> > > many sinks
> > 
> > I believe it would take a great deal of sinks for a binary heap to be more
> > efficient than this implementation, and even more before the difference
> > becomes not negligible compared to other bookkeeping operations in the
> > filtergraph (and I am not even referring to actual frame processing or
> > encoding).
> 
> iam not so sure the sink selection needs negligible time with lets say
> 15 sinks and small audio packets
> 
> 15audio streams (in 15 languages) seem a realistic use case
> 
> bubble sort needs a worst case of 15 compares&swaps for this, a heap
> needs a worst case of 6 compares and swaps

that should have been 6 compares, 3 swaps

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Old school: Use the lowest level language in which you can solve the problem
            conveniently.
New school: Use the highest level language in which the latest supercomputer
            can solve the problem without the user falling asleep waiting.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20120421/846cab84/attachment.asc>