Skip to main content
Share Your Experience: Take the 2024 Developer Survey
21 votes
Accepted

Why do we have to trade abstraction for speed?

Debunking some myths There is no such thing as a fast langauge. A language can generally produce fast code, but different languages will excel on different benchmarks. We can rank languages on a ...
Joey Eremondi's user avatar
12 votes
Accepted

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

Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass? Donald Knuth and Michael Plass. "Breaking Paragraphs into Lines". ...
David Cary's user avatar
8 votes

Is Timsort more efficient than merge sort and why?

In terms of asymptotic complexity, timsort and merge sort have the same worst-case complexity: they both make $O(n \log n)$ comparisons to sort a list of $n$ elements. Given a particular input, a ...
Gilles 'SO- stop being evil''s user avatar
8 votes
Accepted

Why computer take long time to open huge text files?

The difference would be between loading the complete file into memory and reading the file part-by-part as you need each part. If I open a file in some applications I am asking for it to be fully ...
StephenG - Help Ukraine's user avatar
7 votes
Accepted

Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?

Assuming $n$ is a power of $2$, you have: $$ \sum_{i=0}^{\log n} \log \frac{n}{2^i} = \sum_{i=0}^{\log n} \left( \log n - i \right) = \sum_{i=0}^{\log n} i = \frac{(\log n)(\log n+1)}{2} = \Theta(\log^...
Steven's user avatar
  • 29.5k
5 votes

A faster, leaner JavaScript for scientific computing: what features should I keep?

Creating a new language is not necessary. One can write performant numeric computing in JavaScript today, without compilation/transpilation. As a scripting language, JavaScript compares quite ...
kgryte's user avatar
  • 151
5 votes
Accepted

Variable size and CPU performance

Would it make any difference performance-wise to only use the largest variable size on the platform and use business logic to enforce reasonableness in the values being processed and stored? Yes, it ...
manlio's user avatar
  • 2,062
5 votes
Accepted

Cache effective access time calculation

This is the kind of case where all you need to do is to find and follow the definitions. There is nothing more you need to know semantically. What is actually happening in the physically world should ...
John L.'s user avatar
  • 39k
5 votes
Accepted

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

There are at least 3 architectural tricks by which an increased number of transistors can lead to higher performance. One of them is parallelism, as you point out. A second technique trading off ...
Wandering Logic's user avatar
5 votes

What is the difference between FLOPS and OPS?

What is the difference between FLOPS and OPS? FLOPS is floating-point operations per second OPS is operations per second The difference should be obvious from the name: one is the number of ...
Jörg W Mittag's user avatar
5 votes

Why do benchmark results vary at all?

Your assumption that the clock rate is constant is wrong. My computer at home can at any time switch each core to one of 15 different clock speeds. Your assumption that the same operation always takes ...
gnasher729's user avatar
  • 30.4k
4 votes

Maximum number of segments with no intersection

I can show you a solution that I suspect is $O(n \log n)$, but I haven't proven the runtime. Edit: Following a linked solution, I amended this solution to be simpler and run in $O(n \log n)$. So the ...
ConcernedCitizen's user avatar
4 votes
Accepted

Are there absolute reasons to prefer row/column-major memory ordering?

Whether row-major or column-major order is more efficient, depends on the storage access patterns of a specific application. The underlying principle of computing is that accessing storage in ...
Steve's user avatar
  • 494
3 votes

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

r1 = reverse_string2(s[:mdpt]) r2 = reverse_string2(s[mdpt:]) Here you go in recursion twice. In both recursions you will again recurse twice, etc, which ...
Albert Hendriks's user avatar
3 votes
Accepted

Slowdown when accessing data at page boundaries?

Go to Agner manuals page and download them all, you will find tons of interesting info there. In particular, microarchitecture.pdf says There is a false dependence between memory addresses with ...
Bulat's user avatar
  • 1,873
3 votes

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

This can be solved with dynamic programming; see https://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness or https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Doubt on Performance Comparison of Splay Trees

There have been various real world applications that use splay tree. One of the most prominent examples is the gcc compiler that applies splay tree. There are many other examples. In fact, ACM ...
John L.'s user avatar
  • 39k
3 votes
Accepted

Fast computing of a matrix power for large integer values in C++

Since your matrices are small $(50 \times 50)$, you can probably just compute $M^t$ through repeated exponentiation where the exponents are powers of $2$. Write $t$ in binary so that $t = 2^{k_1} + ...
Steven's user avatar
  • 29.5k
3 votes
Accepted

Why do computers become slow over time (HW PoV)?

As mentioned in the comments, this has many open ends but there are certain major aspects which could contribute to slowing down. It comes down to physics. As you said heat. Heat does a lot more than ...
Rinkesh P's user avatar
  • 1,024
3 votes

Why does Elbrus use VLIW architecture?

At some point in time people thought that VLIW computers were a very reasonable approach. And as long as you cannot handle out-of-order execution it is quite useful. You may be able to execute say ...
gnasher729's user avatar
  • 30.4k
3 votes
Accepted

Tree algorithm - arrange integer array numbers to form largest number

I'd like to say good work on the soluton! It's a nice attempt you have converting it to a tree as well, and I think a tree can be used in some way. However, I think using specifically an N-ary tree, ...
Minko_Minkov's user avatar
2 votes

Are fractions more computationally "expensive" than whole numbers?

This link below compares all arithmetic operations between floating point and integer variables on various architectures and processors. With the general conclusion drawn that additions and ...
Raghavendra Singh Dasila's user avatar
2 votes
Accepted

How to get the quick answer to the "Is there AT LEAST ONE subset that contains all given elements?" question if the set of subsets is very large?

It's possible to answer such queries in time $O(M^{1 - S/N})$, where $S$ is the size of the subset in the query, using a data structure from Ron Rivest: Partial-Match Retrieval Algorithms. Ronald L. ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Sorting networks hybrid sort

The article Applying Sorting Networks to Synthesize Optimized Sorting Libraries by Codish et al. experiments in this area, trying to take advantage of "instruction level parallelism and non-...
Morwenn's user avatar
  • 304
2 votes

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

First of all, repeat until convergence isn't quite a well-defined command. Typically, such instructions are implemented by checking the "progress" of some performance measure, stopping once progress ...
Yuval Filmus's user avatar
2 votes

Variable size and CPU performance

I would say it depends on the application and target architecture. Usually the x86 is the main target, but practices used there might not transfer well into a embedded domain. Other architectures (...
Anton Krug's user avatar
2 votes
Accepted

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

Odds are, you can't. That's a judgement call, and it's notoriously hard to get other people to change their judgement. The path is to find new evidence or facts they might not be aware of; assemble ...
D.W.'s user avatar
  • 161k
2 votes

Big-O notation analysis

c) is incorrect. It looks like you are saying it is $O(n^{\frac{1}{2}})$ or $O(\sqrt{n})$. That cannot be the case. You are adding one to $i$ and subtracting one from $j$ on each loop iteration. ...
mikeazo's user avatar
  • 233
2 votes
Accepted

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

It is equivalent to $$\bigwedge_{k=1}^{N} \bigvee_{i_k=1}^{M} x_{i_k k}.$$ This is a much simpler expression: $NM$ terms instead of $M^N$ terms, if you expand everything out.
D.W.'s user avatar
  • 161k

Only top scored, non community-wiki answers of a minimum length are eligible