Форум русскоязычного сообщества Ubuntu


Следите за новостями русскоязычного сообщества Ubuntu в Twitter-ленте @ubuntu_ru_loco

Автор Тема: Не запускается сортировка на 10000 елементов. java.  (Прочитано 828 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Есть сортировки на java(пузырёк и быстрая) и массив на 10000 элементов, при компиляции выдает code too large.Диапазон от 0 до 1000.
методы везде берут инт, на лонг заменить не получается. Что делать?

Код: (java) [Выделить]
public static int[] bubblesort(int arr[]){
        boolean p = true;
        int k = 1;
        while (p){
            p = false;
            for(int i = 0; i < arr.length - 1; i++){
                if(arr[i] > arr[i+1]) {swap(arr, i, i+1); p = true;}
            }
            k++;
        }
        return arr;
    }
Код: (java) [Выделить]
public static int[] quicksort(int[] arr, int start, int end){
        int i = start;
        int j = end;
        int mid = arr[start + (end - start) / 2];
        while (i <= j) {
            while (arr[i] < mid) i++;
            while (arr[j] > mid) j--;
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        if (start<j) quicksort(arr, start, j);

        if(i<end) quicksort(arr, i, end);
        return arr;
    }
Прошу не отправляйте в google, ответьте срочно завтра доклад сдавать.
« Последнее редактирование: 03 Октября 2015, 23:03:27 от DenisVASI »

Оффлайн Serbis

  • Любитель
  • *
  • Сообщений: 91
    • Просмотр профиля
Ну я так сходу затрудняюсь ответить (четыре литра пива дают о себе знать, все таки суббота  ;D ), но зачем вы массивы в методах принимаете в itn[]. Попробуйте использовать списки, типа того public static ArrayList<int> bubblesort(ArrayList<int> arr) . Java не особо любит примитивные типы.

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Из вычитанного на американских сайтах понял, что метод не может быть больше 64k. Этот размер полностью покрывает собой массив. Разделить метод на несколько методов не получится. Я даже и не знаю, как такое обойти.

Оффлайн Serbis

  • Любитель
  • *
  • Сообщений: 91
    • Просмотр профиля
DenisVASI, пффф, допер в чем суть ошибки. Вы грузите массив int arr[] в статическом методе. В jvm существует ограничение на на размер статических объектов в 64кб. При размере в 10000 элементов это будет - 4 * 10000 = 40000байт, или 40кб. Ну либо у вас больше 10000 элементов и эту цифру вы написали просто так, либо я не знаю что сказать. Если первое верно, уберите статическое объявление метода и используйте инстанциирование класса. Например:

public class Blablabla {
    public static Blablabla instance;

    public Blablabla() {
        instance = this;
    }

    public static Blablabla getInstance() {
        return instance;
    }

    public int[] bubblesort(int arr[]){
        boolean p = true;
        int k = 1;
        while (p){
            p = false;
            for(int i = 0; i < arr.length - 1; i++){
                if(arr[i] > arr[i+1]) {swap(arr, i, i+1); p = true;}
            }
            k++;
        }
        return arr;
    }

    public int[] quicksort(int[] arr, int start, int end){
        int i = start;
        int j = end;
        int mid = arr[start + (end - start) / 2];
        while (i <= j) {
            while (arr[i] < mid) i++;
            while (arr[j] > mid) j--;
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        if (start<j) quicksort(arr, start, j);

        if(i<end) quicksort(arr, i, end);
        return arr;
    }

    private void swap(int[] arr, int a, int b) { //Хз че за метод, но че то делает...

    }
}

И обращаемся к методам так

int[] abc = new int[] {1, 2, 3};
Blablabla blablabla = new Blablabla();
int[] arrInt = blablabla.getInstance().bubblesort(abc);

В таком случае по идее подобной ошибки быть не должно

Пользователь решил продолжить мысль [time]04 Октябрь 2015, 00:52:50[/time]:
DenisVASI, а что делает метод swap? и можно ли увидеть полный вывод ошибки?


Пользователь решил продолжить мысль [time]04 Октябрь 2015, 01:02:34[/time]:
Ну вот я тоже почитал маны на ангилцких сайтах. Просто сам с такой проблемой дело не имел, не любою я вызовы статики подобным образом. Суть я так понял в том, что 64 кб это общий объем метода, те если arr[] 40кб, а swap например вернет 30кб, то это уже уже переполнение и приведет к крешу программы. Поэтому использовать статику при таких объемах категорически воспрещается. Используй инстансы как я показал, и проблем быть не должно.

Еще и в коде чуши понаписал, пьянт блин  ;D . Исправил, вроде теперь норм.
« Последнее редактирование: 04 Октября 2015, 00:06:25 от Serbis »

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
swap просто обмен производит.
Код: (java) [Выделить]
public static int[] swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
Код:
Код: (html5) [Выделить]
denis@denis-Aspire-V5-552G:~/proj/src$ javac Quick.java Bubble.java
Quick.java:6: error: code too large
    public static void main(String[] args){
                       ^
1 error

Пользователь решил продолжить мысль [time]04 Октябрь 2015, 01:09:48[/time]:
Сейчас попробую. А ведь говорила мама иди на ТО ;D ;D

Пользователь решил продолжить мысль 04 Октября 2015, 00:10:38:
А не расскажите заодно, с чем такое ограничение вообще связано?
« Последнее редактирование: 04 Октября 2015, 00:10:38 от DenisVASI »

Оффлайн Serbis

  • Любитель
  • *
  • Сообщений: 91
    • Просмотр профиля
DenisVASI, ну ошибка же на main указывает. Вы откуда этот массив берете, через командную аргументы main вводите в программу, т е через аргумент командной строки?


Пользователь решил продолжить мысль 04 Октября 2015, 00:17:35:
Хотя чет я туплю, весь арг строки принимает, тогда скорее всего то что я написал.
« Последнее редактирование: 04 Октября 2015, 00:17:35 от Serbis »

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Вот что имеем
Код: (html5) [Выделить]
uick.java:9: error: method quicksort in class sorting cannot be applied to given types;
        int[] arr0 = src.getInstance().quicksort(arr);
                                      ^
  required: int[],int,int
  found: int[]
  reason: actual and formal argument lists differ in length
1 error
denis@denis-Aspire-V5-552G:~/proj/src$ javac Quick.java Bubble.java
Quick.java:6: error: code too large
    public static void main(String[] args){
                       ^
1 error
полностью код:
Код: (java) [Выделить]

/**
 * Created by denis on 27.09.15.
 */
public class sorting {
    public static sorting instance;

    public sorting() {
        instance = this;
    }

    public static sorting getInstance() {
        return instance;
    }
    //helper methods
    public int[] swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
    public void swap(int i, int j) {
        int t = fieldArray[i];
        fieldArray[i] = fieldArray[j];
        fieldArray[j] = t;
    }
    public void printarray(int[] arr){
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    //helper methods
    public int[] bubblesort(int arr[]){
        boolean p = true;
        int k = 1;
        while (p){
            p = false;
            for(int i = 0; i < arr.length - 1; i++){
                if(arr[i] > arr[i+1]) {swap(arr, i, i+1); p = true;}
            }
            k++;
        }
        return arr;
    }
    public int[] insertionsort(int[] arr){
        int temp = 0;
        for(int i = 0; i < arr.length; i++)
        {
            temp = arr[i];
            int j = i - 1;
            while(j >= 0 && temp < arr[j]){
                swap(arr, j + 1, j);
                j--;
            }
        }
        return arr;
    }
    public int[] selectsort(int[] arr){
        int i, j, min, temp;
        int n = arr.length;
        for (i = 0; i < n - 1; i++) {
            min = i;
            for (j = i + 1; j < n; j++)
                if (arr[j] < arr[min])
                    min = j;
            if (min != i) {
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
        return arr;
    }
    public int[] shakesort(int[] arr){
        int left = 0;
        int rigth = arr.length - 1;
        int b = 0;
        while (left < rigth){
            for(int i = left; i < rigth; i++){
                if(arr[i] > arr[i + 1]){
                    b = i;
                    swap(arr, i, i + 1);
                }
                rigth = b;
            }
            if(left >= rigth) break;
            for(int i = rigth; i < left; i--){
                if(arr[i - 1] > arr[i]){
                    b = i;
                    swap(arr, i, i - 1);
                }
            }
            left = b;
        }
        return arr;
    }
    public int[] shellsort(int[] arr){
        int middle = arr.length / 2;
        while (middle > 0){
            for(int i = 0; i < arr.length - middle; i++){
                int j = i;
                while ((j >= 0) && (arr[j] > arr[j + middle])){
                    swap(arr, j, j + 1);
                    j--;
                }
            }
            middle /= 2;
        }
        return arr;
    }
    public int[] quicksort(int[] arr, int start, int end){
        int i = start;
        int j = end;
        int mid = arr[start + (end - start) / 2];
        while (i <= j) {
            while (arr[i] < mid) i++;
            while (arr[j] > mid) j--;
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        if (start<j) quicksort(arr, start, j);

        if(i<end) quicksort(arr, i, end);
        return arr;
    }
    //pancake
    public void flip(int[] arr, int m, int n){
        for(int i = m; i < --n; i++){
            swap(arr, i, n);
        }
    }
    public int[] pancakesort(int[] arr){
        int i, j, a, max, moves = 0;
        if(arr.length < 2) return arr;
        for(i = arr.length; i > 1; i--){
            max = 0;
            for (a = 0; a < i; a++){
                if(arr[a] > arr[max]) max = a;
            }
            if(max == (i - 1)) continue;
            if(max >= 0){
                flip(arr, max, i);
                moves++;
            }
        }
        return arr;
    }
    //pancake
    public static int[] bucketsort(int[] arr){
        int max = arr[0];
        for(int i = 0; i < arr.length; i++)
            if(arr[i] > max)
                max = arr[i];
        int [] bucket=new int[max+1];

        for (int i=0; i<bucket.length; i++) bucket[i]=0;
        for (int i=0; i<arr.length; i++) bucket[arr[i]]++;
        int pos=0;
        for (int i=0; i<bucket.length; i++)
            for (int j=0; j<bucket[i]; j++) arr[pos++]=i;
        return arr;
    }
    public static int[] countsort(int[] arr){
        int min = arr[0], max = arr[0];
        for(int i = 0; i < arr.length; i++){
            if(arr[i] > max) max = arr[i];
            if(arr[i] < min) min = arr[i];
        }
        int[] c = new int[max - min + 1];
        for(int x: arr) c[x - min]++;
        int n = 0;
        for(int i = 0; i < c.length; i++)
            for(int j = 0; j < c[i]; j++)
                arr[n++] = i + min;
        return arr;
    }
    //heap
    private static int[] fieldArray;
    private static int n;
    protected static int left;
    protected static int right;
    protected static int largest;
    public void buildheap(int []arr) {
        n = arr.length-1;
        for(int i=n/2; i>=0; i--){
            maxheap(arr,i);
        }
    }
    public void maxheap(int[] arr, int i) {
        left = 2*i;
        right = 2*i+1;

        if(left <= n && arr[left] > arr[i]){
            largest=left;
        } else {
            largest=i;
        }

        if(right <= n && arr[right] > arr[largest]) {
            largest=right;
        }
        if(largest!=i) {
            swap(i, largest);
            maxheap(arr, largest);
        }
    }

    public int[] heapsort(int[] arr) {
        fieldArray = arr;
        buildheap(fieldArray);
        for(int i=n; i>0; i--) {
            swap(0, i);
            n=n-1;
            maxheap(fieldArray, 0);
        }
        return arr;
    }
    //heap
}
Код: (java) [Выделить]
/**
 * Created by denis on 30.09.15.
 */
public class Bubble {
    public static void main(String[] args){
        int[] arr = {784, 134, 319, 225, 897, 676, 596, 84, 443, 707, 109, 71, 590, 310, 431, 319, 242, 52, 786, 736, 658, 498, 466, 776, 999, 930, 337, 374, 226, 645, 752, 413, 897, 498, 44, 239, 203, 475, 349, 872, 374, 840, 257, 600, 453, 650, 176, 588, 624, 438, 568, 506, 619, 979, 201, 831, 833, 618, 323, 648, 265, 594, 379, 625, 406, 557, 733, 756, 20, 883, 11, 873, 558, 249, 691, 918, 293, 357, 14, 332, 947, 912, 397, 743, 30, 160, 895, 423, 919, 73, 637, 775, 522, 512, 526, 754, 416, 524, 470, 661, 296, 33, 505, 676, 133, 698, 966, 53, 785, 786, 78, 787, 535, 216, 140, 640, 413, 213, 558, 171, 216, 418, 329, 833, 82, 682, 916, 491, 446, 978, 539, 180, 556, 817, 427, 582, 616, 704, 581, 496, 533, 823, 36, 717, 239, 184, 976, 931,  };
        sorting src = new sorting();
        int[] arr0 = src.getInstance().bubblesort(arr);
        src.printarray(arr0);
    }
}

Пользователь решил продолжить мысль 04 Октября 2015, 00:27:58:
для Bubble ошибка сохранена в том-же виде.
« Последнее редактирование: 04 Октября 2015, 00:27:58 от DenisVASI »

Оффлайн Serbis

  • Любитель
  • *
  • Сообщений: 91
    • Просмотр профиля
Ну я честно сказать затрудняюсь даль какой либо рациональный ответ, так как ваш код работает и очень хорошо

/usr/lib/jvm/java-8-oracle/bin/java -Didea.launcher.port=7537 -Didea.launcher.bin.path=/home/serbis/idea/bin -Dfile.encoding=UTF-8 -classpath /usr/lib/jvm/java-8-oracle/jre/lib/jfxswt.jar:/usr/lib/jvm/java-8-oracle/jre/lib/javaws.jar:/usr/lib/jvm/java-8-oracle/jre/lib/charsets.jar:/usr/lib/jvm/java-8-oracle/jre/lib/plugin.jar:/usr/lib/jvm/java-8-oracle/jre/lib/resources.jar:/usr/lib/jvm/java-8-oracle/jre/lib/jce.jar:/usr/lib/jvm/java-8-oracle/jre/lib/rt.jar:/usr/lib/jvm/java-8-oracle/jre/lib/jfr.jar:/usr/lib/jvm/java-8-oracle/jre/lib/jsse.jar:/usr/lib/jvm/java-8-oracle/jre/lib/deploy.jar:/usr/lib/jvm/java-8-oracle/jre/lib/management-agent.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/cldrdata.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/jfxrt.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/dnsns.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/nashorn.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/sunjce_provider.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/localedata.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/sunec.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/sunpkcs11.jar:/usr/lib/jvm/java-8-oracle/jre/lib/ext/zipfs.jar:/home/serbis/Projects/JAVA/untitled/out/production/untitled:/home/serbis/idea/lib/idea_rt.jar com.intellij.rt.execution.application.AppMain sample.Main
11 14 20 30 33 36 44 52 53 71 73 78 82 84 109 133 134 140 160 171 176 180 184 201 203 213 216 216 225 226 239 239 242 249 257 265 293 296 310 319 319 323 329 332 337 349 357 374 374 379 397 406 413 413 416 418 423 427 431 438 443 446 453 466 470 475 491 496 498 498 505 506 512 522 524 526 533 535 539 556 557 558 558 568 581 582 588 590 594 596 600 616 618 619 624 625 637 640 645 648 650 658 661 676 676 682 691 698 704 707 717 733 736 743 752 754 756 775 776 784 785 786 786 787 817 823 831 833 833 840 872 873 883 895 897 897 912 916 918 919 930 931 947 966 976 978 979 999

Process finished with exit code 0


А в чем пишете, в чем запускаете. Пробовали выводить определение массивы за пределы main в отдельный метод? И что за java у вас, не Open JDK случаем ли?
« Последнее редактирование: 04 Октября 2015, 00:43:51 от Serbis »

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Пробовал, java 8 стоит, все 10000 элементов у меня просто в сообщение не вошли.

Пользователь решил продолжить мысль [time]04 Октябрь 2015, 02:04:25[/time]:
intellij IDEA

Пользователь решил продолжить мысль 04 Октября 2015, 01:05:04:
Выводил массив как поле класса.

Оффлайн Serbis

  • Любитель
  • *
  • Сообщений: 91
    • Просмотр профиля
DenisVASI,
Ну кто-же в ините массива забивает столько данных. Я честно не знаю ограничение на размер инициализации, но накопировал полторы тысячи intов и получил эту же ошибку. Нафига вы это делаете, если нужно просто проверить работу функции ну так инициализирте массив randomом. Вот так вот например

        int[] arr = new int[10000];
        Random random = new Random();

        for (int i = 0; i < 10000; i++) {
            arr[i] = random.nextInt(1000);
        }


Если нужно проверить на конкретных данных, забивайте их в файл и грузите их оттуда. А в вашем случае ошибка полностью обоснована, так делать нельзя!

p. s. К инстансу класса следует обращаться напрямую, я неправильно вверху написал, вот так правильно.

int[] arr0 = sortings.getInstance().heapsort(arr);

Во вторых в java существует соглашение об именах. Имена классов начинаются только с заглавной буквы, иначе вы запутаетесь, не отличая методов от классов. Так что не sortings а Sortings.
« Последнее редактирование: 04 Октября 2015, 01:24:33 от Serbis »

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Спасибо большое помогли)

Оффлайн Serbis

  • Любитель
  • *
  • Сообщений: 91
    • Просмотр профиля
Ну а касаемо ограничения в 64кб на статики, попробую ткнуть пальцем и не промахнуться. Скорее всего это связано с жестким ограничением на размер голого байт-кода. Ну т. е. статические методы скорее всего загоняются в jvm в отдельную секцию, на уровне с константами и там задан жесткий размер области памяти в 64кб. Как только байт-код выходит за эти рамки, все, каюк программе.

Оффлайн DenisVASI

  • Автор темы
  • Участник
  • *
  • Сообщений: 116
    • Просмотр профиля
Кстати хочу заметить массивы до 8000 у меня запускались и без изменений.

 

Страница сгенерирована за 0.091 секунд. Запросов: 25.