Questions tagged [performance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
2answers
495 views

What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment. Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
1
vote
1answer
15 views

Time efficient way to implement Multi-Armed-Bandits?

I'm doing a research on Multi-Armed Bandit (MAB) problem with approx. 1 million arms. In contrast, the number of iterations is of course much larger, about 10-20 million. Most MAB-algorithms require ...
-2
votes
0answers
29 views

How to calculate average of Performance Efficiencies

Problem description: Assume you have a sample of application's performance efficiencies on different computers. Performance efficiency is defined as the ratio of application performance to peak ...
0
votes
0answers
28 views

Amdahl's Law and efficient algorithms

Does the efficiency of algorithm leading to better performance of the system can be attributed to Amdahl's Law? or Is the Amdahl's law only applicable for the analysis of efficient hardwares and ...
0
votes
1answer
22 views

F-measure with $\beta > 1$

Consider the F-measure $F_{\beta}$. I know that with $\beta < 1$ precision is given more importance, ending with $F_{0} = precision$. With $\beta > 1$ means recall gets the upper hand, with the ...
0
votes
1answer
24 views

Performance speedup with Amdahl's law

Consider this question: A program has 1M instructions and 30% of them are SQRT with CPI=8. The CPI of the rest of the instructions are 3. If we reduce the CPI of SQRT to 2, how much speedup is ...
0
votes
0answers
29 views

How does database indexing improve performance for lookup?

I read that indexing a database will improve its performance by assigning a number to each row to loop through. Even after indexing, to get the data at say row 1024, shouldn't the memory reader go ...
0
votes
1answer
38 views

Classification accuracy based on top 3 most likely classifications

My goal is to recommend jobs to job seekers based on their skill set. Currently I'm using an SVM for this, which is outputting one prediction, e.g. "software engineer at Microsoft". However, consider ...
1
vote
1answer
28 views

Simplification of a multi-index Boolean expression towards computation in fewer steps

Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following ...
2
votes
2answers
37 views

Minimum words in a string given a dictionary

The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
0
votes
0answers
17 views

How to model internal queues shared between services in queueing networks

I am trying to model a load balancer as a queueing network. The load balancer has a number $n$ of internal threads. There is a central queue of requests from which the threads are fed. Each thread ...
1
vote
1answer
72 views

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
1
vote
1answer
44 views

Slowdown when accessing data at page boundaries?

Hi I have a program which accesses memory words that are located X bytes apart in virtual address space. For instance, ...
0
votes
2answers
29 views

How to properly compare performance of a prototype against a baseline

Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average). ...
-1
votes
2answers
709 views

Confusion in speed up calculation for pipeline architecture

This is an online question I am trying to solve. You are given a non-pipelined processor design which has a cycle time of 10ns and average CPI of 1.4.If a pipelined processor having 5 stages are 1ns, ...
1
vote
0answers
23 views

Can graph execution be better optimized than imperative programs?

I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why ...
0
votes
2answers
116 views

Importance of Frequency vs CAS Latency in memory performance

I was looking at the Wikipedia page for CAS Latency: https://en.wikipedia.org/wiki/CAS_latency And I noticed the obvious trend - at higher frequency, despite CAS latency degrading (growing), the ...
1
vote
1answer
84 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
3
votes
1answer
120 views

Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|). Now let's modify ...
3
votes
1answer
191 views

d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
1
vote
0answers
45 views

Accuracy and performance between a division and subtraction for a ratio in decibels

For comparing two images, one can use the Peak Signal-to-Noise Ratio (PSNR) metric, defined as follows: $\mathrm{PSNR} = 10 \cdot \log_{10}\left(\frac{\mathrm{MAX}^2}{\mathrm{MSE}}\right) = 20 \cdot \...
7
votes
1answer
151 views

Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

