sorting: different languages, different styles

Discussion of programming on Linux, including shell scripting, perl, python, c/c++, mono, java. Whatever tickles your fancy.

sorting: different languages, different styles

Postby lambda » Sat Mar 17, 2007 1:29 am

a friend posted about a simple situation. he had a bunch of java objects, each with an instance variable named "index". he wanted to sort the objects. with java, you can use a "List" collection to store multiple objects. you can then use the Collection.sort(listname) method to sort the list.

however, to do this, you must modify your classes. each item in the list (each of his java objects) must implement the Comparable interface, and have a public method named compareTo(). so, to sort his list the way he wanted to, he had to write

Code: Select all

public class Lump implements Comparable<Lump>
{
    public int index;
   
    public int compareTo(Lump otherLump)
    {
        // do comparison based on what we know about Lumps
        int ourIndex = this.index;
        int theirIndex = otherLump.index;
       
        if (ourIndex < theirIndex)
            return -1;
        else if (ourIndex > theirIndex)
            return 1;
        else
            return 0;
    }
}


compare this with how you would do it in other languages.

python:

Code: Select all

# class
class Lump(object):
  def __init__(self, index=0):
    self.index = index

# sort function
def sortLump(a, b):
  if a.index < b.index:
    return -1
  elif a.index > b.index:
    return 1
  else:
    return 0

# create three lumps, place them in a list and sort them
l1 = Lump(10)
l2 = Lump(5)
l3 = Lump(20)

ls = [ l1, l2, l3 ]
ls.sort(sortLump)


or, say, smalltak:

Code: Select all

# create the class
Object subclass: #Lump
        instanceVariableNames: 'index'
        classVariableNames: ''.

# "getter and setter" methods for the index instance variable
Lump >> index
        "return value of index instance variable."
        ^ index!

Lump >> index: aNumber
        "set index's value."
        index := aNumber

# ----------------------------------------------
# and now, the code to create a list with three elements, and sort it

| l1 l2 l3 arr |

l1 := Lump new index: 10.
l2 := Lump new index: 5.
l3 := Lump new index 20.

arr := Array with: l1 with: l2 with: l3.
arr sort: [ :a :b | (a index) < (b index) ].

why is the code so much smaller for smalltalk? it's because the sort method takes a block of code that compares two lump objects, and returns true if the first object is less than the second object. in java and python, you have to do more work to tell their sort functions how to handle the other cases.

ruby steals a lot of ideas from smalltalk, so its code looks similar:

Code: Select all

class Lump
  attr_accessor :index
 
  def initialize(index)
    @index = index
  end
end

l1 = Lump.new(10)
l2 = Lump.new(5)
l3 = Lump.new(20)

arr = Array.new(l1, l2, l3)
arr.sort { |x, y| x.index <=> y.index }

lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore

Postby fawad » Sun Mar 18, 2007 7:37 am

Not to detract from your point or anything, but the python version could have been a lot smaller if you had used the __cmp__ operator. This takes advantage of the fact that python can compare the primitive types already. All you have to do it set the compare for Lump to use it.

I'm not an expert, but I think the 3 way value for comparison might be for doing hash lookups really quickly.

Code: Select all

# class
class Lump(object):
  def __init__(self, index=0):
    self.index = index
  def __cmp__(self, other):
    return cmp(self.index, other.index)

# create three lumps, place them in a list and sort them
l1 = Lump(10)
l2 = Lump(5)
l3 = Lump(20)

ls = [ l1, l2, l3 ]
ls.sort()
fawad
Site Admin
 
Posts: 918
Joined: Wed Aug 07, 2002 8:00 pm
ICQ: 17672437
Website: http://www.fawad.net
WLM: fawadhalim@hotmail.com
Yahoo Messenger: fawad2048
AOL: fawadhalim
Location: Addison, IL

Postby lambda » Sun Mar 18, 2007 2:03 pm

that's true -- if you have access to the class (you're not sorting someone else's objects), you could add a __cmp__ method, and it would be similar to the above java code.

if you don't have access to the class, you can use http://java.sun.com/javase/6/docs/api/j ... Comparator) in java.
lambda
Major General
 
Posts: 3452
Joined: Tue May 27, 2003 7:04 pm
Website: http://www.hungry.com/~fn/
Location: Lahore

Postby kragen » Sat Mar 31, 2007 9:33 am

If there were no java.util.sort(List, Comparator), which sounds like exactly the same thing you're using in Python, you could still wrap the objects in Comparable wrappers. You could even make a sort(List, Comparator) facade to hide that part from the user.

The main problem is that

Code: Select all

new Comparator() {
    public int compare(Object o1, Object o2) { ... }
}

(is that how you write it? My Java is rusty) is just a lot more noise than Smalltalk's

Code: Select all

[:o1 :o2| ... ]

or even Python's

Code: Select all

def compare(o1, o2):

or if you like

Code: Select all

lambda o1, o2: ...

Perl's (or K's) is the shortest:

Code: Select all

{...}

because the parameters are named only implicitly --- $a and $b for Perl, x and y for K.

Fawad's point is good too --- you could imagine a Comparable.compare implementation that reads

Code: Select all

new Comparator() {
    public int compare(Object o1, Object o2) {
        return (Lump)o1.index.compareTo((Lump)o2.index)
    }
}

but you can't do even that in Java because integers aren't objects!
kragen
Cadet
 
Posts: 8
Joined: Sun Mar 25, 2007 3:56 am
Website: http://pobox.com/~kragen/about


Return to “%s” Programming

Who is online

Users browsing this forum: No registered users and 2 guests

cron