Saturday, February 10, 2007

Effective Java Summary

  1. Static factory methods vs. constructors.
    1. Advantages
      1. They have descriptive names.
        1. Example: BigInteger.probablePrime
      2. They can reuse existing objects.
        1. Example: Boolean.valueOf(boolean)
      3. They can return a subtype of the declared type - good for hiding impl classes.
        1. Example: java.util.Collections methods
        2. Example: service provider frameworks like Java Cryptography Extension
    2. Disadvantages
      1. If class has no public or protected ctors, it can't be subclassed.
      2. Static factory methods are not distinguished in javadoc from other static methods.
        1. Can compensate by using standard naming conventions (still evolving), e.g. valueOf, getInstance, etc.
  2. Use private ctor to enforce singleton
    1. More future flexibility if singleton obtained through static method. E.g. lets you return a unique instance per thread in the future without changing API.
    2. If singleton is Serializable, must also implement readResolve().
  3. Use private ctor to enforce noninstantiability.
    1. Making class abstract for this purpose does not work.
  4. Avoid duplicate objects
    1. Especially if object is immutable.
    2. Relates to using static factory methods instead of ctors (Item 1).
    3. Can make it clear when objects are used as if they were constants (e.g. Calendar).
    4. Relates to lazy initialization (Item 48).
    5. Case: adapters that delegate to a backing object.
    6. But, object pools are generally bad, except when object is extremely expensive to create (e.g. database connection).
  5. Clean out obsolete objects
    1. Mainly to prevent memory leaks (termed unintentional object retentions).
    2. Essential when a class manages its own memory.
    3. Common issue in caches. Possible solution strategies:
      1. WeakHashMap
      2. Timer-based expiration of old objects.
      3. java.util.LinkedHashMap - has a removeEldestEntry method, which can expire entries based on insertion-order or access-order, depending on how the LinkedHashMap is constructed.
    4. Diagnosis of memory leaks usually requires using a heap profiler.
  6. Finalizer issues
    1. Two legitimate uses: safety net and cleaning up noncritical native resources.
    2. Finalizer guardian idiom - consider using for every nonfinal public class with a finalizer.
  7. Contract of equals
    1. When not overriding is ok:
      1. Each instance of the class is inherently unique (e.g. Thread).
      2. A logical equality test isn't really needed (e.g. java.util.Random).
      3. A superclass alread implements equals adequately (e.g. AbstractSet, AbstractList, AbstractMap).
      4. Class is private or package-private, and you're certain equals will never be called. But, could implement anyway to at least throw UnsupportedOperationException, just to make sure.
    2. When overriding is recommended:
      1. When there's a concept of logical equality that's different from object identity.
  8. Override hashCode when overriding equals
    1. Required if object used as key in HashMap/Hashtable or value in HashSet.
    2. Equal objects must have equal hash codes.

  9. Override toString
  10. clone
    1. clone() is like another constructor.
    2. Callers of clone() must cope with catching an exception.
    3. clone() is incompatible with the normal use of final fields.
    4. You are probably better off providing an alternative means of object copying.
    5. One alternative is the copy constructor.
  11. Comparable
  12. Minimize accessibility
    1. For information hiding and encapsulation
    2. Purpose is to hide design decisions, so that they may be changed in the future with no impact to the API.
  13. Immutable objects
    1. Inherently thread-safe; no synchronization required.
    2. Can be shared freely.
    3. Even internals can be shared
    4. But they require a new object for each distinct value (e.g. BigInteger).
    5. Classes should be immutable unless there's a very good reason to make them mutable.
    6. If a class cannot be made immutable, limit its mutability as much as possible.
    7. Constructors should create fully initialized objects with all their invariants established.
  14. Composition vs. inheritance
    1. Inheritance breaks encapsulation.
    2. Inheritance must document self-use (evidence of broken encapsulation).
  15. Prohibit inheritance if not designed for inheritance
    1. Must document precisely the effects of overriding any method.
    2. May have to provide hooks into internal workings for subclass to use.
    3. Constructors must not invoke overridable methods.
    4. Neither clone nor readObject may invoke an overridable method, directly or indirectly.
  16. Interfaces vs. abstract classes
    1. Existing classes can be easily retrofitted to implement a new interface.
    2. Interfaces are ideal for defining mixins.
    3. Interfaces allow the construction of nonhierarchical type frameworks.
    4. Intefaces enable safe, powerful functionality enhancements via the wrapper class idiom.
    5. It is far easier to evolve an abstract class than it is to evolve an interface.
  17. Proper use of interfaces
    1. Don't use interfaces as a means of exporting constants.
  18. Static vs. nonstatic member classes
    1. If you declare a member class that doesn't require access to an enclosing instance, put the static modifier in the declaration.
  19. C structures => classes
  20. C unions => class hierarchies
  21. C enum => classes (in JDK 1.5, enum)
  22. C function pointers => classes and interfaces
  23. Validate method parameters
    1. Document restrictions and enforce them with checks that throw runtime exceptions.
    2. Nonpublic methods should generaly check their parameters using assertions rather than normal checks.
  24. Defensive copies
    1. You must program defensively with the assumption that clients of your class will do their best to destroy its invariants.
    2. It's essential to make a defensive copy of each mutable parameter to the constructor.
    3. Defensive copies are made before checking the validity of the parameters, and the validity check is performed on the copies rather than the originals -- prevents possible race with another thread.
    4. Do not use the clone method to make a defensive copy of a parameter whose type is subclassable by untrusted parties.
  25. Method signature design
    1. Choose method names carefully, following standard naming conventions (item 38).
    2. Don't go overboard in providing convenience methods. When in doubt, leave it out.
    3. Avoid long parameter lists. Long sequences of identically typed parameters are especially harmful.
      1. Break up method into multiple methods, each with fewer parameters.
      2. Create helper classes (aka parameter object) to hold aggregates of parameters.
    4. For parameter types, favor interfaces over classes.
    5. Avoid function objects unless there is good reason to use them.
  26. Method overloading
    1. The choice of which method overload to invoke is made at compile time.
    2. Note: selection among overloaded methods is static, but selection among overridden methods is dynamic.
    3. Avoid confusing uses of overloading. A safe, conservative policy is nevr to export two overloadings with the same number of parameters.
      1. Use differently named methods instead - e.g. ObjectOutputStream's write* and read* methods.
  27. Returning zero-length array vs. null
    1. Null causes special-case code to be in both the method and the client.
    2. Zero-length arrays are immutable and thus can be shared freely.
    3. There is no reason ever to return null from an array-valued method instead of returning a zero-length array.
  28. Document all exported APIs
    1. Every exported class, interface, and member should be preceded with a doc comment.
    2. Method doc should succinctly describe the contract between the method and the client.
    3. The contract should say what the method does rather than how it does its job.
    4. Sometimes necessary to document overall architecture of a complex API in a separate document, linked from the related class or package doc comments.
  29. Minimize local variable scope
  30. Know the libraries
  31. float/double and exact answers
  32. String vs. non-string
  33. Perf of string concatenation
  34. Refer to objects by their interfaces
  35. Interfaces vs. reflection
  36. Avoid native methods
  37. Optimizing
  38. Naming conventions
  39. Proper use of Exceptions
  40. Checked vs. runtime exceptions
  41. Proper use of checked exceptions
  42. Benefits of standard exceptions
  43. Exceptions and abstraction
  44. Document all thrown exceptions
  45. Exception message detail
  46. Failure atomicity
  47. Don't ignore exceptions
  48. Synchronize access to shared mutable data
  49. Avoid excessive synchronization
  50. Never invoke wait outside a loop
  51. Don't depend on the thread scheduler
  52. Document thread safety
  53. Avoid thread groups
    1. They are basically obsolete.
    2. Only useful bit is ThreadGroup.uncaughtException for handling an uncaught exception thrown from one of the threads in the group.
  54. Implementing Serializable
  55. Custom serialized form
  56. Defensive readObject impl
  57. When to provide readResolve

Algorithms Summary

  • Sorting
    • quicksort, heapsort, mergesort
  • Shortest Path
    • Dijstra's Algorithm -- O(E V log V) -- priority queue
  • Approximate Algorithms
    • NP-complete problems, e.g. TSP
    • Find a path that is at most 10% longer than the shortest path.
  • Random Algorithms
    • Quicksort -- average O(N log N)
    • Find median number -- average O(N)
  • Compression
    • LZW, MP3, JPG
  • Maximum Flow, Minimum Cut
    • Fastest flow of supplies through rail network.
    • Minimum change needed to disrupt flow.
    • How to assign N employees to M jobs so that every job gets done.
  • Sequence Comparison
    • Use DP to get O(N*M) instead of exponential.

Tuesday, January 23, 2007

Greedy Algorithms

A greedy algorithm is very similar to a dynamic programming algorithm. Both require the problem to have optimal substructure. However, whereas DP also needs overlapping subproblems, a greedy algorithm must have the opposite -- subproblems are not interdependent. Furthermore, the subproblems must be structured in such a way that making a locally optimal decision at each step in constructing the solution always leads to the globally optimal solution. This is known as the greedy-choice property. To know that a greedy algorithm will correctly solve a problem, you generally need to prove that the problem has the greedy-choice property. According to CLR, that proof can sometimes require "some cleverness."

The textbook examples are:
  • Activity Scheduling
  • Fractional Knapsack Problem (but not 0-1 Knapsack Problem)
  • Huffman Codes
  • Dijkstra's Algorithm

Dynamic Programming Algorithms

Notes on dynamic programming, from CLR Algorithms Ch 16.

Key points:
  • Solves problems by combining solutions to subproblems.
  • Requires that the problem possess optimal substructure.
  • Differs from divide-and-conquer in that subproblems are overlapping.
  • Can use table lookup (memoization) to avoid solving a subproblem more than once.
    • Memoization allows for a top-down strategy, instead of DP's usual bottom-up approach.
  • DP is typically used for optimization problems, where a minimum or maximum value is sought.
Four steps to developing a dynamic programming algorithm:
  1. Describe the structure of an optimal solution.
  2. Recursively define the value of an optimal solution.
  3. Compute the value of an optimal solution in bottom-up fashion.
  4. Construct an optimal solution from the computed information.
Textbook examples where dynamic programming solutions apply:
  • Matrix-chain multiplication
  • Longest common subsequence of two sequences
  • Optimal triangulation of a convex polygon
CLR says: "In general practice, if all subproblems must be solved at least once, a bottom-up DP algorithm usually outperforms a top-down memoized algorithm by a constant factor, because there is no overhead for recursion and less overhead for maintaining the table. Moreover, there are some problems for which the regular pattern of table accesses in the DP algorithm can be exploited to reduce time or space requirements even further. Alternatively if some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of only solving those subproblems that are definitely required."

Monday, January 22, 2007

class Enum<K extends Enum<K>>

In Java, the java.lang.Enum class is declared as:

public abstract class Enum<E extends Enum<E>>

Why is the type parameter declared as <E extends Enum<E>>? What would happen if it were declared as <E extends Enum> instead?
Solution


This pattern is used when a generic base class needs to reference the type of the subclass. For example, suppose we had:

public enum CardSuit { HEARTS, CLUBS, DIAMONDS, SPADES }

This gets compiled as something like:

public class CardSuit extends Enum<CardSuit>....

which then means that every occurrence of type parameter E in Enum's declaration becomes CardSuit. Thus, the superclass (Enum) is able to reference subclass types in its method signatures and return types this way through the type parameter.

