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

Question

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

Глядя на некоторые советы мирного :)

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

Мари

Answer 1

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

[EDIT] В зависимости от размера индексов вы можете использовать технику, как в Integer.valueOf(int), для кэширования объектов для бокса. Но это будет работать только при создании большого количества карт, а индексы находятся в несколько ограниченном диапазоне.

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

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

Answer 2

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

PS: на все другие ответы и комментарии, которые Dont почему использование обращали внимание на карту слишком медленно. Он медленный, потому что карта помещает все индексы в объекты Integer!

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

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

// ... 

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 3

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

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

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

карта будет гораздо медленнее. У любой библиотеки будет такая же проблема.

Разве это разреженный массив? Вы торгуете временем для космоса.

Answer 4

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