Why are run times on top solutions so high.


  • -1
    E

    As the title suggests, it seems the runtime for the quick select solutions are longer than the naive sort and select for these test cases. I even implemented my own quick sort and it runs faster than the quick select algorithms. Can anyone explain why this is the case? Does it have to do with the choice of test cases?


  • 1
    W

    You have to take runtimes on leetcode with a pinch of salt - they vary greatly even for the subsequent runs of the same code. You can achieve a good runtime by submitting multiple times until you are happy with the runtime.
    Also, it's possible that the tests change over time, making later solutions slower. Probably some of the fast solutions would not achieve the same runtimes if they were re-submitted now.


  • 0

    What is "so high"? What do "seems" and "longer" mean? How much longer? Why aren't you giving us details? And why aren't you showing us your code? You're not even telling us which language you're talking about. Why do you provide as little information as possible, making it as hard as possible to help you?


  • 0
    E

    @ManuelP Relax. The language I used was Java. I didn't need specific code to be evaluated. It was just a trend I noticed among different solutions I tried. The best solutions using the quick select algorithms tend to perform more slowly I have tried a few.

    Example from the top voted discussion post. This uses the quick select algorithm.

    public int findKthLargest(int[] nums, int k) {
    
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }
    
    private int partition(int[] a, int lo, int hi) {
    
        int i = lo;
        int j = hi + 1;
        while(true) {
            while(i < hi && less(a[++i], a[lo]));
            while(j > lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
    
    private void exch(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    
    private boolean less(int v, int w) {
        return v < w;
    }
    

    This is the solution I wrote for testing purposes. This sorts the array using quick sort then simply grabs the kth largest from the sorted array.

    public int findKthLargest(int[] nums, int k){
        quickSort(nums);
        return nums[nums.length - k];
    }
    
    public void quickSort(int[] arr){
        partition(arr, 0, arr.length - 1);
    }
    
    public void partition(int[] arr, int lo, int hi){
        int pivot = arr[(lo + (hi-lo)/2)];
        int i = lo, j = hi;
        while(i < j){
            while(arr[i] < pivot){
                i++;
            }
            while(arr[j] > pivot){
                j--;
            }
            if(i<=j){
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        if(lo < j){
            partition(arr, lo, j);
        }
        if(hi > i){
            partition(arr, i, hi);
        }
    }
    void swap(int[] arr, int ind1, int ind2){
        int temp = arr[ind1];
        arr[ind1] = arr[ind2];
        arr[ind2] = temp;
    }
    

    The second solution was much faster, 9ms vs 70 ms for the former.


  • 0

    @elmubark Better. That's something we can work with. And now it's pretty obvious. I'm actually surprised you didn't see the reason yourself. I mean, you chose arr[(lo + (hi-lo)/2)] as your pivot. So clearly you're aware that picking a good pivot is important. And you can see that that top-voted solution doesn't. It uses a[lo] as the pivot. Which is very very bad, as you probably know. If you in your solution use arr[lo] instead, you'll get a lot slower as well. I submitted that five times, average was 115 ms (single times were 183, 87, 110, 81 and 113 ms). Btw, the "9ms" and "70 ms" you reported, those are averages (?) of how many submissions each?

    The baseline is btw about 3 ms, as achieved by my following cheat solution every time in five submissions.

    public class Solution {
        static int answers[] = {1, 2, 1, 99, -1, 2, 0, -1, 3, 6, 3, 6, 6, 5, 3, 3, 3, 4, 3, 3, 4, 1, 6, 10, 11, 2, 8221, 0, 4999, 0, 4999};
        static int i = 0;
        public int findKthLargest(int[] nums, int k) {
            return answers[i++];
        }
    }
    

  • 0
    E

    @ManuelP I tried 5 submissions 64 - 81ms for the quick select. Submitted the quick sort solution 5 times as well and ended up 9-12ms. I've tried other solutions with different pivots. I can't seem to understand how sorting the entire list seems to perform better.

    Edit: I removed the less function and just used <. (Not sure why a separate function was used anyway... That improved the time but it's still around 60 ms. I will continue to investigate.
    Edit: I suppose it must be the pivot thanks for bearing with me. Not sure why so many of the most popular solutions pick such poor pivots.


  • 1

    @elmubark Well, for quicksort with a good pivot you can expect O(n log n). For quickselect with a bad pivot, you can only expect O(n2).

    Yes, it's definitely the pivot. Like I said, yours takes about 115 ms if you just change it to use that bad pivot. And I just changed the above quickselect solution by inserting exch(a, lo, (lo + hi) / 2); at the start of the partition function and it got accepted in 7 ms.

    I think people use bad pivots because they don't realize that it's bad or because they don't care (and the test cases are sadly small enough that they don't need to care).

    Using the middle value as pivot isn't safe, either, but it's more work to construct a case where it takes quadratic time. But when using the first or last value as pivot, most likely you get quadratic time simply when the input is an already sorted array. Which one should expect to be among the test cases.


  • 0
    E

    @ManuelP Thanks! Appreciate it!


  • 0

    @waitingtodie said in Why are run times on top solutions so high.:

    Also, it's possible that the tests change over time, making later solutions slower. Probably some of the fast solutions would not achieve the same runtimes if they were re-submitted now.

    I think the statistics are recomputed once a week, using only the submissions of the last week. Or something like that. And this is an old problem, so it's unlikely that the test cases have changed in the last week.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.