VPF::Открытый чемпионат Java коллекций

powerOn

Дата 3.4.2006, 17:35 (ссылка)

(нет голосов)

Загрузка ...

software saboteur

Профиль
Группа: Участник
Сообщений: 4367
Регистрация: 7.10.2005

Репутация: 47
Всего: 159

Здравствуйте!

Думаю, что многие задавались вопросом какая из коллекций работает быстрее. И у меня возник такой же вопрос, решить который я попытался организовав "открытый чемпионат Java коллекций"!

Первый чемпионат будет состоять из 2 соревнований: добавление элемента и удаление элемента.

В соревнованиях принимали учатстие 4 команды (интерфейсы коллекций):
Map, Set, Queue и List.

Среди кандидатов на победу от сборной Set были следующии:

Код


        // Set Interface
        HashSet hashSet = new HashSet();
        TreeSet treeSet = new TreeSet();
        LinkedHashSet linkedHashSet = new LinkedHashSet();

Среди кандидатов на победу от сборной List были следующии:

Код


        // List Interface
        ArrayList arrayList = new ArrayList();
        Vector vector = new Vector();
        LinkedList linkedList = new LinkedList();

Среди кандидатов на победу от сборной Map были следующии:

Код


        // Map Interface
        HashMap hashMap = new HashMap();
        TreeMap treeMap = new TreeMap();
        LinkedHashMap linkedHashMap = new LinkedHashMap();

И наконец сборная Queue представлена след. спортсменами:

Код


        // Queue Inteface
        PriorityQueue priorityQueue = new PriorityQueue();
        ConcurrentLinkedQueue concurrentLinkedQueue = new ConcurrentLinkedQueue();
        LinkedBlockingQueue linkedBlockingQueue = new LinkedBlockingQueue();
        PriorityBlockingQueue priorityBlockingQueue = new PriorityBlockingQueue();

Вот план соревнавания, представленный в Java коде. Спортмены сначала добавляют в себя элементы, а потом удаляют их. Пусть победит быстрейший!!!

Код


package test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;

/**
 *
 * @author Asu-Tjurikov
 */
public class TestMachine {
    
    /** Creates a new instance of Main */
    public TestMachine() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        // Set Interface
        HashSet hashSet = new HashSet();
        TreeSet treeSet = new TreeSet();
        LinkedHashSet linkedHashSet = new LinkedHashSet();
        
        // List Interface
        ArrayList arrayList = new ArrayList();
        Vector vector = new Vector();
        LinkedList linkedList = new LinkedList();
        
        // Queue Inteface
        PriorityQueue priorityQueue = new PriorityQueue();
        ConcurrentLinkedQueue concurrentLinkedQueue = new ConcurrentLinkedQueue();
        LinkedBlockingQueue linkedBlockingQueue = new LinkedBlockingQueue();
        PriorityBlockingQueue priorityBlockingQueue = new PriorityBlockingQueue();
        
        // Map Interface
        HashMap hashMap = new HashMap();
        TreeMap treeMap = new TreeMap();
        LinkedHashMap linkedHashMap = new LinkedHashMap();
        
        //----------------------------------------------------------------------
        
        TestMachine test = new TestMachine();
        int N = 100000;
        //----------------------------------------------------------------------
        
        System.out.println("- HashSet -");
        System.out.print(" - ADD : " + test.test_Set_add(hashSet,N));
        System.out.println("\t DEL : " + test.test_Set_del(hashSet,N));
        
        System.out.println("- TreeSet -");
        System.out.print(" - ADD : "+ test.test_Set_add(treeSet,N));
        System.out.println("\t DEL : " + test.test_Set_del(treeSet,N));
        
        System.out.println("- LinkedHashSet -");
        System.out.print(" - ADD : " + test.test_Set_add(linkedHashSet,N));
        System.out.println("\t DEL : " + test.test_Set_del(linkedHashSet,N));
        
        System.out.println("- HashMap -");
        System.out.print(" - ADD : " + test.test_Map_add(hashMap,N));
        System.out.println("\t DEL : " + test.test_Map_del(hashMap,N));
        
