# Tag Info

30

First let me note that I didn't write PositionIndex, so I can't speak to its internals without doing a bit of digging (which at the moment I do not have time to do). I agree performance could be improved in the case where there are many collisions. Let's quantify how bad the situation is, especially since complexity was mentioned! We'll use the ...

30

The first example seems to intentionally set Mathematica up to "fail" by specifying insufficient input accuracy. With additional precision: ClearAll[s] s[i_] := s[i] = 2*s[i - 1] - 3*s[i - 1]^2 s[0] = 0.330; s[40] 0.333333 And Mathematica is capable of far greater precision if necessary: ClearAll[s] $RecursionLimit = ∞ s[i_] := s[i] = 2*s[i - 1] - ... 26 The behavior described here is the same from 10.0.0 up to at least 10.1.0, with the minor exception of IndexBy. Summary We can look at the code of DeleteDuplicatesBy and it turns out it uses GroupBy. The test cases proposed by Mr.Wizard are all handled by some part of the code of DeleteDuplicatesBy. Other parts of this code also seem to have some issues. ... 22 A very simple and straightforward test for square-freeness (and should be reasonably fast) is: squareFreeQ[str_] := StringFreeQ[str, x__ ~~ x__] Testing on your inputs: squareFreeQ["0101"] (* False*) squareFreeQ["0102012021"] (* True *) You can then possibly restrict this further to operate only on certain alphabets using Repeated and Alternatives. ... 22 Simon Woods points out in a comment that: In fact the delay on the initial run is caused by compiling code to provide the Poisson distribution :-) You can look at ImageColorOperationsDumpiImageEffectPoissonNoise to see how it works internally. Now, although PoissonDistribution can't be compiled, there's nothing stopping the use of my own C++ ... 21 You are trying to implement Euler-Maruyama simulation method for a 2-stage short-term interest rate model which is given by the following system of SDEs:$$\begin{eqnarray} \mathrm{d} \theta_t &=& -\lambda_\theta \left( \theta_t - \bar\theta\right) \mathrm{d}t + \sigma_\theta \mathrm{d}W_{\theta,t} \\ \mathrm{d} \pi_t &=& ... 21 Without commenting on how much attention one should pay to marketing literature: the second example is somewhat relevant. Mathematica's polynomial factoring algorithm is known to be at least fifteen years behind the state of the art, and things that Maple will factor in seconds will go away (literally) forever in Mathematica. This is, of course, not too ... 20 The critical issue in the first example is that Mathematica is using significance arithmetic to track precision. This is certainly billed as a feature by Wolfram Research. As we see in this example though, it can be portrayed as a weakness. In truth, you might need to know what you're doing to use it correctly. In this answer, I mentioned that significance ... 20 The general case There are indeed some functions in Mathematica that are/were not performing nicely. The one I am most scared of is Total (the issue is addressed here) (update: apparently Total has been fixed in version 10.0.2). Pickett provides some more examples in his comment. But I feel the case of Union is different, as it is simply specialised for a ... 18 This is your idea with different functions: FreeQ[Differences@IntegerDigits[n], _?Negative] hmmm.. OrderedQ@IntegerDigits[n] This is in case if sequence is non-descending instead of ascending but OP's functiong gives True for 133. 18 Timing charts updated for version 10.0.2. The behavior remains unchanged. Attempting to analyze the performance of this function in the manner that Taliesin Beynon did for PositionIndex I shall use the same tools. The old method that will be compared in all cases below: myDeDupeBy[x_, f_] := GatherBy[x, f][[All, 1]] Speed A BenchmarkPlot of ... 16 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 ... 15 This happens because of unpacking when the numbers exceed$MaxMachineNumber: fast = Dot @@@ Partition[tab, Divisors[3960][[42]]]; DeveloperPackedArrayQ /@ fast (* {True, True, True, True, True, True, True, True} *) Max[fast] <= $MaxMachineNumber (* True *) slow = Dot @@@ Partition[tab, Divisors[3960][[43]]]; DeveloperPackedArrayQ /@ slow (* {False, ... 14 GraphicsMeshPolygonIntersection[] is not documented; it builds full polygon triangulations. To handle holes, you can use: PolygonIntersection[a, b, FillingMethod -> "OddEvenRule"] or PolygonIntersection[a, b, FillingMethod -> "WindingRule"] To create the visualization: GraphicsMeshMeshInit[]; a = Polygon@RandomReal[1, {100, 2}]; b = ... 14 Sum, like Integrate, does some symbolic processing. For instance, your sum with an indefinite end point n returns a closed-form formula: Sum[i, {i, n}] (* 1/2 n (1 + n) *) ParallelSum will do the actual summation, one term at a time. There is overhead in parallelization. Often a significant bottleneck is the amount of data that has to be transferred ... 14 Let's start by taking a look at the compiled form of one of our queries: DatasetCompileQuery[Query @ First @ spans] (* DatasetWithOverrides@*Checked[Slice[205 ;; 313], Identity] *) We can see that the operation is not implemented directly in terms of part. Indeed, there are three components: DatasetWithOverrides, GeneralUtilitiesChecked and ... 14 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]] // ... 13 Nasser gives good standard ControlActive approach. But that by definition looses quality during motion. I just would like to share a trick that avoids that. Most of the time is spent on rendering your bell shape. But it is static. Plane moves but it is simple, so it should not all the time trigger recomputing of static bell shape. You can separate motion of ... 13 Here is a solution based on binary search (compiled). Implementation First, this is a version of a binary search, which would return the position of a maximal number in a list, smaller or equal to yours, and -1 if no such is found: ClearAll[bsminComp]; bsminComp= Compile[ {{lst,_Integer,1},{elem,_Integer}}, ... 13 Compilation is a certainly a good idea if you're going the brute-force route. So let's first tackle that, which will get us the answer in roughly 30 seconds computation time. Afterwards we'll come up with better strategy, which can do it in 0.3 seconds. Compilation A performance pitfall when compiling functions is that sometimes the compiled function just ... 13 For a 1D list you can also use Pick[Range@Length@list, list, Max@list] 12 This seems fast(er): Extract[a, Transpose[{v, Range@Length@v}]] Addendum Mr.Wizard's clean method Diagonal @ a[[v]] has a surprising property for those of us who think that packed arrays rank just below the wheel in the list of inventions for the sake of efficiency. For unpacked arrays a, it uses virtually no extra memory. Example Initialization. ... 11 I hope I see the essence here. You are interested in the convolution of an interpolated function with a Gauss function Your underlying data has regular spacings in x-direction and the convolution with a Gaussian is extremely fast implemented in GaussianFilter for discrete data. Why are you making it so complicated when the only thing you have to do is ... 11 If you need the ultimate speed, the following compiled code will be about 20 - 30 times faster than the elegant string-pattern based solution of @R.M. (but, of course, as many times longer and uglier): With[{part = Compile`GetElement}, squareFreeQLSC = Compile[{{ll, _Integer, 1}}, Module[{res = 0, ctr = 1, sctr = 1, len = 0, start = 0, i = 0}, ... 11 Edit This one is much simpler than those I posted before . And very efficient Timing@StringFreeQ[benchmark, RegularExpression["(.+)\\1"]] Previous posts: Timings done on a VERY slow machine: Timing@Not@StringMatchQ[benchmark, RegularExpression[".*(.{1,1000})\\1(.*)"]] (* -> {0.735, True} *) Edit There is a problem if the repeated string has ... 11 Try this: n = 1000; coeffs = RandomVariate[NormalDistribution[], n]; f[x_] := Sum[coeffs[[k]] Sin[k x]/k, {k, 1, n}]; Plot[Evaluate@f[x], {x, 0, 2. Pi}, PlotPoints -> n, MaxRecursion -> 0, Mesh -> All] // Timing With[{n = 1000}, First@Timing[Table[Evaluate@f[x], {x, 0, 2. Pi, 2. Pi/n}]] ] 2 times as fast as plot. I remembered my own ... 11 This function will be rewritten in C for 10.0.2 and should come down to average-case complexity of$O(n)$from its current$O(n \log(n))$. Note that the version most users will be bothered to write (and the way we advertized this before in the docpage for DeleteDuplicates) is$O(n^2)\$, so most users are probably already winning. In the meantime, my advice ...

11

Assuming that the values of your matrix are all distinct, or that you don't count repetitions in n, you can do this: ClearAll[largest]; largest[mat_, n_] := Clip[mat,{RankedMax[#, n], Max[#]}, {0, 0}] &[Flatten@mat] So that large = RandomReal[{1, 10}, {50, 50}]; Do[largest[large, 50], {1000}]; // Timing // First (* 0.076633 *)

10

This has [quadratic, he said] actually perhaps cubic complexity in a worst case (okay, now I'm just confused. More below).. Not the fastest of the lot, but it seems reasonable, or at least not entirely unreasonable. Requires some thought for me to see what I'm doing that keeps it relatively slow. squareFree[wrd_String] := squareFreeC[ToCharacterCode[wrd]] ...

10

I will use big and small rather than bigList and smallList, for brevity. As stated by others if you can select the positions at random in the first place this will be faster, e.g.: pos = RandomSample[Range @ Length @ big, 1200]; You can then get the small list with: small = big[[pos]]. To carry out the specific operation you describe the key detail will ...

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