[
https://issues.apache.org/jira/browse/MAHOUT-300?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12836433#action_12836433
]
Ted Dunning commented on MAHOUT-300:
------------------------------------
I think that this is a cleaner style for the merge loop. In particular, the
average inner loop is much tighter. The trick is that either iterator can take
many steps per outer iteration and that whenever either iterator is stepping,
you only check that iterator, its index and a constant. In sparse vectors,
this is a big win. Even in fairly dense vectors there are just a few extra
tests which the compiler may well be able to eliminate with common
sub-expression analysis. This form has the added benefit of having a simple
correctness argument.
{noformat}
Iterator<Element> myIter = iterateNonZero();
Iterator<Element> otherIter = x.iterateNonZero();
while (myIter.hasNext() && otherIter.hasNext()) {
// loop invariant: neither entry is up to date
// scan to end or equality
while (myCurrent.index() != otherCurrent.index() &&
((myIter.hasNext() && myCurrent.index() <
otherCurrent.index()) ||
(otherIter.hasNext() && otherCurrent.index() <
myCurrent.index()))) {
// invariant: both entries are current
// catch up my side
while (myIter.hasNext() && myCurrent.index() < otherCurrent.index()) {
myCurrent = myIter.next();
}
// catch up other side
while (otherIter.hasNext() && otherCurrent.index() <
myCurrent.index()) {
otherCurrent = otherIter.next();
}
// invariant: both entries are current
}
// exit: (both entries are current AND equal index) OR one side ran out
early
if (myCurrent.index() == otherCurrent.index()) {
// if equal, use it
result += myCurrent.get() * otherCurrent.get();
}
// invariant: neither entry is up to date or we will exit loop
}
{noformat}
> Solve performance issues with Vector Implementations
> ----------------------------------------------------
>
> Key: MAHOUT-300
> URL: https://issues.apache.org/jira/browse/MAHOUT-300
> Project: Mahout
> Issue Type: Improvement
> Affects Versions: 0.3
> Reporter: Robin Anil
> Fix For: 0.3
>
> Attachments: MAHOUT-300.patch, MAHOUT-300.patch, MAHOUT-300.patch
>
>
> AbstractVector operations like times
> public Vector times(double x) {
> Vector result = clone();
> Iterator<Element> iter = iterateNonZero();
> while (iter.hasNext()) {
> Element element = iter.next();
> int index = element.index();
> result.setQuick(index, element.get() * x);
> }
> return result;
> }
> should be implemented as follows
> public Vector times(double x) {
> Vector result = clone();
> Iterator<Element> iter = result.iterateNonZero();
> while (iter.hasNext()) {
> Element element = iter.next();
> element.set(element.get() * x);
> }
> return result;
> }
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
