VPF::Передача параметра по ссылке и по значению

Мурлыкатам_

Дата 10.11.2008, 18:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 265
Регистрация: 5.2.2007
Где: город-герой Минск

Репутация: нет
Всего: 2

Простите, что я продолжаю тему, я честно гуглил и честно смотрел статьи на форуме, но так и не понял как передать по ссылке к примеру массив целых чисел.

Задача: отсортировать массив случайных чисел от 0 до 5000, записанных в файл размером 1 мб, т.е. в файле 1 мб этих чисел.

Решение (сразу сделал под .net): решаю задачу через алгоритм быстрой сортировки (QuickSort: http://ru.wikipedia.org/wiki/Quicksort#Java.2FC.23), получается быстро, но не достаточно. Передаю массив через ref, и о чудо, все сортируется меньше чем за секунду...

Проблема: задача была поставлена для java, реализую все на java и сталкиваюсь с невозможностью передать массив по ссылке, в результате сортировка 100кб массива - 53 секунды. Очевидно проблема в постоянной передачи массива по значению.

Верно ли я понял, что для решения этой задачи мне нужно просто массив завернуть в класс, сделать экземпляр этого класса и вместо массива передавать экземпляр класса для увеличения производительности?

Если нет, то подскажите плз что-нить, потому что уже - smile

--------------------

Хочешь что-то сделать - сделай это сам или попроси помощи на винграде smile

powerOn

Дата 10.11.2008, 19:44 (ссылка)

(нет голосов)

Загрузка ...

software saboteur

Профиль
Группа: Участник
Сообщений: 4367
Регистрация: 7.10.2005

Репутация: 47
Всего: 159

вообще-то, массивы в java всегда передаются по ссылке... smile

--------------------

нет времени думать - нужно писать КОД!

Мурлыкатам_

Дата 10.11.2008, 19:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 265
Регистрация: 5.2.2007
Где: город-герой Минск

Репутация: нет
Всего: 2

Хммм... завтра выкину код. smile

Может в руках дело smile

--------------------

Хочешь что-то сделать - сделай это сам или попроси помощи на винграде smile

Дрон

Дата 10.11.2008, 21:10 (ссылка)

(нет голосов)

Загрузка ...

Java-ненавистник :)

Профиль
Группа: Участник Клуба
Сообщений: 3179
Регистрация: 29.12.2002
Где: Санкт-Петербург

Репутация: 6
Всего: 92

Цитата(powerOn @ 10.11.2008, 20:44

)

вообще-то, массивы в java всегда передаются по ссылке...

Ровно как и в .NET

Поэтому сказанное ниже очень странно:

Цитата(Мурлыкатам_ @ 10.11.2008, 19:20

)

Передаю массив через ref, и о чудо, все сортируется меньше чем за секунду...

Так что ждём код smile

--------------------

Да. Именно так.

SoulKeeper

Дата 11.11.2008, 10:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 14.1.2007
Где: Ukraine, Lviv.

Репутация: 11
Всего: 15

По алгоритму с Википедии вываливается StackOverflowError на 100кб массиве.

P.S. 100кб массив (1024 * 1024 / 4) элементов?

Это сообщение отредактировал(а) SoulKeeper - 11.11.2008, 10:53

LSD

Дата 11.11.2008, 13:14 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Цитата(SoulKeeper @ 11.11.2008, 10:50

)

По алгоритму с Википедии вываливается StackOverflowError на 100кб массиве.

Как тебе это удалось?

Код


import java.util.Random;

public class QSort {
  public static final int ARRAY_SIZE = 8 * 1024 * 1024;

  public static int partition(int[] m, int a, int b) {
    int i = a;
    for(int j = a; j <= b; j++) {
      if(m[j] <= m[b]) {
        int t = m[i];
        m[i] = m[j];
        m[j] = t;
        i++;
      }
    }
    return i - 1;
  }

  public static void quickSort(int[] m, int a, int b) {
    if(a >= b) return;
    int c = partition(m, a, b);
    quickSort(m, a, c - 1);
    quickSort(m, c + 1, b);
  }

  public static void main(String[] args) {
    int[] ints = new int[ARRAY_SIZE];
    Random rnd = new Random();
    for(int i = 0; i < ints.length; i++) {
      ints[i] = rnd.nextInt();
    }

    quickSort(ints, 0, ARRAY_SIZE - 1);

    for(int i = 1; i < ints.length; i++) {
      if(ints[i - 1] > ints[i]) {
        System.err.printf("Array not sorted a[%1$d] = %2$d, a[%3$d] = %4$d; %n", i - 1, ints[i - 1], i, ints[i]);
        break;
      }
    }
  }
}

--------------------

Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.

Мурлыкатам_

Дата 11.11.2008, 13:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 265
Регистрация: 5.2.2007
Где: город-герой Минск

Репутация: нет
Всего: 2

Цитата(Дрон @ 10.11.2008, 21:10

)

вообще-то, массивы в java всегда передаются по ссылке...

Ровно как и в .NET

Точно

Все таки хромала реализация smile

Я еще чуток поковыряюсь сам, а если не получиться, то напишу, стыдно немного кривоватый код показывать

Хотя словом, "немного" я наверное себе зальстил smile

