Tag: Fastest

Select arbitrary single value for GROUP BY: What’s the fastest option?

I have a query that I use to indicate locations in a map where there are overlapping points:

select     min(objectid) as min_objectid,     longitudex,     latitudey,     count(1) as count,     min(shape) as min_shape from     workorders group by     longitudex,     latitudey having     count(1) > 1

In the mapping software that I use, I need to include columns like objectid and shape. For those columns, it doesn’t matter which of the grouped-by rows the values come from, just as long as there is a value.

Presently, I’m using min() to get an arbitrary value for those columns. However, I don’t know if that’s the fastest option since finding the minimum value would require calculation — and I wonder if that time spent is unnecessary.

What is the fastest option for getting an arbitrary/single value for GROUP BY in an Oracle query?

Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

As discussed here Johnson’s Algorithm can be used to solve the APSP-Problem in $ O(V^2\log V + VE)$ in stead of $ O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the case that some weights are negative. Is there a faster way to compute this given that all weights are positive?

Fastest land speed creature with HD of 8 or less?

In the interest of haunt shifting an undead creature into a carriage and getting the carriage to go fast, I am looking for what the haunting’s base creature should be. With templates, most creatures could be made undead, so we’re looking for:

  1. A creature that is, or can be made, undead
  2. Without getting above 8HD
  3. Featuring the highest available base walking speed
  4. Being controllable in a permanent manner by its method of creation or otherwise
  5. With as little ‘exotic material’ as possible – keep is as simple as we can.

Fastest algorithm for connectivity problem

Let $ G = (V,E)$ be any undirected graph. Let $ k$ be some number and $ C = |u \longrightarrow v|$ where $ u \longrightarrow v$ means there is a path from $ u$ to $ v$ . We want to add $ k \subseteq V \times V\ E$ edges into $ G$ such that $ C$ is maximised in the new graph.

Question : What is the fastest algorithm for this problem?

I can solve the above problem in $ n^{O(k)}$ time by brute force method.

What is the fastest way to merge two B trees?

Given two B-trees of some order $ m$ $ T_1,T_2$ , such that $ y > x$ for every pair $ x \in T_1$ and $ y \in T_2$ . What is the fastest way to create a new tree that is the union of both $ T_1,T_2$ ?

My current solution is naive in a sense that I create an array and insert all $ T_1$ elements, than all $ T_2$ elements. As a result I have a sorted array which I can create a new tree off of with a cost of $ n \log n$

I’m thinking that there must be a better solution, something like the AVL merging question but I can’t figure it out.

Fastest way to ArrayFlatten a 2D array of 2D arrays, both for Sparse and Dense

I am using Mathematica 12 and want to know what is the fastest way to transform a 2D array of 2D arrays both for dense and sparse arrays. I remember looking for this a few versions of Mathematica ago, when ArrayFlatten was not that good. Since then I have been using option one below (which I found somewhere here, but I can’t find the question anymore – it had other suggestions as well). But a quick check shows that for SparseArrays that is not the case anymore. Is there anything better than ArrayFlatten

Also, why is the SparseArray version of 3 not the same as the other two, unless I make them dense?

dim = 5; eles = 50; sparse = Table[    KroneckerProduct[RandomReal[{-10, 10}, {eles, eles}],      IdentityMatrix[eles, SparseArray]], {ii, 1, dim}, {jj, 1, dim}]; Dimensions[sparse]  {5, 5, 2500, 2500}  RepeatedTiming[  jSparse1 =     Apply[Join[##, 2] &,      Table[Join @@ sparse[[All, ii]], {ii, 1, dim}]];]  {0.04, Null}  RepeatedTiming[jSparse2 = ArrayFlatten[sparse];]  {0.0094, Null}  RepeatedTiming[  jSparse3 =     SparseArray`SparseBlockMatrix[{{i_, j_} :> sparse[[i, j]]}, {dim,       dim}];]  {0.23, Null}  Dimensions /@ {jSparse1, jSparse2, jSparse3}  {{12500, 12500}, {12500, 12500}, {12500, 12500}}  jSparse1 === jSparse2  True  jSparse1 === jSparse3  False  jSparse2 === jSparse3  False  Normal[jSparse1] === Normal[jSparse2] === Normal[jSparse3]  True

And here is the dense version with same conclusion

dim = 5; eles = 50; dense =    Table[KroneckerProduct[RandomReal[{-10, 10}, {eles, eles}],      IdentityMatrix[eles]], {ii, 1, dim}, {jj, 1, dim}]; Dimensions[dense]  {5, 5, 2500, 2500}  RepeatedTiming[  jDense1 =     Apply[Join[##, 2] &,      Table[Join @@ dense[[All, ii]], {ii, 1, dim}]];]  {1.251, Null}  In[5]:= RepeatedTiming[jDense2 = ArrayFlatten[dense];]  {0.61, Null}  RepeatedTiming[  jDense3 =     Normal[SparseArray`SparseBlockMatrix[{{i_, j_} :>         dense[[i, j]]}, {dim, dim}]];]  {2.3, Null}  Dimensions /@ {jDense1, jDense2, jDense3}  {{12500, 12500}, {12500, 12500}, {12500, 12500}}  jDense1 === jDense2  True  jDense1 === jDense3  False  jDense2 === jDense3  False  Max[jDense1 - jDense2]  0.  Max[jDense1 - jDense3]  0.  Max[jDense2 - jDense3]  0.

and again the third version produces a result that apparently is not identical with the other two, though numerically they seem to be the same.

What is the fastest (non-spell) way to breach a castle wall?

A while back, my Pathfinder (1st edition) group was discussing late-game possibilities. I, playing a monk, noted that at 16th level my fists counted as adamantine for the purposes of overcoming damage reduction – I could literally punch holes in mountains, given a bit of time. I was reconsidering this conversation today and I got to wondering – what is the most efficient human siege weapon we can create?

So here’s the challenge: We are faced with a standard castle wall, 10 feet thick and made of stone (Per 3 feet of wall thickness: AC 2, hardness 8, 540 HP, Burst DC 50). We want to create a 20-foot-wide hole in the wall, in order to create a breach wide enough for soldiers to attack through. Since a wizard would have no trouble with this, we will be disallowing all spells and spell-like abilities (including those cast through an item). We’ll also ignore any siege weapons, excluding the PC themself. Everything else is valid, as long as it is official/published – supernatural and exceptional abilities, feats, magic weapons, and so on. How can we accomplish this in as few combat rounds as possible?

Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?

I am trying to find the fastest algorithm to find all the possible paths of length $ N$ from a given node in a directed graph.

My solution is to do a modification of breadth first search from the given node for $ N$ iteration. Its time complexity is around $ \theta(V+E)$ . But the problem is $ |V|$ & $ |E|$ becomes exponential because as long as there is an edge, the same node can be visited again.

Can there be a solution of this problem with polynomial time complexity? It seems this problem has optimal substructure solution. Is there any solution using dynamic approach?