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

Question

Хотя у меня есть 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]);
    }
}

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

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

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

РЕДАКТИРОВАТЬ:

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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]);
    }
  }
}

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