        System.out.println("- TreeMap -");
        System.out.print(" - ADD : " + test.test_Map_add(treeMap,N));
        System.out.println("\t DEL : " + test.test_Map_del(treeMap,N));
        
        System.out.println("- LinkedHashMap -");
        System.out.print(" - ADD : " + test.test_Map_add(linkedHashMap,N));
        System.out.println("\t DEL : " + test.test_Map_del(linkedHashMap,N));
        
        System.out.println("- ArrayList -");
        System.out.print(" - ADD : " + test.test_List_add(arrayList,N));
        System.out.println("\t DEL : " + test.test_List_del(arrayList,N));
        
        System.out.println("- Vector -");
        System.out.print(" - ADD : " + test.test_List_add(vector,N));
        System.out.println("\t DEL : " + test.test_List_del(vector,N));
        
        System.out.println("- LinkedList -");
        System.out.print(" - ADD : " + test.test_List_add(linkedList,N));
        System.out.println("\t DEL : " + test.test_List_del(linkedList,N));
        
        System.out.println("- PriorityQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(priorityQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(priorityQueue,N));
        
        System.out.println("- ConcurrentLinkedQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(concurrentLinkedQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(concurrentLinkedQueue,N));
        
        System.out.println("- LinkedBlockingQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(linkedBlockingQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(linkedBlockingQueue,N));
        
        System.out.println("- PriorityBlockingQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(priorityBlockingQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(priorityBlockingQueue,N));
    }
    
    // Set Interface
    public long test_Set_add(Set s, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            s.add( "be faster baby!" );
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_Set_del(Set s, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            s.remove( "be faster baby!" );
        }
        return System.currentTimeMillis() - start_time;
    }
    // Map Interface
    public long test_Map_add(Map m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.put(i, "be faster baby!" );
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_Map_del(Map m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.remove(i);
        }
        return System.currentTimeMillis() - start_time;
    }
    // List Interface
    public long test_List_add(List m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.add( "be faster baby!" );
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_List_del(List m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.remove(0);
        }
        return System.currentTimeMillis() - start_time;
    }
    // Queue Interface
    public long test_Queue_add(Queue q, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            q.offer( "be faster baby!" );
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_Queue_del(Queue q, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            q.remove();
        }
        return System.currentTimeMillis() - start_time;
    }
    ////////////////////////////////////////////////////////////////////////////
}

Я предлагаю что бы вы самостаятельно провели соревнавание на своем "стадионе", чтобы лучше почувствовать дух соперничества, а результаты выложить и обсудить здесь. Что касается проведенного у меня турнира, то мой стадион таков: Intel Celeron 2.6 512 RAM

результаты:

Код


- HashSet -
 - ADD : 16     DEL : 0
- TreeSet -
 - ADD : 31     DEL : 0
- LinkedHashSet -
 - ADD : 0     DEL : 16
- HashMap -
 - ADD : 312     DEL : 63
- TreeMap -
 - ADD : 187     DEL : 63
- LinkedHashMap -
 - ADD : 359     DEL : 78
- ArrayList -
 - ADD : 0     DEL : 13453
- Vector -
 - ADD : 15     DEL : 13422
- LinkedList -
 - ADD : 63     DEL : 15
- PriorityQueue -
 - ADD : 32     DEL : 15
- ConcurrentLinkedQueue -
 - ADD : 62     DEL : 32
- LinkedBlockingQueue -
 - ADD : 47     DEL : 15
- PriorityBlockingQueue -
 - ADD : 47     DEL : 31

По добавлению самые быстрые: ArrayList, LinkedHashSet.
По удалению самые быстрые: HashSet, TreeSet.
По добавлению самые медленные: HashMap, LinkedHashMap.
По удалению самые медленные: ArrayList, Vector.

PS: Правила соревнаваний, впрочем, еще можно пересмотреть. smile

--------------------

нет времени думать - нужно писать КОД!

powerOn

Дата 4.4.2006, 22:22 (ссылка)

(нет голосов)

Загрузка ...

software saboteur

Профиль
Группа: Участник
Сообщений: 4367
Регистрация: 7.10.2005

Репутация: 47
Всего: 159

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

Код


package test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;


public class TestMachine {
    
    /** Creates a new instance of Main */
    public TestMachine() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        // Set Interface
        HashSet hashSet = new HashSet();
        TreeSet treeSet = new TreeSet();
        LinkedHashSet linkedHashSet = new LinkedHashSet();
        
        // List Interface
        ArrayList arrayList = new ArrayList();
        Vector vector = new Vector();
        LinkedList linkedList = new LinkedList();
        
        // Queue Inteface
        PriorityQueue priorityQueue = new PriorityQueue();
        ConcurrentLinkedQueue concurrentLinkedQueue = new ConcurrentLinkedQueue();
        LinkedBlockingQueue linkedBlockingQueue = new LinkedBlockingQueue();
        PriorityBlockingQueue priorityBlockingQueue = new PriorityBlockingQueue();
        
        // Map Interface
        HashMap hashMap = new HashMap();
        TreeMap treeMap = new TreeMap();
        LinkedHashMap linkedHashMap = new LinkedHashMap();
        
        //----------------------------------------------------------------------
        
        TestMachine test = new TestMachine();
        int N = 100000;
        //----------------------------------------------------------------------
        
        System.out.println("- HashSet -");
        System.out.print(" - ADD : " + test.test_Set_add(hashSet,N));
        System.out.println("\t DEL : " + test.test_Set_del(hashSet,N));
        
        System.out.println("- TreeSet -");
        System.out.print(" - ADD : "+ test.test_Set_add(treeSet,N));
        System.out.println("\t DEL : " + test.test_Set_del(treeSet,N));
        
        System.out.println("- LinkedHashSet -");
        System.out.print(" - ADD : " + test.test_Set_add(linkedHashSet,N));
        System.out.println("\t DEL : " + test.test_Set_del(linkedHashSet,N));
        
        System.out.println("- HashMap -");
        System.out.print(" - ADD : " + test.test_Map_add(hashMap,N));
        System.out.println("\t DEL : " + test.test_Map_del(hashMap,N));
        
        System.out.println("- TreeMap -");
        System.out.print(" - ADD : " + test.test_Map_add(treeMap,N));
        System.out.println("\t DEL : " + test.test_Map_del(treeMap,N));
        
        System.out.println("- LinkedHashMap -");
        System.out.print(" - ADD : " + test.test_Map_add(linkedHashMap,N));
        System.out.println("\t DEL : " + test.test_Map_del(linkedHashMap,N));
        
        System.out.println("- ArrayList -");
        System.out.print(" - ADD : " + test.test_List_add(arrayList,N));
        System.out.println("\t DEL : " + test.test_List_del(arrayList,N));
        
        System.out.println("- Vector -");
        System.out.print(" - ADD : " + test.test_List_add(vector,N));
        System.out.println("\t DEL : " + test.test_List_del(vector,N));
        
        System.out.println("- LinkedList -");
        System.out.print(" - ADD : " + test.test_List_add(linkedList,N));
        System.out.println("\t DEL : " + test.test_List_del(linkedList,N));
        
        System.out.println("- PriorityQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(priorityQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(priorityQueue,N));
        
        System.out.println("- ConcurrentLinkedQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(concurrentLinkedQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(concurrentLinkedQueue,N));
        
        System.out.println("- LinkedBlockingQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(linkedBlockingQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(linkedBlockingQueue,N));
        
        System.out.println("- PriorityBlockingQueue -");
        System.out.print(" - ADD : " + test.test_Queue_add(priorityBlockingQueue,N));
        System.out.println("\t DEL : " + test.test_Queue_del(priorityBlockingQueue,N));
    }
    
    // Set Interface
    public long test_Set_add(Set s, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            s.add( i ); // добавлена полная уникальность 
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_Set_del(Set s, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            s.remove( i );
        }
        return System.currentTimeMillis() - start_time;
    }
    // Map Interface
    public long test_Map_add(Map m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.put(i, i );
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_Map_del(Map m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.remove(i);
        }
        return System.currentTimeMillis() - start_time;
    }
    // List Interface
    public long test_List_add(List m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.add( i );
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_List_del(List m, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            m.remove(0);
        }
        return System.currentTimeMillis() - start_time;
    }
    // Queue Interface
    public long test_Queue_add(Queue q, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            q.offer( i );
        }
        return System.currentTimeMillis() - start_time;
    }
    
    public long test_Queue_del(Queue q, int N) {
        long start_time = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
            q.remove();
        }
        return System.currentTimeMillis() - start_time;
    }
    ////////////////////////////////////////////////////////////////////////////
}

Результаты:

Код


- HashSet -
 - ADD : 411     DEL : 100
- TreeSet -
 - ADD : 230     DEL : 90
- LinkedHashSet -
 - ADD : 401     DEL : 90
- HashMap -
 - ADD : 361     DEL : 100
- TreeMap -
 - ADD : 250     DEL : 90
- LinkedHashMap -
 - ADD : 461     DEL : 110
- ArrayList -
 - ADD : 40     DEL : 10025
- Vector -
 - ADD : 40     DEL : 8762
- LinkedList -
 - ADD : 100     DEL : 20
- PriorityQueue -
 - ADD : 40     DEL : 191
- ConcurrentLinkedQueue -
 - ADD : 100     DEL : 220
- LinkedBlockingQueue -
 - ADD : 70     DEL : 30
- PriorityBlockingQueue -
 - ADD : 110     DEL : 211

добавление
самые быстрые: ArrayList, PriorityQueue, Vector
самые медленные: LinkedHashMap, HashSet.
удаление
самые быстрые: LinkedList, LinkedBlockingQueue.
самые медленные: ArrayList, Vector.

вот так smile

Это сообщение отредактировал(а) MoonCat - 5.4.2006, 11:45

--------------------

нет времени думать - нужно писать КОД!

ALKS

Дата 5.4.2006, 10:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 354
Регистрация: 22.3.2006

Репутация: 1
Всего: 11

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

Bozo

Дата 5.4.2006, 20:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 32
Регистрация: 5.4.2006

Репутация: нет
Всего: нет

Цитата(MoonCat @ 3.4.2006, 17:35)

Думаю, что многие задавались вопросом какая из коллекций работает быстрее. И у меня возник такой же вопрос, решить который я попытался организовав "открытый чемпионат Java коллекций"!

Такой тест уже существует. Здесь пример запуска либы и результат выполнения на P4 3400. Здесь результат на моей машине.

COVD

Дата 5.4.2006, 22:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1655
Регистрация: 26.7.2005

Репутация: 17
Всего: 43

Во всемирно известной книге Эккеля тоже нечто такое есть:

Type Get Iteration Insert Remove
Массив 1430 3850 нет нет
ArrayList 3070 12200 500 46850
LinkedList 16320 9110 110 60
Vector 4890 16250 550 46850

Но все эти коллекции предполагают кастинг, поскольку возвращают обьекты. Если уж скорость важна, то возможно имеет смысл специализированные коллекции делать.
А почему вы только добавление\удаление рассматриваете. Вы данные только добавляете-удаляете и больше никак не используете ? smile

Это сообщение отредактировал(а) COVD - 5.4.2006, 23:10

powerOn

Дата 6.4.2006, 08:24 (ссылка)

(нет голосов)

Загрузка ...

software saboteur

Профиль
Группа: Участник
Сообщений: 4367
Регистрация: 7.10.2005

Репутация: 47
Всего: 159

Цитата

Вы данные только добавляете-удаляете и больше никак не используете ? smile

ну это только эксперимент, ничего сверх серьезного я написать не хотел. Удаление и Добавление поскольку это наиболее часто используемые операции. Но если Вам угодно, то допишите другие операции и выкладывайте получившийся тест сюда, лично мне будет интерено. Я может и сам через некоторое время еще что-нибудь допишу.... smile

--------------------

нет времени думать - нужно писать КОД!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »