Hi softworkz On Tue, Apr 08, 2025 at 04:56:36PM +0000, softworkz . wrote: [...] > Hi Michael, > > it's been a while, but as far as memory serves, wasn't a linear search even > more efficient than other methods as long as we're dealing with no more than > a few dozens of items?
a dozen is 12, so a few dozen would minimally be 24 at average to find an entry in a list of 24 you need 12 comparisions with a linear search and 24 in worst case an AVL tree with 24 entries i think needs 7 comparisions in the worst case So its certainly faster in number of comparisions the cost of strcmp() and overhead then come into play but small sets arent really what seperates the 2 choices. The seperation happens with there are many entries. dictionary is generic if you had a million entries a linear search will take about a million comparisions, the AVL tree should need less than ~30 in the worst case thats 5 orders of magnitude difference > > In turn, my question would be whether we even have use cases with hundreds or > thousands of dictionary entries? We use dictionary for metadata and options mainly. It would be possible to also use a linear list until the number of entries reaches a threshold thx [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB I have never wished to cater to the crowd; for what I know they do not approve, and what they approve I do not know. -- Epicurus
signature.asc
Description: PGP signature
_______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-requ...@ffmpeg.org with subject "unsubscribe".
