Есть ли список, поддерживаемый картой?

Question

У меня есть 100 тыс. Элементов в списке, который отображается в Swing TreeList. См. AutoFilterTreeTableDemo в jide-demo https://www.jidesoft.com/products/download.htm

При фильтрации требуется много времени для расширения узлов.

При профилировании Vector.indexOf() принимал ~ 20 секунд. Я переключил его на ArrayList, и потребовалось ~ 5 секунд.

Затем я кэшировал список как Map<Row, Integer>, где Integer является индексом в списке. Это уменьшило фильтрацию до ~ 0,2 с.

Однако, если я добавляю строку где-то посередине, я должен перестроить карту, поскольку индексы списка будут изменены.

Есть ли структура данных, которая использует карту для возврата индекса списка? Или мне нужно управлять этим самостоятельно?

В качестве альтернативы, есть ли обычный список, который имеет очень быстрое значение indexOf? Я не против жертвовать временем вставки/удаления немного за счет этого.

Третий вариант: если есть более оптимальная фильтрующая сетка Swing, которую я мог бы использовать.

EDIT: Фрагмент кода:

private Map<Row, Integer> rowLookup = new ConcurrentHashMap<Row, Integer>(); 

    @Override 
    public int getRowIndex(Row row) { 
     if(rowLookup.isEmpty()) { 
      List<Row> existingRows = getRows(); 
      for(int i = 0; i < existingRows.size(); i++) { 
       Row mappingRow = existingRows.get(i); 
       rowLookup.put(mappingRow, i); 
      } 
     } 
     if(row == null) { 
      return -1; 
     } else { 
      Integer lineNumber = rowLookup.get(row); 
      if(lineNumber == null) { 
       lineNumber = -1; 
      } 
      return lineNumber; 
     } 
    } 

Answer 1

Я думаю, что вы, вероятно, близко к оптимальному решению, как это. У вас есть две противоречивые потребности:

1. Вы хотите, чтобы иметь возможность случайным образом вставить элементы
2. Вы хотите, чтобы иметь возможность доступа к этим элементам на основе фиксированного индекса

Как правило, для (1) вам будет использовать что-то вроде либо карты или Linked List

Для (2) вы бы использовать массив

причину (1) конфликты с (2) является то, что когда вы делаете (1) вам должны обновить каждые последующий элемент, чтобы обновить его индекс. Я не думаю, что вы найдете структуру данных общего назначения, которая делает это, потому что это невозможно сделать эффективно.

Я думаю, что если бы я был вами, помимо реструктуризации проблемы, которую, я думаю, сейчас невозможно, я бы сделал то, что вы делаете.

Однако, вместо того чтобы рассматривать карту как интегральную, вы должны использовать ее в качестве кеша.

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

public int getRowIndex(Row row) { 

    Integer index = rowLookup.get(mappingRow); 

    List<Row> existingRows = getRows(); 

    if (index != null) { 

     int i = index.intValue(); 

     if (i < existingRows.size() && row == existingRows.get(i)) { 
      return i; 
     } 

     rowLookup.remove(i); 
    } 

    /* Otherwise we'll have to look it up the slow way */ 
    int i = existingRows.indexOf(row); 
    rowLookup.put(row, i); 
    return i; 
} 

К сожалению не пробовал компиляции этого предназначается только для иллюстрации

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

Answer 2

Не совсем то, что вы ищете, но это можно было бы рассматривать в качестве альтернативного решения вашей проблемы: org.apache.commons.collections.list.TreeList Метод IndexOf не превосходит по реализации ArrayList, но для случая использования, я думаю, что это будет приемлемо.

Эта реализация списка использует внутреннюю структуру дерева, чтобы гарантировать, что все вставки и удаления являются O (log n).

Нижеследующая таблица была получена из их документации в качестве показателя их эффективности по сравнению с другими реализациями списка. Даунсайд потребляет немного больше памяти:

*    get add insert iterate remove 
* TreeList  3 5  1  2  1 
* ArrayList  1 1  40  1  40 
* LinkedList 5800 1  350  2  325