Вообщем есть одна программа на 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)   

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