Category Archives: Algorithm

Robocode New Beta Release

Robocode Logo

Robocode Logo

 

Robocode has released a beta version for 1.7.3.0, I am happy to contribute 1 feature and 1 bug fix in this release. Please download, test it and tell us any bugs you found

 

 

 

Reference:

Robocode in SourceForge

iPhone App Performance Optimization

iphone performance

iPhone Performance Benchmark

Working in a power limited environment like mobile, and especially, iPhone here, we soon have to face with performance problem in many different kinds. Different than the web model where web front end (javascript) do some (usually not much) processing – also browsers support you a lot, iPhone native application usually has to do quite a lot of processing.

Image Source

For iPhone native app, you cannot add any hardware to help you to have better performance. The only way you can try to deal is to deal with the software code itself. I will list some few problems and solutions that I figure out these days when I really focus on optimization. The list is applicable somehow to other mobile areas like Android or limited environment like embedded device

1/ Benchmark

It is a really traditional advice, but you always have to remember to benchmark your code, even by using simple tools like NSLog or Instrument tool. You should only care about places that is slow in terms of your test rather than trying guess and error possible places.

2/ Test on iPhone device

This is another traditional advice but people usually forget. You have to test on the real iPhone device. Let me give you an example: on my iPhone simulator, a method runs within 1 second, but in my iPhone device, it takes 8 seconds, a huge difference.

So, when you test your app on the iPhone device, don’t just test for UI, memory or features that the simulator doesn’t have. Remember testing the performance as well.

3/ Multithreading and the main thread

Some people may come to you and tell you that iPhone device just has 1 core and you never need to care about multithreading. It is just WRONG.  You still need to do a lot of multithreading to reach a better level of performance.

The main thread will do the user touch event handler and view rendering. Then, if you use the main thread for some calculation that takes a lot of time then your UI just become frozen or not smooth when you scroll.

For UI like UITableView where users scroll between many cells, the runtime will run a loop over visible cells and set the contents. Because this process runs in a row not concurrently, and it will not allow you to view or scroll the UITableView until it returns all cells, you can possibly let some of the cell content run on another thread. (more about performance on UITableViewCell part).

The other reasons for using thread are well-known, heavy IO and network processing, all of them block processing and you need thread so that your main thread is not block. This will help to make users feel your app run with higher performance

But, be CAREFUL, Multithreading comes with its own disadvantages. For rendering the view, you should do it on the main thread or somtimes, your app will just crash randomly. Another traditional reason is that the CPU has to switch too much between threads and it takes more time than usual to finish a task

4/ Use Memory wisely

Some questions on stackoverflow that I sometimes see shows a scare feeling about memory. It is right that iPhone has limited memory but it doesn’t necessarily mean that you should use it as least as you can. Memory and Performance is always a trade-off problem, you must use it smartly

The right mind you need to keep is using that limited memory smartly. We all know the priority of speed is Memory > File and Local IO > Network, the fastest access is always using memory cache for the data. There are some problems for memory caching in iPhone:

    – You have to respond to 1 method in every UIViewController:  (void)didReceiveMemoryWarning. In this method, you have to smartly release some memory cache of data to reduce your memory usage.- Know what/when to cache something in memory. There are lots of Caching algorithms outside from simplest ones like: Random Replacement, Least Recently Used, Most Recently Used. It is also an issue of caching big images or caching lots of small images. It all depends on your app. For my app, my main view contains lots of thumbnail images that need displaying fast and the user can wait for seeing big images. So, we cache a lot of images (60-100) for just 2 MB of memory. Knowing how to balance memory usage and good performance will help you a lot

5/ Algorithms and Data Structure

For my case, I didn’t really need to solve big performance issue with Algorithm and Data Structure, but in a limited environment, a small mistake may lead to a big deal and hard to detect. My case was that I need to merge 2 data arrays from the network using some unique characteristics of elements.

The app works really well in the Simulator for about 50-100 for each array (less than 0.5 second) . However, when I tested on the device, the time surprised  me, 8 seconds (16 times slower). It cost me 1 hour to detect that I use 2 for loops through 2 arrays which means O(n2), and then, I changed it to a dictionary which reduced the algorithm to O(n) and took me back to 1 second. Phew! Finally, performance is up now

What I learnt here is that even we don’t ever need to deal with Massive Data, we still need to be careful about some algorithm and data structure. 50 elements are nothing in a desktop or server scale but can cause a huge issue on limited environments in iPhone. Another lesson is a remind for me that I should always test on the real device to get the real performance

6/ Reuse UITableViewCell to improve Scrolling Performance

This part is quite unique for iPhone but may be good for other people to learn. In iPhone, we have a concept of UITableView for displaying a list and a table can contain a lot of cell.

