[MPlayer-dev-eng] [PATCH] add lavfpref demuxer for formats where lavf is preferred over native demuxers

[Michael Niedermayer]

Hi

On Tue, Apr 10, 2007 at 12:32:52PM -0400, Rich Felker wrote:
> On Tue, Apr 10, 2007 at 02:31:05PM +0200, Michael Niedermayer wrote:
> > > > in what way is it supperior? IIRC it has O(n) seeking while lavf-nut has
> > > > O(log n)
> > > 
> > > It has O(log n) seeking or even O(1) seeking in lucky cases, unless you 
> > > mean in purely memory operations (dealing with syncpoint cache), though 
> > 
> > if theres any single operation O(n) then the whole is O(n) or worse, thats
> > how O() works, having mostly O(log n) and just one n byte memcpy() somewhere
> > is not O(log n)
> 
> It depends on what you're talking about. Technically, seeking with an
> index is O(n) (or at best O(log n) if you binary search the index),

if you binary search the index then it must be sorted and keeping it sorted
will be O(n) per insertion again, so it gets a little more tricky if you
want O(log n) insertions and O(log n) search, balanced binary trees are
one option


> but people call it O(1) because the number of _media_ operations (as
> opposed to memory operations) is independent of the file size. It's a
> matter of _which quantity_ you're asking for a big-O for..

of course but if the quantity is unspecified then "any operation" seems
like the logic choice ...

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Let us carefully observe those good qualities wherein our enemies excel us
and endeavor to excel them, by avoiding what is faulty, and imitating what
is excellent in them. -- Plutarch
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/mplayer-dev-eng/attachments/20070411/a939bd8c/attachment.pgp>