Strict Standards: Declaration of Walker_Page::start_lvl() should be compatible with Walker::start_lvl(&$output) in /home/public/blog/wp-includes/classes.php on line 576

Strict Standards: Declaration of Walker_Page::end_lvl() should be compatible with Walker::end_lvl(&$output) in /home/public/blog/wp-includes/classes.php on line 576

Strict Standards: Declaration of Walker_Page::start_el() should be compatible with Walker::start_el(&$output) in /home/public/blog/wp-includes/classes.php on line 576

Strict Standards: Declaration of Walker_Page::end_el() should be compatible with Walker::end_el(&$output) in /home/public/blog/wp-includes/classes.php on line 576

Strict Standards: Declaration of Walker_PageDropdown::start_el() should be compatible with Walker::start_el(&$output) in /home/public/blog/wp-includes/classes.php on line 593

Strict Standards: Declaration of Walker_Category::start_lvl() should be compatible with Walker::start_lvl(&$output) in /home/public/blog/wp-includes/classes.php on line 687

Strict Standards: Declaration of Walker_Category::end_lvl() should be compatible with Walker::end_lvl(&$output) in /home/public/blog/wp-includes/classes.php on line 687

Strict Standards: Declaration of Walker_Category::start_el() should be compatible with Walker::start_el(&$output) in /home/public/blog/wp-includes/classes.php on line 687

Strict Standards: Declaration of Walker_Category::end_el() should be compatible with Walker::end_el(&$output) in /home/public/blog/wp-includes/classes.php on line 687

Strict Standards: Declaration of Walker_CategoryDropdown::start_el() should be compatible with Walker::start_el(&$output) in /home/public/blog/wp-includes/classes.php on line 710

Strict Standards: Redefining already defined constructor for class wpdb in /home/public/blog/wp-includes/wp-db.php on line 58

Strict Standards: Redefining already defined constructor for class WP_Object_Cache in /home/public/blog/wp-includes/cache.php on line 405

Strict Standards: Non-static method K2::init() should not be called statically in /home/public/blog/wp-content/themes/k2/functions.php on line 34

Strict Standards: Non-static method K2::register_scripts() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/k2.php on line 51

Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method K2Options::init() should not be called statically in /home/public/blog/wp-includes/plugin.php on line 311

Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method K2Header::init() should not be called statically in /home/public/blog/wp-includes/plugin.php on line 311

Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method K2::filter_post_comments() should not be called statically in /home/public/blog/wp-includes/plugin.php on line 163

Strict Standards: array_filter() expects parameter 2 to be a valid callback, non-static method K2::strip_trackback() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/k2.php on line 483
Com-Pugh-ter Science at Lightspeed Blog
Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method K2Header::output_header_css() should not be called statically in /home/public/blog/wp-includes/plugin.php on line 311

Strict Standards: Non-static method K2Header::random_picture() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/header.php on line 50

Strict Standards: Non-static method K2Header::get_header_images() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/header.php on line 35

Strict Standards: Non-static method K2::files_scan() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/header.php on line 24

Strict Standards: Non-static method K2::_files_scan() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/k2.php on line 349

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

Com-Pugh-ter Science

Disclaimer: non-Computer Scientists may want to avoid reading this; it contains opinions of a geek-oriented nature, and pedantic discussion of data structures. You have been warned.

This Tuesday I return to college from a 2 week break. Things had been pretty much non-stop since I got back in January (hence the lack of updates) and since I don’t expect it to be any less frantic from when I’m back (what with me having 5 weeks to code a Real-Time Strategy Game), I decided I’d try to get as many of my assignments done over the break as possible. Despite making that commitment, I managed to spend the first 2 days of it furiously coding in Java, despite the fact that I’m not even using Java in any classes this semester.

I had read about Skip Lists a while ago, and thought the break was a perfect time to implement one. Skip Lists maintain several sorted lists of data; the lowest level has a link to every item, like a normal Linked List, and each higher layer has progressively fewer, allowing you to “skip” a number of elements in a traversal. If you’ve passed the object you’re looking for, you go back one link and drop down to a finer-grained list (The original paper on the subject explains things much more clearly than I can). Because of the need to maintain several lists, Skip Lists use more memory to provide faster access; but as any NASCAR driver or amphetamine junkie will tell you, it’s all about the speed.

I wanted to make sure my code was neat, so I downloaded and ran both Checkstyle and FindBugs on it (FindBugs is actually developed by the same guy who invented Skip Lists, Bill Pugh). Sure enough, FindBugs found several situations where crashes could potentially occur, such as not checking if method arguments were null. It also found a few glaring errors, which would have taken much humming, hawing, pondering and noggin-scratching to fix. In short, it saved me a LOT of time, and that was just in writing one class. I’ll certainly be coming back to that plugin…

While using Checkstyle definitely improved the quality of my code, it certainly wasn’t as pleasant an experience. Straight from the start it gave me dozens of misleading warnings, because it wasn’t set up to work with generics. it was asking me to insert a space before and after every occurrence of ‘<’ and ‘>’, which is fine if they’re being used as arithmetic less-than and greater-than; not so helpful when they’re specifying a generic parameter. I came across this bug filed in the Checkstyle bug tracker, which contains fixes.

So, where’s the finished product, you ask? Right here. It implements the Collection interface, so it can be used in place of any other Collection. I’m pretty proud of it; it’s clearly written and well documented. It’s also probably the only code I’ve ever written that’s immediately useful to someone else :P

(To anyone who waded through this post without knowing what I was talking about: first, why? and second, here’s something a little more entertaining)


Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method K2::filter_comments_array() should not be called statically in /home/public/blog/wp-includes/plugin.php on line 163

Strict Standards: array_filter() expects parameter 2 to be a valid callback, non-static method K2::strip_trackback() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/k2.php on line 494

Strict Standards: array_filter() expects parameter 2 to be a valid callback, non-static method K2::strip_comment() should not be called statically in /home/public/blog/wp-content/themes/k2/app/classes/k2.php on line 495

1 Response to “Com-Pugh-ter Science”


  1. 1 Radu Grigore

    Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 932

    Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/public/blog/wp-includes/kses.php on line 933

    Random comments:

    1. randomLevel() returns an int in the interval [1.. MAX_LEVEL], but the comment says “[0 - MAX_LEVEL}” (note the curly bracket too)

    2. Since skip-lists are essentially sorted sets you should probably implement SortedSet.

    3. I believe (but didn’t check) most JRE collections have custom implementations when something can be done faster. For example addAl(Collection) is (randomized) O(n lg n) the way you do it, but it can be done in O(n) if the collection is actually a sorted set (which you can test).

    4. Even if the interface has contains(Object) it’s probably nicer if you overload with contains(E), so that clients who say “SkipList s=…; s.contains(e);” don’t go thru the cast check.

    5. DISTRIUBUTION and MAX_LEVEL could be set by the user.

    6. Does the generic toArray work (without warnings)? I thought the only way to do it is to use the magic java.lang.reflect.Array.newInstance (directly or indirectly).

    7. You might want to look at the implementation in the last section here: http://infoarena.ro/skiplists

    8. It would be nice to give some numbers on how it compares to TreeSet time/space-wise.

    9. Since you spent time to write it nicely, it would be nice if people would use it. You should consider sending it as a patch to a library like Apache Commons Collections (http://commons.apache.org/collections/). (I use google collections but they don’t say how to send patches, at least i didn’t find how.)

Leave a Reply