The problem is that rendering the Cell (or generally the UIView), takes lots of time and can cause the app to look like stuck when it is scrolling. Usually, if you use the default UITableViewController template, the template already gives you the code for reusing the UITableViewCell.

The only problem is when you create a custom UITableViewCell using some usual tutorials like this and this (especially using Interface Builder), they forget to tell you that setting a CellIdentifer in the UITableView is not enough to reuse a cell. What you need to do is to set it in InterfaceBuilder or write a method to return it. I know that many people will forget it and think that they still reuse the cell, but they don’t. I suffer the same problem until I did benchmark and found the problem recently.

Here are 2 good techniques:

Copied from Stackoverflow, this question:

1st way: Just implement a method with the appropriate method signature:

- (NSString *) reuseIdentifier {
  return @"myIdentifier";
}

2nd way:

How to Reuse a Cell in Interface Builder

Cell Reuse in IB

References:

1/ Web Caching, wikipedia

2/ Web Caching, Stanley Luong’s course material

3/ Stackoverflow – reuseable Cell

4/ Stackoverflow – custom UITableViewCell

RoboCode Team Battle (Week 4)

Hi, everybody, the robocode competition goes up to another level, promising more fun and more jobs for you guys. We just released a new rule this morning requiring people to compete in team, 2-2 battle. The era of 1-1 battle ended. This morning is just a practice for a new game. You do not have time to improve your robot a lot, that’s ok now. You just need to have a better communication with your ally.

Now, we just take a look at battles between 2-2. There would only have 4 teams this morning but creating a lot of fun and entertain for people. Poor you guys, the people not joining this morning

The first match:

The Red and the Blue guy on the same team while the White and Black on the other team. The match was quite in the first team when the Black guy use the still strategy, which was good for some robot cases that can not shoot the still robot

The second match:

The 2 yellow guys compete with Gray and Blue guy. The 2 yellows shoot quite correctly but the strategy of the other team is against the Yellow team when they move in line but change direction really fast.

The third match:

We found the anti-Indian guy. Welcome to Yellow guys, you guys did a really well job when running in a spin strategy and the Indian strategy almost dies.

Wait for tomorrow, when we will have a real team battle. Never have the case that we will shoot each other any more. And AWARDS, will officially be given for the first 2 teams tomorrow.

RoboCode Report Week 2

And now, we are already on the week 2. Different than week 1 when I am too busy to write some brief report. I will write some brief report, feedback and evaluation about the second competition.

First, come to the battle between Police and Indian. We can see that Police does not have a big improvement over the last week, while Indian goes into the next level by getting the ideas of running around the opponents from his own opponents (ideas started by Police). We also wait for some peole to kill that suck Indian. Everybody really wants to kill the Indian

Then, we come to the next match between Tester and Rammer. Rammer tried to implements a combining strategy between Rammer, Indian and Spin Bot. But, to be honest, it was an example for what people say : “good idea, bad implementation”. Rammer tried to change the algorithm at the bad times and the RunAway strategy was not good enough. Waiting for the next version when Ramming and Indian shake their hands:D. We also welcome the new comer, a handsome guy, Phan Vo. Hope that we will see a better implementation in the next version

Yeah, now, we see how good Alosa (a loser) is and if it is a real alosa. With a quick implementation in the Web Dev class (Buu will get disappointed for that news), a new version of SweetPo has come into the world. And welcome Huy, another new comer this week. Inherits from the Indian, Huy produced a better implementation. That’s so good and fit exactly what we expect when publishing our source code. I can see a good future for Huy in later versions.

RoboCode Game competition

Hi, I am really happy and excited that we, RMIT students (RMITC), held a good competition. It was just a beginning for a series of RoboCode , game competition as said in previous post. No more talking, I will show you a demo from our students first.

That’s really cool and so simple, and we will have many more AI techniques and Software development there. We will try to add some more intelligence, game strategies in those robots to make it really fun (I already had some ideas in my head). We also have several activities around like tutorials (Instruction 1 and Instruction 2), code review (I did code review for my friends, Khang Nguyen and Phu Hoang) and open some of our source codes (Khang Nguyen, Phu Hoang, Tuan Anh, and Khang Vo). You do not need to be an expert programmer to start programming with RoboCode, the only need is your PASSION. Feel fun, just start. Play and learn. You will become an expert soon

Two more video examples

So, now, how can you join? If you are an RMIT student, it should be extremely easy, just come in. If you are not and you want to join, please contact me: vodkhang@gmail.com so that I can arrange for you to join. Or just wait, I and Youth House also try to operate some robocode competition events.

Online Programming and Software Development Competitions

