Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [performance]

The tag has no usage guidance.

0
votes
1answer
16 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
46 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
3
votes
1answer
75 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
126 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
41 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 \...
6
votes
1answer
71 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
2k 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 ...
2
votes
1answer
104 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
79 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
25 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
28 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 ...
0
votes
0answers
16 views

Relevance of Pure ALOHA for small network load G?

The theoretic performance of Pure ALOHA networks is a vastly studied topic and references can easily be found , e.g. on https://en.wikipedia.org/wiki/ALOHAnet#cite_note-tann-14 Using a Poisson ...
0
votes
0answers
29 views

Type of CPU Instructions used in text processing

Scientific applications use MFLOP(floating point operations per second) as a performance metric. However, it would be useless metric for text processing applications because text processing does not ...
-1
votes
2answers
83 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
54 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
42 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 ...
3
votes
1answer
480 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 ...
3
votes
1answer
1k 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
150 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
97 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
373 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
613 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
98 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
3k 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
41 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
146 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
58 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
60 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
242 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
213 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
37 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
422 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
197 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 ...
2
votes
3answers
126 views

Why computer take long time to open huge text files? [closed]

Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be ...
4
votes
1answer
255 views

Best way to merge different trees to single data structure?

I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast ...
2
votes
1answer
566 views

Understanding Amdahl's Law calculation

I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput. Which is a pretty ...
0
votes
1answer
47 views

The impact of caching on the system performance or on the user experience

I am working on modeling a certain system's cache layer and comparing two algorithms. One outperforms the other one; it shows the higher cache hit rate (%). But what is important is the impact of ...
1
vote
1answer
42 views

How to measure the degree of randomness in Disk I/Os?

Most disk-based system's performance heavily depends on its disk access patterns. So maximizing the sequential I/Os while avoiding the random I/Os is a typical goal in performance perspective. I am ...
12
votes
3answers
1k views

Why do we have to trade abstraction for speed?

Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier ...
0
votes
0answers
238 views

Hashtable vs cache-oblivious

This question has been asked in the theoretical community, but deemed as too practical. I am moving it here, I hope it is on-topic. I'd like to know more about real performances of data structures, ...
0
votes
0answers
66 views

Performance on modifying cycle time

I learnt in my computer architecture course on Caches, that if we keep the memory speed of a machine the same and half the clock cycle time, the miss penalty doubles. Why does this happen? What is ...
3
votes
1answer
87 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
10
votes
3answers
2k views

Why is a (collision-less) hashtable lookup really O(1)?

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for. My question is: why is collision-less ...
5
votes
3answers
125 views

Scientifically acceptable method for comparing performance of algorithms

I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the ...
2
votes
1answer
273 views

Can a vectorized computation always be parallelized?

If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, ...
0
votes
1answer
77 views

Is program analysis part of programming language theory?

If I am correct, programming language theory studies syntax and semantics of programming languages, and design and implementation of programming languages (e.g. compiler, ...) Does programming in ...
1
vote
0answers
40 views

Better Algorithm to determine the number of all TRUE rows in a logical matrix

I have a matrix of logicals (TRUE, FALSE) and I need to count the number of rows that contain only ...