You are viewing sancho_ex

< back | 0 - 10 |  

Active learning of Graph algorithms via Java Applets

November 21st, 2006 (11:39 am)

I am fairly wary of just reading books without applying the techniques described because it just does not stick. However I have been guiltly wading through "Algorithm Design" by Kleinberg & Tardos. To assuage my guilt I sort out interactive demos of the Kruskal algorithm and the Prim algorithm for finding the minimum spanning tree of a connected graph. I then tested my understanding of the algoritms by guessing what the demo would do next.

I used the Java Applet demos at http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/KruskalApp.shtml?demo1. Thanks Kenji Ikeda!

overlap function in Haskell for Retangles

November 20th, 2006 (12:01 pm)

I am continuing with Haskell despite the Scala language vieing for my attention. This is my partial solution to Exercise 14.11 from "Haskell: The Craft of Functional Programming" 2/e. It includes the test data.

-- Exercise 14.11
-- Define a function to test whether two NewShapes overlap
overlap :: NewShape -> NewShape -> Bool
overlap (NewRectangle (Point x y) h w) (NewRectangle (Point x' y') h' w')
  | x + w <= x' = False
  | x >= x' + w' = False
  | y + h <= y' = False
  | y == y' + h' = False
  | otherwise = True
  
r1 = NewRectangle (Point 0 0) 1 1 
r2 = NewRectangle (Point 1 0) 1 1

r3 = NewRectangle (Point 0 1) 1 1
r4 = NewRectangle (Point 0.5 0.6) 1 1

Stepping out with jdb

November 17th, 2006 (11:25 am)

Tried out the Java Command Line Debugger today.

This is how I started it

$ jdb -classpath src/ debugger.Threads


Here's part of my debugger session,

threads
Group system:
  (java.lang.ref.Reference$ReferenceHandler)0x10f Reference Handler cond. waiting
  (java.lang.ref.Finalizer$FinalizerThread)0x10e  Finalizer         cond. waiting
  (java.lang.Thread)0x10d                         Signal Dispatcher running
Group main:
  (java.lang.Thread)0x144                         Thread-0          sleeping
  (java.lang.Thread)0x145                         Thread-1          sleeping
  (java.lang.Thread)0x146                         DestroyJavaVM     running
> thread 0x144
Thread-0[1] list
Current thread isn't suspended.
Thread-0[1] suspend 0x144
Thread-0[1] list
Current method is native
Thread-0[1] step
>
Step completed: "thread=Thread-0", debugger.Counter.run(), line=26 bci=12
26                      }

Thread-0[1] list
22                              Thread.sleep(5);
23                      } catch (InterruptedException e) {
24                              // TODO Auto-generated catch block
25                              e.printStackTrace();
26 =>                   }
27              }
28
29      }
30
31    }
Thread-0[1] step
>
Step completed: "thread=Thread-0", debugger.Counter.run(), line=20 bci=2
20                      i = i + 1;

Thread-0[1] locals
Method arguments:
Local variables:
i = 12107
Thread-0[1] step
>
Step completed: "thread=Thread-0", debugger.Counter.run(), line=22 bci=6
22                              Thread.sleep(5);



I doubt I will ever use this in preference to the Eclipse debugger but it is best to be prepared.

Adding (Point x y) to Shape

November 10th, 2006 (11:43 am)

Here my solutions to exercises 14.9 and 14.10 of "Haskell: The Craft of Functional Programming"/2e.

-- Exercise 14.9
-- The type Shape takes no account of the position or orientation of a shape. After
-- deciding how to represent points, how would you modify the original definition
-- of Shape to contain the centre of each object? you can assume that rectangles
-- lie with their sides parallel to the axes, thus:
-- .

data Point = Point Float Float
  deriving (Show)
  
data NewShape = NewCircle Point Float | NewRectangle Point Float Float | NewTriangle Point Float Float Float
  deriving (Show)

-- Exercise 14.10
-- Calling the new type NewShape, define a function
move :: Float -> Float -> NewShape -> NewShape
-- which moves a shape by the two offsets given.
move dx dy (NewCircle (Point x y) r) = NewCircle (Point (x + dx) (y + dy)) r
move dx dy (NewRectangle (Point x y) h w) = NewRectangle (Point (x + dx) (y + dy)) h w
move dx dy (NewTriangle (Point x y) a b c) = NewTriangle (Point (x + dx) (y + dy)) a b c

Defining equality over an algebraic type with instance

November 2nd, 2006 (11:58 am)

It took a while to sort this out as the example of defining equalilty over Temp in the Haskell book I'm following did not work when typed in literally. I found the solution on the second Google result hit and here it is,

-- Exercise 14.8
-- Define == over Shape so that all circles of negative radius are equated. How
-- would you treat rectangles with negative sides?
--(==) :: Shape -> Shape -> Bool
instance Eq Shape where
  Circle r == Circle r'
    | r < 0 && r' < 0 = True
    | otherwise = r == r'
  Rectangle w h == Rectangle w' h' = normalise w == normalise w' && normalise h == normalise h'
    where
      normalise x = if x < 0 then 0 else x


The key was the instance declaration, shown in a simpler form here,

data Phase = Morning | Afternoon | Evening | Night
instance Eq Phase where
  Morning == Morning = True
  Morning == _ = False


It's interesting that I was on the verge of giving up learning Haskell because I could not be bothered to reread sections of the book in the hope of finding the solution, nor would I post to a mailing list for fear of appearing dumb. In the end the correct Google keywords led to a solution.

Java Tools revisted: jps, jinfo, jmap

November 1st, 2006 (12:53 pm)

Fiddled with some java command line tools today.

jps with arguments produces a list of JVM processes for the current user, or for all user if run as root.

# jps
22492 startup.jar
8317 Bootstrap
18957 jar
1496 jar
26918 Main
14233 Jps


Once the pids are known jmap and jinfo can be used to find out information about the jvm invocation.

# jinfo -flags 8317
Attaching to process ID 8317, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 1.5.0_07-b03
-Xms384m -Xmx384m -agentlib:yjpagent=dir=/var/spool/yjp -Dcom.sun.management.jmxremote=true 


# jmap -histo 8317|less -N 
      1 Object Histogram:
      2
      3 Size    Count   Class description
      4 -------------------------------------------------------
      5 119923712       2033512 char[]
      6 49026336        2042764 java.lang.String
      7 18014904        750621  java.util.HashMap$Entry
      8 15559704        648321  org.apache.commons.collections.SequencedHashMap$Entry
      9 8822144 275692  org.jdom.Attribute
     10 6782784 211962  org.jdom.Element
     11 6358224 16846   java.util.HashMap$Entry[]
     12 5587240 39294   * ConstMethodKlass
     13 5120704 159996  org.jdom.Attribute[]
     14 5087184 211966  org.jdom.ContentList
     15 5087088 211962  org.jdom.AttributeList
     16 4381104 109048  java.lang.String[]
     17 4013864 114027  org.jdom.Content[]
     18 3973432 35440   java.lang.Object[]
     19 3266800 61315   int[]


jmap -perstat is a handy way to see a list of all classloaders in use,

# jmap -permstat 8317
Attaching to process ID 8317, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 1.5.0_07-b03
finding class loader instances ..Unknown oop at 0x605a6b18
Oop's klass is null
Unknown oop at 0x6062ac08
Oop's klass is null
done.
computing per loader stat ..done.
please wait.. computing liveness.............LivenessAnalysis: WARNING: java.lang.NullPointerException during traversal
LivenessAnalysis: WARNING: sun.jvm.hotspot.utilities.AssertionFailure: FIXME: add derived pointer table during traversal
LivenessAnalysis: WARNING: java.lang.NullPointerException during traversal
LivenessAnalysis: WARNING: java.lang.NullPointerException during traversal
LivenessAnalysis: WARNING: java.lang.NullPointerException during traversal
.done.
class_loader    classes bytes   parent_loader   alive?  type

     1457    3383456   null          live    
0x4ca97ad0      1       1520    0x4ccbb0a0      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4ccb70c0      195     519568  0x4ccf1a50      live    org/apache/catalina/loader/WebappClassLoader@0x47764360
0x58bcfe68      28      62808   0x4d66ec58      live    org/apache/jasper/servlet/JasperLoader@0x47c9b730
0x4db84560      1       968     0x4ccbb0a0      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4caa3858      1       1528    0x4ccbb0a0      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4d66b588      1       1512    0x4ccbd1a8      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4caa8140      1       1520    0x4ccbb0a0      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4d45a220      4       9280    0x4ccf1a50      live    org/apache/catalina/loader/WebappClassLoader@0x47764360
...
0x4cac45e0      1       1520      null          dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4db8ea78      1       1520    0x4ccbb0a0      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4ccbcaa0      4       9280    0x4ccf1a50      live    org/apache/catalina/loader/WebappClassLoader@0x47764360
0x4cac4b68      1       1512    0x4ccf1a50      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4cac4d40      1       1520    0x4ccf1a50      dead    sun/reflect/DelegatingClassLoader@0x46f76a98
0x4ccbd238      155     449544  0x4af855b8      live    sun/misc/Launcher$AppClassLoader@0x4707cfa8
0x4caa80e8      1       1528    0x4ccbb0a0      dead    sun/reflect/DelegatingClassLoader@0x46f76a98

total = 182     5055    12494616            N/A         alive=42, dead=140          N/A

HAProxy working out the box

October 23rd, 2006 (11:36 am)

I downloaded haproxy (http://haproxy.1wt.eu/), make'd it, conf'd it and run it on my local box as a reverse proxy to a servlet container. It worked fine. I had it running is about 10 minues.

It is a classic Unix style tool - highly focused on one thing and written in C. In fact most of haproxy is coded in just one C file with 10645 lines. A print out would span ~200 pages of A4. Phew!

Bash Tip: repeat the last word on the current input line

October 19th, 2006 (10:32 am)

Here's neat Bash tip which is useful when renaming a file in a directory when you can't be bothered to cd to the directory. This is the command you want

$ mv /home/sancho/schedule/oct/plan1.txt /home/sancho/schedule/oct/plan2.txt

Make sure histverify is on

$ shopt -s histverify

then type and press enter

$ mv /home/sancho/schedule/oct/plan1.txt !#$

this will load the command below into the Readline edit buffer,

$ mv /home/sancho/work/schedule/plan1.txt /home/sancho/work/schedule/plan1.txt

then just edit it. Alternatively modify the history with "s"

$ mv /home/sancho/work/schedule/plan1.txt !#$:s/plan1/plan2/
$ mv /home/sancho/work/schedule/plan1.txt /home/sancho/work/schedule/plan2.txt

Extremely handy for frightening noobs with.

Stumped by defining == over Shape

October 17th, 2006 (10:30 am)

This has me stumped,

-- Exercise 14.8
-- Define == over Shape so that all circles of negative radius are equated. How
-- would you treat rectangles with negative sides?


I try this
(Circle a) == (Circle b) = if (a>=0) && (b>=0) then (a == b) else if (a<0) && (b<0) then True else False

but get this error
Chapter14.hs:134:55:
    Ambiguous occurrence `=='
    It could refer to either `Chapter14.==', defined at Chapter14.hs:134:11
                          or `GHC.Base.==', imported from Prelude at Implicit import declaration


As a reminder this is the constructor for Circle
data Shape = Circle Float | Rectangle Float Float | Triangle Float Float Float
  deriving (Show)

Haskell: Exercise 14.6

October 13th, 2006 (11:30 am)

Grinding on with "Haskell: The Craft of Functional Programming" 2/e.

-- Exercise 14.6
-- Define a function which decides whether a Shape is regular: a cricle is regular,
-- a square is regular rectangle and being equilateral makes a triangle regular.
isRegular :: Shape -> Bool
isRegular (Circle _) = True
isRegular (Rectangle w h) = w == h
isRegular (Triangle a b c) = (a == b) && (b == c)

< back | 0 - 10 |