Вообщем есть одна программа на Java(точнее один математический алгоритм), работающая с огромным кличеством информации! 
В ходе этого алгоритма в массив (ну назовем его A) записываються данные по порядку.. т.е A[1] = data1 , A[2] = data2 ..... A[n] = datan;
n может достигать >>1000000 . Тип данных - целочисленный. Так же в ходе алгоритма нужно получать данные по индексу A[i] = datai.
Но до выполнения программы n - неизвестно! Поэтому обычный массив в качестве A не подходит! 
Пробовал использовать классы - коллекции из стандартного набора Java: Vector, ArrayList, Hashtable, Stack ....но при их использовании алгоритм работает ну оооочень долго! Я сделал небольшой эксперимент , сначала запустил алгоритм , используя динамическую структуру ArrayList , определил n = 30308841 . Алгоритм выполнился за 22 секунды. Потом взял тот же пример , но уже зная заранее именно для этого примера n - взял в качестве A - обычный массив и время выполнения   его составило всего 800 миллисек. Разница как вы видите огромная! Есть ли в Java такая структура  чтобы она с одной стороны имела скорость доступа, записи и чтения элементов такую же или  хотя бы не намного меньшую чем у обычного массива и с другой стороны  могла динамически менять всой размер! 

А если делать размер массива очень-очень большим? И сделать счетчик - реальное количество данных, вот с ним и работать.
Или может поиграться с initialCapacity в ArrayList'e - при создании arrayList'a задавать сразу большой ему размер.

Пробовал уже на том же примере срузу выделил память так:  ArrayList <Integer> A = new ArrayList<Integer>(30308841); и запустил алгоритм ! Выполнился за 13 секунд. - уже в почти 2 раза быстрее но всё равно очень очень долго! А делать заранее размер массива очень очень большим так не пойдет: 
1) Может вообще памяти не хватить, потому что задачи , которые этот алгоритм обрабатывает очень велики!
2) N может быть и не большим и поэтому будет не целесообразно выделять много не нужной памяти!

 
 
Это параметра в структуре ArrayList нету... есть в структуре Vector, но Vector в тыс. раз медленее работает чем ArrayList!!!

Здесь всё дело в доступе к элементам.... ArrayList это же линейный список - чтоб получить доступ к элементу нужно перестраивать указатели а в обычном статическом массиве всё делаеться на прямую поэтому и быстрее работает!!!

Вооющем мне нужна структура , чтобы имела такой же доступ к элементам как у статического массива, но могла в процессе выполнения программы менять свой размер!

Ну а в чем собсвенно проблема то? Загоняем изначально в любой List<Integer>, а потом перекидываем его в массив нужной длинны.

К примеру vector.toArray(new int[vector.size()])

Получаем динамический размер + высокую скорость доступа

Это как? Вы ж выше его сами использовали - ArrayList <Integer> A = new ArrayList<Integer>(30308841); 



Нет. Посмотрите код ArrayList'a - это просто обертка над обычным массивом.



Да, я про это что-то не подумал. Vitaly333, подходит?

И чем это отличается от варанта "int[] = new int[n]" кроме существенно большего расхода памяти и большего времени выполнения?

Vitaly333, думаю, вы теряете время ещё и на boxing/unboxing'е. Если перед началом работы программы вам уже известна размерность, то проблем вообще никаких - просто создавайте обычный массив int[], если информация о размерности становится вам известна не сразу, используйте коллекции для примитивов trove4j.

Это сообщение отредактировал(а) w1nd - 20.1.2008, 17:36

Я же выше писал что размерность перед началом работы программы мне не известна, она становится известна  только в конце , когда вся программа уже выполнилась.... поэтому как вы написали с перекидываниями не получиться... 
Если хотите могу выложить сюда сам алгоритм чтоб стало всё понятно

Не писал я ни про какое перекидывание. По trove4j что не понятно?

Это сообщение отредактировал(а) w1nd - 20.1.2008, 19:19

я думал это подойдет, если:
1) Сначала считали неизвестное количество данных в ArrayList
2) Потом перекинули в обычный массив
3) Алгоритм работает с обычным массивом.

Но теперь понятно, что это не подходит.



Выкладывай.
Или использую библиотеку, которую w1nd предложил

