iPhone optimization -- timing your code

Direct C calls are the best in the iPhone the below test doesn't account for the time to release the date object as well but it clearly shows which is the better approach.

CFAbsoluteTime profile_start = CFAbsoluteTimeGetCurrent();

for(int i = 0; i < 100000; i++)
  CFAbsoluteTimeGetCurrent();
NSLog(@"direct C call: %0.5f", CFAbsoluteTimeGetCurrent() -　profile_start);

profile_start = CFAbsoluteTimeGetCurrent();
for(int i = 0; i < 100000; i++)
　　[NSDate date];

NSLog(@"NSDate call: %0.5f", CFAbsoluteTimeGetCurrent() - profile_start);

The output is;

direct C call: 0.01097
NSDate call: 0.05005

Pointer sizes

On 32 bit systems;
- pointers are 32bits or 4 bytes
- the memory is limited to 4GB

On 64 bit systems
- pointers are 64bits or 8bytes

Special notes;
- Microsoft likes to make a mess... for Microsoft compilers pointers can vary in size when multiple inheritance is involved. (http://blogs.msdn.com/b/oldnewthing/archive/2004/02/09/70002.aspx)
- some far pointers also include a virtual page index in the upper bits, for a 32 bit machine you might end up with a 48 bit far pointer.

Breath First Search

Breath first search

Algorithm;
1) place the header node into the open node queue (FIFO)
2) get the next item from the queue
3) check for a match of the search
4) push all child nodes that havent been visited into the queue in order
5) repeat from 2

Complexity:
The numbers are odd.. need to find out why..

class Node
{
public:
  string title;
  list children;

  Node(string _title);
  virtual ~Node();

  void addChild(Node* kid);
  Node& operator<<(Node& kid);
};

typedef list NodeList;
typedef set NodeTree;

Node* breath_first_search(Node* node, string target)
{
  NodeList open;
  NodeTree visited;

  open.push_back(node);

  NodeList::iterator nit;
  while(open.size() > 0)
    {
      node = open.front();
      open.pop_front();
      cout << node->title << " ";
      
      if(node->title == target)
        return node;
      
      for(nit = node->children.begin();nit != node->children.end();nit++)
        {
          Node* child = *nit;
          if(visited.find(child) == visited.end())
            {
              visited.insert(child);
              open.push_back(child);
            }
        }
    }
  return NULL;
}

Depth first search

Depth first search

Algorithm;
1) place the header node into the open node stack (LIFO)
2) get the next item from the stack
3) check for a match of the search
4) push all child nodes that havent been visited into the stack in reverse order
5) repeat from 2

Complexity:
The numbers are odd.. need to find out why..

class Node
{
public:
  string title;
  list children;

  Node(string _title);
  virtual ~Node();

  void addChild(Node* kid);
  Node& operator<<(Node& kid);
};

Node* depth_first_search(Node* node, string target)
{
  NodeList open;
  NodeTree visited;

  open.push_back(node);

  NodeList::reverse_iterator nit;
  while(open.size() > 0)
    {
      node = open.front();
      open.pop_front();
      cout << node->title << " ";

      if(node->title == target)
        return node;

      for(nit = node->children.rbegin();nit != node->children.rend();nit++)
        {
          Node* child = *nit;
          if(visited.find(child) == visited.end())
            {
              visited.insert(child);
              open.push_front(child);
            }
        }
    }
   return NULL;
}