Список карт: эффективные реализации

Question

Список карт: эффективные реализации

У меня есть код, который создает и использует коллекцию, такую как:

List<Map<String, Object>> tableData;

Этот список карт заполняется n картами, каждая из которых представляет одну строку в базе данных. Каждая строка представлена в виде карты между именем поля и объектом, соответствующим полю (тип в данном случае не имеет значения). Некоторые поля могут отсутствовать. Количество полей m всегда намного меньше числа строк (n ≈ 10000 × m). Мне нужно повторно использовать одну и ту же коллекцию несколько раз, чтобы прочитать все строки, поэтому я не могу просто использовать какой-то ленивый итератор.

Существует ли эффективная структура данных для хранения этого? Гуава обеспечивает Table Коллекция, но это, кажется, не отвечает всем требованиям. Я думаю о создании интерфейса, такого как:

interface TableData{
  int size();
  Map<String, Object> get(int i);
  // ... (interators, etc.)
}

А затем создать реализацию, которая использует один Map<String,List<Object>> так что я только создаю экземпляры m списков вместо n карт и создаю карты на лету только тогда, когда это необходимо, но мне было интересно, существует ли там более универсальная структура данных.

Спасибо

5

java collections guava space-efficiency

Источник

user1327788 28 окт '13 в 16:37

4 ответа

Решение

Сначала убедитесь, что вам действительно нужно оптимизировать.

Предполагая, что в среднем не более 50% столбцов отсутствуют, List<Object[]> явный победитель:

class TableDataImpl implements TableData {
    private List<Object[]> data;
    private Map<String, Integer> columnNameToIndexMap;

    public Map<String, Object> get(int i) {
        return new ArrayMap(data.get(i));
    }

    private class ArrayMap implements Map<String, Object> {

        private Object[] row;

        ArrayMap(Object[] row) {
            this.row = row;
        }

        public Object get(String key) {
            Integer index = columnNameToIndexMap.get(key);
            if (index==null) return null;
            return row[index];
       }

       // all the other Map stuff... a lot of code!
    }
}

Я бы не назвал это простым, поэтому убедитесь, что вам действительно нужно оптимизировать.

В противном случае, если предположить, что в среднем не более 95% столбцов не хватает, следует сделать несколько более сложную конструкцию: для каждой строки используйте доморощенный BitSet (long[]) для хранения, какие столбцы существуют. Таким образом, вы будете тратить только один бит, а не целую запись (32 или 64 бита) в Object[],

Это еще сложнее, поэтому убедитесь, что вам действительно нужно оптимизировать.

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

4

Источник

user581205 28 окт '13 в 19:45

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

Если вы обеспокоены эффективностью создания и очистки объектов, я бы предложил использовать пул объектов. Вот основная идея того, как это может работать:

public class TableRowPool {

    private static final int INITIAL_CAPACITY = 10000;

    private Queue<Map<String, Object>> mapObjects;

    public TableRowPool() {
        mapObjects = new LinkedList<Map<String, Object>>();
        for(int i = 0; i < INITIAL_CAPACITY; i++) {
            mapObjects.add(new HashMap<String, Object>());
        }
    }

    public Map<String, Object> getTableRowObject() {
        if(mapObjects.size() == 0) {
            mapObjects.add(new HashMap<String, Object>());
        }
        return mapObjects.remove();
    }

    public void returnTableRowObject(Map<String, Object> obj) {
        mapObjects.add(obj);
    }

}

LinkedList хорошо работает как очередь, поэтому поиск объекта будет быстрым. Он также быстр при добавлении новых объектов, если вы хотите, чтобы он динамически рос. Однако вам может потребоваться изменить структуры данных в зависимости от того, должна ли она быть поточно-ориентированной.

Чтобы использовать пул объектов, вы должны сделать что-то вроде следующего:

//Load data
while((row = getResultSetRow()) != null) {
    Map<String, Object> rowObj = tableRowPool.getTableRowObject();
    //Fill in data
    myRows.add(rowObj);
}

//... Do all your business logic ...

//Cleanup
for(Map<String, Object> rowObj : myRows) {
    tableRowPool.returnTableRowObject(rowObj);
}
myRows = null;

0

Источник

user2216670 28 окт '13 в 17:04

Если у меня есть такие большие данные, что я боюсь, что получу OOM, вместо того, чтобы найти оптимальную структуру данных для хранения этих данных, я бы искал, как я могу использовать параллелизм SIMD или что-то вроде Map-Reduce. Как бы вы ни оптимизировали структуру данных, вы всегда можете исчерпать пространство памяти. Например, если вы найдете оптимальную структуру данных, которая работает в конкретной конфигурации машины, она все равно может не работать в машине с немного меньшей оперативной памятью.

Но если вы все еще хотите придерживаться своего текущего подхода, почему вы не можете нормализовать данные, чтобы можно было представить поля, пропущенные с помощью: 'Null' . Поэтому, когда вы читаете данные и создаете карту, почему бы просто не добавить "ноль" для отсутствующих полей? Таким образом, вы, по крайней мере, не должны иметь структуру данных ключ-значение, такую как hashmap, и вы можете просто List<List<Object>>

0

Источник

user2616681 28 окт '13 в 18:26

Другие вопросы по тегам java collections guava space-efficiency

user1327788 29 окт '13 в 13:59 2013-10-29 13:59 · Accepted Answer · 2013-10-29 13:59

Я провел несколько тестов (не окончательных, но весьма показательных), чтобы определить объем памяти List<Map<String, Object>> Реализации. Базовая линия - это Java ArrayList<> с элементами, являющимися экземплярами гуавы ImmutableMap,

Реализации, с которыми я сравнивал, следующие:

Реализация на основе Map<String,List<Object>> используя HashMap а также ArrayList s;
Реализация на основе List<Object[]> используя ArrayList;
Гуава-х HashBasedTable<Integer,String,Object>;
Гуава-х ArrayTable<Integer,String,Object>;

Мой тест состоял в создании n случайных строк, каждая из которых имеет m столбцов и "коэффициент заполнения" k, где коэффициент заполнения определяется как вероятность того, что каждая строка содержит значения для всех столбцов. Для простоты значения являются случайными строками длины l, сгенерированными с использованием Apache Commons RandomStringUtils,

Но давайте перейдем к результатам. Имея n = 200000, m = 50, l = 10 и k в (1,0, 7,5, 0,5), я получил следующие следы памяти в процентах от базовой линии:

    | k = 1.0  | k = 0.75 | k = 0.5  |
----------------------------------------
1.  |     71 % |     71 % |     71 % |
2.  |     71 % |     72 % |     73 % |
3.  |    111 % |    107 % |    109 % |
4.  |     71 % |     73 % |     76 % |

Я попытался уменьшить до 20000 примерно с теми же результатами.

Я нашел результаты выше довольно интересными. Во-первых, похоже, что нет места для улучшения за пределами 70% от базовой линии. Во-вторых, я был приятно удивлен, обнаружив, что эффективный ArrayTable Guava так же хорош, как две реализации, предложенные в этом вопросе. Я буду копать больше, но я склоняюсь к решению 1.

Спасибо