Hashed Array Tree.
Штука тривиальная. Если доступ более-менее локальный (вокруг некой текущей позиции), то отдалённые части структуры можно сбрасывать/подгружать на диск, желательно в отдельном треде.

Неужели это так сложно по мере необходимости увеличивать размер массива?

Хотя в принципе вариант с trove4j или Commons Collections, вполне подходит.

Извини... я перепутал Это к SooulKeepery )))
А на счет trove4j.... какую из коллеций там представленных мне использовать .. там их много


Каким образом это можно сделать, если он статический?



Вот собственно сам алгоритм... сразу напишу n - это не то n про которое говориться выше...
Размерность массива JU  определяеться только по окончанию  работы алгоритма. С ArrayList работает очень долго. Сделать просто 
int[] JU = new int[size] не могу потому что не знаю размерность (size) заранее!!!





Это сообщение отредактировал(а) Vitaly333 - 21.1.2008, 02:05

Чтобы получить линейную скорость, надо увеличивать размер массива в два раза каждый раз когда нужно увеличивать. Тогда скорость такого алгоритма для n добавлений будет линейна относительно n. Вряд ли что то может побить такое кроме изначально созданного массива. 

Народ, не нужны тут вектора вообще! По мере надобности выделяются блоки памяти, когда не нужны - освобождаются. Читаем мой пост "Hashed Array Tree". Структура очевидна, правда люди о подобном забывают, когда сильно привыкают к троице (linked list, array, hashtable)   

Один фиг - динамический массив с той же постоянной времени доступа. 

В поддержку 

А создавать массив на n (n можно побирать на основе какого-нибудь несложного анализа данных, если алгоритм позволяет что-нибудь спрогнозировать) больше предыдущего, перекладывать в него данные (через System.arraycopy(..)) и продолжать в нем? Как думаете долго будет?

К чему споры о производительности? Не нравятся стандартный массив и ArrayList - берите LinkedList и радуйтесь. Чуть ли не холивор уже, чесслово. 

Добавлено через 58 секунд
В крайнем случае пишем реализацию списка сами - быстрее уже точно не будет, если вылизать.

Так же как это делается в том же ArrayList  




По скорости массив выгодней. А раз он спокойно помещается в память, то и лишние заморочки с "Hashed Array Tree" ни к чему.

Добавлено через 1 минуту и 9 секунд

Стандартные коллекции здесь не подойдут, т.к. boxing/unboxing займет большую часть времени работы алгоритма, не говоря уж о памяти.

Ну, тогда как вариант:

Суть идеи в том, чтобы минимизировать операции выделения памяти (тут всё будет зависеть от совпадения partSize и разницы capacity в примере LSD) и копирования данных (у меня его вообще нет, зато есть постоянный каст от Object к int[].

LSD, так всё таки какой структурой из  trove4j  мне воспользоваться?



Функцию ensureCapacity ты выдрал из исходников ArrayList? Ну и напишу я такой класс - это же будет клон класса ArrayList!

1. Слегка модифицировал.
2. Нет не такой же, он будет работать с примитивными типами, а не с обертками.
3. Зачем тебе писать полнофункциональный класс, просто используй этот код для увеличения размера массива по мере необходимости.



TIntArrayList

Значительное время съедят ещё и операции new на каждый элемент.

Vitaly333, ваш алгоритм  - это факторизация чисел (разложение на множители?).
можете привести начальные данные для параметров функции??


помоему оптимальным считается увеличение, когда масив заполнен более чем на 3/4.

Да это факторизация ,  только символическая а не численная! 



Конечно могу.... вот  ссылка на массивы IA и JA! Это тот пример о котором я писал в первом своем сообщении. N = 67500 

ого...

А что значит символьная факторизация (или таки символическая) ?

Добавлено через 18 секунд
возможно можна как то оптимизировать сам алгоритм?

Символическая - это значит операции проводяться не над самими  данными а над информацией которая позволяет получить доступ к этим  данным! Массивы IA и JA как раз таки  и есть та информация которая позволяет получить доступ к данным!  Данные (вещественные числа) храняться в отдельном массиве размером равным размеру JA и в символической факторизации не принемают участия!


Вряд ли ... он и так оптимизированный! Очень быстро работает если  использовать подходящие структуры данных.

Это сообщение отредактировал(а) Vitaly333 - 22.1.2008, 16:47