Hot answers tagged

34

General comments First, if you plan to use multi-dimensional integrals it is better to test with multi-dimensional integrals not with one dimensional ones. One might think that the test in the question is an appropriate one if multi-dimensional integration is done by the integrator in a recursive manner. This seems to be case for scipy.integrate.nquad (see ...


33

I don't think it is possible for FullSimplify to assess how far it is from a meaningful reduction of complexity. At every stage parts of the expression may after some transformation cancel (or not). Sometimes complexity has to be increased before it can be lowered (as I showed in this answer). Simplification is the process of minimizing complexity, where ...


24

Update 20/02/2015 I've now adapted my code to work with a binomial distribution, since that seemed to be the most problematic case for the OP. The relevant C++ code is at the bottom of this answer. Needs["CCompilerDriver`"] BinomialVariateLib = CreateLibrary[{ToString[NotebookDirectory[]] <> "binomialvariate.cpp"}, "BinomialVariateLib", ...


24

I can't take much credit for this answer--I hadn't even got version 10.2 installed until J. M. commented to me that these functions could be written efficiently in terms of the Hamming weight function. But, it is understandable that he doesn't want to write an answer using a smartphone. The definition of the built-in ThueMorse is: ThueMorse[n_Integer] := ...


24

First off, your function is very simple without any hard number-crunching, so it will always be hard to get a large speedup for the compiled version. Secondly, your Parallelization option for Compile is useless because it doesn't do any parallelization this way. Let me give slightly changed versions of your examples and explain how you can achieve a large ...


23

This is a poor use of the random functions in Mathematica. As clearly stated in the documentation, generation of variates one at a time has significant overhead, and generating them en masse has significant benefits, particularly with statistical distributions: For statistical distributions, the speed advantage of generating many numbers at once can be ...


23

Chunks of weak compositions Here is slightly modified version of algorithm used in Combinatorica`NextComposition converted to a LibraryFunction. Needs["CCompilerDriver`"] " #include \"WolframLibrary.h\" DLLEXPORT mint WolframLibrary_getVersion() { return WolframLibraryVersion; } DLLEXPORT int WolframLibrary_initialize(WolframLibraryData libData) { ...


22

Following the advice in comments, I've made a test library for BesselJ[1, #] & function to evaluate via GSL. I still consider it a workaround, so if you find a way to use Mathematica built-in functions with good performance, please do make a new answer. Needs["CCompilerDriver`"] besselJ1src = " #include \"WolframLibrary.h\" DLLEXPORT mint ...


22

I've decided to expand on my comment. Before I delve into the solution, let's all pause for a moment and marvel at the stereographic parametrization of a unit circle: $$\begin{pmatrix}\frac{1-t^2}{1+t^2}\\\frac{2t}{1+t^2}\end{pmatrix}$$ Sometimes also referred to as the Weierstrass substitution, it has often been used as a tool in the solution of algebraic ...


20

My answer is based on a modification of a binary heap. Basically the construction looks something like this. We start with a binary tree: Notice that if we label the nodes breadth-first, the labels have an interesting property. Each parent node $n$ has two children, $2n$ and $2n+1$. This also works in reverse: the parent of node $n$ is node ...


20

I've always wondered about the scalability of MathLink (now officially "Wolfram Symbolic Transfer Protocol"). This is the protocol used by Mathematica to communicate between the front end and the kernel, and the basis of the Parallel` package. It has quite low bandwidth and high latency relative to, for example, MPI libraries. I also wonder how many MathLink ...


19

We can take advantage of the fact that IntegerDigits is very fast when the base is large. But not too large: no bigger than $2^{63}-1$ on a 64-bit system or $2^{31}-1$ on a 32-bit one, because Mathematica's machine integers are signed. Additionally, non-power-of-two bases require more work to get the result than just partitioning a bit-string, and are ...


18

It seems that there is a significant overhead every time a color scheme is switched. Once a scheme is loaded each use is fast, but changing color schemes apparently unloads and reloads the mechanism. The result is that the speed of application is directly related to the frequency of switching. With sorted values there is only one switch and application is ...


18

Here's an edited version of my answer to a related question (elsewhere). Since your central question was about speed (or time complexity), you might wish to know an important result from elementary theory of algorithms and computational complexity, which is that the time and space complexity of matrix multiplication depends upon the order of such ...


18

SatisfiableQ has three methods: "BDD": converts the expression to a BDD (binary decision diagram), "SAT": uses the Minisat library, "TREE": a branch-and-bound method based on the expression tree. SatisfiabilityCount counts instances by converting the expression to a BDD, so its timing should be close to SatisfiableQ with the "BDD" method (counting ...


17

Preface Below, you will find two different solutions. For understanding the problem itself, the first, iterative solution is better suited since it gives insight in how the solution can be found without directly executing the instructions given as input. Iterative Solution Detailed explanation To explain the idea behind this approach let us work with a ...


17

Here is a summary of comments (before @ciao's best answer above), with a change in notation. These functions calculate the number of partitions of n into exactly k distinct parts of size at most m. NumberOfWays000[n_, k_, m_] := Count[Map[Length,Map[DeleteDuplicates, IntegerPartitions[n,{k},Range[m]]]], k] NumberOfWays001[n_, k_, m_] := ...


16

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]; Developer`FromPackedArray[test]; // AbsoluteTiming {0.207012, Null} ...


16

This happens because of unpacking when the numbers exceed $MaxMachineNumber: fast = Dot @@@ Partition[tab, Divisors[3960][[42]]]; Developer`PackedArrayQ /@ fast (* {True, True, True, True, True, True, True, True} *) Max[fast] <= $MaxMachineNumber (* True *) slow = Dot @@@ Partition[tab, Divisors[3960][[43]]]; Developer`PackedArrayQ /@ slow (* {False, ...


16

For a 1D list you can also use Pick[Range@Length@list, list, Max@list]


16

This seems pretty quick, particularly on larger cases / larger k, e.g. 451, 29, 101 finishes in a few seconds on the loungebook. N.B. - I have not tested this exhaustively, just thrown together from ideas... If[Min[#3, #1 - Tr@Range@(#2 - 1)] < 0, 0, SeriesCoefficient[QPochhammer[-x y, x, Min[#3, #1 - Tr@Range@(#2 - 1)]], {x , ...


16

Vectorization will help a lot: a[x_?NumericQ] := N[Exp[-Abs[x]]]; x = Table[-10 + 0.02 (j - 1), {j, 1, 1001}]; A = Outer[a[#1 - #2] &, x, x]; // AbsoluteTiming (* {2.11988, Null} *) B = Exp[-Abs[x - #]] & /@ x; // AbsoluteTiming (* {0.016182, Null} *) A == B (* True *) Notice that I am doing arithmetic on vectors the size of x instead of ...


15

A fast uncompiled alternative without pattern matching is to use the NonzeroPositions property of SparseArray, as long as you're dealing with numerical data. list = RandomInteger[{1, 100}, 10^7]; Needs["GeneralUtilities`"] SparseArray[Unitize[list - Max[list]] - 1]["NonzeroPositions"] // AccurateTiming (* 0.120459 *) Position[list, Max[list]] // ...


15

You can speed it up by only invoking the NearestFunction once: KPosition3[x_, y_] := Module[{step0, step1, nf}, step0 = Thread[x -> Range[1, Length@x, 1]]; nf = Nearest[step0]; step1 = nf[#, y] & /@ x]; Running your three timing tests gives: {0.003057, 0.004344, 0.051009}


15

Here is a totally different approach based on the fact that successive products forming the generating function are due to multiplication by a binomial $1+t*z^j$. Form a matrix $v$ of zeros with $n+1$ rows and $k+1$ columns. Initialize the top left corner to 1. Iterate $v=v+w$ where $w$ is the matrix $v$ shifted down by $j$ rows and to the right by 1. The ...


15

The following is a much faster, but not optimal, recursive solution: pts = RandomReal[1, {10000, 2}]; f = Nearest[pts]; k[{}, r_] := r k[ptsaux_, r_: {}] := Module[{x = RandomChoice[ptsaux]}, k[Complement[ptsaux, f[x, {Infinity, .05}]], Append[r, x]]] ListPlot@k[pts] Some timings show this is two orders of magnitude faster ...


15

You are right, it can be done in a fraction of second. One can explicitly construct an array of indexes blockArray[mat_] := SparseArray[ Tuples[Range@# - {1, 0, 0}].{Rest@#, {1, 0}, {0, 1}} &@Dimensions@mat -> Flatten@mat] Timings: matrices = RandomReal[1, {48, 128, 128}]; s1 = SparseArray@ ...


14

You miss that many Mathematica functions are listable. It allows you to write a fast and clear code init2[distance_] := uniMass Total[liuQuartic[distance, h] UnitStep[2 h - distance], {2}] h = 0.1; uniMass = 1.0; liuQuartic[d_, h_] := d^2 - h^2; totalPos = RandomReal[1, {1119, 2}]; res1 = initializeDensity@computeDistance[totalPos]; // AbsoluteTiming res2 ...


14

It is because they use different algorithms. MeanFilter is one of a family of filters which use Developer`PartitionMap 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: ...


14

idtz = Internal`DeleteTrailingZeros; trim0a = With[{t = Reverse/@ idtz/@DeleteCases[#, ConstantArray[0, Length@#[[1]]]]}, Reverse /@ idtz /@ t] &; trim0b = With[{t = DeleteCases[#, ConstantArray[0, Length@#[[1]]]]}, Fold[idtz@#2@# &, #, {Reverse, Reverse}] & /@ t] &; Equal @@ (#@test & /@ {trim0, trim0a, ...



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