Эффективный поиск в Списке

Из того, что вы сказали, похоже, что здесь важнее всего быстрый поиск.

Так что, возможно, вам следует использовать HashMap вместо ArrayList . В HashMap сохраните события TransactionEvents, используя TransactionID в качестве ключа. Поиск в HashMap осуществляется за O (1).

Обратите внимание, что добавление в HashMap может стать довольно медленным, если вы превысите его начальную емкость - так как он должен выполнять повторное хеширование. Если вы можете, попробуйте инициализировать его с наилучшим предположением (ошибкой на высокой стороне) относительно количества элементов, которые он будет содержать.

При 100 КБ строк вам, возможно, придется увеличить размер кучи java, чтобы предотвратить OutOfMemoryErrors.

java -Xms<initial heap size> -Xmx<maximum heap size>

По умолчанию:

java -Xms32m -Xmx128m

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

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

Используя LinkedHashMap, который объединяет двусвязный список с хеш-доступом, вы должны иметь возможность взаимодействовать с TableModel, как и с ArrayList но также получить доступ к записям через поиск хэша по TransactionID.

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

Я бы использовал двоичный поиск, чтобы получить приблизительное местоположение идентификатора, а затем начал бы линейный поиск вовне. Обратной стороной является то, что если идентификатор, который вы ищете, отсутствует в списке, потребуется O (n + log n).

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

ArrayList предназначен для задач игрушечного размера. 100000 рядов мало занимают место для игрушек. Это означает, что вы должны быть более точными в отношении шаблонов доступа, которые вам необходимо поддерживать. Сортированного ArrayList может быть достаточно, и если скорость обработки растет быстрее, чем размер вашей проблемы, вы можете не беспокоиться, но BTree будет быстрее при 100 КБ элементов.

ArrayList имеет следующие проблемы с большими размерами проблем:

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

Двухуровневая коллекция с фиксированный размер страницы (например, BTree) может помочь, потому что рост будет означать добавление (в идеале) страницы примерно sqrt (размер), а случайная вставка максимально разделит одну страницу на две.

При двух необходимых порядках сортировки,

[править] Ответ на предыдущий вопрос - ключ к проблеме. Для ArrayList из 1000 элементов вставка стоит 7 микросекунд, для 1000000 элементов - 7 миллисекунд. BTree остается в диапазоне микросекунд (но может быть вдвое медленнее при размере страницы 1000 элементов).

Индексированные доступы, которые вы можете создать, сохраняя индекс количества элементов на каждой странице. Если вы установите флаг «грязный» на каждой странице, вы можете использовать фоновый поток для обновления начального индекса каждой страницы или можете добавить массовые операции с отложенным построением индекса.

Индекс может быть недействительным, но это просто sqrt ( размер) большой. Для 100K элементов это всего лишь увеличивает в среднем 150 индексов. Это занимает микросекунды, а не миллисекунды

Список можно отсортировать. Если вы вставляете сортировку по мере добавления элементов, а добавляемые элементы почти отсортированы, то вставки по-прежнему будут выполняться с постоянным временем. Тогда это позволит вам выполнять двоичный поиск в логарифмическом времени.

У меня была такая же проблема. Решение, которое я придумал, - это настраиваемая коллекция на основе ArrayList, которая также включает карту всех элементов. Сделать это несложно. Если вы хотите, чтобы я опубликовал исходный код - дайте мне знать

Мой первый ответ был не совсем тем, что вы искали. Теперь, когда я лучше понимаю проблему, попробуйте. Я реализовал только ключевые части. Это потребует немного больше памяти, но поскольку я почти уверен, что ArrayList хранит ссылки, а не сами объекты, разница в памяти не должна быть слишком большой по сравнению с реальным хранилищем объектов.

class TransactionEventStore
{
    private ArrayList<TransactionEvent> byOrder, byId;

    private void insertByOrder(TransactionEvent e) { this.byOrder.add(e); }

    private void insertById(TransactionEvent e)
    {
        for(int i = this.byId.length() - 1; i > 0; i--)
            if(e.getId() > this.byId.get(i).getId())
            {
                this.byId.add(i,e);
                break;
            }
    }

    public void insert(TransactionEvent e)
    {
        this.insertByOrder(e);
        this.insertById(e);
    }
}

Теперь, когда вам нужно искать по порядку вставки, посмотрите this.byOrder , а когда вам нужно искать по идентификатору, посмотрите this.byId .

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

1. Это будет быстрее, чем обычная вставка, потому что вставка в ArrayList ближе к концу происходит быстрее, чем вставка около начала (нужно перемещать меньше элементов), и большая часть ваших вставок будет в конце или ближе к концу ( потому что они почти упорядочены).
2. Обычно вы найдете точку вставки для вставки в ArrayList, используя алгоритм двоичного поиска. В этом случае быстрее выполнять линейный поиск, начиная с конца, так как большинство вставок будет происходить в конце или почти в конце.

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

Я почему-то подумал, что вы можете использовать map.headSet (key) и найти k-ю запись - это не сработает. У вас должна быть возможность получить из строки таблицы -> EventID (или близко к нему).

если вы используете подобную модель

Map<EventID, Event> model = new TreeSet<EventID, Event>();

Концептуально ваш getValueAt () выглядит следующим образом:

getValueAt(int row, column) {
 eventID = getSortPosition(row);
 Event e = model.headSet(eventID).next();
 return getColumn(e, column);
}

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

ArrayList<Event> orderedEvents = new ArrayList<Event>();
public void insert(Event event) {
 model.put(event.getID(), event);

 // update the 
 model.headSet().addAll(orderedEvents);
}

Ваш getValueAt () будет довольно простым.

getValueAt(int row, column) {w);
 Event e = orderedEvents.get(row);
 return getColumn(e, column);
}

• это делает вставки O (n) вместо O (n log n) (все еще не очень хорошо )

Думаю, вам следует пересмотреть дизайн пользовательского интерфейса Если у вас есть пользователи просматривают таблицу из 100 тыс. Строк, добавление фильтра поиска решит вашу проблему производительности:

• Ни один пользователь НИКОГДА не будет читать 100 тыс. Строк
• Если для ваших пользователей имеет смысл выполнять поиск по идентификатору события, тогда это отлично работает, когда пользователь выбирает eventID, вы делаете: sortedMap.headSet (searchFilterID) // берете первые 200, помещаете их в вашу таблицу
• Если пользователям имеет смысл искать по времени, то создайте карту и сделайте то же самое.

Я немного почистил из своего предыдущего поста. @Lizzard, ваше решение лучше всего подходит для того свойства, что новые записи обычно находятся в конце. Приведенное ниже решение должно работать лучше, если у вас есть случайные прибытия за счет большего объема памяти для карт. Это также позволяет вам отложить вставку вашего массива (потенциально O (n) в худшем случае) до тех пор, пока вам действительно не понадобится нарисовать ячейку для строки ниже самой ранней точки вставки.

// sorted events (using natural ordering on eventID)
SortedSet<Event> model = new TreeSet<Event>();
ArrayList<Event> sortedList = new ArrayList<Event>();
Event lowestAddition, additionPrevEntry; // low water mark for insertions

public void insert(Event x) {
 if (x < lowestAddition) {
  Set<Event> headSet = model.headSet(x); // find the insertion point
  additionPrevEntry = headSet.isEmpty()?model.last():headSet.first();  
  lowestAddition = x;
 }

 model.add(x);  // add
}

public void materialize() {
 SortedSet<Event> tailSet = model.tailSet(additionPrevEntry);

 Event firstValue = tailSet.first();    // this element does not change its order
 Integer order = firstValue.getOrder(); // keep order on Event
 for (Event x : tailSet) {
  x.setOrder(order);
  sortedList.set(order, x);
  order++;
 }

 lowestAddition = null; additionPrevEntry = null;
}

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

// now your model code uses the array
public Object getValueAt(int row, int col) {
 return getColumn(sortedList.elementAt(row), col);
}

// you can gain significant performance by deferring
// materialization until you acutally need it
public class DeferredJTable extends JTable {
 public void paintComponent(Graphics G, ...) {
  // if you knew what rows in the table were being drawn
  // ahead of time, you could further defer
  materialize();

  super.paintComponent();
 }
}