If just <E extends Enum> were used instead, that would still be the case, but some information would be lost. The type parameter E is mentioned in three places in Enum:
  1. implements Comparable<E>
  2. public int compareTo(E o)
  3. public Class<E> getDeclaringClass()
If the class declaration just had E extends Enum, then the Comparable interface is only aware of Comparable<Enum> instead of Comparable<CardSuit>. So E extends Enum<E> contains some extra information, making it more typesafe.

Monday, October 30, 2006

XOR Using NAND

Create an XOR gate using only NAND gates.
Solution

By definition:

a XOR b = (a OR b) AND NOT(a AND B)

The key is to apply De Morgan's rule repeatedly:

NOT(x OR y) = (NOT x) AND (NOT y)
NOT(x AND y) = (NOT x) OR (NOT y)

and the fact that:

NOT(x AND y) = x NAND y
NOT x = x NAND x

until XOR can be expressed entirely as NOT and NAND operations:

a XOR b
= (a OR b) AND (a NAND b)
= (NOT(NOT(a OR b))) AND (a NAND b)
= (NOT((NOT a) AND (NOT b))) AND (a NAND b)
= ((NOT a) NAND (NOT b)) AND (a NAND b)
= NOT(((NOT a) NAND (NOT b)) NAND (a NAND b))

Chameleons

An isolated population of chameleons was initially divided as follows:
  • 13 red chameleons
  • 15 green chameleons
  • 17 blue chameleons
Each time two different colored chameleons would meet, they would change their color to the third one. For example, if green meets red, they both change their color to blue. Is it ever possible for all chameleons to become the same color? Why or why not?

Solution

To get all the same color, two of the colors must first have the exact same number of chameleons. Then the chameleons would just pair up and eventually all turn into the same color. So for example, we'd have x of color A, x of color B, and y of color C. Going back another step, in order to get x A's and x B's, it would have to be preceded by one of the following:
  • x+1 A's, x+1 B's, y-2 C's
  • x+1 A's, x-2 B's, y+1 C's
  • x-2 A's, x+1 B's, y+1 C's
That is, in the step before, there were either the same number of A's and B's, or the difference between A's and B's changed by +/- 3. Since these are all the possible preceeding steps, we can generalize and say that on each step the difference between A's and B's either changes by 0 or 3. So in order to reach equal numbers, we must be able to have:

(C1 - C2) mod 3 = [0]

for any two colors C1 and C2. Initially, we have:

(A - B) mod 3 = (13 - 15) mod 3 = [1]
(A - C) mod 3 = (13 - 17) mod 3 = [2]
(B - C) mod 3 = (15 - 17) mod 3 = [1]

If any of these can be turned into [0], then we have a way to get all chameleons the same color. However, consider the case where an A and B meet and both change into C:

((A-1) - (B-1)) mod 3 = (A - B) mod 3 = [1]
((A-1) - (C+2)) mod 3 = (A - C - 3) mod 3 = [2]
((B-1) - (C+2)) mod 3 = (B - C - 3) mod 3 = [1]

None of the equations changed! Now what about when B and C meet and change into A:

((A+2) - (B-1)) mod 3 = (A - B + 3) mod 3 = [1]
((A+2) - (C-1)) mod 3 = (A - C + 3) mod 3 = [2]
((B-1) - (C-1)) mod 3 = (B - C) mod 3 = [1]

Still no change! And finally when A and C meet and change into B:

((A-1) - (B+2)) mod 3 = (A - B - 3) mod 3 = [1]
((A-1) - (C-1)) mod 3 = (A - C) mod 3 = [2]
((B+2) - (C-1)) mod 3 = (B - C + 3) mod 3 = [1]

So regardless of what step is taken, all three "(C1-C2) mod 3" equations continue to be either [1]or [2]. There is no step that causes any of the equations to be [0], and therefore there is no way to end up with the same number of chameleons.