VPF::Подскажите подходящую структуру данных

Maksym

Дата 21.1.2008, 11:07 (ссылка)

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

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 1456
Регистрация: 19.8.2005
Где: Odessa, Black Sea

Репутация: 14
Всего: 62

В поддержку

Цитата(LSD @ 20.1.2008, 19:16

)

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

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

nornad

Дата 21.1.2008, 12:25 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31

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

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

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

Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл

LSD

Дата 21.1.2008, 12:40 (ссылка)

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

Загрузка ...

Leprechaun Software Developer

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

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

Цитата(Vitaly333 @ 21.1.2008, 01:52

)

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

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

Код


  private int[] data;
  
  public void ensureCapacity(int minCapacity)
  {
    int oldCapacity = data.length;
    if(minCapacity > oldCapacity)
    {
      int[] oldData = data;
      int newCapacity = (oldCapacity * 3) / 2 + 1;
      if(newCapacity < minCapacity)
        newCapacity = minCapacity;
      data = new int[newCapacity];
      System.arraycopy(oldData, 0, data, 0, oldCapacity);
    }
  }

Цитата(Sardar @ 21.1.2008, 04:18

)

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

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

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

Цитата(nornad @ 21.1.2008, 12:25

)

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

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

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

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.

nornad

Дата 21.1.2008, 14:19 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

Репутация: 16
Всего: 31

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

Код


public class Colossus
{
    private List<Object> data = new ArrayList<Object>();
    int count = 0;
    int limit = 0;
    int partSize = 1000;
    public void setValue(int idx, int value) {
        if(idx >= limit) {
            data.add(new int[partSize]);
        }
        // для упрощения считаем, что добавляем индексы последовательно
        int partIdx = idx / partSize;
        int[] part = (int[])(data.get(partIdx));
        part[idx%partSize] = value;
    }
}

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

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

Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл

Vitaly333

Дата 21.1.2008, 14:52 (ссылка)

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

Загрузка ...

Бывалый

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

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

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

Цитата

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

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

LSD

Дата 21.1.2008, 16:15 (ссылка)

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

Загрузка ...

Leprechaun Software Developer

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

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

Цитата(Vitaly333 @ 21.1.2008, 14:52

)

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

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

Цитата(Vitaly333 @ 21.1.2008, 14:52

)

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

TIntArrayList

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

w1nd

Дата 21.1.2008, 18:36 (ссылка)

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

Загрузка ...

Вертилятор

Профиль
Группа: Завсегдатай
Сообщений: 1077
Регистрация: 22.3.2006
Где: Москва

Репутация: 20
Всего: 54

Цитата(LSD @ 21.1.2008, 12:40

)

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

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

v2v

Дата 22.1.2008, 00:21 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1620
Регистрация: 20.9.2006
Где: Киев

Репутация: 8
Всего: 56

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

Цитата(niasilil @ 21.1.2008, 03:50

)

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

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

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

java блох

Vitaly333

Дата 22.1.2008, 01:03 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата

ваш алгоритм - это факторизация чисел (разложение на множители?).

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

Цитата

Можете привести начальные данные для параметров функции??

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

v2v

Дата 22.1.2008, 01:15 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1620
Регистрация: 20.9.2006
Где: Киев

Репутация: 8
Всего: 56

Цитата(Vitaly333 @ 22.1.2008, 01:03

)

Конечно могу.... вот ссылка

ого...

Цитата(Vitaly333 @ 22.1.2008, 01:03

)

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

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

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

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

java блох

Vitaly333

Дата 22.1.2008, 16:46 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата

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

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

Цитата

возможно можна как то оптимизировать сам алгоритм?

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

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

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