In my university, it was hard to find chances to go for programming and software competitions (like ACM and Imagine Cup), part of the problem is my fault as well. So, I usually find and join online competitions. Anyway, it is not the main ideas of this post. I want to introduce programming competitions that other people can find fun.

For me, competitions are chances to be fun, to boost skills and to communicate with other people. Fun may be the most important thing, because if it is not fun, interesting and challenging, there is no reason to do it.

1. TopCoder : a lot of kinds of competitions here. This is my favourite one.

A short competition lasts about 1 hour to compete with other people in a 3-problem test with easy, normal and difficult level. You can also do code review, challenge others’ solutions by your own test cases. I love this idea because now, your solution is both validated as well as verified by other people.

It is fun and realistic for software developer. You can even earn money. The only problem is that time to compete is really short, about 2 or 3 days and require in-depth knowledge about J2EE and .NET. I did not have any time to try out with this competition

This is a NP-complete problem competition. You can only find the way to make it better, find the most optimal solution. There are many kinds of problems here: range from encryption, game strategy and image analysis. I love game strategy most. The drawback is you have to spend a lot of time but I think that’s worth and give you a lot of fun

Bug Race will be good for tester, joining, finding bugs. Studio is good for designers. That’s all I know because I never tried this


2. Sphere Online Judge (SPOJ): Pure-algorithm competitions

I think this site is good for beginner and for people who wants to boost algorithms skills and knowledge.  If you are an algorithm lover, this site will be fun; otherwise, it seems quite boring when discussion and sharing ideas are quite limited. People compete with each other to try to get a little bit faster in time to be in the top. That is the disadvantage of this site, people spend too much time for a little performance improve, which is usually not a good practice for a software developer to do so.


 

An algorithm competition, challenging. I tried only once in last year and then this year, I think that I am still not good enough for that. It is a 3-people team competition by solving really tough algorithm problems in 5 hours. If you win, you can go to compete onsite with a wide range of topics: Information Theory, AI, Game Theory, Networking…

4. RoboCode (I think in www.diendantinhoc.org somebody is also interested in)
I am currently doing research and trying with this one for the purpose of RMITC club. RMIT students will try to learn by doing in this challenge. I hope we can learn in many different technologies: Event-Driven, Multi-threading, Agent-Oriented, Game Strategy, Software Design… See the demo below.

For me, that game looks like another agent game that RMIT Melbourne teaches for the course Agent-Oriented Programming and Design

Software Engineering and Algorithms

Algorithms and Data Structure against Software Engineering

Firstly, I want to talk a little bit about algorithms, data structure against software engineering.  Joel’s Article pointed out an excellent point that algorithms, data structure, functional programming is really important to learn, to challenge your mentality. And he is also right that current CS (and maybe IT, SE) degree is not hard enough, simply because if you designed a stupid software, it still WORKS, students will at least get  90+ points in your assignment. I see many not excellent students get 3.8 – 4.0 without any problems, because as Joel already stated, the problem in Software Engineering is when you have to extend, to make the software scalable, not when you create it. He’s all right about that. But he may make people misunderstand.

Algorithms is not the most important skill

For me, algorithm (if we consider it as a specific method to solve a specific problem rather than defined in wikipedia) is important, but it is no longer the most important skill and knowledge software engineer must have. Software engineers, nowadays, should expert about SOLID principles, and write reusable and maintainable code. Software engineers know how to design, architect and integrate between different system to write and maintain a scalable system. Software engineers can work with usability, working directly with client, understand and see the business and users’ world. These things require practice, thinking, learning from failure not just memorize them.  There are now many different jobs that do not require software engineers to become expert in algorithms, and also many great jobs requiring you to become algorithm expert. You may say that they are different jobs (like understand user’s business would be business analysis)) rather than software developers, you are wrong. Software developers now have to understand users’ mind, in general and specific domain to write usable features (read the Usability part in understand and see the business and users’ world for more details).

Algorithms != IT

Another misunderstanding about learning algorithms is that it will give you great mind in thinking in IT. It is right but not that much. In many cases, we work directly with a specific problem, like searching, sorting and computer vision. But that is a specific problem, people tried to solve it under a specific set of constraints. But software architect see the big picture, when to integrate, what to integrate and how to integrate. Both kinds of thinking are really difficult, requires creativity and experiences but hard to go for both. If people go too much into specific problem, it takes time to become an expert in another area. So, if people love one and want to become an expert in one, go for it.

But I like Algorithms

Personally, I do like algorithms so I usually do some algorithms competition in my free time on topcoder. Currently, I am working on this problem (another link if you can not access topcoder), if you want to join, just come. More people, more fun. I will write another entry to introduce about online IT competitions.