Self optimizing iterable

[Zac Burns]

Greetings,

I would like a set like object that when iterated maintains a count of
where iteration stopped and then re-orders itself based on that count
so that the iteration stopped on the most bubble to the top.

An example use case for this would be for something like a large table
of regular expressions that would be iterated over trying to match in
some string. If some regular expressions are more statistically more
successful then the iteration will generally be short.

Does anyone know of a pre-existing recipe for this or feel like taking
on the challenge?

Bonus points for:
Best possible BigO notation on switching order and iteration
Threadsafety
Extend to also include a mapping version



--
Zachary Burns
(407)590-4814
Aim - Zac256FL
Production Engineer (Digital Overlord)
Zindagi Games

 

[Paul Rubin]

An example use case for this would be for something like a large table
of regular expressions that would be iterated over trying to match in
some string. If some regular expressions are more statistically more
successful then the iteration will generally be short.

Generally if you are matching against a bunch of regexps, they will
tend to match overlapping sets, so you want to control precisely what
order they are tested in. Having stuff bubble around based on hit
counts doesn't sound good.

 

[Carl Banks]

Generally if you are matching against a bunch of regexps, they will
tend to match overlapping sets, so you want to control precisely what
order they are tested in.  Having stuff bubble around based on hit
counts doesn't sound good.

As a corrollary, if you happen to be matching non-overlapping sets,
then it is a red flag that there could be some other (better) way to
dispatch than a linear regexp search. For instance, if all your
regexps start with a different keyword, then you should dispatch on
that keyword using a dictionary. A regexp can be used after
dispatching to extract parameters if necessary.

It's possible to have disjoint regexps without a simple dispatch
criterion, but I'd guess that's less common.


Carl Banks