Реализация уважаемого LSD, работает просто выше всяких похвал.

Спасибо!

Это сообщение отредактировал(а) Мурлыкатам_ - 11.11.2008, 14:12

--------------------

Хочешь что-то сделать - сделай это сам или попроси помощи на винграде smile

SoulKeeper

Дата 11.11.2008, 13:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 14.1.2007
Где: Ukraine, Lviv.

Репутация: 11
Всего: 15

Цитата(LSD @ 11.11.2008, 13:14)

Как тебе это удалось?

Хмм... таки не вываливается.
Может что-то умудрился поломать пока копипейстил smile

EDIT:

Код


public static final int ARRAY_SIZE = 8 * 1024 * 1024;

тут если 8 поменять на 32, то вывалиться ;)

Это сообщение отредактировал(а) SoulKeeper - 11.11.2008, 13:55

LSD

Дата 11.11.2008, 14:37 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Цитата(SoulKeeper @ 11.11.2008, 13:49

)

тут если 8 поменять на 32, то вывалиться ;)

Дык вываливается с OutOfMemoryError, а не StackOverflowError. Что вполне законно, т.к. массив занимает 128 мегабайт памяти, а по умолчанию JVM берет себе 32 мегабайта. Надо просто запустить с ключём -Xmx140m и все заработает.
OutOfMemoryError это простая нехватка памяти, решается ключами запуска. А вот StackOverflowError уже более серьезная проблема, как правило это бесконечная или слишком "глубокая" рекурсия.

--------------------

SoulKeeper

Дата 11.11.2008, 16:33 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 14.1.2007
Где: Ukraine, Lviv.

Репутация: 11
Всего: 15

Код


Exception in thread "main" java.lang.StackOverflowError
    at SortDemo.quicksort(SortDemo.java:41)
    at SortDemo.quicksort(SortDemo.java:42)
    at SortDemo.quicksort(SortDemo.java:42)
...

Код


import java.util.Random;

public class SortDemo {

  public static void main(String[] args) {

    int length = 1024 * 1024 * 32;
    int[] arr = new int[length];

    Random rnd = new Random();
    for (int i = 0; i < arr.length; i++) {
      arr[i] = rnd.nextInt(5000);
    }

    long time = System.currentTimeMillis();
    quicksort(arr, 0, length - 1);
    // Arrays.sort(arr);
    System.out.println(System.currentTimeMillis() - time);
    System.out.println("Sorted");
  }

  private static int partition(int[] m, int a, int b) {
    int i = a;
    for (int j = a; j <= b; j++) // просматриваем с a по b
    {
      if (m[j] <= m[b]) // если элемент m[j] не превосходит m[b],
      {
        int t = m[i]; // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее...
        m[i] = m[j]; // то есть переносим элементы меньшие m[b] в начало,
        m[j] = t; // а затем и сам m[b] «сверху»
        i++; // таким образом последний обмен: m[b] и m[i], после чего i++
      }
    }
    return i - 1; // в индексе i хранится <новая позиция элемента m[b]> + 1
  }

  public static void quicksort(int[] m, int a, int b) // a - начало подмножества, b - конец
  { // для первого вызова: a = 0, b = <элементов в массиве> - 1
    if (a >= b)
      return;
    int c = partition(m, a, b);
    quicksort(m, a, c - 1);
    quicksort(m, c + 1, b);
  }
}

Отличить нехватку памяти от переполнения стэка я еше могу.

Это сообщение отредактировал(а) SoulKeeper - 11.11.2008, 16:35

LSD

Дата 11.11.2008, 17:25 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Цитата

Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n²) обменов, но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
....
Представленные здесь реализации, кроме варианта на языке Паскаль, используют в качестве опорного элемента один из крайних элементов подмассива. Все эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра они приводят к самому худшему случаю.

Вот в чем проблема. Надо доработать метод partition().

--------------------

SoulKeeper

Дата 11.11.2008, 17:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 14.1.2007
Где: Ukraine, Lviv.

Репутация: 11
Всего: 15

Честно говоря я вообще не понимаю зачем использовать данный велосипед. Arrays.sort() работает и быстрее и вылеты оверфловы за ним не замечались ;)

LSD

Дата 11.11.2008, 17:39 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Ну я считаю, что знать базовые алгоритмы полезно и нужно. Тем более что Arrays.sort() сам использует quicksort, хотя там конечно реализация более грамотная с защитой от подобных проблем.

--------------------

SoulKeeper

Дата 11.11.2008, 17:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 14.1.2007
Где: Ukraine, Lviv.

Репутация: 11
Всего: 15

Что-то не верится что на этом форуме наберется десяток программистов которые смогут написать по памяти хоть пару из
этих алгоритмов

Одно дело знать что они существуют, другое - их писать.

LSD

Дата 11.11.2008, 17:59 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 210
Всего: 538

Пузырек и сортировку слиянием думаю напишут многие smile

Не надо их знать на память, достаточно знать что они есть и знать про их особенности (потребление дополнительной памяти, отношение к частично упорядоченным данным и т.п.). Чтобы в случае необходимости знать какой алгоритм стоит использовать (готовую реализацию найти не проблема).

А вообще это все оффтопик.

--------------------

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »