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

Question

У меня есть ситуация, когда я заполняю ArrayList с "TransactionEvent". TransactionEvent имеет свойство «идентификатор транзакции». В подавляющем большинстве случаев каждое новое событие имеет идентификатор транзакции, который больше идентификатора предыдущего события - однако это не гарантируется; то есть данные почти отсортированы .

У меня такой вопрос: как я могу выполнить быстрый поиск на основе идентификатора транзакции? Моя текущая идея заключается в том, чтобы позвонить Collections.binarySearch(...) и, если это не удалось, выполнить линейный поиск. Тем не менее, я заметил, что Javadoc утверждает, что результат binarySearch не определен, если данные неупорядочены, поэтому мне, возможно, придется свернуть мою собственную реализацию.

Дополнительно:

• Я пытался использовать карту индекса -> идентификатор транзакции, но этот подход некорректен, потому что всякий раз, когда элемент списка обновляется / удаляется, мне приходится перестраивать всю карту; т. е. любые выигрыши стираются этим.
• Это не случай преждевременной оптимизации: List является основой для TableModel, который в настоящее время работает очень медленно, когда содержит большое количество строк (100 000).

Любая помощь приветствуется.

Answer 1

Вы можете сохранить ArrayList отсортированным путем поиска точки вставки при добавлении каждого TransactionEvent. Collections.binarySearch возвращает

индекс ключа поиска, если он содержится в списке; в противном случае (- (точка вставки) - 1). Точка вставки определяется как точка, в которой ключ будет вставлен в список: индекс первого элемента больше, чем ключ, или list.size (), если все элементы в списке меньше указанного ключа. Обратите внимание, что это гарантирует, что возвращаемое значение будет> = 0, если и только если ключ найден.

После поиска точки вставки вы можете использовать метод ArrayList add (int index, Object) вместо простого добавления в конец списка, как обычно. Это немного замедлит каждую вставку, но позволит вам использовать бинарный поиск для быстрого поиска.

Answer 2

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

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

Answer 3

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

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

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

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

Имея два необходимых порядка сортировки, вы можете просто использовать два (отсортированных) BTrees

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

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

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

Answer 4

Я немного почищен от предыдущего поста. @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();
 }
}

Answer 5

Мой первый ответ был не совсем тем, что вы искали. Теперь, когда я лучше понимаю проблему, попробуйте. Я реализовал только ключевые части. Это займет немного больше памяти, но, поскольку я уверен, что 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, а когда вам нужно искать по id, смотрите this.byId.

Answer 6

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

Я почему-то подумал, что вы можете использовать map.headSet (ключ) и найти запись kth - это не сработает. Вы должны быть в состоянии получить из строки таблицы -> 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);
}

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

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

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 КБ, добавление поискового фильтра решит проблему с производительностью:

• Пользователь никогда не будет читать 100k строк
• Если для ваших пользователей имеет смысл выполнять поиск по eventID, тогда это прекрасно работает, когда пользователи выбирают eventID, вы делаете: sortedMap.headSet (searchFilterID) // берете первые 200, помещаете их в вашу таблицу
• Если для пользователей имеет смысл искать по времени, составьте карту и сделайте то же самое.

Answer 7

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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