jump to navigation

How to properly implement shuffle May 17, 2010

Posted by metalickl in Java, Software Insights, Uncategorized.
Tags: , , ,
add a comment

I was challenged by a coworker to implement a shuffle function while playing a card game. Immediately, I thought of an algorithm that involves a random number generator. My algorithm loops through all n elements in the input. For each element, it ‘swaps’ itself with any other element in the sequenced input, the swapping index is determined by the random number generator. I thought this was a good approach, since the probability of any element been swapped and the position it swaps to is equal with respect to any other element. The method had turned out to be incorrect. The code illustrates my algorithm is as follows:

// my algorithm. Don't do this
public static void shuffle(List<Object> input) {
	Random rand = new Random();
	for (int i = 0; i < input.size(); i++) {
		Object tmp = input.elementAt(i);
		int index = rand.nextInt(input.size());
		input.setElement(i, input.elementAt(index));
		input.setElement(index, tmp);
	}
}

Close analysis reveals that this function is actually unfair generating random permutations. The number of possible permutations can be generated through shuffling n inputs is n!. But this function generates n^n arrangements. This means that there would be permutations appear more frequent than others.

I scratched my head (metaphorically) and wondered how Java std library did it. The source code of Collections.shuffle is as follows:

 // Java Standard Library, java.util.Collections.java. Use this.
 1845       /**
 1846        * Moves every element of the list to a random new position in the list.
 1847        *
 1848        * @param list
 1849        *            the List to shuffle.
 1850        *
 1851        * @throws UnsupportedOperationException
 1852        *             when replacing an element in the List is not supported.
 1853        */
 1854       public static void shuffle(List<?> list) {
 1855           shuffle(list, new Random());
 1856       }

...

 1858       /**
 1859        * Moves every element of the list to a random new position in the list
 1860        * using the specified random number generator.
 1861        *
 1862        * @param list
 1863        *            the list to shuffle.
 1864        * @param random
 1865        *            the random number generator.
 1866        * @throws UnsupportedOperationException
 1867        *             when replacing an element in the list is not supported.
 1868        */
 1869       public static void shuffle(List<?> list, Random random) {
 1870           @SuppressWarnings("unchecked") // we won't put foreign objects in
 1871           final List<Object> objectList = (List<Object>) list;
 1872
 1873           if (list instanceof RandomAccess) {
 1874               for (int i = objectList.size() - 1; i > 0; i--) {
 1875                   int index = random.nextInt(i + 1);
 1876                   objectList.set(index, objectList.set(i, objectList.get(index)));
 1877               }
 1878           } else {
 1879               Object[] array = objectList.toArray();
 1880               for (int i = array.length - 1; i > 0; i--) {
 1881                   int index = random.nextInt(i + 1);
 1882                   Object temp = array[i];
 1883                   array[i] = array[index];
 1884                   array[index] = temp;
 1885               }
 1886
 1887               int i = 0;
 1888               ListIterator<Object> it = objectList.listIterator();
 1889               while (it.hasNext()) {
 1890                   it.next();
 1891                   it.set(array[i++]);
 1892               }
 1893           }
 1894       }

This algorithm traverses the list from the end, each step it assumes that the elements visited are already shuffled, and thus not considered. The number of permutations generated by this algorithm is n!, exactly matches our mathematic model. I guess the lesson for me, and maybe the reader as well, is that never attempt to implement your own algorithm, because it’s very probable that your algorithm has been carefully implemented by other experts who had gone through the trouble of been criticized. At the same time, mistakes are avoided.

API Design: Observer pattern in state change or transactional communication December 27, 2009

Posted by metalickl in Java, Software Insights.
Tags: , , , ,
add a comment

The challenge I’ve personally met can be boiled down to design a simple interfacing method to a web service call, for example authentication. The caveats here include network latency, response handling and possible errors(timeout, 404, IOException’s you name it). In terms of response handling, I remembered in C we had some kind of predetermined response codes (such as those found in HTTP response, 200′s, 300′s indicating success, and the 400′s/500′s indicating failure). With this design, you simply define a list of response codes (with thorough documentation), and then simply return an int that describes the response in the least verbose manner. To visualize, it becomes something like this:

// Don't do this
/** indicating success in authentication  */
public static final int AUTHENTICATION_SUCCESS = 200;
...
/** 
 *  returns response code,
 *  such as {@link AUTHENTICATION_SUCCESS}
 */
public int authenticate();

