current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite
1

I've implemented a SortedList which takes in streams of floats and returns a median at any point.

public class SortedList {

        float[] list;
        int pos;
        int capacity;

        public SortedList(){
            this.pos = 0;
            this.capacity = 2;
            list = new float[capacity];
        }

        public void offer(int item){
            if(pos == 0){
                list[pos] = item;
                pos++;
                return;
            }
            if(pos == 1){
                if(item > list[0]){
                    list[1] = item;
                }else{
                    float temp = list[0];
                    list[0] = item;
                    list[1] = temp;

                }
                pos++;
                return;
            }
            if(pos - list.length <= 1) resize();
            int index = -1;
            for(int i=0; i< pos -1; i++){
                if(item < list[i]){
                    index = i;
                    break;

                }else if((item > list[i] && item < list[i+1])){
                    index = i+1;
                    break;
                }
            }
            if(index > -1){
                for(int i= pos; i > index; i--){
                    list[i] = list[i -1];
                }
                list[index] = item;

            }else{
                list[pos] = item;
            }
            pos++;
        }
        public float median(){
            float median = -1;
            if(pos%2 == 0){
                median = (list[pos/2 -1] + list[(pos/2)])/2;
            }else{
                median = list[(pos/2)];
            }
            return median;
        }
        private void resize(){

            capacity = capacity*2;
            float[] arr = new float[capacity];
            for(int i=0; i< pos; i++){
                arr[i] = list[i];
            }
            list = arr;
        }

        public void trace(){
            for(int i=0; i< pos; i++){
                System.out.print(list[i] + " ");
            }
            System.out.println();
        }
}

Invite comments on efficiency and accuracy. In the test case that I've used it works fine.

share|improve this question
up vote 2 down vote

Please protect your internals by preceding them with private:

private float[] list;
private int pos;
private int capacity;

pos is a very poor name for a field caching the size of the list: size is more clear.

You don't need capacity, just ask list.length.

Instead of trace(), I would override the String toString() method.

All in all, I had this in mind:

import java.util.Random;

public class SortedList {

    private float[] list;
    private int size;

    public SortedList() {
        this.list = new float[2];
    }

    public void offer(float item) {
        if (size == list.length) {
            expandArray();
        }

        int i = 0;

        for (; i < size; ++i) {
            if (list[i] > item) {
                break;
            }
        }

        for (int j = size - 1; j >= i; --j) {
            list[j + 1] = list[j];
        }

        list[i] = item;
        size++;
    }

    public float median() {
        if (size == 0) {
            return Float.NaN;
        }

        if (size % 2 == 0) {
            return (list[size / 2 - 1] + list[(size / 2)]) / 2;
        } else {
            return list[(size / 2)];
        }
    }

    private void expandArray() {
        float[] arr = new float[2 * list.length];
        System.arraycopy(list, 0, arr, 0, list.length);
        list = arr;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder().append("[");

        for (int i = 0; i < size; ++i) {
            sb.append(list[i]);

            if (i < size - 1) {
                sb.append(", ");
            }
        }

        return sb.append(']').toString();
    }

    public static void main(String[] args) {
        long seed = System.nanoTime();
        SortedList l = new SortedList();
        Random random = new Random(seed);

        System.out.println("Seed = " + seed);

        for (int i = 0; i < 10; ++i) {
            l.offer(random.nextInt(100));
            System.out.println(l);
        }
    }
}

Hope this helps.

share|improve this answer
up vote 2 down vote

There are 2 functions that will help you with this class: java.util.Arrays.binarySearch and java.lang.System.arraycopy.

The will search and copy the data much more effectively than what you are doing now:

public void offer(int item){

    int index = Arrays.binarySearch(list, item, 0, pos);
    if(index<0) index = -index+1

    if(pos - list.length <= 1) resize();

    System.arraycopy(list, index, list, index+1, pos - index);
    list[index] = item;

}

Also for resize you can use java.util.Arrays.copyOf which can be faster than your own loop.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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