[QZ#2] Deciphering Runtime about dsa-java HOT 10 CLOSED

Hello, I also had a question about the output in the console and asked during office hours.

Assuming you didn't modify testRuntime() in TernaryHeapQuizTest:
If you look at the line that starts with 1000 the 47 is how long it takes to add using a binary heap and the 62 is how long it takes to add using a ternary heap. The 94 is how long binary heap took to remove and 126 is how long ternary heap took to remove. All time units are in milliseconds.

from dsa-java.

Hello TFloyd. What really helped me was running the test in two different runs. Like in separate lines. If you read the documentation. I believe the first line is the time for add and the second line is the time for remove. If ran by itself. I am not sure if binary heap or trenary heap is either/or. In this case, the chart created is comparing the add methods of both binary/trenary heap, then the remove methods of binary/trenary heap.

from dsa-java.

Thanks for your guys' reponses.

Below is the code what Abner3 tries to refer to:

    @SafeVarargs
    final void testRuntime(AbstractPriorityQueue<Integer>... queues) {
        final int begin_size = 1000;
        final int end_size = 10000;
        final int inc = 1000;
        final Random rand = new Random();

        for (int size = begin_size; size <= end_size; size += inc) {
            // JVM warm-up
            benchmark(queues, size, 10, rand::nextInt);
            // benchmark all priority queues with the same keys
            Time[] times = benchmark(queues, size, 1000, rand::nextInt);

            StringJoiner joiner = new StringJoiner("\t");
            joiner.add(Integer.toString(size));  // size of heap
            joiner.add(Arrays.stream(times).map(t -> Long.toString(t.add)).collect(Collectors.joining("\t"))); // "add" of the input heaps
            joiner.add(Arrays.stream(times).map(t -> Long.toString(t.remove)).collect(Collectors.joining("\t"))); // "remove" of the input heaps
            System.out.println(joiner.toString());
        }
    }

I added some comments in the above code around the joiner.add and hope it helps.

So in the end, if you are comparing 2 heaps, it will become:
size, heap1 add, heap2 add, heap1 remove, heap2 remove

from dsa-java.

Oh okay thank you all. Should the binary heap add and remove be faster than the ternary heap add and remove?

from dsa-java.

As for plotting, you can do it either way by using an Excel or some online graph tools where you can input your data.

from dsa-java.

As for which is faster, please refer to the course notebook to find the answer and I believe you can find it out!

from dsa-java.

According to the notebook log base 3(1000) for ternary > log 10(1000) binary. This is correct?

from dsa-java.

@TFloyd1989 Sorry, we can not answer the question that is directly related to quiz questions

from dsa-java.

According to the notebook log base 3(1000) for ternary > log 10(1000) binary. This is correct?

However, for binary it should be log base 2(n)

This is depicted in the textbook

A binary heap is a PQ that takes O(logn) for both add() and remove()

And in computer science, if the base of log is ignored, it typically means log base 2.

from dsa-java.

Hello, I also had a question about the output in the console and asked during office hours.

Assuming you didn't modify testRuntime() in TernaryHeapQuizTest:
If you look at the line that starts with 1000 the 47 is how long it takes to add using a binary heap and the 62 is how long it takes to add using a ternary heap. The 94 is how long binary heap took to remove and 126 is how long ternary heap took to remove. All time units are in milliseconds.

@Abner3 thanks for answering this but figuring out the output format of this method is a part of assignment so I'm closing this issue.

from dsa-java.