Выбор между картами (Map)

Когда выбираете между реализациями Map, размер Map - это то, что сильно влияет на производительность и приведенная ниже программа показывает необходимые затраты:

//: c09:MapPerformance.java

// Демонстрация различий в производительности для Maps.

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

public class MapPerformance { private abstract static class Tester { String name; Tester(String name) { this.name = name; } abstract void test(Map m, int size, int reps); } private static Tester[] tests = { new Tester("put") { void test(Map m, int size, int reps) { for(int i = 0; i < reps; i++) { m.clear(); Collections2.fill(m, Collections2.geography.reset(), size); } } }, new Tester("get") { void test(Map m, int size, int reps) { for(int i = 0; i < reps; i++) for(int j = 0; j < size; j++) m.get(Integer.toString(j)); } }, new Tester("iteration") { void test(Map m, int size, int reps) { for(int i = 0; i < reps * 10; i++) { Iterator it = m.entrySet().iterator(); while(it.hasNext()) it.next(); } } }, }; public static void test(Map m, int size, int reps) { System.out.println("Testing " + m.getClass().getName() + " size " + size); Collections2.fill(m, Collections2.geography.reset(), size); for(int i = 0; i < tests.length; i++) { System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(m, 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 TreeMap(), 10, reps); test(new HashMap(), 10, reps); test(new Hashtable(), 10, reps); // Средний:

test(new TreeMap(), 100, reps); test(new HashMap(), 100, reps); test(new Hashtable(), 100, reps); // Большой:

test(new TreeMap(), 1000, reps); test(new HashMap(), 1000, reps); test(new Hashtable(), 1000, reps); } } ///:~

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

Тип

Тестовый размер

Put



Get

Iteration

	10	143.0	110.0	186.0
TreeMap	100	201.1	188.4	280.1
	1000	222.8	205.2	40.7
	10	66.0	83.0	197.0
HashMap	100	80.7	135.7	278.5
	1000	48.2	105.7	41.4
	10	61.0	93.0	302.0
Hashtable	100	90.6	143.3	329.0
	1000	54.1	110.95	47.3

Как вы можете ожидать, производительность Hashtable примерно равна производительности HashMap. (Вы так же можете заметить, что HashMap в общем немного быстрее. HashMap предназначена заменить Hashtable.) TreeMap обычно медленнее, чем HashMap, так почему же вы должны использовать ее? Так как вы можете использовать ее не как Map, а как способ создания упорядоченного списка. Поведение дерева такое, что оно всегда упорядочено и не требует специального упорядочивания. Как только вы заполните TreeMap, вы можете вызвать keySet( ), чтобы получить Set представление ключей, а затем toArray( ) для производства массива этих ключей. Затем вы можете использовать статический метод Arrays.binarySearch( ) (будет обсужден позже) для повторного поиска объектов в вашем сохраненном массиве. Конечно, вам, вероятно, нужно будет делать это, если, по каким-то причинам, поведение HashMap будет неприемлемым, так как HashMap предназначена для повторного поиска вещей. Так же вы можете легко создать HashMap из TreeMap путем создания единственного объекта. В конце концов, при использовании Map, вашим первым выбором должен быть класс HashMap, и только если вам нужно постоянно упорядоченная Map, вам нужен TreeMap.


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

---

---