Преобразование в массив, ориентированный на столбцы, в Java - PullRequest
Новая
       25

Преобразование в массив, ориентированный на столбцы, в Java

3 голосов
/ 29 апреля 2010

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

У меня есть метод, который постоянно получает массив Object []. Мне нужно разделить Объекты в этом массиве по нескольким массивам (List или что-то), чтобы у меня был независимый список для каждого столбца всех массивов, которые получает метод.

Пример: 

List<List<Object>> column-oriented = new ArrayList<ArrayList<Object>>();

public void newObject(Object[] obj) {
    for(int i = 0; i < obj.length; i++) {
        column-oriented.get(i).add(obj[i]);
    }
}

Примечание: для простоты я пропустил инициализацию объектов и прочего.

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

Как бы вы сделали это, зная, что это очень чувствительно к производительности?

EDIT:

Я проверил несколько вещей и обнаружил, что:

Вместо использования ArrayList (или любой другой коллекции) я обернул массив Object [] в другой объект для хранения отдельных столбцов. Если этот массив достигает своей емкости, я создаю другой массив с удвоенным размером и копирую содержимое из одного в другое, используя System.copyArray. Удивительно (по крайней мере для меня) это быстрее, чем использование ArrayList для хранения внутренних столбцов ...

Ответы [ 4 ]

2 голосов
/ 29 апреля 2010

Ответ зависит от данных и профиля использования. Сколько данных у вас есть в таких коллекциях? Каковы пропорции чтения / записи (добавление массива объектов)? Это влияет на то, какая структура внутреннего списка лучше, и на множество других возможных оптимизаций.

Самый быстрый способ скопировать данные - это вообще не копировать. Если вы знаете, что массив obj не изменяется в дальнейшем кодом вызывающей стороны (это важное условие), одним из возможных приемов является реализация собственного класса List для использования в качестве внутреннего списка. Внутренне вы будете хранить общий List<Object[]>. При каждом вызове мы просто добавляем новый массив в этот список. Пользовательский класс внутреннего списка будет знать, какой столбец он представляет (пусть он будет n), и когда его попросят дать элемент в позиции m, он транспонирует m и n и запросит внутреннюю структуру, чтобы получить internalArray.get(m)[n]. Эта реализация небезопасна из-за ограничений на вызывающую функцию, о которых легко забыть, но при некоторых условиях она может быть быстрее (однако при других условиях она может быть медленнее).

0 голосов
/ 29 апреля 2010

ArrayList может быть медленным из-за копирования массивов (он использует тот же подход, что и ваша самописная коллекция).

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

Пример: 

//Notice: You can use a LinkedList for rows, as no index based access is used.
List<Object[]> rows =... 

List<List<Object>> columns;

public void processColumns() {
  columns = new ArrayList<List<Object>>();
  for(Object[] aRow : rows){

    while (aRow.size() > columns.size()){
      //This ensures that the ArrayList is big enough, so no copying is necessary
      List<Object> newColumn = new ArrayList<Object>(rows.size())
      columns.add(newColumn); 
    }

    for (int i = 0; i < aRow.length; i++){
      columns.get(i).add(aRow[i]);
    }
  }
}

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

0 голосов
/ 29 апреля 2010

Я бы попробовал использовать LinkedList для внутреннего списка, потому что он должен иметь лучшую производительность для вставок. Может быть, может помочь обертывание объекта Object в коллекцию и использование addAll.

0 голосов
/ 29 апреля 2010

Используйте LinkedList для реализации списков столбцов. Он растет линейно с данными и равен O (1). (Если вы используете ArrayList, он должен время от времени изменять размер внутреннего массива).

После сбора значений вы можете преобразовать эти связанные списки в массивы. Если N - это количество строк, вы перейдете от удержания 3 * N ссылок для каждого списка (каждый LInkedList имеет prevRef / nextRef / itemRef) до только N ссылок.

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

Надеюсь, это поможет!

Редактировать тесты и теория показывают, что ArrayList лучше по амортизированной стоимости, то есть общая стоимость делится на количество обработанных элементов ... так что не следуйте моим «советам»:)

...