## Glas :## Re: [glas] Vector Spaces vs. "Objects called vectors" |

**From:** Ian McCulloch (*ianmcc_at_[hidden]*)

**Date:** 2005-02-04 10:24:10

**Next message:**David Abrahams: "Re: [glas] Vector Spaces vs. "Objects called vectors""**Previous message:**Toon Knapen: "[glas] summary: auto-resizing vectors in assignment"**In reply to:**Kevin Wheatley: "Re: [glas] Vector Spaces vs. "Objects called vectors""**Next in thread:**David Abrahams: "Re: [glas] Vector Spaces vs. "Objects called vectors""**Reply:**David Abrahams: "Re: [glas] Vector Spaces vs. "Objects called vectors""

On Fri, 4 Feb 2005, Kevin Wheatley wrote:

> Ian McCulloch wrote:

> > Clearly, in a lot of cases it doesn't make sense to resize the vector.

> > eg, "x += y", x and y should be the same size. The only case where it

> > would be sensible to consider resizing is for ordinary assignment. Here,

> > I don't think it is even sensible to fix a policy, if only for

> > interoperability reasons (how would you prevent a resize for std::vector?

> > How would you allow resize for a fixed-size array?).

>

> x += y, what if x has a sparse representation? (OK so I'm playing

> advocate here)

The guiding rule needs to be the computational complexity. The assignment

here should be no worse than O(N) (probably O(N log N) would be acceptable

too). Beyond that, it would be faster to create a temporary vector x+y in

some easily resizable structure that is O(N) in speed, and then copy that

structure into X at the end (again O(N)).

For example, if the left hand side uses a sparse structure that requires a

O(N) reallocation on every insert, then the operation as a whole would be

O(N^2), which could be catastrophic.

Another example is fixed structure sparse vectors. For an operation on

two such vectors the index structure is assumed to be the same, so many

operations can be very fast - often you don't even need to touch the

index array at all.

Of course, in the above example if ONLY x had a sparse representation and

y was dense, then the operation should be forbidden - it would effectively

destroy the sparse structure of x.

>

> I think what your meaning is that the size (math?) is like the

> capacity (CS) and that x and y have the same notional

> capacity/dimensionality. This would be a different thing to the

> underliying storage capacity/size which may need to be modified.

yes.

>

> Is this a desirable property of a vector (and thus by orthoganally a

> matrix), to be able to allow the user of the objects to stop

> themselves from incurring this 'hidden' memory allocation cost. I

> think it is.

Well, it depends how relevant the allocation cost is. For fixed

structure vectors, then there is no memory allocation penalty beyond the

inevitable construction cost. If you are concerned about memory

allocation, then by all means use such a structure. But these are not

useful in cases where the sparse structure is not known in advance.

>

> Conversly is it desirable to allow flexibility and the user to care

> less about the underlying representation, also a yes I think.

>

> Conclusions:

>

> a point of variation in policy is probably needed for storage

> reallocation

> maybe dimensionality miss-match is an error - provide an explicit

> conversion mechanism like a dimensionality_cast<>() ?

Well, certainly different storage formats have different

assignment/reallocation semantics. The question is, whether these need to

be explicitly spelled out, or whether it works to just 'do the natural

thing'. For example, if you had a sparse matrix in CSR format implemented

by something like a vector of sparse vectors, then the matrix assignment

operator is severly complicated by having to do a dimensionality_cast<>()

on all of the row vectors [unless it is a fixed-structure type of course].

By the way, do the people here pushing for strict dimensionality checks

have the same opinion about std::string automagically doing a reallocation

on assignment? Why/why not? This part of the discussion seems very

surreal to me.

> a glossary/dictionary of terms and concepts is important (most

> important?) to progress anywhere between the two meeting groups

> here...

Good idea. I think the notation is pretty uniform, try

http://www.psc.edu/~burkardt/papers/linear_glossary.html

David (or anyone else ;), do you have a link to a good intro on generic

programming?

Cheers,

Ian

**Next message:**David Abrahams: "Re: [glas] Vector Spaces vs. "Objects called vectors""**Previous message:**Toon Knapen: "[glas] summary: auto-resizing vectors in assignment"**In reply to:**Kevin Wheatley: "Re: [glas] Vector Spaces vs. "Objects called vectors""**Next in thread:**David Abrahams: "Re: [glas] Vector Spaces vs. "Objects called vectors""**Reply:**David Abrahams: "Re: [glas] Vector Spaces vs. "Objects called vectors""