Archive for the 'Skip Lists' Category

PHP Skip Lists 2: Implementing Skip Lists in PHP

Published on February 20, 2014 by Bill Sanders in Factory Method, Iterator, Linked List and Skip Lists. 0 Comments Tags: , , , , .

GunMoll250The Perfect Skip List

I ran across the perfect skip list in a presentation by Eileen Kraemer, a computer science professor at the University of Georgia. (You can find several academic papers on the perfect skip list if you do a Web search: key = perfect skip list.) In the most simple terms, the perfect skip list is one where each level has exactly double the nodes as the one above it. In a sense, it is arranged like a binary search. The head node (far left) has a value of minus infinity using the PHP constant with a minus sign (-INF) and the node on the far right has a value of infinity, (INF). (I’m calling the far right node the tail node for the sake of symmetry. You’ll also see it labeled the “sentinel.”) By having the highest and lowest possible values bracketing the search values, it contains the search parameters so that you can enter any values you want in the skip list. Figure 1 shows the perfect skip list without values except for the tail node with a value of infinity.

Figure 1: Perfect Skip List

Figure 1: Perfect Skip List


That looks a lot like the train lines used in the previous post on skip lists, and if it helps to visualize the skip list as train lines to see what’s going on, you can think of them as such. Figure 1 also may remind you of a binary search pattern, and that’s because perfect skip lists and binary searches have a lot in common. All that’s left to do is to program it. First, though, give it a quick play and download the files:
PlayDownload

Programming Skip Lists with the SplDoublyLinkedList class

Most of what you need to know about programming linked lists can be found in the post on Linked Lists on this blog. Using the built-in PHP SplDoublyLinkedList class (PHP 5.3+), I generated five linked lists, naming them level4 to level0, reflecting those in Figure 1. The trick was in figuring out how to best iterate through the lists. Here’s the iteration process I was looking for:

  • Start with level4 and check the first node to the right
  • If less than move down one level; greater than move right
  • Synch list nodes with levels
  • Repeat until match found

Initially, I tried using the next() and prev() methods in the SplDoublyLinkedList class, but it was very difficult to synch all levels with those methods. Then I tried using the offsetGet(n) method, and it worked easily and well for both searching and synching levels.

The Skip List Product and Factory

A Factory Method design pattern serves to create the linked lists and final skip list. Figure 2 shows the class diagram in file format:

Figure 2: File Diagram of Skip List Factory Method pattern

Figure 2: File Diagram of Skip List Factory Method pattern

The Client makes all requests through the factory for linked lists. The lists themselves have been configured as implemented products, and the Client puts them together as a skip list. An alternative design would have been to have a fully loaded SkipList class (an encapsulated skip list) and have the Client pass on search requests with the search methods in the SkipList class instead of the Client. Either way, the Factory Method has ensured loose binding, and so if you’d like to experiment with a separate skip list class, go ahead. (Click below to see how the different objects are implemented.)
Continue reading ‘PHP Skip Lists 2: Implementing Skip Lists in PHP’

PHP Skip Lists 1: The Quickest Route Home

Published on February 4, 2014 by Bill Sanders in Binary Searches, Linked List and Skip Lists. 0 Comments Tags: , , , .

skiptownA few years ago I created a post on Skip Lists (different blog), and several people told me that it clarified the concept of skip lists for them; so I’m reproducing it here for PHP developers. Using the analogy of rail travel in the New York-Hartford-Boston area, I show how the skip list can work in the world apart from programming. Living in Bloomfield, Connecticut, I’m about halfway between Boston and New York City. Lately they’ve been talking about building a high speed rail to Hartford and on to Springfield, Massachusetts. Naturally, when thinking about such a rail system, I like to think that the really fast part of the trip would be between New York City, Hartford, and Boston. Of course they’d need an express to stop off in New Haven and Springfield. Further, lots of other towns, including Bloomfield, would need some kind of local line. Left to my own devices, I would build the following lines:

Bullet

  1. New York
  2. Hartford
  3. Boston

Express

  1. New York
  2. New Haven
  3. Hartford
  4. Springfield
  5. Boston

Local

  1. New York
  2. Stamford
  3. New Haven
  4. Middletown
  5. Hartford
  6. Bloomfield
  7. Springfield
  8. Boston

Given these choices, I know that I can easily get to Bloomfield by taking the Local at Grand Central Terminal in New York City. However, I’d really like to skip stops in Stamford, New Haven and Middletown. If I took the express, I’d have a stop in New Haven and then on to Hartford where I could get on the Local to Bloomfield. That would be faster, but it would not be the fastest route.

To determine the fastest route, assuming that I have to go in the same direction and cannot backtrack, I diagramed the three lines in Figure 1.

Figure 1: Three train lines between NYC and Boston

Figure 1: Three train lines between NYC and Boston

Looking at Figure 1, it is not too difficult to determine the quickest route between NYC and Bloomfield.

The route that skips the most stops is the quickest route.

Trace your finger from NYC to Bloomfield in Figure 1 and you can determine that route. To see if you found it, look at Figure 2 to see the fastest route highlighted in yellow.

Figure 2: The Route that Skips the Most Stops

Figure 2: The Route that Skips the Most Stops


If you traced the route highlighted in yellow in Figure 2; then you understand how skip lists work. In a similar way, the Binary Search discussed here does not start at the beginning and iterate through an entire ordered list. Rather it splits the list determining the quickest way to the search item.

From Train Lines to Linked Lists

To go to the next step, you need to understand Linked Lists which we discussed in a recent post. What I’d like to do is to transform our train lines into a linked list. The first step is to change the different towns on the lines to nodes in a linked list. Figure 3 shows the first step in this transformation:

Figure 3: From Train Stops to Nodes in a Linked List

Figure 3: From Train Stops to Nodes in a Linked List

My hunch is that if I asked you what was the quickest route to find the value “30” you’d know just what to do. However, the diagram still looks like a train dispatcher’s chart, and so we’ll update it a bit to look more like a linked list. Figure 4 shows this new diagram.

Figure 4: Linked list with multiple pointers<

Figure 4: Linked list with multiple pointers<[/caption] Figure 5: Node with multiple pointers Figure 5: Node with multiple pointers

The arrows now have balls on their tails and look like pointers—and we know that pointers hold a reference to the next node. If we have multiple pointers with some of our nodes, we can have a single linked list that includes pointers that skip certain nodes. Figure 5 shows how that might look in the first node:

Keeping in mind that the linked lists are ordered (sorted) our search for the value “30” would look something like this:

  • Starting point would be on the shortest linked list: 30 is > 25 but < 53.
  • Drop to next level down to the second shortest list: 30 is < 43.
  • Drop to next level down to the third shortest list: 30 == 30. Your search is over.

Now we’re ready to deal with coding skip lists in PHP5. We’ll have to work out the algorithms, and in the next post on skip lists we should be able to have a working skip list that we can use with an iterator pattern.