출처: http://people.ksp.sk/~kuko/bak/index.html


Binary search tree, AVL tree, B tree, Red-black tree, AA tree, Skiplist, Max heap, Min heap, Treap, Scapegoat tree, Splay tree 등의 자료구조들을 직접 동작시켜 볼 수 있는 Java Applet을 제공하는 사이트입니다.

저는 Skiplist를 공부해보려고 자료를 찾다가 발견하게 되었습니다.

기초적인 Binary search tree부터 고급 자료구조인 Skiplist나 Splay tree같은 것들도 다루고 있습니다.





  

HashSet vs TreeSet

Posted by epicdev Archive : 2012. 8. 23. 20:01

출처: http://stackoverflow.com/questions/1463284/hashset-vs-treeset


HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.

HashSet:

  • class offers constant time performance for the basic operations (add, remove, contains and size).
  • it does not guarantee that the order of elements will remain constant over time
  • iteration performance depends on the initial capacity and the load factor of the HashSet.
    • It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.

TreeSet:

  • guarantees log(n) time cost for the basic operations (add, remove and contains)
  • guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via it's constructor)
  • doesn't offer any tuning parameters for iteration performance
  • offers a few handy methods to deal with the ordered set like first(), last(), headSet(), and tailSet() etc

Important points:

  • Both guarantee duplicate-free collection of elements
  • It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
  • None of these implementation are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
  • LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.

So choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.

  • e.g. Set<String> s = new TreeSet<String>(hashSet);

  

HashTable vs HashMap vs ConcurrentHashMap

Posted by epicdev Archive : 2012. 8. 23. 19:41

출처: http://apurvagnihotri.blogspot.kr/2010/06/hashmap-vs-hashtable.html


HashMap and HashTable both provide key-value access to data.


The Hashtable is among the original collection classes in Java.Hashtable extends the Dictionary class, which as the Javadocs state, is obsolete and has been replaced by the Map interface. HashMap is part of the new Collections Framework, added with Java 2.


The key difference between the two is that access to the Hashtable is synchronized on the table while access to the HashMap is not synchronized.This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones


HashMap has a more complex hashing algorithm then Hashtable. It takes the hash value from the key and then hashes it again (double hashing). This can improve the distribution of the keys and hence the performance of the Map.


Another difference is that iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't. If we change the map while iterating, it will throw exception. 


Third difference is that HashMap permits null values in it, while Hashtable doesn't.Also note that only one NULL value is allowed as a key in HashMap. HashMap does not allow multiple keys to be NULL. Nevertheless, it can have multiple NULL values.


Using ConcurrentHashmap: for having a thread safe map we can use ConcurrenthashMap(from java5 onwards) as well instead of Hashtable which has become obsolete.


private Map myConcMap = new ConcurrentHashMap();


Now The question arises why ConcurrentHashMap and not HashTable or just have a synchronised access to HasMap.


So the major advantage of using ConcurrentHashMap is "performance" as the lock is not applied on wholeMap as is the case with a Synchronised access to hashmap or Hashtable.


As we know that hash maps store their data in a series of separate buckets, it is possible to lock only the portion of the map that is being accessed.ConcurrentHashMap uses this to provide us a highly optimized synchronised way of accessing HashMap.ConcurrentHash hash map follows following to provide a concurrent access:


1. Writing to a ConcurrentHashMap locks only a portion of the map

2. Reads can occur without locking.


Some disadvantges of ConcurrentHashMap:

ConcurrentHashMap will generally take up more memory.

it cannot take null as a key.

  


Procedure

Binary Heap

(Worst-Case)

Binomial Heap

(Worst-Case) 

Fibonacci Heap

(Amortized) 

 Pairing Heap

(Amortized)

 Brodal Queue

(Worst-Case)

MAKE-HEAP

Θ(1)

Θ(1)

Θ(1)

?

O(1)

INSERT

Θ(lg n)

O(lg n)

Θ(1)

O(1)

O(1)

MINIMUM

Θ(1)

O(lg n)

Θ(1)

O(1)

O(1)

EXTRACT-MIN

Θ(lg n)

Θ(lg n)

O(lg n)

O(lg n)

O(lg n)

UNION

Θ(n)

Θ(lg n)

Θ(1)

O(1)

O(1)

DECREASE-KEY

Θ(lg n)

Θ(lg n)

Θ(1)

O(lg n)

O(1)

DELETE 

Θ(lg n)

Θ(lg n)

O(lg n)

O(lg n)

O(lg n)


Fibonacci heaps are especially desirable when the number of EXTRACT-MIN and DELETE operations is small relative to the number of other operations performed. This situation arises in many applications. For example, some algorithms for graph problems may call DECREASE-KEY once per edge. For dense graphs, which have many edges, the O(1) amortized time of each call of DECREASE-KEY adds up to a big improvement over the Θ(lg n) worst-case time of binary or binomial heaps.


From a practical point of view, however, the constant factors and programming complexity of Fibonacci heaps make them less desirable than ordinary binary (or k-ary) heaps for most applications. Thus, Fibonacci heaps are predominantly of theoretical interest.


Binary heap과 Binomial heap에서 각각의 operation이 왜 위와 같은 복잡도가 나오는지 잘 설명해주는 강의노트

binary_and_binomial_heaps.pdf




Introduction to Algorithms

저자
Cormen, Thomas H./ Leiserson, Charles E./ Rivest, 지음
출판사
McGraw-Hill | 2001-07-01 출간
카테고리
과학/기술
책소개
-
가격비교


'Archive' 카테고리의 다른 글

객체지향 설계의 5원칙: OCP, SRP, LSP, DIP, ISP  (0) 2012.07.29
Average-case Analysis vs Amortized Analysis  (0) 2012.07.29
MapReduce  (0) 2012.06.23
지나친 테스트  (0) 2012.06.16
테스트에 친숙한 개발  (0) 2012.06.16
  
 «이전 1  다음»