Как удалить все определенные элементы из вектора

Question

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

Итак, мой вопрос: есть ли у нас более эффективный подход к этому?

Из кейса я хочу убрать лишний пробел "" и лишний "a" из вектора.

Мой вектор включает:

{"a", "rainy", " ", "day", "with", " ", "a", "cold", "wind", "day", "a"}

Вот мой код:

List lt = new LinkedList();
lt = new ArrayList();
lt.add("a");
lt.add(" ");
vec1.removeAll(lt);

Как вы можете видеть дополнительные пробелы в списке Vector, причина в том, что я использую Vector, чтобы прочитать и портировать слово изword document, а иногда и документ может содержать дополнительные пробелы, вызванные человеческой ошибкой.

Answer 1

Ваш текущий подход страдает проблемой, заключающейся в том, что удаление элемента из Vector является операцией O(N) ... и вы потенциально делаете это M раз (5 в вашем примере).

Предполагая, что у вас есть несколько "стоп-слов" и что вы можете изменять структуры данных, вот версия, которая должна (в теории) быть более эффективной:

    public List<String> removeStopWords(
            List<String> input, HashSet<String> stopWords) {
        List<String> output = new ArrayList<String>(input.size());
        for (String elem : input) {
            if (!stopWords.contains(elem)) {
                 output.append(elem);
            }
        }
        return res;
    }

    // This could be saved somewhere, assuming that you are always filtering
    // out the same stopwords.
    HashSet<String> stopWords = new HashSet<String>();
    stopWords.add(" ");
    stopWords.add("a");
    ... // and more

    List<String> newList = removeStopwords(list, stopWords);

---

Примечания:

• Выше создается новый список. Если вам необходимо повторно использовать существующий список, очистите его, а затем addAll новые элементы списка. (Это еще один O(N-M) шаг ... так что не делайте, если не нужно.)

• Если есть несколько стоп-слов, тогда использование HashSet будет более эффективным; например если сделано как указано выше. Я не уверен точно, где находится точка безубыточности (по сравнению с использованием списка), но я подозреваю, что она находится между 2 и 3 стоп-словами.

• Выше создается новый список, но копируются только элементы N - M. Напротив, алгоритм removeAll при применении к Vector может копировать O(NM) элементов.

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