[	Tags	|	algorithms, java	]
[	Nuna humoro	|	relaxed	]
[	Nuna muziko	|	Comalies (Lacuna Coil)	]

deltas := { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 }.
sum := the sum of all digits in the input.
for every other digit d in the input:
sum := sum + deltas[d].

check := 10 - (sum mod 10).

So, let's say you need a Java program to generate a large number of "valid" credit card numbers quickly. The credit card numbers need to be passed into another function as 16-position byte arrays filled with base-10 ASCII digits.

By "valid" numbers, I mean that they're of appropriate length, format, BIN, and meet the Luhn mod-10 check. They may or may not map to an actual credit card number.

This would be useful if one were, hypothetically, brute-force colliding an SHA-1 hash on a Saturday night to prove a point. But I digress.

How best to do it?

Using the current semi-final algorithm, my little iBook can generate a valid number per 27ns — a sustained throughput rate of 565MB/sec.

Anyone have any additional suggestions?

Splash screens are a standard part of any modern graphical user interface (GUI) application.

Their primary purpose is to let the user know that the application is starting up. An application that displays a polished and professional-looking splash screen can occupy the user's attention and gain the user's confidence that the application is starting.

array = [1, 2, 3, 4, 5]
funcs = [(lambda y: x * y) for x in array]

[foo(2) for foo in funcs]

[10, 10, 10, 10, 10]

funcs = [eval("lambda y : %s * y" % str(x)) for x in array]

[x(2) for x in [(lambda y: x * y) for x in [1,2,3,4,5]]]

[	Tags	|	java, sim, swing	]
[	Nuna humoro	|	amused	]
[	Nuna muziko	|	Jolene (Cake)	]

Here's the full example sources — SIM and Java — for the AddressBook example.

This does not include the SIM sources. You won't be able to build this. But it makes for interesting reading.

The end result? Click the button, a person is added to the list, the table updates instantly, etc. It just works.

[	Tags	|	java, sim, swing	]
[	Nuna humoro	|	amused	]
[	Nuna muziko	|	Honey (Moby)	]

Here's a slightly more interesting SIM example. This one presents a traditional master-detail interface for a simple address book.

New features:

• Splitters, which provide a draggable divider between two components.
• Tables, which are lists of items with multiple columns.
• Bindings between UI components themselves, instead of direct to the controller.

<?xml version="1.0"?>
<s:sim-ui xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
          xmlns:s="http://www.cliff.biffle.org/sim/ui.xsd"
          xsi:schemaLocation="http://www.cliff.biffle.org/sim/ui.xsd ./sim.xsd">

    <!-- A vertical splitter presents two components, one above the other. -->
    <s:splitter axis="vertical" id="addressPanel">

        <!-- The table gets its data from the owner's 'people' property,
             and provides a virtual bean called 'person' for each row to bind to. -->
        <s:table id="peopleList" var="person"
                 value="#{.people}">
            <s:tableColumn name="Name" value="#{person.name}"/>
            <s:tableColumn name="Phone" value="#{person.phone}"/>
        </s:table>

        <s:grid columns="2">
            <s:col autosize="false"/>
            <s:col autosize="true"/>

            <!-- The text fields bind to properties of the table's selectedObject object,
                 causing them to update as the selection changes. -->
            <s:label for="name" value="Name:" mnemonic="n"/>
            <s:textField id="name" value="#{peopleList.selectedObject.name}"/>
            <s:label for="phone" value="Phone:" mnemonic="p"/>
            <s:textField id="phone" value="#{peopleList.selectedObject.phone}"/>

       </s:grid>
    </s:splitter>
</s:sim-ui>

I'll post a demo JAR once I'm not at work (no external ssh here). For now, some details:

• The table cells and text fields automatically become editable or non-editable, depending on whether their bound property can be changed.
• All the same two-way bound-property mojo from the last example exists here. That is, for editable properties, the table cells affect the text fields, the text fields affect the table cells, and programmatic updates affect both.
• Column sorting in the table will work soon. Swing makes this marginally more difficult than it should be (though, I would argue, not as difficult as Cocoa).

<?xml version="1.0"?>
<s:sim-ui xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xmlns:s="http://www.cliff.biffle.org/sim/ui.xsd"
        xsi:schemaLocation="http://www.cliff.biffle.org/sim/ui.xsd ./sim.xsd">
   <s:grid columns="2">
      <s:col autosize="false"/>
      <s:col autosize="true"/>
      <s:label for="degreesF" value="F:" mnemonic="f"/>
      <s:textField id="degreesF" value="#{fahrenheit}"/>
      <s:spacer/>
      <s:slider min="-40" max="300" value="#{fahrenheit}"/>
      <s:label for="degreesC" value="C:" mnemonic="c"/>
      <s:textField id="degreesC" value="#{celsius}"/>
      <s:spacer/>
      <s:slider min="-40" max="300" value="#{celsius}"/>
   </s:grid>
</s:sim-ui>

[	Tags	|	java	]
[	Nuna humoro	|	aggravated	]
[	Nuna muziko	|	His Truth is Marching On (Mike Doughty)	]

public <E> List<E> listFromSet(Set<E> items) {
  return new ArrayList<E>(items);
}

public <E extends Cloneable> List<E> listFromSet(Set<E> items) {
  List<E> list = new ArrayList<E>();
  for(E item : items) {
    list.add(item.clone());
  }
}

try {
  beginTransaction();
  doSomeWork();
  commit();
} finally {
  endTransaction();
}

@Persistence(READ_ONLY)
public List<Customer> findCustomers(String namePattern) {
  /° whatever */
}

@Persistence(READ_WRITE)
public void deleteCustomer(CustID id) {
  /* make customer go bye-bye */
}

After my most recent Google interview (and pursuant to subsequent discussion with mge), I've been looking into the various definitions of the median.

I've encountered three thus far. I've given them names for the purposes of discussion; these are not formal names by any means.

1. The statistical median is what I learned in stats, and is what is used by social scientists (like psych folks) for reporting the median. To avoid ambiguity, it is best stated graphically: if all the elements in your data are placed on a histogram, the statistical median is the value that divides the graph area exactly in half, were you to draw a vertical line through it.
2. The arithmetic median is apparently taught in some elementary schools. If you have an odd number of data points, sorted in order, the arithmetic median is the middle value. If you have an even number, choose the two middle values and average them.
3. The median element is frequently used in discussions of algorithms in computer science. When working with numbers, it is identical to the arithmetic median. When working with non-number items — say, letters — it is more loosely defined as the middle element, which may be either of the two "middles" if there are an even number of data points (depending on the algorithm).

In the order I've presented them, these are basically approximations. The arithmetic median is a decent approximation of the statistical median: if the data set does not have a number of equal values clustered at the median, they produce the same result. Likewise, the median element is a good approximation of the arithmetic median — and if the operation "average the two middle elements" makes sense for the data, they are equivalent.

Why the disconnect? Why have three methods with the same name? Here's how I see it:

• The median element algorithm is popular in computer science because it's a special case of a more general problem: the k-smallest problem. Frequently, one will wish to find the k-smallest element of some data set — the 1st-smallest is the smallest element, and so on. Finding the median element for data of size n is finding the n/2-smallest element; most methods for finding the median element can be generalized to finding the k-smallest for any value of k. (It's also the only version of "median" that makes sense if one is dealing with something other than numbers, which is quite common in computer science.)
• The statistical median exists as an exact measure of central tendency; the two other popular measures are the mean, or average, and the mode. These are frequently used in statistics. It accurately reflects skewing of the data set toward the median, but only makes sense if your data lies along a continuum — it won't work if discrete math is necessary.

I'm not sure what the purpose of the arithmetic median is, except as a simplified case of the statistical median. Its results will hold in some cases, but be off by ±1 element in others. Clearly, users of the arithmetic median want to take skew into account — otherwise, they'd just compute min(data) + (max(data) - min(data))/2, which will equal the median in a normal (unskewed) distribution.

I'm vaguely annoyed at the communities involved for this disconnect, and at Google for asking for a median algorithm rather than a k-smallest algorithm. In hindsight, they were nudging me toward deriving Rivest's algorithm for computing the median element, which unfortunately won't work for the statistical median. (I derived a distributed, low-O way of approximating the median using a few other measures of central tendency and some measures of skew, which is probably more complex than they were expecting.)

If anyone can come up with a reason for the arithmetic median to exist, I'm interested.

[	Nuna humoro	|	bored	]
[	Nuna muziko	|	Girlfriend for a Day (Radio Free America)	]

1. The method body will execute precisely once.


2. The return value from that execution will be cached, and returned from all future calls.

private Foo theFoo;

public once Foo getFoo() {
  if(theFoo == null) {
    synchronized(this) {
      if(theFoo == null) theFoo = new Foo();
    }
  }
  return theFoo;
}

1. At the level of the VM (and the compiled JIT code), object allocation and object initialization (via the constructor) are separate steps. In the face of reordering (both of code and writes), I'm pretty sure the method could return an uninitialized object instance. (I need to do some disassembly to see if the JIT will really do this.)


2. Moreover, threads are capable of making their own copy of a variable, including instance fields. It's possible for a thread to see its copy of theFoo as null even when another thread has already initialized it. volatile may help there, but last time I tried it, it didn't do anything.


3. The monitorexit op, used to end a synchronized block, does not flush state to memory.


4. Don't even get me started on issues like cache coherency in multiprocessor systems.

I've put up a preliminary page for my superset of Java, tentatively called Kona. It's looking more and more like I'll need to implement my own javac — which is fine, because javac sucks in the warnings department.

If only it were properly open-source, eh?

Currently, the only area in which Kona is incompatible with Java — that is, where source that compiles as Java will not compile as Kona — has to do with implicit conversion to floating-point. Java will implicitly convert an int (signed, 32-bit integer) to a float (signed, 32-bit IEEE-754 floating-point value). This is bad, because while a float has a greater dynamic range than an int, it is of lower precision — 22 bits worth, to be exact. (The rest of the word is reserved for exponent and sign bits.) Thus, any int with more than 22 significant bits may change in value when converted to a float.

Kona will have a warning for this case, just as javac warns about float⇒int conversions.

However, it got me to thinking more about the notion of 'significant bits,' and how a compiler can track this. I'm sure someone else in CS has already done this, but I haven't read their work, so feel free to correct me where I screw this up: