Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-13 13:45:27
At Wed, 13 Oct 2010 17:09:38 +0100,
Mathias Gaunard wrote:
> I didn't know binary_search (and similar functions) worked with
> forward iterators. I have trouble seeing how they could work
> effectively at all.
O(N) steps, O(log N) comparisons. Better than linear search if
comparison is not cheap.
> >> But do we want generic capability at the cost of complicated code
> >> which is hard to optimize?
> > I don't believe you have to choose.
> Segmented iterators are neither practical to write nor to use.
Why do you say that? I don't think anyone has made a serious effort.
> > rotate,
> Interesting one, because it modifies itself.
> I'm not convinced it's not possible to write it.
I'd like to see that one.
> > equal,
> > transform (2-input version), includes, merge...
> Indeed, there is a combination problem.
> >> I believe writing a zip_iterator (or similar) would be no easier for
> >> segmented iterators than for generators due to the arbitrary
> >> recursion.
> > I'm not sure what you're getting at here, again. Is it relevant?
> Well, the limitation is how you can combine those "generators" to
> iterate several at the same time, be it for merge or otherwise.
> I don't see a good way to do this with segmented iterators either.
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk