Как к эффективно (работе) удаляют много пунктов из Списка на Яве?

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

Но, если вы также хотите попробовать редактировать список на месте, то эффективным способом сделать это является использование Iterables.removeIf() из Гуавы. Если его аргументом является список, то он соединяет сохраненные элементы спереди, а затем просто отрубает конец - намного быстрее, чем удалять() внутренние элементы один за другим.

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

public static List<T> removeMany(List<T> items) {
    List<T> tempList = new ArrayList<T>(items.size()/2); //if about half the elements are going to be removed
    Iterator<T> iter = items.iterator();
    while (item : items) {
        // <cond> goes here
        if (/*<cond>: */i % 2 != 0) {
            tempList.add(item);
        }
    }
    return tempList;
}

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

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

Но ...

Постоянный фактор для ArrayList меньше, чем в LinkedList ( ). Поскольку вы можете сделать разумное предположение о том, сколько элементов будет удалено (вы сказали «около половины» в вашем вопросе), добавляя элемент к концу ArrayList - это o (1), если вы Не нужно переопределять это. Итак, если вы могут сделать разумное предположение, я ожидал, что Arraylist будет незначительно быстрее, чем в большинстве случаев . (Это относится к коду, которое я опубликовал. В вашу наивную реализацию, я думаю LinkedList будет быстрее).

Может быть, список не Оптимальная структура данных для вас? Можете ли вы изменить это? Возможно, вы можете использовать дерево, в котором элементы сортируются в способ, которым удаляет один узел, удаляет все элементы, соответствующие условию? Или что, по крайней мере, ускорив свои операции?

в вашем упрощенном примере, используя два списка (один с элементами, где i% 2! = 0 верно и один с элементами, где I% 2! = 0 неверно) Что ж. Но это, конечно, очень зависит от домена.

Попробуйте реализовать рекурсию в свой алгоритм.

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

Я бы предположил, что построение нового списка, а не изменение существующего списка, будет более эффективным - особенно, когда количество предметов так велико, как вы указываете. Предполагается, что ваш список является ArrayList , а не LinkedList . Для некруглого LinkedList вставкой является O (n), но удаление в существующем положении итератора - O (1); в этом случае ваш наивный алгоритм должен быть достаточно эффективным.

Если список не является LinkedList , затраты на изменение списка при каждом вызове remove () , вероятно, являются одной из самых дорогих частей реализации. Для списков массивов я бы рассмотрел использование:

public static <T> List<T> removeMany(List<T> items) {
    List<T> newList = new ArrayList<T>(items.size());
    Iterator<T> iter = items.iterator();
    while (iter.hasNext()) {
        T item = iter.next();
        // <cond> goes here
        if (/*<cond>: */i++ % 2 != 0) {
            newList.add(item);
        }
    }
    return newList;
}

http://book.cakephp.org/view/121/Global-Functions это функции быстрого вызова в cakePHP

Многие из них устарели в 1,3, поэтому остерегайтесь использовать их самостоятельно

Можно попробовать использовать LinkedList вместо ArrayList , как и ArrayList , все остальные элементы необходимо скопировать, если элементы удалены из списка.

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

Алгоритм предполагает, что по меньшей мере одно из следующих действий верно:

• Все элементы исходного списка не нужно тестировать. Это может произойти, если мы действительно ищем первые n элементов, которые соответствуют нашему условию, а не все элементы, соответствующие нашему условию.
• Это дороже, чтобы скопировать список в новую память. Это может произойти, если оригинальный список использует более 50% от выделенной памяти, поэтому работающее на месте может быть лучше или если операции памяти оказываются медленнее (это было бы неожиданным результатом).
• Наказание скорости удаления элементов из списка слишком велико, чтобы принять все сразу, но распространение того, что наказание по нескольким операциям приемлемо, даже если общий наказание больше, чем принимать все сразу. Это похоже на получение ипотеки в размере 200 тысяч долларов: оплата 1000 долларов в месяц в течение 30 лет доступно ежемесячно и имеет преимущества владения домом и капиталом, даже если общий платеж - 360 тыс. За жизнь кредита.

Отказ от ответственности: есть синтаксические ошибки пролёта - я не пытался что-либо компилировать.

Во-первых, подкласс ArrayList

public class ConditionalArrayList extends ArrayList {

  public Iterator iterator(Condition condition)
  { 
    return listIterator(condition);
  }

  public ListIterator listIterator(Condition condition)
  {
    return new ConditionalArrayListIterator(this.iterator(),condition); 
  }

  public ListIterator listIterator(){ return iterator(); }
  public iterator(){ 
    throw new InvalidArgumentException("You must specify a condition for the iterator"); 
  }
}

, тогда нам нужен классы помощника:

public class ConditionalArrayListIterator implements ListIterator
{
  private ListIterator listIterator;
  Condition condition;

  // the two following flags are used as a quick optimization so that 
  // we don't repeat tests on known-good elements unnecessarially.
  boolean nextKnownGood = false;
  boolean prevKnownGood = false;

  public ConditionalArrayListIterator(ListIterator listIterator, Condition condition)
  {
    this.listIterator = listIterator;
    this.condition = condition;
  }

  public void add(Object o){ listIterator.add(o); }

  /**
   * Note that this it is extremely inefficient to 
   * call hasNext() and hasPrev() alternatively when
   * there's a bunch of non-matching elements between
   * two matching elements.
   */
  public boolean hasNext()
  { 
     if( nextKnownGood ) return true;

     /* find the next object in the list that 
      * matches our condition, if any.
      */
     while( ! listIterator.hasNext() )
     {
       Object next = listIterator.next();
       if( condition.matches(next) ) {
         listIterator.set(next);
         nextKnownGood = true;
         return true;
       }
     }

     nextKnownGood = false;
     // no matching element was found.
     return false;
  }

  /**
   *  See hasPrevious for efficiency notes.
   *  Copy & paste of hasNext().
   */
  public boolean hasPrevious()
  { 
     if( prevKnownGood ) return true;

     /* find the next object in the list that 
      * matches our condition, if any.
      */
     while( ! listIterator.hasPrevious() )
     {
       Object prev = listIterator.next();
       if( condition.matches(prev) ) {
         prevKnownGood = true;
         listIterator.set(prev);
         return true;
       }
     }

     // no matching element was found.
     prevKnwonGood = false;
     return false;
  }

  /** see hasNext() for efficiency note **/
  public Object next()
  {
     if( nextKnownGood || hasNext() ) 
     { 
       prevKnownGood = nextKnownGood;
       nextKnownGood = false;
       return listIterator.next();
     }

     throw NoSuchElementException("No more matching elements");
  }

  /** see hasNext() for efficiency note; copy & paste of next() **/
  public Object previous()
  {
     if( prevKnownGood || hasPrevious() ) 
     { 
       nextKnownGood = prevKnownGood;
       prevKnownGood = false;
       return listIterator.previous();                        
     }
     throw NoSuchElementException("No more matching elements");
  }

  /** 
   * Note that nextIndex() and previousIndex() return the array index
   * of the value, not the number of results that this class has returned.
   * if this isn't good for you, just maintain your own current index and
   * increment or decriment in next() and previous()
   */
  public int nextIndex(){ return listIterator.previousIndex(); }
  public int previousIndex(){ return listIterator.previousIndex(); }

  public remove(){ listIterator.remove(); }
  public set(Object o) { listIterator.set(o); }
}

и, конечно, нам нужен интерфейс состояния:

/** much like a comparator... **/
public interface Condition
{
  public boolean matches(Object obj);
}

и условие, с которым к тесту

public class IsEvenCondition {
{
  public boolean matches(Object obj){ return (Number(obj)).intValue() % 2 == 0;
}

, и мы наконец Готов к некоторому тестому коду

    Condition condition = new IsEvenCondition();

    System.out.println("preparing items");
    startMillis = System.currentTimeMillis();
    List<Integer> items = new ArrayList<Integer>(); // Integer is for demo
    for (int i = 0; i < 1000000; i++) {
        items.add(i * 3); // just for demo
    }
    endMillis = System.currentTimeMillis();
    System.out.println("It took " + (endmillis-startmillis) + " to prepare the list. ");

    System.out.println("deleting items");
    startMillis = System.currentTimeMillis();
    // we don't actually ever remove from this list, so 
    // removeMany is effectively "instantaneous"
    // items = removeMany(items);
    endMillis = System.currentTimeMillis();
    System.out.println("after remove: items.size=" + items.size() + 
            " and it took " + (endMillis - startMillis) + " milli(s)");
    System.out.println("--> NOTE: Nothing is actually removed.  This algorithm uses extra"
                       + " memory to avoid modifying or duplicating the original list.");

