Философия Java

         

Выбор между множествами (Set)


Вы можете выбирать между TreeSet и HashSet, в зависимости от размера множества Set (если вам необходимо производить упорядоченную последовательность из Set, используйте TreeSet). Следующая тестовая программа дает оценить затраты:

//: c09:SetPerformance.java

import java.util.*; import com.bruceeckel.util.*;

public class SetPerformance { private abstract static class Tester { String name; Tester(String name) { this.name = name; } abstract void test(Set s, int size, int reps); } private static Tester[] tests = { new Tester("add") { void test(Set s, int size, int reps) { for(int i = 0; i < reps; i++) { s.clear(); Collections2.fill(s, Collections2.countries.reset(),size); } } }, new Tester("contains") { void test(Set s, int size, int reps) { for(int i = 0; i < reps; i++) for(int j = 0; j < size; j++) s.contains(Integer.toString(j)); } }, new Tester("iteration") { void test(Set s, int size, int reps) { for(int i = 0; i < reps * 10; i++) { Iterator it = s.iterator(); while(it.hasNext()) it.next(); } } }, }; public static void test(Set s, int size, int reps) { System.out.println("Testing " + s.getClass().getName() + " size " + size); Collections2.fill(s, Collections2.countries.reset(), size); for(int i = 0; i < tests.length; i++) { System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(s, size, reps); long t2 = System.currentTimeMillis(); System.out.println(": " + ((double)(t2 - t1)/(double)size)); } } public static void main(String[] args) { int reps = 50000; // Или выбираем число повторов

// из командной строки:

if(args.length > 0) reps = Integer.parseInt(args[0]); // Маленький:

test(new TreeSet(), 10, reps); test(new HashSet(), 10, reps); // Средний:

test(new TreeSet(), 100, reps); test(new HashSet(), 100, reps); // Большой:

test(new TreeSet(), 1000, reps); test(new HashSet(), 1000, reps); } } ///:~

Следующая таблица показывает результаты одного запуска. (Конечно они будут различаться в зависимости от компьютера и используемой JVM; вы должны запустить тест сами):




Тип Тестовый размер Добавление Содержится Итерации
10 138.0 115.0 187.0
TreeSet 100 189.5 151.1 206.5
  1000 150.6 177.4 40.04
  10 55.0 82.0 192.0
HashSet 100 45.6 90.0 202.2
  1000 36.14 106.5 39.39
Производительность HashSet значительно отличается от TreeSet для всех операций (но обычно при добавлении и поиске, это две наиболее важные операции). Причина использования TreeSet в том, что он содержит се содержимое упорядоченным, так что используйте его только если вам нужно отсортированное множество.


Содержание раздела