10
\$\begingroup\$

I am doing this problem on SPOJ:

My kid's kindergarten class is putting up a Christmas play. (I hope he gets the lead role.) The kids are all excited, but the teacher has a lot of work. She has to produce costumes for a scene with \$K\$ soldiers. She wants to buy all the costumes in the same size, allowing for some small amount of length alteration to be done by the kids' parents later. So she has taken all the kids' height measurements. Can you help her select \$K\$ kids from her class of \$N\$ to play the soldier role, such that the height difference between the tallest and shortest in the group is minimized, and alternations will be easiest? Tell her what this minimum difference is.

INPUT

The first line contains the number of test cases \$T\$. \$T\$ test cases follow each containing 2 lines.

The first line of each test case contains 2 integers \$N\$ and \$K\$. The second line contains \$N\$ integers denoting the height of the \$N\$ kids.

OUTPUT

Output \$T\$ lines, each line containing the required answer for the corresponding test case.

CONSTRAINTS

  • \$T \le 30\$
  • \$1 \le K \le N \le 20000\$
  • \$1 \le \text{height} \le 1000000000\$

My approach

I am first storing all the heights in the array and then sorting the array using quicksort (I also tried std::sort), and after that finding the minimum difference using sliding window (I do not exactly know the name of algorithm, I heard it is known as sliding window).

After optimizing my code to the best that I can, my code takes 0.05s to execute all test cases, but when I see the best result, it is 0.00s or 0.02s, so less than 0.05s.

By the way, I had also tested with std::sort but it was only marginally faster (0.05 s instead of 0.06 s). How can I optimize it more?

#include <cstdio>
#include <algorithm>
#include<iostream>
int partition(int *arr, const int left, const int right) {
const int mid = left + (right - left) / 2;
const int pivot = arr[mid];
// move the mid point value to the front.
std::swap(arr[mid],arr[left]);
int i = left + 1;
int j = right;
while (i <= j) {
    while(i <= j && arr[i] <= pivot) {
        i++;
    }

    while(i <= j && arr[j] > pivot) {
        j--;
    }

    if (i < j) {
        std::swap(arr[i], arr[j]);
    }
}
std::swap(arr[i - 1],arr[left]);
return i - 1;
}

void quicksort(int *arr, const int left, const int right, const int sz)
{

if (left >= right) {
    return;
}


int part = partition(arr, left, right);

quicksort(arr, left, part - 1, sz);
quicksort(arr, part + 1, right, sz);
}

using namespace std;

int main(){
int T,N,K,h[20000];

scanf("%d",&T);

while(T--){
    scanf("%d %d",&N,&K);

    for(int i = 0;i < N;++i) scanf("%d",&h[i]);
    quicksort(h,0,N-1,N);

    int ans = h[K - 1] - h[0];

    for(int i = 1;i + K - 1 < N;++i)
        ans = min(ans,h[i + K - 1] - h[i]);

    printf("%d\n",ans);
}

return 0;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ General suggestion: Do not try to overoptimise SPOJ solutions. Some people achieve fastest times on SPOJ by crazy fast I/O routines - and in some cases, by making quick algorithms which work for the given set of testdata but not for all general inputs. I would strongly suggest that you try to solve more problems and learn algorithms in the process instead of wasting time going for the fastest. Also, why implement your own sort instead of std::sort? \$\endgroup\$ – Raziman T V Jan 20 '17 at 15:55
  • \$\begingroup\$ You could try some O(N) sorting method like count sort or radix sort for example. \$\endgroup\$ – Raziman T V Jan 20 '17 at 18:42
  • 3
    \$\begingroup\$ Try reading up and implementing these sorts. They will be very useful while solving some other spoj problems. \$\endgroup\$ – Raziman T V Jan 20 '17 at 18:46
  • 1
    \$\begingroup\$ I get 0.04 using std::sort and std::cin/std::cout. Conclusion: Micro optimizations are not the solution. You should be looking for algorithmic improvements. Node: std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr); makes the stream library as fast as the C IO code. \$\endgroup\$ – Martin York Feb 7 '17 at 6:12
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Feb 7 '17 at 13:34
3
+50
\$\begingroup\$

Time is mostly spent in I/O

I played with your program and found that most of the time was spent doing I/O. However, from your comments, it appears you already improved your I/O so that your best solution is now 0.02 seconds instead of 0.05 seconds.

I took your improved I/O code and took it one step further. What I did was read the entire input into a buffer using a single fread(), and then instead of using getchar_unlocked(), I just advanced a pointer through the buffer using *p++.

Why is *p++ faster than getchar_unlocked()? Here is what getchar_unlocked() does (not exactly but something close to this):

char getchar_unlocked()
{
    if (stdin.ptr >= stdin.buffer_len) {
        refill_stdin_buffer();
        stdin.ptr = 0;
    }
    return stdin.buffer[stdin.ptr++];
}

So for every character you read, it does a check to see if it needs to reload the buffer. If you read the entire input from stdin to a local buffer, you are essentially skipping and end of buffer check for each character you read.

Update: Later I found that my I/O changes didn't matter. Both yours and mine were able to achieve 0.00 time, as long as radix sort was used (see next section).

Radix sort

Radix sort is 0.02 seconds faster than std::sort for this test. I know because I tried it both ways. First I tried radix sort, which took 0.00 seconds overall. Then I replaced radix sort with std::sort and got 0.02 seconds.

In general, radix sort should be faster than quicksort for large arrays of integers. The radix sort I used operates on bytes at a time, so for 32-bit integers it uses exactly 4 rounds. On each round it does a counting pass followed by a rearranging pass. So in total, it does approximately \$8n\$ operations to sort an array of \$n\$ integers, plus a fixed overhead of 1024 operations to deal with the buckets.

From my own testing, I found that radix sort is 5x faster than std::sort for sorting arrays of 10 million integers. For 20000 integers, it is around 4x faster.

The final program, which achieved 0.00 seconds

Here is my program. You can see in the SPOJ status that I got 0.00 seconds with it. FYI, my first entry was a C program that got 0.00 seconds, but I changed it to the following C++ program:

#include <bits/stdc++.h>
#include <cstdio>

#define MAX                20000

// 30 testcases, 11 characters per number, 20000 numbers
char buf[MAX*11*30];
int array    [MAX];
int arrayTemp[MAX];

static inline int readInt(char **pPtr)
{
    char *p   = *pPtr;
    int   ret = 0;
    char  c   = *p++;

    while (c < '0')
        c = *p++;
    do {
        ret = (ret << 3) + (ret << 1) + c - 48;
        c   = *p++;
    } while (c >= '0');

    *pPtr = p;
    return ret;
}

void radixsort(int *a, int len)
{
    int *space       = arrayTemp;
    int *current     = a;
    int *scratch     = space;
    int *tmp         = NULL;
    int  radixByte   = 0;
    int  i           = 0;
    int  bucket[256];

    // Iterate once per byte.
    for (radixByte=0;radixByte<4;radixByte++) {
        int shift = (radixByte << 3);
        memset(bucket, 0, sizeof(bucket));

        // Count how many of each byte.
        for (i=0;i<len;i++)
            bucket[(current[i] >> shift) & 0xff]++;

        // Change bucket to be cumulative count.
        for (i=1;i<256;i++)
            bucket[i] += bucket[i-1];

        // Copy from current to scratch, using bucket counts.
        for (i=len-1;i>=0;i--)
            scratch[--bucket[(current[i] >> shift) & 0xff]] = current[i];

        // Switch arrays
        tmp     = current;
        current = scratch;
        scratch = tmp;
    }
}

