4
\$\begingroup\$

What are the better solutions possible?

I have a character array with different strings. There is a max size for the strings. In case a string is smaller than max size remaining places are filled with '-'. Sorting has to be done on this.

Example:

maxStringSize = 5

totalStrings = 4

InputArray: w,a,t,e,r, c,a,t,-,-, f,i,v,e,-, b,a,l,l,-,-

outputArray: b,a,l,l,-,-, c,a,t,-,-, f,i,v,e,-, w,a,t,e,r

-

public class QuestionOne {


char[] mInput = {'w','a','t','e','r','c','a','t','-','-','f','i','v','e','-','b','a','l','l','-','-'};
int mBlockSize = 5;
int mTotalBlocks = 4;

public void init(char[] input, int blockSize, int totalBlocks)
{
    mInput = input;
    mBlockSize = blockSize;
    mTotalBlocks = totalBlocks;
}

public char[] sort()
{

    for(int i=0; i < mTotalBlocks; i++)
    {
        for(int j=i+1; j<mTotalBlocks; j++)
        {
            for(int count = 0; count < mBlockSize; count++ )
            {
                if(mInput[i*mBlockSize+count]>mInput[j*mBlockSize+count])
                {
                    swapBlocks(i,j);
                    break;
                }
                else if(mInput[i*mBlockSize+count]<mInput[j*mBlockSize+count])
                    break;
            }
        }
    }
    return mInput;
}

private void swapBlocks(int blockOne, int blockTwo)
{
    for(int i=0; i<mBlockSize; i++)
    {
        swap(blockOne*mBlockSize+i,blockTwo*mBlockSize+i);
    }
}

private void swap(int one, int two)
{
    char temp = mInput[one];
    mInput[one] = mInput[two];
    mInput[two] = temp;
}

}

What are the better solutions possible?

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you please provide more context to your code? \$\endgroup\$ – Bobby Dec 11 '13 at 15:44
  • \$\begingroup\$ So transforming it into strings, sorting these, joining them back together is not an option I guess? \$\endgroup\$ – Bobby Dec 11 '13 at 15:48
  • \$\begingroup\$ It's what I would do.... \$\endgroup\$ – rolfl Dec 11 '13 at 15:49
  • 1
    \$\begingroup\$ "Converting to string will hamper performance." So you did measure performance and came to the conclusion it's not fast enough? \$\endgroup\$ – Bobby Dec 11 '13 at 15:56
  • 1
    \$\begingroup\$ "10000+ such arrays with each array holding 50 - 100 strings." 10000*100*8*5 = 40 Mo of ram if you convert to strings, no biggie. \$\endgroup\$ – C4stor Dec 11 '13 at 16:42
4
\$\begingroup\$

How about the simple process of converting the chars to separate strings, sorting the Strings, then copying the results back to an array?

It would look something like:

String source = new String(input);
String[] values = new String[input.length / blocksize];
for (int i = 0; i < values.length; i++) {
    values[i] = source.substring(i * blocksize, (i + 1) * blocksize);
}
Arrays.sort(values);
char[] result = new char[values.length * blocksize];
for (int i = 0; i < values.length; i++) {
    System.arraycopy(values[i].toCharArray(), 0, result, i* blocksize, blocksize);
}
return result;
\$\endgroup\$
  • \$\begingroup\$ I thought about using String.copyValueOf(), otherwise would do it exactly like that. \$\endgroup\$ – Bobby Dec 11 '13 at 15:56
  • \$\begingroup\$ In pre-Java8 JVM's the string.substring is memory efficient ... which is an aspect to consider. \$\endgroup\$ – rolfl Dec 11 '13 at 15:57
  • \$\begingroup\$ To be honest, I did not try (was in the middle of writing it when seeing your answer). I just thought that it might be more elegant in this situation. \$\endgroup\$ – Bobby Dec 11 '13 at 15:59
  • \$\begingroup\$ This looks good other than that, I would prefer solution to be in place. \$\endgroup\$ – varsh Dec 11 '13 at 16:03
  • \$\begingroup\$ I'd use the String(char[] value, int offset, int count) constructor to create the strings and String.getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin) to reconstitute the result. \$\endgroup\$ – 200_success Dec 11 '13 at 19:42
3
\$\begingroup\$

So let's start with the easy things, Java normally uses a modified K&R style with the opening braces on the same line:

function void test() {
    if (someVar) {
        // code
    } else {
        // code
    }
}

I don't need to tell you that QuestionOne is a bad class name?


char[] mInput = ...

Normally variables don't get prefixes with an identifier that tells you their visibility (and if I'm not mistaken m is normally used for private variables). It hinders only readability, and if you need to use such prefixes for clarity, there's something wrong with your code.


public void init(char[] input, int blockSize, int totalBlocks)
{
    mInput = input;
    // ...
}

public char[] sort()
{
    // ...
    return mInput;
}

First, I don't see a reason why this could not be a static helper function instead of a class.

Second, imagine the following code:

char[] input = getInput();
QuestionOne sorter = new QuestionOne();
sorter.init(input, 5, 5);
char[] output = sorter.sort();

Quick, what values do input and output hold?

If your answer was

input holds the unsorted, output the sorted array.

then your answer was wrong. Arrays are passed by reference, so input and output are in fact the same array. That's a problem when it comes to design of the API of this class. Either don't return something.

