Questions tagged [program-optimization]

Questions about how to optimise a program's performance, both manually and automatically, e.g. in compilers.

Filter by
Sorted by
Tagged with
0 votes
0 answers
15 views

Minimum number of swaps to achieve prefix constraint

(An isogram is a word in which no letters repeat.) I'd like to know if there's a standard name for this problem, and/or any standard algorithms. If not, I'm interested in whether anyone has any ideas ...
SocraticMathTutor's user avatar
0 votes
1 answer
48 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: ...
Peter Wu's user avatar
  • 101
0 votes
1 answer
94 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 ...
J. Schmidt's user avatar
1 vote
1 answer
75 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 ...
user51515151's user avatar
0 votes
1 answer
3k 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; ...
JavaHopper's user avatar
1 vote
7 answers
202 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 ...
Luxspes's user avatar
  • 113
0 votes
0 answers
31 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 ...
Fernanda's user avatar
1 vote
1 answer
130 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 ...
Björn Lindqvist's user avatar
1 vote
1 answer
60 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 ...
MathCrackExchange's user avatar
1 vote
0 answers
40 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: ...
Max Heiber's user avatar
0 votes
1 answer
40 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 ...
yangvz's user avatar
  • 1
0 votes
1 answer
69 views

SVMs - Fat (Margin) Boundary: Why is $\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$?

I am trying to understand SVMs in depth watching lectures from MIT. The professor to reduces the classification problem into an optimization problem. To do that, he first defines the decision and ...
HelloWorld's user avatar
1 vote
1 answer
685 views

What is the difference between speculative execution & branch prediction?

In computer architecture I'm confused between speculative execution & branch prediction. Are the same or different?
user836026's user avatar
10 votes
1 answer
1k views

What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

On an imperative programming language, let us consider the following program: ...
yuezato's user avatar
  • 123
1 vote
1 answer
88 views

optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$

I want to optimize an algorithm for calculating $g(n)=\sum^n_{k=2} p(\Omega(k))\Omega(k)$ where $$ p(n) = \begin{cases} 1 &\text{if $n$ is odd} \\ -1 &\text{if $n$ is even} \end{cases}$$ and ...
razivo's user avatar
  • 113
6 votes
2 answers
292 views

Does strong typing contribute to better performance optimization by compiler?

Do guarantees provided by the type systems enable better performance optimizations by the modern compilers? I found a 20+ year article suggesting that it would. Also, intuitively speaking, knowing ...
kolistivra's user avatar
3 votes
1 answer
118 views

Algorithm to find the minimum (additional) popular votes to win the electoral college

So I'm thinking of a simple election prediction program to keep track of the minimum ballots the candidates must gain from the uncounted votes in order to win the election. Assuming we are considering ...
Doug Adam's user avatar
0 votes
1 answer
115 views

Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?

I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations. What I'm trying to calculate: I have number of items. Lets call items a1, ...
Mikko Korhonen's user avatar
1 vote
1 answer
143 views

Minimizing series of XORs

Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form $$x_i \leftarrow x_i \oplus x_j,$$ (where $\oplus$ is the binary XOR) can we efficiently ...
orlp's user avatar
  • 12.6k
3 votes
1 answer
65 views

How to best calculate the best possible path with weights

Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output ...
SopitaBanon's user avatar
1 vote
0 answers
195 views

Is this a valid heuristic for Dots and Boxes to reduce the branching factor of the search tree?

I am implementing an AI based on the MiniMax algorithm that plays the game Dots and Boxes. I would like to reduce the branching factor of the search tree, by introducing a heuristic rule that limits ...
Zyx's user avatar
  • 145
4 votes
0 answers
201 views

Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
xopticx's user avatar
  • 41
2 votes
0 answers
59 views

Compiler optimization which does an SMT-like optimization in software?

Say I had two functions called one after the other: ...
user130558's user avatar
2 votes
2 answers
738 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
user108534's user avatar
1 vote
0 answers
123 views

Tree Optimization, Combinatorics, algorithm [closed]

My Partners and me, we are trying to optimize frequency process... I used Java to show our Problem, but the question is about algorithm NOT about Java implementation. Although implementations in java ...
Anita's user avatar
  • 111
0 votes
1 answer
451 views

Autocorrect algorithm - How to implement a decent "apostrophe & elision" feature?