int main(void)
{
    char *p = buf;
    fread(buf, 1, sizeof(buf), stdin);

    int t = readInt(&p);
    while (t-- > 0) {
        int n = readInt(&p);
        int k = readInt(&p);

        for (int i = 0; i < n; i++)
            array[i] = readInt(&p);

        if (k == 1) {
            puts("0");
            continue;
        }

        radixsort(array, n);

        int diff = INT_MAX;
        n -= k;
        k--;
        for (int i = 0; i <= n; i++) {
            int newDiff = array[i+k] - array[i];
            if (newDiff < diff)
                diff = newDiff;
        }
        printf("%d\n", diff);
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ How can radix sort be faster , i did std:sort with getchar_unlocked earlier and got 0.02 , how is that radix sort is faster , also i need to chat with you, can we? \$\endgroup\$ – Suraj Jain Feb 9 '17 at 10:22
  • \$\begingroup\$ @SurajJain I'm not sure why you think radix sort would be slower than std::sort? Radix sort is not a comparison sort, and should be faster than comparison sorts such as quicksort. If you just run my radix sort against std::sort for large integer arrays, you will see that it is much faster (as it should be). \$\endgroup\$ – JS1 Feb 9 '17 at 10:25
  • \$\begingroup\$ Can we chat, some hours later , till then i will prepare list of things i am confused about , and learn a little more about radix sort ? , also i edited your answer , to link to spoj rank where your name is there with time 0.00 \$\endgroup\$ – Suraj Jain Feb 9 '17 at 10:27
  • \$\begingroup\$ And See This softwareengineering.stackexchange.com/questions/77529/… , this is one of the reason i thought quick sort is best , i have never heard of radix sort , so i will learn it first, \$\endgroup\$ – Suraj Jain Feb 9 '17 at 10:29
  • \$\begingroup\$ @SurajJain Well I don't agree with that answer regarding radix sort. It should be faster than quicksort for integers. But it isn't a universal sort because it relies on data types that can be split into digits. Whereas quicksort can be used for any type that can be compared. \$\endgroup\$ – JS1 Feb 9 '17 at 10:33
2
\$\begingroup\$
  1. Fast I/O

    std::ios_base::sync_with_stdio(false);
    

    Or use getchar_unlocked() and putchar_unlocked() (this should do it)

    getchar_unlocked > scanf > cin

  2. Use std::sort over qsort

\$\endgroup\$
  • \$\begingroup\$ Any improvement with fast I/O? \$\endgroup\$ – Rohan Bojja Feb 7 '17 at 14:17
  • \$\begingroup\$ Yes , i got 0.02 , and another thing is said in best answer , thanks for your help and can we chat ? \$\endgroup\$ – Suraj Jain Feb 9 '17 at 10:32
  • \$\begingroup\$ Radix sort plus fast I/O should do it. Sure. \$\endgroup\$ – Rohan Bojja Feb 9 '17 at 10:36
  • \$\begingroup\$ How long have you been competitive programming ? \$\endgroup\$ – Suraj Jain Feb 9 '17 at 10:36
  • \$\begingroup\$ For about an year I guess. Ping me on hangouts or WhatsApp if you want. \$\endgroup\$ – Rohan Bojja Feb 9 '17 at 10:38
1
\$\begingroup\$
  1. Instead of rolling your sorting routine you could use std::sort.

  2. Instead of:

    scanf("%d %d",&N,&K);
    

    You could do:

    cin >> N >> K; 
    
  3. print (arr, sz) seems to be a debugging facility. Consider removing it from your solution.

  4. It might be good to isolate the actual algorithm in its own function, something like:

    int compute(std::vector<int>& vec, int k) 
    {
        std::sort(vec.begin(), vec.end());
        return search(vec, k);
    }
    
  5. If you remove your own print, you can also remove the parameter sz from your quicksort.

\$\endgroup\$
  • \$\begingroup\$ cin is slow than scanf \$\endgroup\$ – Suraj Jain Feb 5 '17 at 11:28
  • \$\begingroup\$ @SurajJain Did you measure? If it is, why C++ at all? \$\endgroup\$ – coderodde Feb 5 '17 at 11:30
  • \$\begingroup\$ i measured it. i tried it in c++ with sort before , i did not changed it then \$\endgroup\$ – Suraj Jain Feb 5 '17 at 11:34
  • \$\begingroup\$ cin is generally consider slow than scanf and cout slow then printf \$\endgroup\$ – Suraj Jain Feb 5 '17 at 11:35
  • 1
    \$\begingroup\$ @RohanBojja: Note: That will may also depend on which version of the standard library you are using. libc++ as used by clang is slower. But libstdc++ as used by g++ is faster (it is the more mature version of the standard library). \$\endgroup\$ – Martin York Feb 7 '17 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.