    System.out.println("About to iterate through the list");
    startMillis = System.currentTimeMillis();
    int count = iterate(items, condition);
    endMillis = System.currentTimeMillis();
    System.out.println("after iteration: items.size=" + items.size() + 
            " count=" + count + " and it took " + (endMillis - startMillis) + " milli(s)");
    System.out.println("--> NOTE: this should be somewhat inefficient."
                       + " mostly due to overhead of multiple classes."
                       + " This algorithm is designed (hoped) to be faster than "
                       + " an algorithm where all elements of the list are used.");

    System.out.println("About to iterate through the list");
    startMillis = System.currentTimeMillis();
    int total = addFirst(30, items, condition);
    endMillis = System.currentTimeMillis();
    System.out.println("after totalling first 30 elements: total=" + total + 
            " and it took " + (endMillis - startMillis) + " milli(s)");

...

private int iterate(List<Integer> items, Condition condition)
{
  // the i++ and return value are really to prevent JVM optimization
  // - just to be safe.
  Iterator iter = items.listIterator(condition);
  for( int i=0; iter.hasNext()); i++){ iter.next(); }
  return i;
}

private int addFirst(int n, List<Integer> items, Condition condition)
{
  int total = 0;
  Iterator iter = items.listIterator(condition);
  for(int i=0; i<n;i++)
  {
    total += ((Integer)iter.next()).intValue();
  }
}

Я представляю себе, что построение нового списка, вместо того, чтобы изменять существующий, было бы более эффективным - особенно, когда количество элементов столь велико, как вы указываете. Это предполагает, что ваш список является ArrayList, а не LinkedList. Для некольцевого LinkedList, вставка - O(n), но удаление в существующем положении итератора - O(1); в этом случае Ваш наивный алгоритм должен быть достаточно производительным.

Если только список не является LinkedList, стоимость перемещения списка при каждом вызове remove(), вероятно, является одной из самых дорогих частей реализации. Для списков массивов я бы подумал об использовании:

public static <T> List<T> removeMany(List<T> items) {
    List<T> newList = new ArrayList<T>(items.size());
    Iterator<T> iter = items.iterator();
    while (iter.hasNext()) {
        T item = iter.next();
        // <cond> goes here
        if (/*<cond>: */i++ % 2 != 0) {
            newList.add(item);
        }
    }
    return newList;
}

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

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

Кроме того:

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

• Каждый раз, когда вы удаляете элемент списка, вы обновляете указатели, например, Lastnode.Next и NextNode.prev или что-то - но если окажется, вы также хотите Удалите NextNode , затем обновление указателя, которое вы только что вызвали новое обновление.)

Удаление много элементов из ArrayList - это работа O (N ^ 2) Отказ Я бы порекомендовал просто использовать LinkedList , который более оптимизирован для вставки и удаления (но не для случайного доступа). LinkedList имеет немного накладных расходов памяти.

Если вам нужно сохранить ArrayList , то вам лучше создавать новый список.

Обновление: сравнение с созданием нового списка:

Обновление того же списка, основная затрата исходит от удаления узла и обновления соответствующих указателей в LinkedList. Это постоянная операция для любого узла.

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

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

Есть больше осложнений, когда вы приносите менеджмент памяти и GC. Я хотел бы оставить их.

Лучший вариант - реализовать альтернативы и создать результаты при запуске типичной нагрузки.

, а не беспомощно мой первый ответ, который уже достаточно длинный, вот второй, связанный вариант: Вы можете создать свой собственный ArrayList, и флаг вещи как «удален». Этот алгоритм делает предположения:

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

Кроме того, это, опять же, не тестируемое, так что есть ошибки синтаксиса.

public class FlaggedList extends ArrayList {
  private Vector<Boolean> flags = new ArrayList();
  private static final String IN = Boolean.TRUE;  // not removed
  private static final String OUT = Boolean.FALSE; // removed
  private int removed = 0;

  public MyArrayList(){ this(1000000); }
  public MyArrayList(int estimate){
    super(estimate);
    flags = new ArrayList(estimate);
  }

  public void remove(int idx){
    flags.set(idx, OUT);
    removed++;
  }

  public boolean isRemoved(int idx){ return flags.get(idx); }
}

И итератор - больше труда может потребоваться сохранить его синхронизированные, и многие методы остаются, на этот раз:

public class FlaggedListIterator implements ListIterator
{
  int idx = 0;

  public FlaggedList list;
  public FlaggedListIterator(FlaggedList list)
  {
    this.list = list;
  }
  public boolean hasNext() {
    while(idx<list.size() && list.isRemoved(idx++)) ;
    return idx < list.size();
  }
}