프로그래밍로그

출처: 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);

출처: 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.

출처: http://stackoverflow.com/questions/10047802/public-static-final-or-private-static-final-with-getter

In Java, it's taught that variables should be kept private to enable better encapsulation, but what about static constants? This:

public static final int FOO = 5;

Would be equivalent in result to this:

private static final int FOO = 5;
...
public static getFoo() { return FOO; }

But which is better practice?

There's one reason to not use a constant directly in your code.

Assume FOO may change later on (but still stay constant), say to public static final int FOO = 10;. Shouldn't break anything as long as nobody's stupid enough to hardcode the value directly right?

No. The Java compiler will inline constants such as Foo above into the calling code, i.e.someFunc(FooClass.FOO); becomes someFunc(5);. Now if you recompile your library but not the calling code you can end up in surprising situations. That's avoided if you use a function - the JIT will still optimize it just fine, so no real performance hit there.

요약: 만약 어떤 코드가 caller와 callee로 되어 있을 때 callee의 상수가 public static final로 되어있을 경우, 그냥 그대로 사용할 경우 문제가 발생할 수 있다.

예를 들어 public static final int Foo = 5라고 정의가 되어있을 때 만약 someFunc(FooClass.Foo)라고 caller에서 사용한다면, JIT에서는 SomeFunc(5)로 치환해서 컴파일을 하게 된다. 그렇게 때문에 나중에 callee의 코드를 public static final int Foo = 10으로 고치게 되버리면 caller를 재컴파일하지 않으면 문제가 발생하게 된다. 이런 상황을 방지하려면, getter를 사용해야 한다.

non-static이나 non-final인 경우 이런 문제가 발생하지 않는다

아래는 추가 자료

출처: http://stackoverflow.com/questions/5173372/java-static-final-values-replaced-in-code-when-compiling

==fileA.java==
class A
{  
    public static final int SIZE = 100;
}  

Then in another file i use this value

==fileB.java==  
import A;
class b
{
      Object[] temp = new Object[A.SIZE];
}

When this gets compiled does SIZE get replaced with the value 100, so that if i were to down the road replace the FileA.jar but not FileB.jar would the object array get the new value or would it have been hardcoded to 100 because thats the value when it was originally built?

Another route to proving that the behavior is to looking at the generated bytecode. When the constant is "small" (presumably < 128):

public B();
  Code:
   0:   aload_0
   1:   invokespecial   #10; //Method java/lang/Object."<init>":()V
   4:   aload_0
   5:   bipush  42
   7:   anewarray       #3; //class java/lang/Object
   10:  putfield        #12; //Field temp:[Ljava/lang/Object;
   13:  return

}

(I used 42 instead of 100 so it stands out more). In this case, it is clearly substituted in the byte code. But, say the constant is "bigger." Then you get byte code that looks like this:

public B();
  Code:
   0:   aload_0
   1:   invokespecial   #10; //Method java/lang/Object."<init>":()V
   4:   aload_0
   5:   ldc     #12; //int 86753098
   7:   anewarray       #3; //class java/lang/Object
   10:  putfield        #13; //Field temp:[Ljava/lang/Object;
   13:  return

When it is bigger, the opcode "ldc" is used, which according to the JVM documentation "an unsigned byte that must be a valid index into the runtime constant pool of the current class".

In either case, the constant is embedded into B. I imagine, since that in opcodes you can only access the current classes runtime constant pool, that this the decision to write the constant into the class file is independent of implementation (but I don't know that for a fact).

출처: http://stackoverflow.com/questions/2062560/what-is-the-use-of-making-constructor-private-in-a-class

By providing a private constructor you prevent class instances from being created in any place other than this very class. There are several use cases for providing such constructor.

A. Your class instances are created in a static method. The static method is then declared aspublic.

class MyClass()
{
private:
  MyClass() { }

public:
  static MyClass * CreateInstance() { return new MyClass(); }
};

B. Your class is a singleton. This means, not more than one instance of your class exists in the program.

class MyClass()
{
private:
  MyClass() { }

public:
  MyClass & Instance()
  {
    static MyClass * aGlobalInst = new MyClass();
    return *aGlobalInst;
  }
};

C. (Only applies to the upcoming C++0x standard) You have several constructors. Some of them are declared public, others private. For reducing code size, public constructors 'call' private constructors which in turn do all the work. Your public constructors are thus called delegatingconstructors:

class MyClass
{
public:
  MyClass() : MyClass(2010, 1, 1) { }

private:
  MyClass(int theYear, int theMonth, int theDay) { /* do real work */ }
};

D. You want to limit object copying (for example, because of using a shared resource):

class MyClass
{
  SharedResource * myResource;

private:
  MyClass(const MyClass & theOriginal) { }
};

E. Your class is a utility class. That means, it only contains static members. In this case, no object instance must ever be created in the program.

여기에 보너스

This can be very useful for a constructor that contains common code; private constructors can be called by other constructors, using the 'this(...);' notation. By making the common initialization code in a private (or protected) constructor, you are also making explicitly clear that it is called only during construction, which is not so if it were simply a method:

public class Point {
   public Point() {
     this(0,0); // call common constructor
   }
   private Point(int x,int y) {
     m_x = x; m_y = y;
   }
};

1) OCP (Open Closed Principle)

소프트웨어의 구성요소(클래스, 모듈, 함수 등) 들은 확장에 대해서는 열려있어야 하지만, 변경에 대해서는 닫혀있어야 한다.

2) SRP (Single Responsibility Principle)

모든 클래스는 하나의 책임만을 지녀야 한다.

이는 또한, 객체를 변경해야 하는 이유는 단 하나여야 한다는 것과도 상통한다.

예를 들어 클래스 A는 출력에 대한 책임만 가지고 있고, 클래스 B는 입력과 출력에 대한 책임을 모두 가지고 있다고 했을 때

SRP를 지키고 있는 클래스 A가 그렇지 않은 B보다 상대적으로 복잡도가 낮을것이며, 또한 코드가 수정 될 가능성도 적을 것이다.

3) LSP (Liskov Substitution Principle)

Parent형의 변수에 Child 클래스의 인스턴스를 대입해도 문제없이 사용할 수 있어야 한다.

http://epicdevs.com/119

4) DIP (Dependency Inversion Principle)

상위 레벨 모듈은 하위 레벨 모듈에 의존하지 않아야 한다. 상위 레벨, 하위 레벨 모두 추상에 의존하여야 한다.

추상은 구상에 의존하지 않아야 한다. 구상 또한 추상에 의존하여야 한다.

http://epicdevs.com/117

5) ISP (Interface Segregation Principle)

클라이언트가 사용하지 않는 인터페이스에 클라이언트가 영향을 받아서는 안된다.

여러개의 클라이언트가 함께 사용하는 매우 큰 인터페이스를 만들지 말고,

좀 더 작고 구체적인 인터페이스를 만들어서, 하나의 인터페이스가 하나의 기능만을 담당하도록 만들어야 한다.

http://extern.tistory.com/14

http://www.oodesign.com/interface-segregation-principle.html

출처: http://stackoverflow.com/questions/7333376/difference-between-average-case-and-amortized-analysis

I am reading an article on amortized analysis of algorithms. Following is text snippet.

Amortized analysis is similar to average-case analysis, in that it is concerned with the cost averaged over a sequence of operations. However, average case analysis relies on probablistic assumptions about the data structures and operations in order to compute an expected running time of an algorithm. Its applicability is therefore dependent on certain assumptions about the probablity distribution of algorithm inputs.

An average case bound doesnot preclude the possiblity that one will get "unlucky" and encounter an input that requires most than expected time even if the assumptions on probablity distriubution of inputs are valid.

My questions on above text snippet are

