# Tag Info

34

You've overlooked the key characteristic of the logarithm base. Because i is divided by 2 in each iteration, the running time is logarithmic with base 2. And log2(500) ~ 8.9 What you are looking at is log10(500) ~ 2.7 (logarithm with base 10) By the way, the reason why the base is often omitted in runtime discussions (and your calculator ...

22

Because in order to free memory as soon as the reference counter hits zero, you have to keep a reference counter. And that doesn't come for free. Typically, it limits your throughput. There are generally two major strategies for implementing garbage collectors: tracing collectors and reference counting collectors. (There are others, but those are the ones ...

18

The complexity class is O(n²). Visual explanation Imagine a n·n square which lists all the values j takes on. We remove the diagonal (which has n entries) and the upper right half because j will never be larger or equal to i. We are then left with an area of (n² - n)/2. i | values of j | no of j values ----+-----------------+--------------- 0 | · ·...

14

Because it would be too expensive to do it continuously. "Mark and sweep" garbage collectors periodically sweep the memory space for objects that have been dereferenced. Generational garbage collectors sweep those objects first that are most likely to have been disposed of recently (which turns out statistically to be the objects most recently created). ...

13

To me, the entire point of suppressing warnings is to maintain a "clean bill of health" for your project. If you know that your entire code base compiles cleanly, it's immediately obvious when someone does something wrong that causes the first warning to appear in the issues list. You can then fix the error or suppress it if you can prove that it's spurious. ...

11

You keep on changing your function. But keep picking ones that will run forever without conversion.. Recursion gets complicated, fast. The first step to analyzing a proposed doubly recursive function is to try to trace it through on some sample values, to see what it does. If your calculation gets into an infinite loop, the function is not well defined. ...

10

Check out GNU MP. It has a C++ class based interface if the C one is too scary. As far as the speed comparison goes, I would seriously take into account programmer speed here. If it's going to take an extra month to do it "the fast way" for a one-shot program because of unfamiliarity with the language, I wouldn't bother.

10

Suppressing warnings is something that needs to be done with extreme care. A warning means: The compiler found something that looks dodgy. It doesn't mean it is dodgy, it just looks like it to the compiler. Sometimes you have code that is perfectly fine and gives a warning. Sometimes you fix it by slightly modifying your code. Sometimes the compiler has ...

9

The MSDN article is subtly incorrect. Instead of "cause different behavior" it should be "requires different behavior". In particular, the compiler enforces different requirements for the two keywords, even though the same mecanism (IL) is used to enable the behavior.

8

Benchmarking is a difficult science. It seems that your computer is conspiring against you: Your CPU keeps often-requested data in caches. As accessing memory in a cache is faster than using other memory, this can warp benchmarks. Your OS may cache files in memory rather than loading them from disk. Obviously this hasn't happened the first time you run a ...

8

In addition to Michael Borgwardt's answer, the tilde character in front of each answer should be read as "proportional to". So if you doubled N (say, from 500 to 1000), you would see that the run time (or, in this case, number of stars printed) would increase by a factor which would be equal to (log1000 / log 500), which is independent from which base you ...

8

Because making a function virtual incurs a non-zero runtime cost. Part of the philosophy of C++ is "you only pay for what you use"; i.e. you don't pay the cost of a virtual function unless you've explicitly asked for it by writing virtual in your code. As for why it incurs that runtime cost, the short answer is that a father pointer by itself does not say ...

7

I would recommend creating your DSL on top of an existing language (internal DSL). I've done this a few times with Python, creating systems where the consumer of the DSL writes a python file that is used as a configuration file for the system. The configuration file uses constructs (classes, functions) that I have defined. These constructs form the DSL. IMO,...

7

By many different methods, not easily reduced to just a few paras. Here are some, in roughly ascending order of abstraction. The OS implements one or more privileged instructions (trap, syscall, etc). The compiler emits code to translate certain language constructs into those instructions. [ASM] The OS provides an API in a form compatible with the external ...

7

No, it is not possible. You should be using composition instead of inheritance here. Have Heap<T> as field and assign specific instance into this field. public class PriorityQueue<T> where T : IComparable<T> { Heap<T> _heap; public PriorityQueue(bool type) { if (type == smallestFirst) { _heap = new MinHeap<T>()...

7

You seem to be confused because “runtime” is both a noun and an adjective. Your question asks about the three distinct concepts of the “run-time environment”, the “language runtime”, and “run-time linking”: As a noun, the “run-time environment” of a program, or phrased differently: the “environment of a process”, refers to the (changing) state of the ...

6

There were a lot of tongue in cheek statistics in black and white. It's also possible that the statistic is just some semi-random number based on some function that is not actually linked to any real code execution statistic.

6

Most of these terms have become very ambiguous. "Library" is the simplest. It's just some utility code that resides on your computer, designed to be used by applications or other libraries. It could be a standard library that came with the compiler/interpreter, or it could be a third-party library. Some "pure" libraries are written only in the user's ...

6

Some languages are pretty strongly static, and only allow the specification of the inheritance relationship between two classes at the time of definition of those classes. For C++, definition time is practically the same as compilation time. (It's slightly different in Java and C#, but not very much.) Other languages allow much more dynamic reconfiguration ...

6

The definition of asymptotic running times is... well asymptotic. That is, it is the behavior of the function as N is very very large. The behavior of the function at smaller N is irrelevant. In this case, as N is very very large, it is larger than 1000. That means that the code inside the if clause is actually completely irrelevant as far as asymptotic ...

6

There are a few components that make up the runtime environment. Not all components are applicable to all environments (e.g. assembler, C++, and C# all have different runtime facilities), but they generally comprise the following: The CPU and hardware platform on which the program runs. The operating system that runs the program, including device drivers ...

6

Returning Unmodifiable Collections only tees you up for runtime exceptions? Yes and no. Yes, it does do that. No, it doesn't only do that. It also prevents a class of problems from occurring; i.e. problems where some code has actually modified a collection that it wasn't supposed to. So what are the alternatives in Java? Instead of returning an ...

6

I don't know why people think of such exceptions as risky. Developer writes code using add. Developer thinks it might be a good idea to test the code he just wrote. Developer gets a big scary exception. Developer fixes code. Much more risky is returning a mutable reference to a data structure which is still used internally to a class, perhaps to avoid ...

5

The line can be very fuzzy, but the distinction lies in their intended purpose rather than their implementation. Language VMs typically operate at a higher level of abstraction. They may execute bytecode or execute the AST directly. JIT compilation may occur in either case, but I don't know of any processors that implement GC (except possibly lisp machines?)...

5

I think the main reason is that BlueJ runs your code in a VM with a debugger attached. BlueJ actually has two VMs running: the main one, and the one with your code inside (the user VM, aka the debug VM). The main VM has a debugger attached to the user VM, which allows it to do things like pause user code, inspect the state of objects and all sorts. I ...

5

What you described is achievable via Aspect-Oriented Programming (AOP). It won't be as straightforward as in your example, but you can get the requested behaviour. AOP has implementations in different languages; AspectJ being one of the most mature one. I will give you an example using AspectJ even though I don't want to go to in too much detail. To ...

5

The runtime of that particular pair of functions is infinite because neither returns without calling the other. The return value of a is always dependent on the return value of a call to b which always calls a... and that's what's known as infinite recursion.

5

For a compiler to do run time checks (to find warnings and errors that cannot be found at compile time, including loop vectorization), it starts to get dangerously close to the Halting Problem. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a ...

4

The obvious method is to run the function and measure how long it takes. This only tells you how long it takes on a particular input, though. And if you don't know beforehand that the function terminates, tough: there's no mechanical way to figure out whether the function terminates — that's the halting problem, and it's undecidable. Finding the run time of ...

4

I'm gonna freak out if its O(n^2) and I over thought this... Don't freak out -- too much. The outer loop will execute n times. The inner loop will execute an average of about (n/2) times. This results in a total of n^2/2 evaluations - or in more precise notation, runtime of O(n^2). Also this is pretty easy to verify by writing a short/simple program.

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