On 09-06-2012 12:45, bearophile wrote:
Often enough you have to perform operations on some non-flat sequence,
like on a 2D matrix:
import std.stdio;
void main() {
auto m1 = [[], [2, 5], [], [10, 20], [], [], [30, 40, 50]];
foreach (row; m1)
foreach (x; row)
writeln(x);
}
Such multi-level ranges are common. But a Range (below an Input Range)
that works on a generic multi level Range is slower than the two nested
for loops because it needs to keep attention to the exhaustion of the
sub-ranges at every iteration (see popFront):
import std.stdio, std.traits, std.array, std.range, std.algorithm;
struct BilevelScan(Range) {
private Range range;
typeof(range.front) currentSegment;
this(Range range_) {
this.range = range_;
_nextItem();
}
@property bool empty() {
return range.empty && currentSegment.empty;
}
@property auto front() {
return currentSegment.front;
}
void popFront() {
currentSegment.popFront();
_nextItem();
}
private void _nextItem() {
while (!range.empty && currentSegment.empty) {
currentSegment = range.front;
range.popFront();
}
}
}
void main() { // some test code
auto m1 = [[], [2, 5], [], [10, 20], [], [], [30, 40, 50]];
foreach (x; BilevelScan!(typeof(m1))(m1))
writeln(x);
writeln(m1, "\n");
auto m2 = [[10.5]];
foreach (x; BilevelScan!(typeof(m2))(m2))
writeln(x);
writeln(m2, "\n");
auto m3 = 6.iota().map!(i => iota(10 ^^ i + i, 10 ^^ i + i + 3))();
foreach (x; BilevelScan!(typeof(m3))(m3))
writeln(x);
writeln(m3, "\n");
}
In the paper "Segmented Iterators and Hierarchical Algorithms" Matthew
H. Austern offers a solution to regain the lost efficiency:
http://
I think your NNTP client ate a link. ;)
Some quotations from the paper:
segmented data structures are common. Within the STL, for example, the
deque container is typically implemented as a segmented array, and
hash tables [6] are typically implemented as arrays of buckets. Other
examples of segmentation include two-dimensional matrices, graphs,
files in record-based file systems, and, on modern NUMA (non-uniform
memory architecture) multiprocessor machines, even ordinary memory.<
A segmented iterator has the same associated types as any other
iterator (a value type, for example), and, additionally, it has an
associated segment iterator type and local iterator type. Writing a
generic algorithm that uses segmented iterators requires the ability
to name those types. Additionally, a fully generic algorithm ought to
be usable with both segmented and nonsegmented iterators.<
The distinction between segmented and nonsegmented iterators is
orthogonal to the distinction between Forward Iterators, Bidirectional
Iterators, and Random Access Iterators.<
Multiple levels of segmentation can be used with no extra effort.
Nothing in this discussion, or this implementation of fill, assumes
that the local iterator is nonsegmented.<
Segmented iterators, an extension of ordinary STL iterators, make it
possible for generic algorithms to treat a segmented data structure as
something other than a uniform range of elements. This allows existing
algorithms to operate more efficiently on segmented data structures,
and provides a natural decomposition for parallel computation.
Segmented iterators enable new kinds of generic algorithms that
explicitly depend on segmentation.<
In D the concept of Input Range is defined as a type that statically
supports (there is also some necessary semantics that can't be expressed
in the D code of such concepts):
R r; // can define a range object
if (r.empty) {} // can test for empty
r.popFront(); // can invoke popFront()
auto h = r.front; // can get the front of the range of non-void type
So an idea is to introduce in D the multi-level Ranges:
SegmentedInputRange
SegmentedOutputRange
SegmentedForwardRange
SegmentedBidirectionalRange
SegmentedRandomAccessRange
I think a Segmented Input Range is more complex than an Input Range.
Inventing such ranges is like finding the miminal set of axioms that
allow to write down a theorem, that is to efficiently implement the
normal algorithms. This is not an easy for me, I don't know much about
this topic.
Bye,
bearophile
--
Alex Rønne Petersen
a...@lycus.org
http://lycus.org
