public class TDoubleArrayList {
private double[] data;
private int pos;
protected static final int DEFAULT_CAPACITY = 1;
public TDoubleArrayList() {
this(DEFAULT_CAPACITY);
}
public TDoubleArrayList(int capacity) {
data = new double[capacity];
pos = 0;
}
public void ensureCapacity(int capacity) {
if (capacity > data.length) {
int newCap = Math.max(data.length << 1, capacity);
double[] tmp = new double[newCap];
System.arraycopy(data, 0, tmp, 0, data.length);
data = tmp;
}
}
public void IncreaseCapacity(int capacity){
int newCap = data.length + capacity;
double[] tmp = new double[newCap];
System.arraycopy(data, 0, tmp, 0, data.length);
data = tmp;
}
public void DecreaseCapacity(int capacity){
int newCap = data.length - capacity;
double[] tmp = new double[newCap];
System.arraycopy(data, 0, tmp, 0, newCap);
data = tmp;
}
public void add(double val) {
ensureCapacity(pos + 1);
data[pos++] = val;
}
public void addQuick(double val) {
data[pos++] = val;
}
public double get(int index) {
return data[index];
}
public double[] getArray(){
return data;
}
public void setQuick(int index, double val) {
data[index] = val;
}
public void clear() {
clear(0);
}
public void clear(int capacity) {
data = new double[capacity];
pos = 0;
}
}
Эффективное изменение размеров массива в процессе вычислений
Есть один алгоритм в котором используется вещественный массив data. В процессе вычислений data строится динамически, т.е. я заранее, (до выполнения алгоритма) не могу узнать какого размера он будет. Сам алгоритм состоит из главного цикла на каждой итерации которого вычисляется целое число n. n – это то число, на которое должен быть увеличен размер массива data на каждой итерации. Для каждой итерации n – это разное число. Отмечу, ещё ту особенность алгоритма, которая заключается в том, что он работает очень большим объемом данных. Data может достигать 100 и более миллионов элементов.
Для организации динамического массива я использую специальную структуру данных TDoubleArrayList (из пакета Trove), немного модифицированную мною.
Вот её код:
Т.е на каждом шаге алгоритма, чтобы увеличить размер линейного массива я вызываю метод void IncreaseCapacity(n) – и размер увеличивается на n – элементов.
Давайте рассмотрим его детально:
Проблема состоит в том, что каждый раз(для каждой новой итерации) выполнять такую процедуру становится очень накладным, поскольку data достигает огромных размеров(особенно для последних итераций) и перебрасывать такие большие объемы данных очень дорого. Это очень сильно тормозит весь алгоритм и делает его применение для больших объемов данных практически невозможным.
Поэтому у меня вопрос к вам:
Как по другому(без создания нового и копирования данных из старого ) менять размер массива в Яве. Других динамических структур не предлагать , так как нужен только прямой доступ к элементам.
Для организации динамического массива я использую специальную структуру данных TDoubleArrayList (из пакета Trove), немного модифицированную мною.
Вот её код:
Код:
Т.е на каждом шаге алгоритма, чтобы увеличить размер линейного массива я вызываю метод void IncreaseCapacity(n) – и размер увеличивается на n – элементов.
Давайте рассмотрим его детально:
Код:
public void IncreaseCapacity(int capacity){
int newCap = data.length + capacity; // Вычисляется новый размер
double[] tmp = new double[newCap]; // Выделяется память под новый массив нового //размера
System.arraycopy(data, 0, tmp, 0, data.length); // Копируются данные из старого в новый
data = tmp; // Перебрасывается ссылка на новый массив, т.е. data теперь ссылается на //новый массив tmp нового размера
}
int newCap = data.length + capacity; // Вычисляется новый размер
double[] tmp = new double[newCap]; // Выделяется память под новый массив нового //размера
System.arraycopy(data, 0, tmp, 0, data.length); // Копируются данные из старого в новый
data = tmp; // Перебрасывается ссылка на новый массив, т.е. data теперь ссылается на //новый массив tmp нового размера
}
Проблема состоит в том, что каждый раз(для каждой новой итерации) выполнять такую процедуру становится очень накладным, поскольку data достигает огромных размеров(особенно для последних итераций) и перебрасывать такие большие объемы данных очень дорого. Это очень сильно тормозит весь алгоритм и делает его применение для больших объемов данных практически невозможным.
Поэтому у меня вопрос к вам:
Как по другому(без создания нового и копирования данных из старого ) менять размер массива в Яве. Других динамических структур не предлагать , так как нужен только прямой доступ к элементам.
Цитата: vitaly333
Проблема состоит в том, что каждый раз(для каждой новой итерации) выполнять такую процедуру становится очень накладным, поскольку data достигает огромных размеров(особенно для последних итераций) и перебрасывать такие большие объемы данных очень дорого. Это очень сильно тормозит весь алгоритм и делает его применение для больших объемов данных практически невозможным.
Поэтому у меня вопрос к вам:
Как по другому(без создания нового и копирования данных из старого ) менять размер массива в Яве. Других динамических структур не предлагать , так как нужен только прямой доступ к элементам.
Изменить размер существующего массива нельзя. Так же точно организовано управление размером Data Store в коллекциях типа ArrayList.
Навскидку предложу:
1. Хранить результаты каждой итерации в отдельной коллекции.
2. Ввести механизм оценки объема массива (эвристический), и заранее резервировать массив большого размера (если это возможно с точки зрения алгоритма и память позволяет).
3.Таки использовать коллекции, основанные не на массивах (что ты понимаешь под "прямым доступом", уверен ли ты, что тебе он необходим,
и что мешает копить в другой коллекции, и потом ее сконвертить в массив?
Цитата:
Изменить размер существующего массива нельзя. Так же точно организовано управление размером Data Store в коллекциях типа ArrayList.
Навскидку предложу:
1. Хранить результаты каждой итерации в отдельной коллекции.
2. Ввести механизм оценки объема массива (эвристический), и заранее резервировать массив большого размера (если это возможно с точки зрения алгоритма и память позволяет).
3.Таки использовать коллекции, основанные не на массивах (что ты понимаешь под "прямым доступом", уверен ли ты, что тебе он необходим,
и что мешает копить в другой коллекции, и потом ее сконвертить в массив?
На счет 1-ого варианта. Если у меня 10.000 итераций - это понадобится 10.000 разных колекций. Как вы это себе представляете?
2 вариант: Нет на вряд ли. Скорее всего просто не хватит памяти.
3 вариант: Под "прямым доступом" я понимаю чтение и запись в структуру данных без каких -либо дополнительных проверок(на "прямую") за лин. время.
Фактически из -той структуры которую я привел мне нужно только две основные ф-ии:
Код:
public void addQuick(double val) {
data[pos++] = val;
}
public double get(int index) {
return data[index];
}
data[pos++] = val;
}
public double get(int index) {
return data[index];
}
Вообщем мне нужна такая структура, в которой чтение и запись элементов проводится со скоростью чтения и записи линейного массива ну и ,конечно, чтобы могла быстро менять свой размер. Если вы знаете такие колекции(стандартные или сторонние) привидите пример.
Простите если ерунду говорю, но нельзя ли организовать массив указателей, и на каждой итерации добавлять в него указатель на только что созданный новый массив? В последствии преобразовать его в одномерный массив не представляет труда. А если иметь информацию о том, сколько элементов на какой итерации было создано(например сохранив в отдельном массиве, если позволит память), можно работать с ним как с двумерным массивом, что и будет "прямым доступом".
Цитата:
На счет 1-ого варианта. Если у меня 10.000 итераций - это понадобится 10.000 разных колекций. Как вы это себе представляете?
Именно так и представляю, так же, как и предложил Штирлиц, например.
Хранить двумерный массив значений (а, как известно, в Java 2-мерный массив это и есть массив одномерных массивов (не обязательно одной длины!) ). С точки зрения скорости доступа это будет быстрей всего.
Цитата:
2 вариант: Нет на вряд ли. Скорее всего просто не хватит памяти.
Т.е. чтобы накопить данные, потом выделить память под новые данные, скопировать данные (т.е. на пике использовать в ДВА С ЛИШНИМ раза больше памяти, чем надо), очистить старые данные - тут памяти хватает, а чтобы выделить заранее какую-то разумную по размеру часть - не хватает?
Если заранее предугадать с какой-то приличной точностью размер массива нельзя с точки зрения алгоритма, тогда трудно что-то точно посоветовать.
Цитата:
Вообщем мне нужна такая структура, в которой чтение и запись элементов проводится со скоростью чтения и записи линейного массива ну и ,конечно, чтобы могла быстро менять свой размер. Если вы знаете такие колекции(стандартные или сторонние) привидите пример.
А может, расскажете подробней про задачу? Как эти данные вы потом используете, после их вычисления? Вам их надо все в памяти держать постоянно? Может, сериализовывать часть, можно организовать ручное кэширование на диск -- это ведь другие алгоритмы уже.
Цитата:
Именно так и представляю, так же, как и предложил Штирлиц, например.
Хранить двумерный массив значений (а, как известно, в Java 2-мерный массив это и есть массив одномерных массивов (не обязательно одной длины!) ). С точки зрения скорости доступа это будет быстрей всего
Это конечно интересно. Но как это реализовать? Есть пример такой коллекции? Но как я понимаю чтобы получить значение какого -либо элемента так уже не пойдет data[index]. Нужно будет уже делать data[data1[index]] Как - то так наверное....
Цитата:
Т.е. чтобы накопить данные, потом выделить память под новые данные, скопировать данные (т.е. на пике использовать в ДВА С ЛИШНИМ раза больше памяти, чем надо), очистить старые данные - тут памяти хватает, а чтобы выделить заранее какую-то разумную по размеру часть - не хватает?
Я просто тестировал на малых задачах с такой организацией памяти. До средних и больших просто не добрался. Естественно для таких задач памяти не хватитило бы. Поэтому собственно и обратился сюда за помощью.
Цитата:
А может, расскажете подробней про задачу? Как эти данные вы потом используете, после их вычисления? Вам их надо все в памяти держать постоянно? Может, сериализовывать часть, можно организовать ручное кэширование на диск -- это ведь другие алгоритмы уже.
Все данные, после вычислений, нужно держать полностью в памяти поскольку они дальше сразу передаются другому алгоритму. Записывать на диск и читать с него слишком долго даже с использованием сериализации и кэширования.
Не могу с уверенностью сказать про Java, но в С++ к массиву указателей на массивы обращаются как к двумерному массиву. Например:
Обращаемся к элементу:
Где array[12][14] 14-ый элемент 12-ого созданного вами массива.
Не уверен, но предполагаю что и в Java это делается также.
Код:
double* array[N];
for(int i=0;i<N;i++)
array=new array[your_length];
for(int i=0;i<N;i++)
array=new array[your_length];
Обращаемся к элементу:
Код:
cout<<array[12][14];
Где array[12][14] 14-ый элемент 12-ого созданного вами массива.
Не уверен, но предполагаю что и в Java это делается также.
Цитата: vitaly333
Это конечно интересно. Но как это реализовать? Есть пример такой коллекции? Но как я понимаю чтобы получить значение какого -либо элемента так уже не пойдет data[index]. Нужно будет уже делать data[data1[index]] Как - то так наверное....
Посмотрите в любой книжке нормальной по Java, как работать с многомерными массивами.
Цитата: vitaly333
Все данные, после вычислений, нужно держать полностью в памяти поскольку они дальше сразу передаются другому алгоритму. Записывать на диск и читать с него слишком долго даже с использованием сериализации и кэширования.
Описанный тобой размер данных - 100 миллионов чисел. Т.е. в double это уже 800 метров будет, это без учетов накладных расходов на обертки для них, если в коллекции запихивать. А если будет задача покрупней, и там будет этих данных скажем, 2-3 Гб? Или 4-5? Что ты тогда будешь делать?
Ты на десктопе все это дело крутишь, или на сервере?
Даже если последнее, все равно - дикое расточительство ресурсов.
Советую в сторону кеширования на винчестере посмотреть попристальней. Потому что если ты оперируешь такими объемами данных -- все равно скорей всего к этому придешь.
И еще - мне трудно сходу представить алгоритм, который бы такими объемами данных оперировал бы единовременно, не допуская пакетной обработки. Может, попробовать оптимизировать алгоритм?
Цитата:
Посмотрите в любой книжке нормальной по Java, как работать с многомерными массивами.
Вот написал примерно то очем говорил Штирлиц:
Код:
import java.util.*;
public class FastDoubleList {
private ArrayList<double[]> Rows; // Строка, каждый элемент которой есть массив
private double[] data;
int row; // указатель на массив
int pos; // позиция в массиве
int n; // Количество массивов
public FastDoubleList(int n){
this.n = n;
Rows = new ArrayList<double[]>(n);
row = 0;
}
public void CreateData(int size){
data = new double[size];
Rows.add(data);
pos = 0;
}
public double[] GetData(int row){
return Rows.get(row);
}
public void AddData(int row,double[] a){
Rows.add(row,a);
}
public double get(int row,int index){
return GetData(row)[index];
}
public void set(int row,int index,double val){
GetData(row)[index] = val;
}
public void add(int row,double val){
Rows.get(row)[pos++] = val;
}
/**
* Изменение указателя на массив
* @param - новый узакатель
*/
public void ChangeRow(int row){
this.row = row;
}
/**
* Изменение позиции в массиве
* @param pos - новая позиция
*/
public void ChangePos(int pos){
this.pos = pos;
}
}
public class FastDoubleList {
private ArrayList<double[]> Rows; // Строка, каждый элемент которой есть массив
private double[] data;
int row; // указатель на массив
int pos; // позиция в массиве
int n; // Количество массивов
public FastDoubleList(int n){
this.n = n;
Rows = new ArrayList<double[]>(n);
row = 0;
}
public void CreateData(int size){
data = new double[size];
Rows.add(data);
pos = 0;
}
public double[] GetData(int row){
return Rows.get(row);
}
public void AddData(int row,double[] a){
Rows.add(row,a);
}
public double get(int row,int index){
return GetData(row)[index];
}
public void set(int row,int index,double val){
GetData(row)[index] = val;
}
public void add(int row,double val){
Rows.get(row)[pos++] = val;
}
/**
* Изменение указателя на массив
* @param - новый узакатель
*/
public void ChangeRow(int row){
this.row = row;
}
/**
* Изменение позиции в массиве
* @param pos - новая позиция
*/
public void ChangePos(int pos){
this.pos = pos;
}
}
Перед началом вычислений:
FastDoubleList(it); , где it - кол -во итераций алгоритма.
На каждой итерации я буду делать так:
После того как вычисленно n (то число на которое нужно увеличить) :
CreateData(n);
И уже можно добавлять только что вычисленные элементы методом add(i,val);
Но есть одно но:
Дело в том, коллекция ArrayList является обёрткой массива и в её методах get и add (которые я использую в своих методах) большую часть времени жрут операции boxing/unboxing("заворачивание" в тип "object" и "разворачивание" в тот тип который указан в < > ). Можно ли её как то переписать так чтобы она работала с типом, которым является массив массивов.
Цитата:
Описанный тобой размер данных - 100 миллионов чисел. Т.е. в double это уже 800 метров будет, это без учетов накладных расходов на обертки для них, если в коллекции запихивать. А если будет задача покрупней, и там будет этих данных скажем, 2-3 Гб? Или 4-5? Что ты тогда будешь делать?
До таких объемов вряд ли доберусь. Максимум 1 Гиг. Да и Windows x32(в которой и применяется программа с данным алгоритмом)
не позволит свыше 2 гигов выделить.
Цитата:
Советую в сторону кеширования на винчестере посмотреть попристальней. Потому что если ты оперируешь такими объемами данных -- все равно скорей всего к этому придешь.
И еще - мне трудно сходу представить алгоритм, который бы такими объемами данных оперировал бы единовременно, не допуская пакетной обработки. Может, попробовать оптимизировать алгоритм?
Скажу лишь одно - алгоритм последовательный, и на каждой итерации требуется данные, полученные, от всех предыдущих.
Раз алгоритм так критичен по времени, то лучше не использовать коллекции, а самостоятельно описать необходимые методы доступа к массиву. Не так уж это и сложно, и никаких лишних действий и "оберток" не будет. Соответственно и объем памяти меньше станет. По-моему при таких объемах данных стандартные контейнеры не выход...
По твоему коду - зачем в классе нужны поля double[] data - которое используется один раз для инициализации массива, и n - которое используется для ресайза массива, и потом уже не требуется?
Кстати - можно использовать теги [highlight = имя_языка] [/highlight]
для расцветки кода.
Протестил тут производительность коллекции с учетом boxing/unboxing.
[highlight=java]
static class BoxingTest {
private ArrayList<Double> testlist;
public BoxingTest(int size) {
testlist = new ArrayList<Double>(size);
for(int i = 0; i < size; i++){
testlist.add(0.0);
}
}
public void populateData(int size) {
Random r = new Random();
for (int i = 0; i < size; i++) {
testlist.set(i , r.nextDouble());
}
}
}
static class ArrayTest {
private double[] array;
public ArrayTest(int size) {
array = new double[size];
}
public void populateData(int size){
Random r = new Random();
for(int i = 0; i < size; i++)
array = r.nextDouble();
}
}
[/highlight]
Замерил NetBeans 6.0 Profiler производительность работы методов populateData() соотв. для массива и листа, проверял на объемах
1 000 000, 5 000 000, 10 000 000 элементов.
Профайлинг показал, что производительность работы массива в этом случае выше примерно в 4 раза, именно за счет отсутствия оборачивания.
Но в твоем случае, autoboxing'a не должно быть. Элементы коллекции - массивы, когда ты обращается к элементу - ты получаешь объект - нужный массив. А потом уже работаешь с этим массивом, типа double. Т.е., массив не будет приводиться к типу Double[] автоматически.
А вообще - такого рода приложения нуждаются в замере производительности.
Ты этот класс(и вообще приложение) профайлил на разных объемах данных? Какие получил результаты? Проверял время выполнение конкретных методов? Откуда твоя уверенность, что именно в приложении ест больше всего времени?
Кстати - можно использовать теги [highlight = имя_языка] [/highlight]
для расцветки кода.
Протестил тут производительность коллекции с учетом boxing/unboxing.
[highlight=java]
static class BoxingTest {
private ArrayList<Double> testlist;
public BoxingTest(int size) {
testlist = new ArrayList<Double>(size);
for(int i = 0; i < size; i++){
testlist.add(0.0);
}
}
public void populateData(int size) {
Random r = new Random();
for (int i = 0; i < size; i++) {
testlist.set(i , r.nextDouble());
}
}
}
static class ArrayTest {
private double[] array;
public ArrayTest(int size) {
array = new double[size];
}
public void populateData(int size){
Random r = new Random();
for(int i = 0; i < size; i++)
array = r.nextDouble();
}
}
[/highlight]
Замерил NetBeans 6.0 Profiler производительность работы методов populateData() соотв. для массива и листа, проверял на объемах
1 000 000, 5 000 000, 10 000 000 элементов.
Профайлинг показал, что производительность работы массива в этом случае выше примерно в 4 раза, именно за счет отсутствия оборачивания.
Но в твоем случае, autoboxing'a не должно быть. Элементы коллекции - массивы, когда ты обращается к элементу - ты получаешь объект - нужный массив. А потом уже работаешь с этим массивом, типа double. Т.е., массив не будет приводиться к типу Double[] автоматически.
А вообще - такого рода приложения нуждаются в замере производительности.
Ты этот класс(и вообще приложение) профайлил на разных объемах данных? Какие получил результаты? Проверял время выполнение конкретных методов? Откуда твоя уверенность, что именно в приложении ест больше всего времени?