1. In first paragraph how average case analysis relies on probabilistic assumptions about data structures and operations? I know average case analysis depend on probablity of input, but what does above statement mean?

2. What does author mean in second pargarph that average case doesnot valid even if input distrubution is valid?

Average case analysis makes assumptions about the input that may not be met in certain cases. Therefore, if your input is not random, in the worst case the actual performace of an algorithm may be much slower than the average case.

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 출간

카테고리

과학/기술

책소개

-

---

출처: http://en.wikipedia.org/wiki/Mapreduce

"Map" step: The master node takes the input, divides it into smaller sub-problems, and distributes them to worker nodes. A worker node may do this again in turn, leading to a multi-level tree structure. The worker node processes the smaller problem, and passes the answer back to its master node.

"Reduce" step: The master node then collects the answers to all the sub-problems and combines them in some way to form the output – the answer to the problem it was originally trying to solve.

한장의 그림으로 요약하는 MapReduce

출처: http://www.searchworkings.org/blog/-/blogs/introduction-to-hadoop/

도가 지나친 수준으로 테스트에 관심을 갖는 경우도 있다.

• 테스트를 기능하게 하려고 실제 코드의 가독성을 희생시킨다. 실제 코드 테스트를 가능하게 하는 것은 반드시 윈-윈 상황이 되어야 한다. 하지만 테스트를 가능하게 하려고 실제 코드에 지저분한 코드를 집어넣어야 한다면, 뭔가 잘못된 것이다.
• 100% 코드 테스트에 집착하는 일. 코드의 90%를 테스트하는 노력이 종종 나머지 10%를 테스트하는 비용보다 적은 노력이 들기도 한다. 그 10%는 어쩌면 버그로 인한 비용이 별로 높지 않기 때문에 굳이 테스트할 필요가 없는 사용자 인터페이스나 이상한 에러 케이스를 포함하고 있을지도 모른다.
• 사실, 코드를 100% 테스트하는 일은 일어나지 않는다. 테스트되지 않은 버그가 있을 수도 있고 테스트되지 않은 기능이 있을 수도 있으며, 요구사항이 달라졌다는 사실을 모르고 있을 수도 있기 때문 이다.
• 버그가 야기하는 비용이 어느 정도인지에 따라서, 테스트 코드를 작성하는 시간이 의미를 갖는 부분이 있고 그렇지 않은 부분도 있기 마련이다. 만약 웹사이트의 프로토타입을 만든다면, 테스트 코드 작성 건은 전혀 의미가 없다. 한편 우주선이나 의료장비를 통제하는 프로그램을 작성한다면 아마 테스트 코드에 주된 관심을 쏟아야 할 것이다.
• 테스트 코드로 실제 제품 개발이 차질을 빚게 되는 일. 우리는 단지 프로젝트의 일부분에 불과한 테스트가 프로젝트 전체를 지배하는 경우를 본 적이 있다. 테스트가 숭배되어야 하는 신의 자리를 차지하고, 프로그래머들은 자신의 시간이 다른 일에 쓰이는 것이 더 낫다는 사실을 망각한 채 자신을 위한 의식과 동작에 몰두한다. 

---

읽기 좋은 코드가 좋은 코드다

저자

더스틴 보즈웰 지음

출판사

한빛미디어 | 2012-04-06 출간

카테고리

컴퓨터/IT

책소개

이 책은 코드를 작성할 때 언제나 적용할 수 있는 기본적인 원리...

---

테스트하기 어려운 코드의 특징과 이것이 설계와 관련된 문제에 미치는 영향

테스트하기 좋은 코드의 특징

---

읽기 좋은 코드가 좋은 코드다

저자

더스틴 보즈웰 지음

출판사

한빛미디어 | 2012-04-06 출간

카테고리

컴퓨터/IT

책소개

이 책은 코드를 작성할 때 언제나 적용할 수 있는 기본적인 원리...

---