On Wednesday, November 20, 2013 2:02:59 AM UTC-8, Felix Breuer wrote:
>
> Hi all!
>
> I have a large collection (~50,000) of integer vectors in low dimension
> (~20). For each of these vectors, I want to divide all entries by their
> gcd. In other words if
>
> def prim_v(v):
> d = abs(gcd(v))
> return v.apply_map(lambda vi: vi.divide_knowing_divisible_by(d))
>
> then I want to compute map(prim_v, V) for a long list V. When trying to
> profile this using %prun, I found it difficult to tell which part of this
> computation is taking the most time. So I rewrote this as
>
> def foo(v,d):
> return v.divide_knowing_divisible_by(d)
>
> def bar(v):
> return abs(gcd(v))
>
> def prim_v(v):
> d = bar(v)
> return v.apply_map(lambda vi: foo(vi,d))
>
> Then, profiling this with %prun yields the following information.
>
> ncalls tottime percall cumtime percall filename:lineno(function)
> 47802 0.119 0.000 13.811 0.000 LDsolver.py:58(prim_v)
> 47802 0.116 0.000 3.593 0.000 LDsolver.py:54(bar)
> 859898 0.360 0.000 0.524 0.000 LDsolver.py:51(foo)
>
>
I am pretty sure that you'll already get much better performance by
avoiding vectors altogether, because gcd(v) probably ends up producing a
list of entries out of your vector already. So if you can just have your
list of vectors as a list of list of integers, I think you'll find that
def normalize(v):
g = gcd(v)
return [c div g for c in v]
Ln=[normalize(v) for v in L]
is already much faster. You can then choose at which point you choose to
wrap or unwrap your data into/out of sage "vectors", i.e., if VL is your
list of vectors then
L= [list(v) for v in VL]
gives you the list of lists and
M=FreeModule(ZZ,20)
VLn=[M(v) for v in Ln]
would give you a list of normalized vectors (modulo typos on my side). By
constructing M beforehand, you're saving sage a lot of work in figuring out
where your vectors are supposed to live.
As mentioned, another option is cython and I expect that numpy could do
this this whole thing completely vectorized, but figuring out how to do
that if you don't already know is probably about as much work as writing a
first-principles cython version.
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/groups/opt_out.
