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

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 element) вместо добавления в конец списка, как обычно. Это замедлит каждую вставку небольшим коэффициентом, но это позволит вам использовать бинарный поиск для быстрого поиска.

Answer 2

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

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

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

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

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

Значения по умолчанию:

java -Xms32m -Xmx128m 

EDIT:

При заказе очень важно, чтобы вы могли использовать SortedMap.

Answer 3

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

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

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

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

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

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

Answer 8

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

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

Answer 9

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

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

Ключ в состоянии эффективно поддерживать карту из индекса сортировки -> ключ (обратное отображение). Это не-trival, поскольку вставка нового события на самом верху влияет на абсолютный порядок всех ниже. Кажется, здесь должен быть ответ 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 (п § п) (еще не большой)

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

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

Answer 10

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

Answer 11

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

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

// 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(); 
} 
}