The advantage of abstraction is also its weakness. The response itself is converted to a number, where much of the information is lost(abstracted away) during the process. The user of this API would first having to read the source/javadoc comments to understand what are each of the response codes, then implement the logic to handle each case respectively. If there’s a bug inside the method, and a number that’s not a valid response is returned, the client code needs to handle that as well. Worst, if there’s declared exception (ie the familiar IOException), and the client needs to call several of these methods, one after the succession of the other, the client code would look something like this.

// Don't do this
// API methods
public int authenticate() throws IOException;
public int fetchBillingInfo() throws IOException;
public int payBill() throws IOException;
...
// Client code
public void run() {
  try {
    if (authenticate() == AUTHENTICATION_SUCCESS) {
	try {
	  if (fetchBillingInfo() == FETCHBILL_SUCCESS) {
	    try {
	      if (payBill() == PAYBILL_SUCCESS) {
		// do something
	      } else { // do somehting }
	    } catch (IOException e) { // do somehting }
           } else { // do something }
	} catch (IOException e) { // do something }
    } else { // do soemthing }
  } catch (IOException e) { // do something }
}

You see where I’m getting? Obviously no.. because the code here is unnecessarily nested, very ugly indeed. In terms of performance, try-catch blocks is also much slower to execute.

The solution to the above concerns I’ve found to be most elegant, which takes advantage of all the goodness of type safety and verboseness is to implement observer pattern. The class that wishes to access the service API first becomes registered as a service state listener. Then the API simply fires appropriate events in place of returning different responses. Look at the example below:

// API
/**
 * an enumeration of service states
 * <p>much clearer to read and understand by client
 */
public Enum ServiceState { 
  AUTHENTICATION_SUCCESS, 
  AUTHENTICATION_BAD_USRNAME_OR_PW, 
  AUTHENTICATION_PASSWORD_EXPIRED, 
  AUTHENTICATION_USER_BANNED, BILL_FETCHED, 
  BILL_UNAVAILABLE, PAYBILL_SUCCESS 
}

/** 
 * client code must implement this interface in order to access 
 * the service interfacing methods and be notified of the responses. 
 */
public interface ServiceStateListener { void serviceStateChanged(ServiceState ss); }

public void Session.authenticate();
public void Session.fetchBillingInfo();
public void Session.payBill();
...

// Client Code
public void run() {
  session.addServiceStateListener(this);
  session.authenticate();
}

public void serviceStateChanged(ServiceState ss) {
  if (ss == AUTHENTICATION_SUCCESS) {
    session.fetchBillingInfo();
  } else if (ss == BILL_FETCHED) {
    session.payBill();
  } else if (ss == PAYBILL_SUCCESS) {
    session.removeServiceStateListener(this);
  } else if (ss == AUTHENTICATION_BAD_USRNAME_OR_PW) {
    ...
  } else {
    ...
  }
}

The API itself defines the different service states or responses, in a case that more service states are needed, they can be easily added to the Enum without breaking the compatibility. The service methods do not declare checked Exceptions, but fires notification to indicate service state changes. To access the API, the client code simply becomes registered as a ServiceStateListener, and then call the first service method, i.e. session.authenticate(). The work is minimum from there on, the state transition and logic is simple and is handled in serviceStateChanged(). This designs takes advantage of the goodness of type safety, the API will never notify of anything other than a Service State. It is also much more readable and organized. This is the solution I have found and implemented in my personal project.

The name you cannot utter December 25, 2009

Posted by metalickl in Software Insights.
Tags: , ,
add a comment

This was an absolute discovery by accident. I created a Java project under Mac OSX with something like com.***.****.con, where con was intended as a package for classes in communication and data connections. I then went ahead and checked the project into SVN.
Later when I tried again to check out the project using Eclipse in Windows XP, I kept on getting errors saying that there’s been errors in creating the folder con. A little researched served me right, and it had turned out that there are some reserved names in windows. Along with con, there are also

CON, PRN, AUX, CLOCK$, NUL
COM0, COM1, COM2, COM3, COM4, COM5, COM6, COM7, COM8, COM9
LPT0, LPT1, LPT2, LPT3, LPT4, LPT5, LPT6, LPT7, LPT8, and LPT9.

which you simply cannot use for as a filename.

The windows distribution of Eclipse has been thoughtful. If you try to create a package with a reserved name, there will be an error message saying that package name is not supported on the current platform.

窦唯/DouWei complete discography December 5, 2009

Posted by metalickl in Life, Music.
add a comment

窦唯 / Dou Wei / Douwei

Being my favourite musician, I wanted to talk about his music for a while now. Douwei is one of the most inventive, talented musicians from China, producing splendid sound across a wide range of music genres. Douwei is a man of authenticity, making music for a life and not a living. Here, I’ll give a personal categorization to his music from the past 15 years.

  • 1991年 黑豹 专辑 与黑豹乐队合作 (heavy metal, chinese rock)
  • 1994年 黑梦 专辑 与做梦乐队合作 (post-punk, chinese rock, neo-psychedelia) similar to Bauhaus – Bauhaus, Cure
  • 1995年 艳阳天 专辑 (electronica, ambient, electronic, indie pop, synth)
  • 1998年 山河水 专辑 (electronica, ambient, electronic, indie pop, synth)
  • 1999年 幻听 专辑 与译乐队合作 (alternative rock, post-rock, ambient)
  • 2000年 雨吁 专辑 与译乐队合作 (录制) (alternative rock, post-rock) -similar to Bark Psychosis – Hex
  • 2003年 壹举·两得 专辑 与不一定乐队合作 (jazz rock, jazz fusion, post-rock, ambient, electronic)
  • 2003年 暮良文王 专辑 与暮良文王乐队合作 (folk, ambient, classic chinese instrumental)
  • 2004年 镜花缘记 专辑 与FM3乐队合作 (electronic, ambient, idm)
  • 2004年 八段锦 专辑 (electronica, synthpop, ambient, disco, indie)
  • 2004年 三国·四记 专辑 与不一定乐队合作 (jazz rock, jazz fusion, post-rock improvisation, ambient, electronic) -similar to Tortoise – TNT
  • 2004年 五鹊·六雁 专辑 与不一定乐队合作 (classic chinese instrumental, post-rock, ambient)
  • 2004年 相相生 专辑 与暮良文王乐队合作 (classic chinese instrumental, folk, ambient)
  • 2004年 期过圣诞 专辑 与不一定乐队合作 (jazz rock, jazz fusion, post-rock, improvisational music, live recording)
  • 2005年 山豆几石页 专辑 与暮良文王乐队合作 (folk, chinese classic instrumental, ambient)
  • 2005年 祭然品气国 专辑 与暮良文王乐队合作 (folk, chinese classic instrumental, ambient)
  • 2005年 八和 专辑 与不一定乐队合作 (jazz rock, jazz fusion)
  • 2005年 九生 专辑 与不一定乐队合作 (jazz rock, jazz fusion)
  • 2006年 东游记 专辑(上、下)与宁英杰、巫娜、张荐、文智涌合作 (ambient, chinese classic instrumental, folk, lp, improvisational music, live recording)
  • 2006年 水先后古清风乐 专辑 与不一定乐队合作 (ambient, idm, chinese chinese classic instrumental, improvisational music, live recording)
  • 2006年 后观音 专辑 与FM3乐队合作 (ambient, electonic)
  • 2007年 松阿珠阿吉 专辑 (ambient, folk)
  • 2007年 35651 EP (ambient, folk)
  • 2007年 佐罗在中国 专辑 (ambient, idm, electronic, folk, chinese classic instrumental)
  • 2008年 五音环乐 专辑 与不一定, 不一样乐队合作 (ambient, folk, jazz rock, cultural, post-rock, improvisational music, live recording)

My personal favourite is 雨吁, after that are 山河水, 三国, 幻听, 壹举, 艳阳天, 八和 and etc. My favourite track is 山秀谷 (雨吁)

downloads:

Why must implement Object.Hashcode along with Object.Equals October 26, 2009

Posted by metalickl in Java, Software Insights.
Tags: , , , , , , , , ,
add a comment

I’ve heard of this advice over and over from various sources, and never been able to fully understand why. Until recently (few weeks ago), I was working with various java.util.Collection classes, there were a few connection made relating to this.

Whenever you get an Objects from hash based collections, such as HashMap, with a String or Integer key, you could simply say map.get(“key”) or map.get(new String(“key”)). This is because Strings or Integers are logical equivalent, which is stronger than traditional identity equivalence (==). This allows greater flexibility to retrieve stored content by constructing a key that is identical to the original one (in our case, a new String with the same characters).

But you cannot do this with entity objects. By default implementation, their Object.equals(Object o) simply returns this==o. This means you can never retrieve the stored content with any other object beside the one you’ve used in Map.put(Object key, Object value).

Hash based collections simply uses the hash code to identify a smaller, refined group of stored objects from the larger collection. If you’ve modified Object.equals to allow both identity and logical equivalence, but not Object.hashcode. Then try to search the collection with the logically equivalent key, then obviously the hash based collection, who relies only on Object.hashcode to refine the search will have no idea that this Type is also logically equivalent. In this case, its attempt to refine the collection fails with false precondition.

May be off topic, but then you would think an easy way to implement equals (for both identity and logical equivalence) along with hashcode would be simply compare the string representation of the 2 Objects (including instance members in some way or the other) and just output the hashcode of the string representation of the Object. This saves you the time (mostly brain power) to implement the non-trivial hash functions. This is acceptable, but not performance efficient or easy to read.

This is why it’s always nice to override Object.toString() ;)

Additionally, Object serialization does preserve identity equivalence, IF:

  1. Both a and b are written as and subsequently read from as parts of the same stream. Here’s a quote from ObjectInputStream documentation: “Graphs of objects are restored correctly using a reference sharing mechanism.”
  2. Class of a and b does not override readResolve() that has the potential of changing how references are restored back; neither do classes that hold a and b.

For all other cases, object identity will NOT be preserved.

A fresh start October 18, 2009

Posted by metalickl in Life.
add a comment

Haven’t been blogging at all for the past two years. Time for a fresh start. So much have changed and it’s also a time to change the focus of the blog. I will be posting more interesting things in software engineering and music.

Next iPhone update could leave you with an iBrick September 24, 2007

Posted by metalickl in Gadegets Insights, Hardware Insights, PDA and Mobile Insights.
2 comments

Apple: Next iPhone update could break unlocked phones

Apple issued a statement Monday afternoon warning users of unlocked iPhones that the next software update it ships will probably break their phones.

It’s not clear how many people have unlocked their iPhone to run on networks other than AT&T’s, but there has definitely been some interest among early adopters who want no part of AT&T’s network. Most of those folks were always operating under the assumption that Apple might relock their iPhones with future software updates, but were they expecting Apple to actually disable the phone?

Hacked your iPhone? The next software update from Apple could break your phone.

(Credit: CNET Networks)

“Apple has discovered that many of the unauthorized iPhone unlocking programs available on the Internet cause irreparable damage to the iPhone’s software, which will likely result in the modified iPhone becoming permanently inoperable when a future Apple-supplied iPhone software update is installed,” the company said in a statement issued after the close of the stock market. “Apple strongly discourages users from installing unauthorized unlocking programs on their iPhones. Users who make unauthorized modifications to the software on their iPhone violate their iPhone software license agreement and void their warranty. The permanent inability to use an iPhone due to installing unlocking software is not covered under the iPhone’s warranty.”

This is not going to sit well with the fringe early adopter who, having already suffered through the price cut debacle, now faces the prospect of a dead iPhone. The probable solution, as discussed earlier today by our new friends at iPhone Atlas, involves restoring the iPhone to the factory default settings before installing the new update. The next update will be released later this week to allow iPhone owners to access the new Wi-Fi Music Store introduced earlier this month.

That assumes, I guess, that the iPhone hackers will probably find some way around the new update next week, and that’s probably not that much of a stretch. But it seems Apple is hell-bent on making sure too many people don’t make unauthorized modifications to its iBaby, which in some ways, makes sense to me. This is a brand new product, and even Apple may not totally be aware of the problems that could arise from willy-nilly hacking.

So, be forewarned: if you hacked your iPhone, you might want to hold off on installing this week’s update unless you’re willing to go back to using AT&T’s network.

Update: The Unofficial Apple Weblog thinks that doing a factory restore might not be enough to reverse the unlocking process. They’ve posted a detailed, step-by-step process for “re-locking” your iPhone that might make you wince unless you’re handy with code. Check it out here, but TUAW warns this is still in the early testing stages.

from cnet news: http://www.news.com/8301-13579_3-9783713-37.html

Microsoft offers downgrade from Vista to XP September 22, 2007

Posted by metalickl in Software Insights, Software Insights@Windows Vista.
add a comment

It’s no shock that Windows Vista isn’t, shall we say, universally loved, and it’s also unsurprising that a plethora of businesses have voiced their preference to keep on runnin’ their operations on Windows XP. Presumably in response, Microsoft is “quietly allowing PC makers to offer a downgrade option to buyers that get machines with the new operating system but want to switch to Windows XP,” but the program only applies to Vista Business and Ultimate editions. The likes of Fujitsu, HP, Lenovo and Dell all have processes in place to ensure that customers have the ability to downgrade if they so choose, and while some firms are still selling their PCs with XP pre-installed, debates are already swirling around how long that tactic can remain in place.

Microsoft presents source code to China August 9, 2007

Posted by metalickl in IT Industries.
add a comment

From ChinaTechNews.com:

Microsoft (MSFT) has announced further plans to open Vista source code in China.

Microsoft has reportedly signed a new government security program source code agreement with China Information Technology Security Certification Center, allowing CNITSEC and other approved institutions to look over the source code and relevant technical data of Microsoft’s products, including Windows Vista, Windows XP, Office, Windows CE and etcetera, so as to improve their evaluation on the security of Microsoft products. The agreement is an important part of the MOU signed between National Development and Reform Commission and Microsoft in April 2006.

Microsoft’s Government Security Program helps government departments and international organizations evaluate the security of Microsoft products. CNITSEC previously signed an agreement with Microsoft on security source code in February 2003 and was authorized to check over the company’s major source code and technical data.

Microsoft’s move should bring good results in the promotion of information and enhancement of mutual trust between China and the United States

 ——

From CCTV.cn

本报北京8月7日电(记者杨谷)微软操作系统的安全性一直受到怀疑。日前,微软公司和我有关机构签约,将新款操作系统视窗Vista等软件的源代码提供给我国查看。    根据微软与中国信息安全产品测评认证中心签署的新一期政府安全计划源代码协议,中国信息安全产品测评认证中心和相关被授权机构可以查

看包括视窗Vista、视窗XP、Office2003、视窗CE等软件的源代码及相关技术信息,从而提高对微软产品的安全分析和测评能力。上一期的政府安全计划源代码协议签署于2003年,随着微软产品的不断更新换代,双方决定签署新一期的政府安全计划源代码协议。

    微软的各种软件在我国拥有广大的用户,不少关键部门采用了微软产品作为信息系统的核心,因此其安全性备受关注。中国信息安全产品测评认证中心主任王海生表示,今后将加深对微软产品安全性的了解和研究分析,不断提高有效控制安全风险的能力,履行“信息海关”的职责。

——————————

E-Insight, 2007

Norwegian hacker crack iPhone just one week after its release July 6, 2007

Posted by metalickl in Gadegets Insights, IT Industries, PDA and Mobile Insights, Software Insights.
add a comment

According to a post on his blog, a well-known Norwegian hacker has figured out a way to bypass restrictions on the iPhone that forces people to activate on the AT&T network. Now the iPhone might be worth buying.Digital Journal — Jon Lech Johansen, a 23-year-old famous for his hacking of consumer electronics, says he has cracked the iPhone. In a post on his blog on July 3 (titled “iPhone Independence Day”), Johansen said: “I’ve found a way to activate a brand new unactivated iPhone without giving any of your money or personal information to AT&T NSA. The iPhone does not have phone capability, but the iPod and WiFi work. Stay tuned!”

Johansen’s blog, titled “So Sue Me” provides source code and software for hackers to activate an iPhone for iPod+WiFi use.

Hackers and coders have been working around the clock to crack the iPhone’s security restrictions since its launch a week ago.Apple is in a long-term contract with AT&T, meaning anyone who wants an iPhone must activate it through the wireless carrier.

Mark Siegel, a spokesman for AT&T said it was “necessary” to activate the iPhone on his company’s network to “ensure optimum performance.”

Despite what AT&T’s spin doctors have said, anyone in the tech world knows the wireless provider has what can only be described as a horribly slow Edge network, and many Apple fans want to use the phone without activating on AT&T.

The hack is important for an iPhone owner who wants to travel abroad and use the Internet or the phone’s music without having to pay AT&T to activate the phone.

As hackers continue to dig through code, cracks will also (likely) eventually lead to a way for the iPhone to work on another network. The phone comes locked, and a crack is (of course) against AT&T and Apple’s contract.

No doubt, few crackers actually care about that.

Johansen is practically a god in the underground tech world, most well-known as “DVD Jon” for reversing the code on DVDs that protect them from being pirated.

On his blog, Johansen warns the “application will not do anything unless you understand the magic numbers as well as add the hosts entry,” and you will need software installed on your computer. 

by Christopher Hogg

——————————

E-Insight, 2007

Follow

Get every new post delivered to your Inbox.