# Tag Info

9

Unless both lists given to Equal are packed arrays Equal will first unpack. Unfortunately for this case {} is not a packable expression, therefore list == {} will always unpack list, assuming it starts packed. That unpacking takes time: test = RandomInteger[100000000, 10000000]; DeveloperFromPackedArray[test]; // AbsoluteTiming {0.207012, Null} ...

8

It's pretty clear that the complexity of this function is $\text{O}(n^3)$, since we're iterating over each element of a matrix (a factor of $n^2$) and taking a sum at each one (an additional factor of $n$). As a former USACO competitor, I don't like $\text{O}(n^3)$ algorithms. However, we can't really do anything to reduce the complexity; LU decomposition ...

7

Here's my functional variant of your code: findSeam2[e_List] := Module[{f = FoldList[MinFilter[#1, 1] + #2 &, First[e], Rest[e]]}, Reverse@ FoldList[#1 + First@Ordering[#2[[Max[1, #1 - 1] ;; Min[Length[#2], #1 + 1]]]] - 1 - If[#1 == 1, 0, 1] &, First@Ordering[Last[f], 1], Reverse@Most[f]]]; And my test case ...

7

It is because they use different algorithms. MeanFilter is one of a family of filters which use DeveloperPartitionMap internally. This means that Mathematica is separately computing the mean of each run of 5 elements in your data set. MovingAverage is based on ListCorrelate which uses a fast FFT method. The documentation states: ...

5

This function prints out the solutions to all polynomials of degree d with coefficients of unit magnitude. printAllSolutions[d_] := Do[ With[{p = FromDigits[c~Prepend~1, x]}, Print[Expand[p] -> (x /. NSolve[p == 0, x])] ], {c, Tuples[{-1, +1}, d]} ] I made one optimization, which is that the leading coefficient is always 1. If it is ...

5

It seems, that a pure function calling a Listable one breaks internal optimization in Mathematica's ImageApply. Compare: t = Abs[Sqrt[#]] &; (* pure function *) q[x_] := Abs[Sqrt[x]]; (* "standard" function, implicitly listable *) SetAttributes[h, Listable]; h[x_] := Abs[Sqrt[x]]; (* explicitly listable function *) First /@ { ...

3

It turns out that Reduce finds candidate solutions relatively quickly and spends the vast majority of time proving correctness and completeness of the result. NSolve didn't have its own code for handling such problems, and was ending up using the same code as Reduce, finding symbolic solutions, and then numericizing them. I have implemented an NSolve version ...

3

I'm not too sure why one is so much slower than the other, but your second (slower) method can be improved by compilation (inspired by this answer). q3Compile = Compile[{{x, _Real}}, Piecewise[{{0., x <= 1/3.}, {.5, x <= 2/3.}, {1., x <= 1.}}, 0], RuntimeAttributes -> {Listable} ]; img = ExampleData[{"TestImage", "Apples"}] ...

3

Updated with cleaner and easier to adapt method: The checking of the patterns gets expensive, more so when conditions are attached. Looking at your generators, it's clear that the fulfillment of the patterns and/or conditions is quite sparse. Better to generate directly the hits, and create the array from those. Using your 'c' generator with just the ...

2

MeanFilter uses different algorithms (as noted by Simon), and is optimized for images (ability to use on "plain" data is a nice feature here, more so with some of the other image processing functions). This can be seen by doing : ImageData[MeanFilter[Image@{dat}, {0, 2}]][[1, 3 ;; -3]] Resulting in roughly comparable timings and the same result as your ...

1

The function doolittleDecomposite2 refactored by @2012rcampion can use Span(;;) to avoid the inner Do loop doolittle[mat_?MatrixQ] := Module[ {temp = ConstantArray[1, Dimensions@mat], row = Length@mat}, Do[ temp[[k, k ;; row]] = mat[[k, k ;; row]] - temp[[k, ;; k - 1]].temp[[;; k - 1, k ;; row]]; temp[[k + 1 ;; row, k]] = (mat[[k + 1 ;; ...

1

I ran your code on my computer, a 4-year old i7 iMac running V10.0.2 on OS X 10.6.8 (Snow Leopard). The first set of timings I got were 0.105747 0.105747 16.865200 The above timings are slower than yours. I attribute that to age of the iMac. For the ratios I got 48.9902 159.486 which are a little better than yours.

Only top voted, non community-wiki answers of a minimum length are eligible