Modern personal computers as far as I understand have increased in power (measured informally by ability to compute “more demanding programs”) due to two “broad factors”: decreased transistor size (...
2
votes
1answer
10k views

Cache effective access time calculation

In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct ...
3
votes
1answer
382 views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
1
vote
1answer
96 views

How to describe the time complexity of a continually running program with a stream of inputs?

Maybe time complexity isn't the right term. Performance? There must be some way of describing the efficiency of a program over time. For instance, I recently had a part of a program that took a ...
-1
votes
1answer
27 views

Performance - Computer Organization and design

A popular app takes 10 seconds to execute on a 11 watt smartphone A, and it takes 8 seconds to execute on a 13 watt smartphone B. The app is a bigger drain on the battery on which smartphone?
0
votes
1answer
37 views

How to show that i have significant improvements over the baselines?

I had review feedbacks regarding my recent publications and reviewers argued that the improvements are not significant over the baselines. I tried my classification algorithm on some image datasets ...
-1
votes
2answers
111 views

Big-O notation analysis [duplicate]

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct. I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$ ...
0
votes
1answer
83 views

Finding maximum clique in a distance matrix created by certain pattern

I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum ...
1
vote
0answers
55 views

Operation count: Solving Ax=b with sparse diagonal matrix

I've seen several tables that list operation counts for matrix-inversion related problems, but none of them actually brought forward the way of computing them. I'm interested in solving ...
0
votes
0answers
28 views

How to define a generic evaluation metric

Given a system (S) that accepts a tuple of parameters ($\alpha, \beta, \gamma \dots$ etc). These parameters affect the performance of S in a different way. For instance, decreasing $\alpha$ would ...
2
votes
1answer
711 views

Recursive functions from O(n) complexity to O(log n)

For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each ...
4
votes
1answer
2k views

Is Timsort more efficient than merge sort and why?

I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.
1
vote
1answer
281 views

Trilinear interpolation for distorted cubes?

Is there a variation of trilinear interpolation that works on a "cube" that has been distorted (by moving one or more of its corners by an arbitrary amount into an arbitrary direction)? I know that I ...
0
votes
1answer
31 views

What do you call a lower/upper bound that is the best one?

I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it ...
0
votes
0answers
143 views

Amdahl's Law when the speedup of new component = ∞

I was doing a problem about Amdahl's Law when I noticed that $s,(local$ $ speed-up)$ was incalculable. The wording: A computer takes 100 seconds to execute a program. The multiplication operations ...
3
votes
1answer
797 views

Variable size and CPU performance

When you learn programming they tell you choose data types that suffice for the concepts you're expressing, i.e. not too small because then your data won't fit and not too big because you don't want ...
1
vote
1answer
916 views

How to handle the repeat until convergence condition in time complexity and summarize the time complexity? [closed]

I am a novice in complexity calculation. I need to calculate the overall time complexity. My attempt is given below: Here, N = number of data points (N>300), C ...
0
votes
0answers
124 views

Probability in Dynamic frame aloha

If I've RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet ...
-1
votes
1answer
6k 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 ...
0
votes
1answer
43 views

Difference in scale between mean page loading times and exponentially distributed page loading times?

Apologies if this is the wrong place to ask. For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The ...
2
votes
2answers
198 views

Sorting networks hybrid sort

I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(< 16 ...
1
vote
2answers
63 views

Are fractions more computationally “expensive” than whole numbers?

I have a problem where the values are represented to humans as [0, .5, 1, ..., 8] But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering ...
2
votes
1answer
148 views

What is the basic idea behind the usage of TLBs?

I know how Translation Lookaside Buffers work, and i also know we use them to improve the performance of data/program access by storing the recent page numbers - frame numbers in a memory cache. The ...
8
votes
2answers
331 views

GCD of a pair of products

I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use ...
2
votes
1answer
320 views

Changing Rabin-Karp without modulo to Rabin-Karp with modulo

I am trying to solve a string matching problem using Rabin-karp algorithm. I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now. (this ...
1
vote
1answer
38 views

Estimating the run time of a program according to a given CPU performance

When we have a recurrence relation of a program, as an example: T(N) = N log N + 9N + 55 and the CPU capability let's say (10^6) or any other number. What is ...
0
votes
0answers
624 views

What is the Effect of Hidden Layer Size?

I aim to gain more intuition with regards to the role of a hidden layer in a neural network architecture. And further to understand whether my classification problem is a linear one or not. Here is ...
1
vote
0answers
243 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 ...