Вопрос производительности Java Collection - PullRequest
5 голосов
/ 27 мая 2010

Я создал метод, который принимает два Collection<String> в качестве входных данных и копирует один в другой.

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

 /**
  * Copies from one collection to the other. Does not allow empty string. 
  * Removes duplicates.
  * Clears the too Collection first
  * @param src
  * @param dest
  */
 public static void copyStringCollectionAndRemoveDuplicates(Collection<String> src, Collection<String> dest) {
  if(src == null || dest == null)
   return;

  //Is this faster to do? Or should I just comment this block out
  if(src.containsAll(dest))
   return;

  dest.clear();
  Set<String> uniqueSet = new LinkedHashSet<String>(src.size());
  for(String f : src) 
   if(!"".equals(f)) 
    uniqueSet.add(f);

  dest.addAll(uniqueSet);
 }

Может быть, быстрее просто удалить

if(src.containsAll(dest))
    return;

Потому что этот метод будет перебирать всю коллекцию в любом случае.

Ответы [ 6 ]

7 голосов
/ 27 мая 2010

Я бы сказал: убери это! Это дублирующий «код», Set выполняет ту же самую операцию «contains ()», поэтому нет необходимости предварительно обрабатывать его здесь. Если у вас нет огромной коллекции входных данных и блестящего теста O (1) для containsAll (); -)

Набор достаточно быстрый. Он имеет сложность O (n), основанную на размере входных данных (одна содержит () и (может быть) одна операция add () для каждой строки), и, если тест target.containsAll () завершается неудачно, contains () выполняется дважды для каждой строки -> менее производительный.

EDIT

Какой-то псевдокод для визуализации моего ответа

void copy(source, dest) {
  bool:containsAll = true;
  foreach(String s in source) {  // iteration 1
    if (not s in dest) {         // contains() test
       containsAll=false
       break
    }
  }
  if (not containsAll) {
    foreach(String s in source) { // iteration 2
      if (not s in dest) {        // contains() test
        add s to dest
      }
    }
  }
}

Если все исходные элементы находятся в dest, то свойство has () вызывается один раз для каждого исходного элемента. Если все, кроме последних исходных элементов, находятся в dest (наихудший случай), тогда метод has () вызывается (2n-1) раз (n = размер коллекции источника). Но общее количество проверок содержит () с , дополнительный тест всегда равен или превышает тот же код без дополнительного теста.

РЕДАКТИРОВАТЬ 2 Предположим, у нас есть следующие коллекции:

source = {"", "a", "b", "c", "c"}
dest = {"a", "b"}

Во-первых, проверка содержит все, потому что пустая строка в исходном коде не находится в dest (это небольшой недостаток в вашем коде;)). Затем вы создаете временный набор, который будет {"a", "b", "c"} (пустая строка и вторая "c" игнорируются). Наконец, вы добавляете что-нибудь в dest и предполагаете, что dest - это простой ArrayList, результат равен {"a", "b", "a", "b", "c"}. Это намерение? Более короткая альтернатива:

void copy(Collection<String> in, Collection<String> out) {
  Set<String> unique = new HashSet<String>(in);
  in.remove("");
  out.addAll(unique);
}
3 голосов
/ 27 мая 2010

containsAll() не поможет, если target содержит больше элементов, чем dest:
цель: [a, b, c, d]
dest: [a, b, c]
target.containsAll(dest) верно, поэтому dest - это [a, b, c], но должно быть [a, b, c, d].

Я думаю, что следующий код более элегантен:

Set<String> uniqueSet = new LinkedHashSet<String>(target.size());
uniqueSet.addAll(target);
if(uniqueSet.contains(""))
    uniqueSet.remove("");

dest.addAll(uniqueSet);
2 голосов
/ 27 мая 2010

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

Но этот код сбивает с толку. Он пытается добавить новые предметы в dest? Так почему же он сначала очищается? Просто вместо этого верните ваш новый uniqueSet вызывающему абоненту вместо того, чтобы беспокоиться. И разве ваш containsAll() чек не отменен?

1 голос
/ 27 мая 2010

Код трудно читать и не очень эффективен. Параметр "dest" сбивает с толку: он передается как параметр, затем очищается и результаты добавляются в него. Какой смысл быть параметром? Почему бы просто не вернуть новую коллекцию? Единственное преимущество, которое я вижу, это то, что вызывающая сторона может определить тип коллекции. Это необходимо?

Я думаю, что этот код может быть написан более четко и, вероятно, более эффективно следующим образом:

public static Set<String> createSet(Collection<String> source) {
    Set<String> destination = new HashSet<String>(source) {
        private static final long serialVersionUID = 1L;

        public boolean add(String o) {
            if ("".equals(o)) {
                return false;
            }
            return super.add(o);
        }
    }; 
    return destination;
}

Другой способ - создать собственный тип набора:

public class NonEmptyStringSet extends HashSet<String> {
    private static final long serialVersionUID = 1L;

    public NonEmptyStringSet() {
        super();
    }

    public NonEmptyStringSet(Collection<String> source) {
        super(source);
    }

    public boolean add(String o) {
        if ("".equals(o)) {
            return false;
        }
        return super.add(o);
    }
}

Использование:

createSet(source);
new NonEmptyStringSet(source);

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

Преимущество типа NonEmptyStringSet заключается в том, что вы можете продолжать добавлять строки и при этом проверять пустую строку.

EDIT1:

Удаление "if (src.containsAll (dest)) return;" код вводит «ошибку» при вызове метода с source == dest; В результате источник будет пустым. Пример:

Collection<String> source = new ArrayList<String>();
source.add("abc");
copyStringCollectionAndRemoveDuplicates(source, source);
System.out.println(source);

EDIT2:

Я сделал небольшой тест, который показывает, что моя реализация примерно на 30% быстрее, чем упрощенная версия вашей начальной реализации. Этот тест является оптимальным случаем для вашей первоначальной реализации, поскольку папка dest пуста, поэтому ее не нужно очищать. Также не думайте, что моя реализация использует HashSet вместо LinkedHashSet, что делает мою реализацию немного быстрее.

Код эталона:

public class SimpleBenchmark {
public static void main(String[] args) {
    Collection<String> source = Arrays.asList("abc", "def", "", "def", "", 
            "jsfldsjdlf", "jlkdsf", "dsfjljka", "sdfa", "abc", "dsljkf", "dsjfl", 
            "js52fldsjdlf", "jladsf", "dsfjdfgljka", "sdf123a", "adfgbc", "dslj452kf", "dsjfafl", 
            "js21ldsjdlf", "jlkdsvbxf", "dsfjljk342a", "sdfdsa", "abxc", "dsljkfsf", "dsjflasd4" );

    int runCount = 1000000;
    long start1 = System.currentTimeMillis();
    for (int i = 0; i < runCount; i++) {
        copyStringCollectionAndRemoveDuplicates(source, new ArrayList<String>());
    }
    long time1 = (System.currentTimeMillis() - start1);
    System.out.println("Time 1: " + time1);


    long start2 = System.currentTimeMillis();
    for (int i = 0; i < runCount; i++) {
        new NonEmptyStringSet(source);
    }
    long time2 = (System.currentTimeMillis() - start2);
    System.out.println("Time 2: " + time2);

    long difference = time1 - time2;
    double percentage = (double)time2 / (double) time1;

    System.out.println("Difference: " + difference + " percentage: " + percentage);
}

public static class NonEmptyStringSet extends HashSet<String> {
    private static final long serialVersionUID = 1L;

    public NonEmptyStringSet() {
    }

    public NonEmptyStringSet(Collection<String> source) {
        super(source);
    }

    @Override
    public boolean add(String o) {
        if ("".equals(o)) {
            return false;
        }
        return super.add(o);
    }
}

public static void copyStringCollectionAndRemoveDuplicates(
        Collection<String> src, Collection<String> dest) {
    Set<String> uniqueSet = new LinkedHashSet<String>(src.size());
    for (String f : src)
        if (!"".equals(f))
            uniqueSet.add(f);

    dest.addAll(uniqueSet);
}
}
1 голос
/ 27 мая 2010
  1. Слишком запутанные имена параметров. dest и target имеют почти одинаковое значение. Вам лучше выбрать что-то вроде dest и source. Это станет намного понятнее даже для вас.

  2. У меня есть ощущение (не уверен, что это правильно), что вы используете API коллекций неправильно. Интерфейс Collection ничего не говорит об уникальности своих элементов, но вы добавляете в него это качество.

  3. Изменение коллекций, переданных в качестве параметров, не лучшая идея (но, как обычно, это зависит). В общем случае изменчивость вредна и не нужна. Кроме того, что, если переданные коллекции являются неизменяемыми / неизменяемыми? Лучше вернуть новую коллекцию, а затем изменить входящие коллекции.

  4. Collection интерфейс имеет методы addAll, removeAll, retainAll. Вы пробовали их сначала? Вы сделали тесты производительности для кода как:

    Collection<String> result = new HashSet<String> (dest);
    result.addAll (target);
    

    или

    target.removeAll (dest);
    dest.addAll (target);
    
0 голосов
/ 27 мая 2010

Не думаю, что я понимаю, почему вы хотите этот метод, но предполагая, что он стоит, я бы реализовал его следующим образом:

public static void copyStringCollectionAndRemoveDuplicates(
        Collection<String> src, Collection<String> dest) {
    if (src == dest) {
         throw new IllegalArgumentException("src == dest");
    }
    dest.clear();
    if (dest instanceof Set) {
        dest.addAll(src);
        dest.remove("");
    } else if (src instance of Set) {
        for (String s : src) {
            if (!"".equals(s)) {
                dest.add(s);
            }
        }
    } else {
        HashSet<String> tmp = new HashSet<String>(src);
        tmp.remove("");
        dest.addAll(tmp);
    }
}

Примечания:

  1. Это не сохраняет порядок элементов в аргументе src во всех случаях, но сигнатура метода подразумевает, что это не имеет значения.
  2. Я сознательно не проверяю на ноль. Это ошибка, если в качестве аргумента задано значение NULL, и правильное решение - разрешить выброс NullPointerException.
  3. Попытка скопировать коллекцию себе также является ошибкой.
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...