/**
 * Sorts the given array.
 */
function void sort(char[] input) { // ...

Or return a copy of the array.

/**
 * Returns a sorted copy of the given array.
 */
function char[] sort(char[] input) {
    char[] clone = input.clone(); // Also has caveats!
    return clone;
}

Also you could derive the block size from the length of the array and the length of each block.

\$\endgroup\$
  • \$\begingroup\$ Java normally uses a modified K&R style with the opening braces on the same line I've been fighting against this style for years now. newline braces make so much more sense to me. Of course, any project I work on that adheres to these style standards, I follow \$\endgroup\$ – Cruncher Dec 11 '13 at 16:30
  • \$\begingroup\$ Thanks for your inputs Bobby, I was more sort of looking for a performance improvement here. Trust me I am not as novice as your answer makes this question look. :) And ya I hate K&R style. \$\endgroup\$ – varsh Dec 11 '13 at 16:57
  • \$\begingroup\$ @Cruncher: I like it, the indentation is (for me) enough to see that a new block of logic starts...though, of course that's preference, but Java code normally is that style, and so I mention it. \$\endgroup\$ – Bobby Dec 11 '13 at 18:21
  • 1
    \$\begingroup\$ @varsh: If you actively choose a different style then the language default, then please mention it next time. Also, this is CR, so I did a code review, highlighting the problems I see with the code. \$\endgroup\$ – Bobby Dec 11 '13 at 18:25
3
\$\begingroup\$

OK, taking in to consideration that memory footprint is a concern, then there is some scope for improvement. First, lets get through some of the basics....

Firstly, your code has a bug, It fails to sort data with duplicates:

'w','a','t','e','r','c','a','t','-','-','b','a','l','l','-','f','i','v','e','-','b','a','l','l','-','-'

Your code sorts the above as:

[b, a, l, l, -, c, a, t, -, -, f, i, v, e, -, w, a, t, e, r, b, a, l, l, -, -]

Secondly, your example data has an extra '-' at the end. Is this intentional?

Then, let's discuss the trade-offs between a few different concepts....

  • Using Strings allows us to use pre-built algorithms for sorting. Arrays.sort uses heavily optimized code (TimSort) to get the data sorted fast, but, we will have an expensive O(n) cost to convert the data first.
  • Additionally this will have a significant memory impact (significantly more than double the memory will be required).
  • an in-between solution may be possible. We can create a custom object, say CharRange which represents a range in the base array. We can make this CharRange class Comparable. Then, we can create a CharRange instance for each word in the class, and sort the results. With the sorted results we can 'swap' the actual data to match the sorted results. This is more memory efficient than String, and has the advantage of using the native Collections.sort() algorithms. The drawback is that it does use memory, and the 'post-swap' algorithm will be 'fiddly'.

Taking things to the other extreme, we can sort the data in-place, and not use any additional memory overhead.... but we will have to implement our own sort.

Our sort will be slower than the native sort, but, we will not have the overhead of creating Objects....

So, I have played with your code, and wrapped it in a quick-sort algorithm.... (your mileage may vary, buyer beware, use at your own risk, etc.)....

Some notes:

  • There is no apparent need for both mBlockSize and mTotalBlocks. The one can be calculated without the other (assuming that there is not more than mBlockSize bytes of 'padding' at the end of the data).
  • The qsort algorithm shuffles through the data in steps of mBlockSize.
  • I have used my own swap-in-place method, I don't like the two-levels of method-call you added to your code.
    char[] mInput = {'w','a','t','e','r','c','a','t','-','-','b','a','l','l','-','f','i','v','e','-','b','a','l','l','-','-'};
    int mBlockSize = 5;
    int mTotalBlocks = 4;

    public void init(char[] input, int blockSize, int totalBlocks)
    {
        mInput = input;
        mBlockSize = blockSize;
        mTotalBlocks = totalBlocks;
    }

    public char[] qsort() {
        // find the start of the right-most character block...
        // this could be: qsortRecurse(0, mBlockSize * (totalBlocks - 1));
        qsortRecurse(0, mBlockSize * (mInput.length / mBlockSize - 1));
        return mInput;
    }

    public void qsortRecurse(final int lbound, final int rbound) {

        final int pivot = lbound;
        int left = lbound + mBlockSize;
        int right = rbound;

        if (right <= left) {
            return;
        }

        while (left <= right) {
            while (left <= right && compareBytes(left, pivot) <= 0) {
                left += mBlockSize;
            }
            while (left <= right && compareBytes(pivot, right) < 0) {
                right -= mBlockSize;
            }
            if (left < right) {
                swapInPlace(left, right);
            }
        }

        swapInPlace(pivot, right);

        qsortRecurse(lbound, right - mBlockSize);
        qsortRecurse(left + mBlockSize, rbound);

    }

    private void swapInPlace(int a, int b) {
        char temp;
        for (int i = 0; i < mBlockSize; i++) {
            temp = mInput[a + i];
            mInput[a + i] = mInput[b + i];
            mInput[b + i] = temp;
        }

    }

    private int compareBytes(final int a, final int b) {
        int i = 0;
        while (i < mBlockSize && mInput[a + i] == mInput[b + i]) {
            i++;
        }
        return i == mBlockSize ? 0 : (mInput[a + i] - mInput[b + i]);
    }
\$\endgroup\$

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.