shorter version of the original question (as requests in comments) What is the algorithm to handle missing apostrophe as it is done in auto-correct feature of Android virtual keyboard? (If it helps /...
Pascal's user avatar
  • 103
1 vote
0 answers
58 views

Order of Traversal in Bidirectional Dataflow Analysis

Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
TheAhmad's user avatar
  • 111
0 votes
1 answer
231 views

Any CPUs using value prediction, dynamic instruction reuse?

There is a lot of research about techniques that try to reuse the previous result of an instruction, either memory loads or arithmetic, such as dynamic instruction reuse, value prediction, based on ...
Gratian Lup's user avatar
2 votes
1 answer
102 views

Optimize sorting matrix entries by row and column

I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
vibe's user avatar
  • 208
4 votes
1 answer
145 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
mathwizzz22's user avatar
0 votes
1 answer
386 views

Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe ...
Timothy's user avatar
  • 115
20 votes
12 answers
13k views

Data structure or algorithm for quickly finding differences between strings

I have an array of 100,000 strings, all of length $k$. I want to compare each string to every other string to see if any two strings differ by 1 character. Right now, as I add each string to the ...
JGut's user avatar
  • 311
0 votes
2 answers
558 views

Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers

This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2). Is it possible to do this question if we entirely want to skip ...
Saras Arya's user avatar
5 votes
0 answers
52 views

Symbolic Math Systems As Speculative Optimization For Numerical Software?

Has there been published work on hiding symbolic math within numeric software, partitioning parallel processes between speculative symbolic optimization search and numeric evaluations? Real world ...
James Bowery's user avatar
3 votes
1 answer
301 views

How to avoid permutations in the n-Queens problem?

EDIT: if you are not familiar with the problem and the solution, it's nicely explained here. I have solved the n-Queens problem as an exercise using backtracking (recursion), but the problem I have ...
Ciprum's user avatar
  • 279
1 vote
3 answers
106 views

Automatic softcore configuration based on intermediate representation (IR) compiler output

When compiling a piece of software (with LLVM for exmple), you first transform your code into some kind of intermediate representation (IR code). This IR code needs to be converted to your target ...
Sap Chicken's user avatar
0 votes
1 answer
530 views

Is there a poly-time algorithm for expanding out polynomials

so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of $$ z = (x+y)(x-y) \implies x^2+xy-xy+y^2 $$ ...
wjmccann's user avatar
  • 549
0 votes
0 answers
24 views

Non-optimal program, bad choice of language or Low-speed system?

To check some results of an article, I wrote the proposed algorithm from the Coding articles. In the article, some results from the algorithm were obtained. Unfortunately, the performance of my ...
maha_ak1990's user avatar
0 votes
0 answers
566 views

Why is sequential search of ordered list slower than search of unordered one

I have got assignment to implement set class with linked list, so I first made it with unordered list and time needed to insert million integers is bit less than hour. Then I thought I can get it to ...
joks's user avatar
  • 1
15 votes
2 answers
1k views

What property of cons allows elimination of tail recursion modulo cons?

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops. ...
Maxpm's user avatar
  • 253
3 votes
4 answers
136 views

Can loops like this one be algorithmically transformed into multiplication

Are there known techniques for converting a loop like the following to an if and a multiplication? ...
Ryan1729's user avatar
  • 354
3 votes
0 answers
106 views

Lazy evaluation on slow Boolean functions (optimization)

Short-circuit evaluation is a straight forward subject for lazy evaluation on Boolean expressions, I noted that two factors could be useful in ordering Boolean functions to improve run-time. But this ...
Abderrahim ben's user avatar
-1 votes
1 answer
12k views

How do I calculate the speedup properly?

I am trying to calculate the speedup of this, but I am getting the wrong answer: Assuming that we have a program where we have two execution phases. One phase takes 1 time unit to execute and can ...
George W's user avatar
2 votes
1 answer
908 views

Why is it so difficult to eliminate dead loops?

I recently came across an issue where my compiler was not able to eliminate some "obviously" dead code - it was a function that returned nothing, with no side effects, and a cursory analysis of the ...
Djzin's user avatar
  • 139
8 votes
3 answers
8k views

Constant folding vs. Constant propogation

What is the difference between constant folding and constant propogation? They both seem to do the same thing, instead of saving constants into stack or evaluating a full arithmetic expression, they ...
nikolaevra's user avatar
3 votes
2 answers
300 views

Is writing a compiler for a compact language easier?

I am contemplating the project of writing a compiler. I am wondering if, aside from the availability of easy google results, it is easier to write a compiler for a more explicit/verbose language such ...
Raoul's user avatar
  • 205
4 votes
1 answer
126 views

What formal representation is commonly used to describe compiler optimizations?

I have devised a compiler optimization that works on any structured language that has arrays assignments array[index] = value and counted loops ...
El Marce's user avatar
  • 333
1 vote
0 answers
31 views

Program Transformation to Disintermediate Isomorphic Representation Transforms

Given two representations of the same abstract data type, any optimal program that incorporates one representation has a corresponding optimal program that incorporates the other. What is the field ...
James Bowery's user avatar
22 votes
2 answers
4k views

Why is static-single assignment preferred over continuation passing style in many industry-used compilers?

According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects ...
CinchBlue's user avatar
  • 584
2 votes
1 answer
2k views

Is it possible to submit every March Madness bracket?

A few years ago Warren Buffett started offering $1 billion to anyone who could correctly predict the winner of every game in the NCAA men's basketball tournament. A 64 team (we won't count the first ...
Chris Dieckhaus's user avatar