Saturday, 15 March 2014

Java 8 : Difference between List.sort and Collections.sort

One of the most anticipated programming language updates in many years is here. Java 8 would be officially released on March 18, 2014. It offers a lot of new features which are worth exploring. One of them that we would be discussing here is List.sort. The addition of List.sort(Comparator) in Java 8 is fantastic. List.sort unsurprisingly allows you to sort a list, but the neat thing about List.sort is that for most of the common list implementations (such as ArrayList), it would sort much more quickly than Collections.sort. To understand this, first we need to know how Collections.sort works internally.

Collections.sort is a stable sort which means that equal elements won't be reordered after sorting. So, quicksort and heapsort are out of question since they are not stable. The most efficient stable sorting algorithm is merge sort. So, Java internally uses a modified version of merge sort. The exact algorithm was derived from Tim Sort which was developed by Tim Peter for Python. Tim sort is a combination of insertion sort and merge sort. If the number of elements is less than a certain value, insertion sort is used. This is because in case of smaller lists, the overhead of making recursive calls in case of merge sort is greater than the performance benefit obtained by using merge sort. Hence, it makes sense to use insertion sort for smaller lists.

Collections.sort implementation first dumps the specified list into a primitive array. Then it sorts this primitive array and puts back the sorted array elements back into the list in sorted order. Now the question is why do we need to copy the list into a new primitive array ? This is because Collections can be backed up by a primitive array (as in ArrayList) or can be backed up by a linked list (as in LinkedList). Copying into a new primitive array is done to avoid n^2 * log(n) performance that would result if we try to sort linked list in place.

But if we see carefully, this copying into a new primitive array is not required in case of ArrayList and some other list implementations since these list implementations are already backed up by a primitive array. This is exactly what List.sort takes advantage of. The default implementation of List.sort still does what Collections.sort does, but concrete implementing classes are free to optimize. For example, ArrayList.sort invokes Arrays.sort on the ArrayList's internal array. Hence the overhead of allocating and deallocating a new primitive array is gone. Also overhead of copying back the sorted elements from the array is gone. This is a big performance gain. Needless to say, we are saving space as well since we are not allocating space for a new primitive array.

Performance isn't the only potential gain from these new methods. Sorting a Collections.synchronizedList is an atomic operation using List.sort. You can iterate over all the elements of a List as an atomic operation using List.forEach. This was not possible in Java 7.

Saturday, 8 March 2014

Bonds

A bond is a fixed income security i.e. the return from a bond is known when it is issued. The essential difference between a bond and a stock can be summed up in one phrase : "Debt Vs Equity". That is, bonds represent debt and stocks represent equity ownership. This difference brings us to the first main advantage of bonds : In general, investing in bonds is safer than investing in stocks. The reason for this is because of the priority that debt holders have over share holders. But not all bonds are safe. There are also very risky bonds which are known as junk bonds. If a company goes bankrupt, debt holders are ahead of shareholders in the line to be paid.

Bond Issuance :

Bonds are issued by public authorities, credit institutions, governments and companies in the primary market. The bonds are mostly issued through a process called underwriting. On the other hand, government bonds are mostly issued in an auction. After the issue, the bonds can be traded in the secondary market just like other instruments.

Important Bond terms:

Principal value or Par value or face value :

This is the amount on which the issuer pays the interest. In most of the bonds, this amount has to be paid at the maturity of the bond. In some bonds, the amount which is paid at maturity is different from the principal amount.

Maturity :

This the date on which the bond expires. The issuer of the bond has to pay back the nominal amount to the holder of the bond on this date. Most of the bonds have term upto 10 to 30 years. But there are bonds with terms upto 100 years. And there are bonds with terms upto 1 year.

Coupon :

This is the interest rate that the issuer of the bond pays to the holder of the bond. Usually it is fixed, but it can also be variable.

Yield:

Yield is the rate of interest received from investing in the bond. It is one of the most important factors that investors care about while investing in bonds. We would talk more about it later.

Credit Rating:

This is the rating given by an agency which tells us the probability that the bond issuer would pay back the promised amount at maturity.

Some major types of bonds:

1) Fixed rate bonds : As the name suggests the coupon rate of these bonds is fixed.
2) Floating rate bonds :  The coupon rate of these bonds is not fixed.
3) Zero coupon bonds : These bonds don't pay any coupon.
4) High yield bonds :  These are also known as junk bonds. These bonds are usually start up companies which need capital to expand but don't have good credit rating. So, to lure the investors these companies issue high-yield bonds which have very high coupon rate. But this comes at the cost of risk associated with these bonds.
5) Convertible bonds : These types of bonds allows the owner of a bond to exchange it for some specific number of shares.

Bond Valuation:

Bond valuation refers to valuing the present value of a bond. The fundamental principle of bond valuation is that the bond's value is equal to the present value of its expected (future) cash flows. While valuing bonds, we consider time value of money concepts. Let's see how to calculate the price of a bond. First we need to compute the present value (PV) of the bond's future cash flows.The PV is the amount that would have to be invested today to generate that future cash flow. To find the value or the price of a bond, the PV of each individual cash flow should be added.

PV at time T = (Expected cash flow in period T) /( (1 + I) to the power T)
where I is the discount rate.

Value of bond = PV @ T1 + PV @ T2 +.........+ PV @ Tn

How does the value of a bond change:

As we can see, discount rate is the only variable factor in bond price. Rest everything is fixed.

  • As the rate increases of decreases, the discount rate that is used also changes. Higher the discount rate, the lower the value of a bond; the lower the discount rate, the higher the value of the bond. 
  • If the discount rate is higher than the coupon rate, the PV will be less than par. If the discount rate is lower than the coupon rate, the PV will be higher than par value.
  • As the bond moves closer to its maturity, it's price will closer to par. At par, market price is equal to par value and yield to maturity is equal to the coupon rate. This is clear since the expected rate of return in this case would be equal to the coupon rate. When a bond is selling at a discount, it's market price is less than the par value. So, it's yield to maturity is greater than the coupon rate. On the other hand, if a bond is selling at a premium, it's market price is greater than it's par value. So, it's yield to maturity is less than the coupon rate.
  • If a bond's market prices increases, then it's yield must increase; conversely if a bond's market price decreases, then it's yield must increase.
  • If a bond's yield does not change over it's life, then the size of it's discount or premium will decrease at an increasing rate as it's life gets shorter.