Java эффективный по времени разреженный массив 1D (двойной)

Question

Мне нужна эффективная структура Java для манипулирования очень разреженными векторами значений типа double: базовые операции чтения / записи. Я реализовал это в HashMap, но доступ слишком медленный. Должен ли я использовать другую структуру данных? Вы рекомендуете какую-нибудь бесплатную библиотеку?

Ищу какой-то мирный совет:)

Большое спасибо,

мари

Answer 1

HashMap это путь Это не должно быть медленным. Запустите свой код через профилировщик, чтобы увидеть, куда все время идет, а затем оптимизировать соответствующим образом. Если вам нужны советы по оптимизации кода, опубликуйте пример здесь, чтобы мы могли помочь с конкретной проблемой.

[РЕДАКТИРОВАТЬ] В зависимости от размера индексов, вы можете использовать технику, как в Integer.valueOf(int) кешировать объекты для бокса. Но это будет работать только тогда, когда вы создаете много карт и индексы находятся в несколько ограниченном диапазоне.

Или вы можете попробовать IntHashMap из общего достояния Это немного сложно использовать (это частный пакет), но вы можете скопировать код.

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

Answer 2

Насколько велик ваш набор данных? Гораздо больше, чем Integer.MAX_VALUE? проблема в том, что HashSet поддерживается массивом. Столкновения снизят производительность. Возможно, не слишком медленный механизм hashmap, а тот факт, что у вас есть несколько коллизий. Возможно, если вы сначала разбили свои данные (например, с помощью другой хэш-функции), а затем сохранили каждый раздел данных в своей собственной хэш-карте, вам повезло больше.

Answer 3

Вы можете скопировать и вставить разреженный вектор из моего проекта Hapax: ch.akuhn.matrix.SparseVector

PS: ко всем тем другим ответам и комментариям, которые не зарываются, почему использование карты слишком медленное. Это медленно, потому что карта упаковывает все индексы в целочисленные объекты!

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

Важными методами в классе разреженных векторов являются

// ...

public class SparseVector {

    /*default*/ int[] keys;
    /*default*/ int size, used;
    /*default*/ double[] values;

    public SparseVector(int size, int capacity) {
        assert size >= 0;
        assert capacity >= 0;
        this.size = size;
        this.keys = new int[capacity];
        this.values = new double[capacity];
    }

    public double get(int key) {
        if (key < 0 || key >= size) throw new IndexOutOfBoundsException(Integer.toString(key));
        int spot = Arrays.binarySearch(keys, 0, used, key);
        return spot < 0 ? 0 : values[spot];
    }

    public boolean isUsed(int key) {
        return 0 <= Arrays.binarySearch(keys, 0, used, key);
    }

    public double put(int key, double value) {
        if (key < 0 || key >= size) throw new IndexOutOfBoundsException(Integer.toString(key));
        int spot = Arrays.binarySearch(keys, 0, used, key);
        if (spot >= 0) return values[spot] = (float) value;
        else return update(-1 - spot, key, value);
    }

    public void resizeTo(int newSize) {
        if (newSize < this.size) throw new UnsupportedOperationException();
        this.size = newSize;
    }

    public int size() {
        return size;
    }

    private double update(int spot, int key, double value) {
        // grow if reaching end of capacity
        if (used == keys.length) {
            int capacity = (keys.length * 3) / 2 + 1;
            keys = Arrays.copyOf(keys, capacity);
            values = Arrays.copyOf(values, capacity);
        }
        // shift values if not appending
        if (spot < used) {
            System.arraycopy(keys, spot, keys, spot + 1, used - spot);
            System.arraycopy(values, spot, values, spot + 1, used - spot);
        }
        used++;
        keys[spot] = key;
        return values[spot] = (float) value;
    }

    public int used() {
        return used;
    }

    public void trim() {
        keys = Arrays.copyOf(keys, used);
        values = Arrays.copyOf(values, used);
    }

}

Answer 4

Для 1D разреженного массива, карта, как правило, путь. Вам нужно использовать библиотеку, только если она многомерна.

Если вы сравните время доступа между картой и массивом,

   map.get(99);
   array[99];

Карта будет намного медленнее. Любая библиотека будет иметь такую ​​же проблему.

Это редкий массив все о? Вы тратите время на космос.