Questions tagged [efficiency]
Using as few resources (e.g. time, space) as possible while solving a problem. Use this tag if your question is specifically about resource usage, not for generic algorithm questions that happen to mention running times.
288
questions
0
votes
0
answers
2k
views
stack vs queue efficiency
Is there any literature / research on the average size efficiency of stacks vs queues? I asked because I was recently working on a problem where, if using a queue, the size quickly blew up and the ...
- 101
1
vote
2
answers
193
views
Optimal generalized bisection method
Suppose I'm looking for a some unknown number $x$ in the interval $[a,b]$ under the following assumptions:
$x$ is unique.
Given any $t \in [a,b]$ I can check, at some fixed computational cost, ...
- 111
1
vote
0
answers
119
views
Advantage of bulkloading in a B-Tree
https://en.wikipedia.org/wiki/B-tree#Initial_construction
Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key.
In the wiki example the keys are sorted, ...
- 131
2
votes
0
answers
36
views
Efficiently find the next item in a sequence to exceed some bounds
I have a bounded sequence of integers, and for each element, I want to know if the sequence next goes some distance above that element, below that element, or neither. This is straightforward in ...
- 121
3
votes
1
answer
111
views
What problems are believed to have an efficient algorithm?
Just out of curiosity,
What problems are believed to have an efficient algorithm, yet haven't been found such an algorithm for them?
This question came up to my mind after reading about PRIMES ...
- 555
0
votes
1
answer
702
views
Efficiency of 0-1 linear programming w.r.t. number of binary variables
I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0.
Lets say I have a fixed number of $n$ ...
- 140
4
votes
2
answers
837
views
Is it possible to implement a WeakMap with primitive keys and weak values?
Theory
Basically, I have a use-case where I would like to use primitives to store weak references to non-primitive values. If the value is no longer referenced anywhere else, then the entry should be ...
- 165
2
votes
1
answer
494
views
Calculating the information density of an encoding system
How do I calculate the information density of an encoding system?
This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major ...
- 364
2
votes
1
answer
175
views
Best combination of values pulled from a matrix
What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized?
For example, given the ...
1
vote
0
answers
45
views
Decode Reed Muller codes efficiently given only a syndrome
So given some erroneous Reed Muller code-word's syndrome as well as the Parity-Check/Generator Matrix how would one find the error vector?
The approach I took naively was to build the syndrome table, ...
- 111
2
votes
2
answers
245
views
GOTO vs. including line in loop - will it affect efficiency?
Let's say I have an algorithm something like as follows:
...
- 364
2
votes
2
answers
506
views
Efficient Algorithm to determine highly composited numbers [closed]
Im writing an algorithm to determine highly composited numbers.
But it's very unefficient with $\Omega(f(n)) = n³$.
Does someone know how i can make my code more efficient. Is my approach ok?
Here is ...
- 21
7
votes
2
answers
2k
views
Data structure for A*'s "open" set
I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet ...
8
votes
2
answers
4k
views
Why is it most efficient to resize a dynamic array to 2 * array.length()?
By dynamic array, I mean an array that when it becomes full we replace it with a new array having greater capacity than the previous array.
I read in a textbook that doubling the size of the array is ...
- 149
1
vote
1
answer
148
views
Parallel or efficient computation of value with momentum
I have a matrix $A$ with dimensions $M \times N$ and I want to compute $A'$ such that:
$$
A'_{i,j} = \alpha A'_{i,j-1} + (1 - \alpha) A_{i,j} \\
1 \leq i \leq M, 1 \leq j \leq N, \alpha \in [0, 1]
$$
...
- 121
0
votes
2
answers
4k
views
Comparing Selection, Insertion, and Bubble Sorts for database application
Explain and compare selection, insertion and bubble sorts. Assume
that your application (say a data base application) deals with
large records where comparisons are performed by means of integer keys....
- 121
0
votes
1
answer
259
views
Most Efficient Way to List All $n$-bit Permutations
Suppose we are tasked with expressing a randomized list of all numbers up to but excluding $2^n$ (ie. a random list of all n-bit numbers). What are some efficient ways to do such a listing using as ...
- 103
5
votes
0
answers
136
views
Evaluating sums of subsets
Let $X=\{x_1,...,x_N\}$ be a set of real numbers. We consider $M$ sums over its subsets, e.g. $N=9$, $M=3$
$$
\begin{align*}
s_1&=x_1+x_2+x_3+x_9,\\
s_2&=x_1+x_2+x_4+x_9,\\
s_3&=x_1+x_2+...
- 187
1
vote
0
answers
341
views
Tips for improving implementation of Wagner-Fischer-algorithm
So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
- 265
0
votes
0
answers
64
views
Multiple Cores vs Single Core Power Efficiency Equations
I was searching for OpenMP tutorials and I came up a video that showed some simple equations that promotes multiple core hierarchies against single core ones.
The equations used are
Capacitance = ...
- 101
22
votes
7
answers
10k
views
One element that differs in two arrays. How to find it efficiently?
I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem.
Let's say we have two arrays consisting of numbers that are unsorted. Array 2 ...
2
votes
0
answers
534
views
Unique integer priority queue with both $O(1)$ insert and extract-min?
I'm aware of the two questions prioritizing inserts and extracts individually, each in $O(1)$ time, but does there exist a unique integer priority queue algorithm for the range $[0, n)$ that can do ...
- 121
4
votes
0
answers
54
views
Element-wise merging and re-sorting lists of sorted elements
Imagine you have a vector of pairs $(id, x)$ where $id \in I$, some set of opaque identifiers (hereafter, ids), and $x \in \mathbb{N}$ some value. Assume that every $id$ value is unique in your list. ...
- 241
5
votes
2
answers
1k
views
Why quicksort instead of a B-tree construction? [duplicate]
As far as I know (despite some variations which provide empirical average-case improvements) quick-sort is worst case $O(n^2)$ with the original Hoare partition scheme having a particularly bad ...
- 387
0
votes
1
answer
47
views
Maximum waiting time between events such that k events are not missed
I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:
In a given motorcycle training circuit, the number of riders ...
2
votes
1
answer
294
views
Computing $n$th lexicographically smallest permutation of length up to $k$
I wonder how to tackle such problem, to be more specific:
Given a set and an integer $k$, find the $n$th lexicographically smallest permutation (with repetitions allowed) of the set. We will say ...
- 21
2
votes
1
answer
132
views
After the training phase, is it better to run neural networks on a GPU or CPU? [closed]
Sorry if this is the wrong forum for this question. My understanding was GPUs were more efficient for running neural nets, but someone recently suggested GPUs are only needed for the training phase. ...
- 171
4
votes
1
answer
541
views
Parsing CFLs (simulating PDA vs CYK algorithm)
We can simulate the PDA and parse the language with the following operations (vaguely):
Read the input symbol and top of stack - $O(1)$
Check all the transition rules (must check all for non-...
- 445
0
votes
0
answers
49
views
Comparing the efficiency of algorithms with finite input sizes
I'm a non-CS grad student working on an algorithm which would be an alternative to conventional GPS position estimation algorithms. My advisor insists that I must compare the run-time of these ...
- 113
0
votes
1
answer
449
views
Joining tables with minimum number of joins
I am working on a generalized problem where I am given only schema definition of multiple tables that i have.
Now i have to retrieve certain columns by joining multiple tables such that number of ...
4
votes
2
answers
182
views
Is there a faster algorithm for my graph problem?
I'm working on a tool that can analyze sizes of individual functions in a compiled binary. For each one it calculates how much space would be saved if the function was removed.
However, the current ...
- 626
11
votes
3
answers
1k
views
Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?
One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there ...
- 1,401
2
votes
2
answers
397
views
Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?
When a CPU simulates a certain program, as they do all the time, this is inherently slower than if the program would have been "baked in" into the hardware and computed directly. We know this from ...
- 3,752
4
votes
3
answers
3k
views
Non-recursive (iterative) DFS with $O(n)$ size stack
I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case.
...
- 1,944
2
votes
2
answers
302
views
Efficient immutable data structure for small multi-sets of integer ranges?
Background
I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure ...
- 710
3
votes
0
answers
161
views
Solving systems of boolean equations
So I have a system of equations where varibles range over $\{0,1\}$ and the only operation is logical or ($\lor$). Each equation is of the one of two forms
1) $a = b \lor c$
2) $1 = a \lor b$
where ...
- 3,810
2
votes
1
answer
4k
views
What is the fastest way to check if an integer is divisible by another?
What would the Big O be?
Can something like this be done in O(log(n)) where n is the number of bits?
- 217
1
vote
3
answers
298
views
More efficient vertex-labelling algorithm than BFS?
I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my ...
- 657
2
votes
2
answers
172
views
Finding perfect matchings with as few database queries as possible
I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows:
There are an equal number of men and women.
Each man has a perfect ...
- 137
10
votes
3
answers
6k
views
Maximum subset pairwise not divisible by $K$
I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$.
I tried to solve this problem, but I have found the ...
- 211
2
votes
1
answer
5k
views
improving java 8's implement to hash map using avl tree
Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup.
Will changing this implement to an avl tree change this O(n) case to ...
- 21
3
votes
1
answer
4k
views
Efficient algorithm for finding weakly connected components
We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to ...
- 165
0
votes
1
answer
284
views
Checking whether a node is expandable
I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable. A node is said to be expandable ...
- 323
0
votes
1
answer
57
views
Searching through all program of a stack-based language with little memory
I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output.
Given a program fragment, I can ...
- 251
6
votes
1
answer
135
views
How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?
Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the ...
- 248
5
votes
3
answers
982
views
Building static hash table with particular collisions
Is there efficient algorithm to encode keys in hash function with provided collisions?
By efficient I mean with low-ish runtime of lookup operation (taking constants into account) and realistic time ...
- 9,455
0
votes
1
answer
128
views
Can any algorithm efficiently be implemented as a SIMT problem?
Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions.
Excluding overhead due to hardware limitations (specifically, memory copy ...
- 155
1
vote
1
answer
226
views
What is the most efficient way to find bSmooth values in QS?
The heaviest part of QS is to search for bSmooth numbers.
So far I thought about two algorithms for solving this.
Trial division
calculate $X$ as a product of all the values in the factor base
speed ...
- 909
6
votes
1
answer
648
views
From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?
I am reading one of Guido van Rossum's essays on optimization in Python.
We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
2
votes
1
answer
482
views
Efficient formulation for binary integer linear programming
Problem:
There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either:
nothing, or
1 S, or
1 B, or
2 S, or
2 B, or
1 B and 2 S
We are given the ...
- 123