Questions tagged [program-optimization]
Questions about how to optimise a program's performance, both manually and automatically, e.g. in compilers.
91 questions
0 votes
1 answer
111 views
Is this optimization of Tarjan's off-line lowest common ancestor algorithm correct?
I have this speed up technique of Robert Tarjan's version: Question: Is it correct?
- 60
0 votes
1 answer
126 views
Undecidable? Redundant computation detection
In a typical implementation of a Turing-complete procedural programming language, it's often desirable to detect redundant computations and optimize them away. But given that I can only think of ...
- 448
0 votes
1 answer
81 views
the maximum element of every subarray in queries
given an array a of length n,and another 2d array queries where queries.size()<=a.size() and queries[i].size()==2 and queries[i][0]=i. queries[i][0]=start index of that subarray and queries[i][1]=...
- 3
1 vote
0 answers
46 views
Is it possible to start a Dijkstra search from a source node s, bounded at r, with a non-empty distance map and priority queue?
TL:DR: I want to know whether correctness is affected if I start Dijkstra with a distances map that already contains shortest paths shorter than $r$ and a priority queue initialised with those ...
- 11
1 vote
0 answers
48 views
The problem of finding a local minimum of a function
I wrote code for the Regular Simplex (RSM) and the Irregular Simplex (Nelder-Mead Method (N-MM)) in Visual Studio in C++. For given functions (quadratic (QF), Rosenbrock with alpha = 1 (RF1), ...
- 11
0 votes
1 answer
96 views
Is it possible to automatically detect which variable is not used in future and free those memory?
What I need is similar to garbage collection but a bit different, consider the following code: ...
- 141
0 votes
2 answers
250 views
How to avoid costly square root operations in A* algorithm?
As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is ...
- 827
1 vote
1 answer
125 views
Programming language compiler that will perform the composition of primitive functions with optimization
Is it possible to create a some programming language compiler that will perform the composition of primitive functions with optimization? In fact, the maximum possible optimization in the context of ...
- 45
0 votes
1 answer
7k views
Update a property of all objects in a List/Collection/Array when at least one object satisfies a criteria using a single loop
Here is the puzzle I was asked in an interview There's a List of Employee objects. Update all the objects in the list to be eligibleForHike if at least one employee exists whose salary is less than x; ...
- 109
1 vote
7 answers
442 views
How to design a faster sort algorithm? Is there sort of meta-algoritm for it? Or we do not understand how better sort algorithms were discovered?
I know that Quicksort or MergeSort are faster than, say, Bubblesort or Selection sort. And I know why (complexity metrics) but I never been able to find out how could someone start with, for example ...
- 113
0 votes
0 answers
67 views
optimization problem about capacitated vehicle routing problem
I have an optimization problem. The problem consists initially of the presence of several trucks, each one having different maximum capacities. There are also multiple customer orders, each with a ...
- 1
1 vote
1 answer
311 views
What is the difference between sparse conditional constant propagation and constant propagation?
Reading the Wikipedia pages on these topics, it seems that sparse conditional constant propagation (SCCP) is a more powerful form of constant propagation (CP)? E.g all optimizations available in CP ...
- 1,312
1 vote
1 answer
163 views
Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related
Let $F$ be a field. Suppose we have a machine $T$ that works with words that are elements of $F$, for exmaple $F = \Bbb{Z}/2, \Bbb{Q}$ (using arbitrary precision arithmetic), or $\Bbb{Z}/p$ for a ...
1 vote
0 answers
78 views
How is a homeomorphic embedding a homeomorphism?
How is a homeomorphic embedding (in the sense of term algebra) a homeomorphism? Definition of homeomorphic embedding: Alt text: ...
- 378
0 votes
1 answer
73 views
Why do the following algorithms for Quadratic Primes perform so differently?
I'm trying to solve for https://projecteuler.net/problem=27, and I have to optimize one part of the implementation from slow() to fast(). Why do they perform so differently? I'm guessing branch ...
- 101