Normalizing A Vector
Lawrence D'Oliveiro
it (scale all components by the same factor) so its magnitude is 1.
The usual way is something like this:
L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
V = (V[0] / L, V[1] / L, V[2] / L)
What I don’t like is having that intermediate variable L leftover after the
computation. Here’s how to do it in one step:
V = tuple \
(
x
/
math.sqrt
(
reduce(lambda a, b : a + b, (y * y for y in V), 0)
)
for x in V
)
which, incidentally, also works for vectors with dimensions other than 3.
Alain Ketterlin
> Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
> it (scale all components by the same factor) so its magnitude is 1.
>
> The usual way is something like this:
>
> L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
> V = (V[0] / L, V[1] / L, V[2] / L)
>
> What I don’t like is having that intermediate variable L leftover after the
> computation.
Well, it also guarantees that the square root is computed once.
> Here’s how to do it in one step:
>
> V = tuple \
> ( x / math.sqrt
> (
> reduce(lambda a, b : a + b, (y * y for y in V), 0)
> )
> for x in V
> )
>
> which, incidentally, also works for vectors with dimensions other than 3.
And how many times does it call math.sqrt?
(That's actually not easy to test. Does any insider know the answer?
Does the compiler hoist the math.sqrt(...) out of the implicit loop? I
guess not, because it can't assert that reduce has no side effect.)
Your best bet is to define a function that does the normalization. Your
(local) name will disappear at the end of the call. If you want it to
work for any vector size:
def norm(V):
L = math.sqrt( sum( [x**2 for x in V] ) )
return [ x/L for x in V ]
If you do a lot of such computations, have a look at numpy.
-- Alain.
Chris Rebert
<l...@geek-central.gen.new_zealand> wrote:
> Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
> it (scale all components by the same factor) so its magnitude is 1.
>
> The usual way is something like this:
>
> L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
> V = (V[0] / L, V[1] / L, V[2] / L)
>
> What I don’t like is having that intermediate variable L leftover after the
> computation. Here’s how to do it in one step:
I suppose you'd be a fan of the proposed "given"/"where" statement
then (but its prognosis isn't great):
http://www.python.org/dev/peps/pep-3150/
Cheers,
Chris
--
http://blog.rebertia.com
John Nagle
> Does the compiler hoist the math.sqrt(...) out of the implicit loop?
Global optimization in Python? Not in CPython.
The program might redefine math.sqrt from another
thread while the program is running, which would invalidate the
hoisting of the function. That has to be supported.
Shed Skin might do it, but it restricts the language and
doesn't allow the full dynamism of Python.
John Nagle
Lawrence D'Oliveiro
> Lawrence D'Oliveiro <l...@geek-central.gen.new_zealand> writes:
>
>> What I don’t like is having that intermediate variable L leftover after
>> the computation.
>
> Well, it also guarantees that the square root is computed once.
OK, this version should solve that problem, without requiring any new
language features:
V = tuple \
(
x
/
l
for x in V
for l in
(math.sqrt(reduce(lambda a, b : a + b, (y * y for y in V), 0)),)
)
Thomas Jollans
>reduce(lambda a, b : a + b, (y * y for y in V), 0))
>
This is a lot more verbose than it has to be, and probably slower too.
firstly:
(lambda a,b: a+b) is equivalent to operator.add.
==>
reduce(operator.add, (y*y for y in V), 0)
However - reduce with operator.add ? we have a special name for this:
==>
sum(y*y for y in V)
Alain Ketterlin
>>> What I don’t like is having that intermediate variable L leftover after
>>> the computation.
>>
>> Well, it also guarantees that the square root is computed once.
>
> OK, this version should solve that problem, without requiring any new
> language features:
>
> V = tuple \
> (
> x
> /
> l
> for x in V
> for l in
> (math.sqrt(reduce(lambda a, b : a + b, (y * y for y in V), 0)),)
> )
You got the order wrong (it has to be for l ... for x ...)
You're kind of lucky here, because the arglist to tuple() provides a
scope that hides x and l. Be careful if you ever change tuple(...) to
[...], because x and l would leak to the outer scope (with python 2.*).
In the general case
for L in [...some-expr...]:
... whatever
doesn't hide L. Python doesn't provide a "let" construct (à la Lisp or
*ML).
-- Alain.
Tim Roberts
>
What is the matter with having a temporary variable hang around? It's only
one double, and it far better performance than the one you posted. As far
as I know, Python doesn't do common subexpression elimination, which means
the version you posted is doing to run the entire magnitude computation
once for every element in V.
A better solution would be to put this in a function:
def Normalize(V):
L = math.sqrt( sum(a*a for a in V) )
return (a/L for a in V)
Now the temporary goes away at the end of the function.
--
Tim Roberts, ti...@probo.com
Providenza & Boekelheide, Inc.
Lawrence D'Oliveiro
> Lawrence D'Oliveiro <l...@geek-central.gen.new_zealand> writes:
>
>> V = tuple \
>> (
>> x
>> /
>> l
>> for x in V
>> for l in
>> (math.sqrt(reduce(lambda a, b : a + b, (y * y for y in V),
>> 0)),)
>> )
>
> You got the order wrong (it has to be for l ... for x ...)
No, I deliberately put it in that order to ensure that the value for l can
only ever be evaulated once.
> You're kind of lucky here, because the arglist to tuple() provides a
> scope that hides x and l. Be careful if you ever change tuple(...) to
> [...], because x and l would leak to the outer scope (with python 2.*).
Interesting. However, using “list( ... )” instead of “[ ... ]” also prevents
the leakage.
Thomas Jollans
Yes. That's because the variable leakage of list comprehensions was
never a good idea, and is kept in Python 2.x only for backwards
compatibility. When generator expressions where introduced, it was done
in such a way that the scope didn't leak (which probably wouldn't make
any sense anyway since there's no guarantee a generator expression is
executed at all before the next line)
In Python 3, list comprehensions don't leak names any more - they act
(nearly?) the same as like( ... expr ... ) now.
Alain Ketterlin
>>> V = tuple \
>>> (
>>> x
>>> /
>>> l
>>> for x in V
>>> for l in
>>> (math.sqrt(reduce(lambda a, b : a + b, (y * y for y in V),
>>> 0)),)
>>> )
>>
>> You got the order wrong (it has to be for l ... for x ...)
>
> No, I deliberately put it in that order to ensure that the value for l can
> only ever be evaulated once.
Try this (essentially equivalent to your code):
def f():
print "hello"
return 1
V = tuple( 1 for x in [1,2,3] for l in (f(),) )
How many "hello"s do you see?
Comprehension are not loops spelled backwards. The values in:
whatever for i ... for j ...
are the values produced by the equivalent code:
for i ...
for j ...
whatever
-- Alain.
Terry Reedy
> Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
> it (scale all components by the same factor) so its magnitude is 1.
>
> The usual way is something like this:
>
> L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
> V = (V[0] / L, V[1] / L, V[2] / L)
>
> What I don’t like is having that intermediate variable L leftover after the
> computation.
So, instead of fooling around with error-prone, hard-to-type
constructions, just delete the damn thing!
def L
Compare those foolproof 5 chars to what at first did not work right and
even what did. And, as other said, in most real applications, you will
normalize in more than one place. In fact, you may well want a vlen
function.
def vlen(seq): return math.sqrt(sum(x*x for x in seq))
--
Terry Jan Reedy
Matteo Landi
> On 7/30/2010 7:46 AM, Lawrence D'Oliveiro wrote:
>>
>> normalize
>> it (scale all components by the same factor) so its magnitude is 1.
>>
>> The usual way is something like this:
>>
>> L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
>> V = (V[0] / L, V[1] / L, V[2] / L)
>>
>> What I don’t like is having that intermediate variable L leftover after
>> the
>> computation.
>
> just delete the damn thing!
>
> def L
del L
:P
>
> Compare those foolproof 5 chars to what at first did not work right and even
> what did. And, as other said, in most real applications, you will normalize
> in more than one place. In fact, you may well want a vlen function.
>
> def vlen(seq): return math.sqrt(sum(x*x for x in seq))
>
> --
> Terry Jan Reedy
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
--
Matteo Landi
http://www.matteolandi.net/
Lawrence D'Oliveiro
Damn. I thought that
e for i ... for j ...
was equivalent to
(e for i ...) for j ...
Looks like I was wrong.
Bartc
news:877hkdh...@dpt-info.u-strasbg.fr...
> Lawrence D'Oliveiro <l...@geek-central.gen.new_zealand> writes:
>
>> Say a vector V is a tuple of 3 numbers, not all zero. You want to
>> normalize
>> it (scale all components by the same factor) so its magnitude is 1.
>>
>> The usual way is something like this:
>>
>> L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
>> V = (V[0] / L, V[1] / L, V[2] / L)
> Your best bet is to define a function that does the normalization. Your
> (local) name will disappear at the end of the call. If you want it to
> work for any vector size:
>
> def norm(V):
> L = math.sqrt( sum( [x**2 for x in V] ) )
> return [ x/L for x in V ]
There's a cost involved in using those fancy constructions. I found the
following to be about twice as fast, when vectors are known to have 3
elements:
def norm3d(v):
L = math.sqrt((v[0]*v[0]+v[1]*v[1]+v[2]*v[2]))
return (v[0]/L,v[1]/L,v[2]/L)
(Strangely, changing those divides to multiplies made it slower.)
--
Bartc
Alain Ketterlin
>> def norm(V):
>> L = math.sqrt( sum( [x**2 for x in V] ) )
>> return [ x/L for x in V ]
>
> There's a cost involved in using those fancy constructions.
Sure. The above has three loops that take some time.
> I found the following to be about twice as fast, when vectors are
> known to have 3 elements:
>
> def norm3d(v):
> L = math.sqrt((v[0]*v[0]+v[1]*v[1]+v[2]*v[2]))
> return (v[0]/L,v[1]/L,v[2]/L)
>
> (Strangely, changing those divides to multiplies made it slower.)
You mean by setting L to 1.0 / math.sqrt(...) and using v[0]*L etc.?
I think * and / have the same cost on floats, and the added / adds
some cost. But what you observe is probably caused by the overloading of
"*", that needs more type checks. You may try with operator.mul to see
if the call compensates the cost of type checking, but I doubt it.
-- Alain.
Bartc
> "Bartc" <ba...@freeuk.com> writes:
>> def norm3d(v):
>> L = math.sqrt((v[0]*v[0]+v[1]*v[1]+v[2]*v[2]))
>> return (v[0]/L,v[1]/L,v[2]/L)
>>
>> (Strangely, changing those divides to multiplies made it slower.)
>
> You mean by setting L to 1.0 / math.sqrt(...) and using v[0]*L etc.?
Yes.
> I think * and / have the same cost on floats, and the added / adds
> some cost.
I expected no measurable difference, not running Python anyway (I tried it
in gcc and using divides increased runtimes by 50%, corresponding to some 1%
for Python).
I would naturally have written it using multiplies, and was just surprised
at a 3-4% slowdown.
> But what you observe is probably caused by the overloading of
> "*", that needs more type checks.
That sounds reasonable.
--
Bartc
Lawrence D'Oliveiro
> There's a cost involved in using those fancy constructions.
Sure. But at the point that starts to matter, you have to ask yourself why
you’re not rewriting the CPU-intensive part in C.
sturlamolden
central.gen.new_zealand> wrote:
> Say a vector V is a tuple of 3 numbers, not all zero. You want to normalize
> it (scale all components by the same factor) so its magnitude is 1.
>
> The usual way is something like this:
>
> L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
> V = (V[0] / L, V[1] / L, V[2] / L)
>
> What I don’t like is having that intermediate variable L leftover after the
> computation.
L = math.sqrt(V[0] * V[0] + V[1] * V[1] + V[2] * V[2])
V = (V[0] / L, V[1] / L, V[2] / L)
del L
But this is the kind of programming tasks where NumPy is nice:
V[:] = V / np.sqrt((V**2).sum())
Sturla