Someone posted "We get paid for work because it is unpleasant .. get used to it" in a thread about the majority of IT workers being unhappy.
These are some of my thoughts on the matter ...
There is no reason why work should be unpleasant, inherently.
Just consider that we were marooned on a desert island. There are things to do -- gather food, build shelter, etc. Are any of these unpleasant? Not necessarily -- pretty similar to camping/fishing/hunting, all of which people do for recreation.
Now, suppose there was some issue about people doing their share. We might keep track of how much time each person puts in in terms of work. We might keep these in "credits" since some people might be doing more dangerous/skilled work.
To make sure that people do their share, we might require a certain number of "credits" for them to eat, or sleep in the shelter, and deduct this from their credits.
In a nutshell, this is our country and economy. Jobs are about doing what society needs done, and the system we have for trying to allocate that work efficiently is the free market capitalist system. People are incentivized to contribute by paying them, and encouraged not to overuse resources by requiring them to pay for them.
However, if everyone was good at figuring out how to contribute, and did their share, and weren't greedy about taking too much, then we wouldn't need any of this at all. The work would still need to be done, and hopefully everyone would be good and efficient about doing what was needed.
But strictly speaking, the work is neither inherently pleasant or unpleasant -- it just needs to be done. It would need to be done regardless of whether someone was paid for it or not -- or we were just mature about doing our share. One could be happy about contributing to the group and survival, without any pay, even if the job was not pleasant.
The current monetary system exists because we live in a large, complex society where the kind of interpersonal incentives that worked within a small group of people (i.e. a family or tribe) don't work in a mass society where no one will notice or care about our contribution, except for someone who now gets the motivation to pay you to do something for them.
Thursday, June 25, 2009
Thursday, June 18, 2009
My Links - improved formatting?
Here's an attempt to improve the appearance of my links:
Google Profile
Programmer's Heaven
Stack Overflow
My Blog
M.Sc Paper
Publications
MacShapa and ESDA
Human Computer Interaction
Google Profile
Programmer's Heaven
Stack Overflow
My Blog
M.Sc Paper
Publications
MacShapa and ESDA
Human Computer Interaction
O(N) for Bunker visiting Problem
Actually, I figured out how to prove my algorithm is O(N) (informally). (see earlier post)
If x is a starting point, then any point y prior to x where each point y .. x contains a surplus will also be a valid starting point. So, the algorithm finds a locally optimal starting point initially, in that it first looks for the first element in a sequence of surpluses.
Now, in the tryLoop sequence, it then attempts to find a way around the loop from this locally optimal starting point. Since it always arrives at the next node with a surplus (else it would return the failed node), then if it arrived at a valid starting point with a surplus then it would be able to complete the circuit, because it is possible to complete the circuit from a valid starting point with no surplus.
So, the starting point cannot be anywhere between the attempted starting point and the point where the algorithm returns a failed node.
Further, by the optimality shown above, skipping nodes that have a deficit will never skip over a valid starting point.
So, the algorithm does not skip over any valid starting points, and either visits every node in the tryloop method, or skipping over deficit nodes. Thus, it will visit at most N + (N - 1) nodes (N to try each node, and N-1 to verify the circuit from the attempted node).
So, the algorithm is worst case O(2N -1) = O(N).
-Larry
http://www.google.com/profiles/larrywatanabe ,
http://stackoverflow.com/users/118860/larry-watanabe ,
http://larrywatanabe.blogspot.com ,
http://portal.acm.org/citation.cfm?id=125337 ,
http://www.programmersheaven.com/user/larrywatanabe/ ,
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html ,
http://portal.acm.org/citation.cfm?id=211243 ,
http://www.interaction-design.org/references/authors/larry_watanabe.html
If x is a starting point, then any point y prior to x where each point y .. x contains a surplus will also be a valid starting point. So, the algorithm finds a locally optimal starting point initially, in that it first looks for the first element in a sequence of surpluses.
Now, in the tryLoop sequence, it then attempts to find a way around the loop from this locally optimal starting point. Since it always arrives at the next node with a surplus (else it would return the failed node), then if it arrived at a valid starting point with a surplus then it would be able to complete the circuit, because it is possible to complete the circuit from a valid starting point with no surplus.
So, the starting point cannot be anywhere between the attempted starting point and the point where the algorithm returns a failed node.
Further, by the optimality shown above, skipping nodes that have a deficit will never skip over a valid starting point.
So, the algorithm does not skip over any valid starting points, and either visits every node in the tryloop method, or skipping over deficit nodes. Thus, it will visit at most N + (N - 1) nodes (N to try each node, and N-1 to verify the circuit from the attempted node).
So, the algorithm is worst case O(2N -1) = O(N).
-Larry
http://www.google.com/profiles/larrywatanabe ,
http://stackoverflow.com/users/118860/larry-watanabe ,
http://larrywatanabe.blogspot.com ,
http://portal.acm.org/citation.cfm?id=125337 ,
http://www.programmersheaven.com/user/larrywatanabe/ ,
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html ,
http://portal.acm.org/citation.cfm?id=211243 ,
http://www.interaction-design.org/references/authors/larry_watanabe.html
Wednesday, June 17, 2009
Fuel Bunker Problem posted on Joel On Software
This looks like a school assignment. But it could be a legitimate question, so here's a solution. The solution appears to be O(N), but I haven't proven that yet, but empirical testing on synthetic data seems to bear that out.
Option Strict On
Option Explicit On
'''
''' Solution to problem posted on Joel on Software:
''' There are n petrol bunks arranged in circle.
''' Each bunk is separated from the rest by a certain distance.
''' You choose some mode of travel which needs 1litre of petrol to cover 1km distance.
''' You can't infinitely draw any amount of petrol from each bunk as each bunk
''' has some limited petrol only. But you know that the sum of litres of petrol
''' in all the bunks is equal to the distance to be covered.
''' ie let P1, P2, ... Pn be n bunks arranged circularly
'''
Module Module1
'''
''' Representation of a bunker. The next bunker
''' is at (m_position + 1) mod N
'''
Class Bunker
'''
''' Amount of fuel at this bunker
'''
'''
Public m_fuel As Integer
Public m_distance As Integer
Public Property fuel() As Integer
Get
Return m_fuel
End Get
Set(ByVal value As Integer)
m_fuel = value
End Set
End Property
Public Property distance() As Integer
Get
Return m_distance
End Get
Set(ByVal value As Integer)
m_distance = value
End Set
End Property
End Class
'Private Const MAX_N As Integer = 25
'Private Const MAX_DISTANCE As Integer = 100
Private Const MAX_SURPLUS As Integer = 100
Private Const DEBUG As Boolean = True
Private g_bunkers As List(Of Bunker) = Nothing
Private genRand As New Random()
Private g_operations As Integer = 0
Private Sub debugMessage(ByVal message As String)
If DEBUG Then
Console.WriteLine(message)
End If
End Sub
'''
''' Generate a random sequence of bunkers with
''' random distances and fuel in them in which
''' there is just enough fuel to get around the
''' circle. There is at least one bunker from which
''' a circuit is possible.
'''
'''the starting point
Private Function generateData(ByVal n As Integer, ByVal distance As Integer) As Integer
g_bunkers = New List(Of Bunker)
For i As Integer = 0 To n - 1
Dim bunker As New Bunker
' randomly assign distances to next bunker
bunker.distance = genRand.Next(0, distance)
g_bunkers.Add(bunker)
Next
' choose random starting point
Dim start As Integer = genRand.Next(0, n - 1)
' go (almost) around the circle ensuring that there is enough fuel to make it around
Dim surplus As Integer
For i As Integer = 0 To n - 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim bunker As Bunker = g_bunkers(bunkerNumber)
' choose random surplus
Dim currSurplus As Integer = genRand.Next(0, MAX_SURPLUS)
' fuel + previous surplus should add up to currSurplus, but cannot have negative fuel
Dim f As Integer = bunker.distance + currSurplus - surplus
f = Math.Max(0, f)
bunker.fuel = f
surplus = surplus + bunker.fuel - bunker.distance
' if last bunker then fudge the distance in case we have remaining fuel
If i = n - 1 And surplus > 0 Then
bunker.distance = bunker.distance + surplus
End If
Next
Return start
End Function
'''
''' Print out the route from start, printing out the distance
''' covered by the hop, fuel used, and current surplus.
'''
''' starting point of the route
Private Sub checkRoute(ByVal start As Integer, Optional ByVal quiet As Boolean = False)
Dim n As Integer = g_bunkers.Count()
Dim surplus As Integer = 0
For i As Integer = 0 To n - 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim b As Bunker = g_bunkers(bunkerNumber)
surplus = surplus + b.fuel - b.distance
If Not quiet Then
Console.Write(String.Format("Bunker[{0}]: fuel = {1}, distance = {2}, surplus = {3}.", _
bunkerNumber, b.fuel, b.distance, surplus))
If surplus < 0 Then
Console.WriteLine(" -- ran out of fuel")
Else
Console.WriteLine()
End If
End If
Next
If surplus >= 0 Then
Console.Write("Success:")
Else
Console.Write("Failure:")
End If
Console.WriteLine(String.Format(" start = {0}, surplus = {1}.", start, surplus))
End Sub
'''
''' Find the next index at or after position in Bunkers with a deficit,
''' modulo number of bunkers. If there is none, returns 0.
'''
''' position at which to start search
'''next bunker with a deficit
Private Function findNextDeficit(ByVal position As Integer) As Integer
debugMessage("findNextDeficit: position = " & position)
Dim n As Integer = g_bunkers.Count
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim j = (i + position) Mod n
If g_bunkers.Item(j).distance > g_bunkers.Item(j).fuel Then
debugMessage("findNextDeficit: returning " & j)
Return j
End If
Next
debugMessage("findNextDeficit: failure - returning 0")
Return 0
End Function
'''
''' Find the next index at or after position in Bunkers with a surplus,
''' modulo number of bunkers. If there is none, throws an exception
''' since there should be at least one.
'''
''' position at which to start search
'''next bunker with a deficit
Private Function findNextSurplus(ByVal position As Integer) As Integer
debugMessage("findNextSurplus: position = " & position)
Dim n As Integer = g_bunkers.Count
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim j = (i + position) Mod n
If g_bunkers.Item(j).distance < g_bunkers.Item(j).fuel Then
debugMessage("findNextSurplus: returning " & j)
Return j
End If
Next
Throw New Exception("findNextSurplus - no surplus found")
End Function
'''
''' Try and see if a loop around the bunkers can be constructed from
''' start. If succeeds, return -1, otherwise return position at
''' which it failed.
'''
'''
'''-1 for success, position of failure otherwise
Private Function tryLoop(ByVal start As Integer) As Integer
debugMessage("tryLoop: start = " & start)
Dim n As Integer = g_bunkers.Count()
Dim surplus As Integer = 0
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim b As Bunker = g_bunkers(bunkerNumber)
surplus = surplus + b.fuel - b.distance
If surplus < 0 Then
' failed
debugMessage("tryLoop: failed - returning " & bunkerNumber)
Return bunkerNumber
End If
Next
' success
debugMessage("tryLoop: suceeded - returning -1")
Return -1
End Function
'''
''' Find a route. Calculate the surplus for each individual hop.
''' The only possible starting points have to be at the beginning of a sequence
''' of positive surpluses.
'''
'''the start position
'''
Private Function findRoute() As Integer
Dim n As Integer = g_bunkers.Count
Dim done As Boolean = False
Dim position As Integer = 0
While True
' find the next deficit
Dim i As Integer = findNextDeficit(position)
' find the next surplus starting point after the deficit
Dim j As Integer = findNextSurplus(i)
position = j
' try and see if a circuit can be completed from position.
' if it can, return position. if not, set position to
' the place where it failed and try again
i = tryLoop(position)
If i = -1 Then
Return position
Else
position = i
End If
End While
' should be able to find a route
Throw New Exception("findRoute - couldn't find route")
End Function
'''
''' Do a single test iteration.
'''
'''
Public Sub test()
Dim start As Integer = generateData(1000, 10000)
g_operations = 0
Try
Dim foundStart = findRoute()
checkRoute(foundStart)
Catch ex As Exception
' failure
Console.WriteLine(ex.Message())
End Try
Console.WriteLine("Number of operations = " & g_operations)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
End Module
Google Profile: http://www.google.com/profiles/larrywatanabe
Stack overflow profile: http://stackoverflow.com/users/118860/larry-watanabe
Blog: http://larrywatanabe.blogspot.com
Master's thesis: http://portal.acm.org/citation.cfm?id=125337
Publications: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html
MacShapa: http://portal.acm.org/citation.cfm?id=211243
Option Strict On
Option Explicit On
'''
''' Solution to problem posted on Joel on Software:
''' There are n petrol bunks arranged in circle.
''' Each bunk is separated from the rest by a certain distance.
''' You choose some mode of travel which needs 1litre of petrol to cover 1km distance.
''' You can't infinitely draw any amount of petrol from each bunk as each bunk
''' has some limited petrol only. But you know that the sum of litres of petrol
''' in all the bunks is equal to the distance to be covered.
''' ie let P1, P2, ... Pn be n bunks arranged circularly
'''
Module Module1
'''
''' Representation of a bunker. The next bunker
''' is at (m_position + 1) mod N
'''
Class Bunker
'''
''' Amount of fuel at this bunker
'''
'''
Public m_fuel As Integer
Public m_distance As Integer
Public Property fuel() As Integer
Get
Return m_fuel
End Get
Set(ByVal value As Integer)
m_fuel = value
End Set
End Property
Public Property distance() As Integer
Get
Return m_distance
End Get
Set(ByVal value As Integer)
m_distance = value
End Set
End Property
End Class
'Private Const MAX_N As Integer = 25
'Private Const MAX_DISTANCE As Integer = 100
Private Const MAX_SURPLUS As Integer = 100
Private Const DEBUG As Boolean = True
Private g_bunkers As List(Of Bunker) = Nothing
Private genRand As New Random()
Private g_operations As Integer = 0
Private Sub debugMessage(ByVal message As String)
If DEBUG Then
Console.WriteLine(message)
End If
End Sub
'''
''' Generate a random sequence of bunkers with
''' random distances and fuel in them in which
''' there is just enough fuel to get around the
''' circle. There is at least one bunker from which
''' a circuit is possible.
'''
'''
Private Function generateData(ByVal n As Integer, ByVal distance As Integer) As Integer
g_bunkers = New List(Of Bunker)
For i As Integer = 0 To n - 1
Dim bunker As New Bunker
' randomly assign distances to next bunker
bunker.distance = genRand.Next(0, distance)
g_bunkers.Add(bunker)
Next
' choose random starting point
Dim start As Integer = genRand.Next(0, n - 1)
' go (almost) around the circle ensuring that there is enough fuel to make it around
Dim surplus As Integer
For i As Integer = 0 To n - 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim bunker As Bunker = g_bunkers(bunkerNumber)
' choose random surplus
Dim currSurplus As Integer = genRand.Next(0, MAX_SURPLUS)
' fuel + previous surplus should add up to currSurplus, but cannot have negative fuel
Dim f As Integer = bunker.distance + currSurplus - surplus
f = Math.Max(0, f)
bunker.fuel = f
surplus = surplus + bunker.fuel - bunker.distance
' if last bunker then fudge the distance in case we have remaining fuel
If i = n - 1 And surplus > 0 Then
bunker.distance = bunker.distance + surplus
End If
Next
Return start
End Function
'''
''' Print out the route from start, printing out the distance
''' covered by the hop, fuel used, and current surplus.
'''
''' starting point of the route
Private Sub checkRoute(ByVal start As Integer, Optional ByVal quiet As Boolean = False)
Dim n As Integer = g_bunkers.Count()
Dim surplus As Integer = 0
For i As Integer = 0 To n - 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim b As Bunker = g_bunkers(bunkerNumber)
surplus = surplus + b.fuel - b.distance
If Not quiet Then
Console.Write(String.Format("Bunker[{0}]: fuel = {1}, distance = {2}, surplus = {3}.", _
bunkerNumber, b.fuel, b.distance, surplus))
If surplus < 0 Then
Console.WriteLine(" -- ran out of fuel")
Else
Console.WriteLine()
End If
End If
Next
If surplus >= 0 Then
Console.Write("Success:")
Else
Console.Write("Failure:")
End If
Console.WriteLine(String.Format(" start = {0}, surplus = {1}.", start, surplus))
End Sub
'''
''' Find the next index at or after position in Bunkers with a deficit,
''' modulo number of bunkers. If there is none, returns 0.
'''
''' position at which to start search
'''
Private Function findNextDeficit(ByVal position As Integer) As Integer
debugMessage("findNextDeficit: position = " & position)
Dim n As Integer = g_bunkers.Count
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim j = (i + position) Mod n
If g_bunkers.Item(j).distance > g_bunkers.Item(j).fuel Then
debugMessage("findNextDeficit: returning " & j)
Return j
End If
Next
debugMessage("findNextDeficit: failure - returning 0")
Return 0
End Function
'''
''' Find the next index at or after position in Bunkers with a surplus,
''' modulo number of bunkers. If there is none, throws an exception
''' since there should be at least one.
'''
''' position at which to start search
'''
Private Function findNextSurplus(ByVal position As Integer) As Integer
debugMessage("findNextSurplus: position = " & position)
Dim n As Integer = g_bunkers.Count
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim j = (i + position) Mod n
If g_bunkers.Item(j).distance < g_bunkers.Item(j).fuel Then
debugMessage("findNextSurplus: returning " & j)
Return j
End If
Next
Throw New Exception("findNextSurplus - no surplus found")
End Function
'''
''' Try and see if a loop around the bunkers can be constructed from
''' start. If succeeds, return -1, otherwise return position at
''' which it failed.
'''
'''
'''
Private Function tryLoop(ByVal start As Integer) As Integer
debugMessage("tryLoop: start = " & start)
Dim n As Integer = g_bunkers.Count()
Dim surplus As Integer = 0
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim b As Bunker = g_bunkers(bunkerNumber)
surplus = surplus + b.fuel - b.distance
If surplus < 0 Then
' failed
debugMessage("tryLoop: failed - returning " & bunkerNumber)
Return bunkerNumber
End If
Next
' success
debugMessage("tryLoop: suceeded - returning -1")
Return -1
End Function
'''
''' Find a route. Calculate the surplus for each individual hop.
''' The only possible starting points have to be at the beginning of a sequence
''' of positive surpluses.
'''
'''
'''
Private Function findRoute() As Integer
Dim n As Integer = g_bunkers.Count
Dim done As Boolean = False
Dim position As Integer = 0
While True
' find the next deficit
Dim i As Integer = findNextDeficit(position)
' find the next surplus starting point after the deficit
Dim j As Integer = findNextSurplus(i)
position = j
' try and see if a circuit can be completed from position.
' if it can, return position. if not, set position to
' the place where it failed and try again
i = tryLoop(position)
If i = -1 Then
Return position
Else
position = i
End If
End While
' should be able to find a route
Throw New Exception("findRoute - couldn't find route")
End Function
'''
''' Do a single test iteration.
'''
'''
Public Sub test()
Dim start As Integer = generateData(1000, 10000)
g_operations = 0
Try
Dim foundStart = findRoute()
checkRoute(foundStart)
Catch ex As Exception
' failure
Console.WriteLine(ex.Message())
End Try
Console.WriteLine("Number of operations = " & g_operations)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
End Module
Google Profile: http://www.google.com/profiles/larrywatanabe
Stack overflow profile: http://stackoverflow.com/users/118860/larry-watanabe
Blog: http://larrywatanabe.blogspot.com
Master's thesis: http://portal.acm.org/citation.cfm?id=125337
Publications: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html
MacShapa: http://portal.acm.org/citation.cfm?id=211243
Shameless Self-Promotion
In today's economy, who knows if one will be employed tomorrow? I'm quite happy at my current job -- the most important factor in a workplace is a boss and co-workers who are pleasant to be around (you're lucky if they're bearable, but I'm more than lucky).
Anyways, knowing how google's pagerank algorithm works, I decided to do a bit of shameles self-promotion by keeping a list of links about me to improve my pagerank.
Google Profile: http://www.google.com/profiles/larrywatanabe
Stack overflow profile: http://stackoverflow.com/users/118860/larry-watanabe
Blog: http://larrywatanabe.blogspot.com
Master's thesis: http://portal.acm.org/citation.cfm?id=125337
Publications: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html
MacShapa: http://portal.acm.org/citation.cfm?id=211243
Anyways, knowing how google's pagerank algorithm works, I decided to do a bit of shameles self-promotion by keeping a list of links about me to improve my pagerank.
Google Profile: http://www.google.com/profiles/larrywatanabe
Stack overflow profile: http://stackoverflow.com/users/118860/larry-watanabe
Blog: http://larrywatanabe.blogspot.com
Master's thesis: http://portal.acm.org/citation.cfm?id=125337
Publications: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html
MacShapa: http://portal.acm.org/citation.cfm?id=211243
Monday, June 15, 2009
Fast Sorting - was Why is my bubblesort in Python so slow?
Someone posted this question in StackOverflow:
http://stackoverflow.com/questions/997322/why-is-my-bubble-sort-in-python-so-slow
I'm not sure why, but radix sort seems to be overlooked a lot as a sorting algorithm. This is a little strange, as the space requirements are not bad and it is O(N) unless you have a strange distribution.
I wrote a quick implementation in a few minutes (it's also easy to implement) and the time was < 1 sec to execute for 100,000 elements, compared to the poster's 2 hrs. Granted, I was using VB instead of Python :)
Option Strict On
Option Explicit On
Module Module1
Private Const MAX_SIZE As Integer = 100000
Private m_input(MAX_SIZE) As Integer
Private m_table(MAX_SIZE) As List(Of Integer)
Private m_randomGen As New Random()
Private m_operations As Integer = 0
Private Sub generateData()
' fill with random numbers between 0 and MAX_SIZE - 1
For i = 0 To MAX_SIZE - 1
m_input(i) = m_randomGen.Next(0, MAX_SIZE - 1)
Next
End Sub
Private Sub sortData()
For i As Integer = 0 To MAX_SIZE - 1
Dim x = m_input(i)
If m_table(x) Is Nothing Then
m_table(x) = New List(Of Integer)
End If
m_table(x).Add(x)
' clearly this is simply going to be MAX_SIZE -1
m_operations = m_operations + 1
Next
End Sub
Private Sub printData(ByVal start As Integer, ByVal finish As Integer)
If start < 0 Or start > MAX_SIZE - 1 Then
Throw New Exception("printData - start out of range")
End If
If finish < 0 Or finish > MAX_SIZE - 1 Then
Throw New Exception("printData - finish out of range")
End If
For i As Integer = start To finish
If m_table(i) IsNot Nothing Then
For Each x In m_table(i)
Console.WriteLine(x)
Next
End If
Next
End Sub
' run the entire sort, but just print out the first 100 for verification purposes
Private Sub test()
m_operations = 0
generateData()
Console.WriteLine("Time started = " & Now.ToString())
sortData()
Console.WriteLine("Time finished = " & Now.ToString & " Number of operations = " & m_operations.ToString())
' print out a random 100 segment from the sorted array
Dim start As Integer = m_randomGen.Next(0, MAX_SIZE - 101)
printData(start, start + 100)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
End Module
Time started = 6/15/2009 4:04:08 PM
Time finished = 6/15/2009 4:04:08 PM Number of operations = 100000
21429
21430
21430
21431
21431
21432
21433
21435
21435
21435
21436
21437
21437
21439
21441
21441
21441
21446
21447
21448
21449
21451
21451
21454
21456
21456
21458
21460
21461
21461
21461
21463
21463
21464
21465
21466
21468
21468
21468
21469
21469
21470
21471
21471
21471
21471
21472
21473
21474
21474
21477
21479
21481
21481
21481
21483
21483
21486
21487
21489
21490
21493
21494
21495
21496
21496
21499
21500
21501
21501
21501
21502
21502
21502
21505
21509
21510
21510
21511
21512
21514
21515
21516
21517
21519
21519
21522
21524
21526
http://stackoverflow.com/questions/997322/why-is-my-bubble-sort-in-python-so-slow
I'm not sure why, but radix sort seems to be overlooked a lot as a sorting algorithm. This is a little strange, as the space requirements are not bad and it is O(N) unless you have a strange distribution.
I wrote a quick implementation in a few minutes (it's also easy to implement) and the time was < 1 sec to execute for 100,000 elements, compared to the poster's 2 hrs. Granted, I was using VB instead of Python :)
Option Strict On
Option Explicit On
Module Module1
Private Const MAX_SIZE As Integer = 100000
Private m_input(MAX_SIZE) As Integer
Private m_table(MAX_SIZE) As List(Of Integer)
Private m_randomGen As New Random()
Private m_operations As Integer = 0
Private Sub generateData()
' fill with random numbers between 0 and MAX_SIZE - 1
For i = 0 To MAX_SIZE - 1
m_input(i) = m_randomGen.Next(0, MAX_SIZE - 1)
Next
End Sub
Private Sub sortData()
For i As Integer = 0 To MAX_SIZE - 1
Dim x = m_input(i)
If m_table(x) Is Nothing Then
m_table(x) = New List(Of Integer)
End If
m_table(x).Add(x)
' clearly this is simply going to be MAX_SIZE -1
m_operations = m_operations + 1
Next
End Sub
Private Sub printData(ByVal start As Integer, ByVal finish As Integer)
If start < 0 Or start > MAX_SIZE - 1 Then
Throw New Exception("printData - start out of range")
End If
If finish < 0 Or finish > MAX_SIZE - 1 Then
Throw New Exception("printData - finish out of range")
End If
For i As Integer = start To finish
If m_table(i) IsNot Nothing Then
For Each x In m_table(i)
Console.WriteLine(x)
Next
End If
Next
End Sub
' run the entire sort, but just print out the first 100 for verification purposes
Private Sub test()
m_operations = 0
generateData()
Console.WriteLine("Time started = " & Now.ToString())
sortData()
Console.WriteLine("Time finished = " & Now.ToString & " Number of operations = " & m_operations.ToString())
' print out a random 100 segment from the sorted array
Dim start As Integer = m_randomGen.Next(0, MAX_SIZE - 101)
printData(start, start + 100)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
End Module
Time started = 6/15/2009 4:04:08 PM
Time finished = 6/15/2009 4:04:08 PM Number of operations = 100000
21429
21430
21430
21431
21431
21432
21433
21435
21435
21435
21436
21437
21437
21439
21441
21441
21441
21446
21447
21448
21449
21451
21451
21454
21456
21456
21458
21460
21461
21461
21461
21463
21463
21464
21465
21466
21468
21468
21468
21469
21469
21470
21471
21471
21471
21471
21472
21473
21474
21474
21477
21479
21481
21481
21481
21483
21483
21486
21487
21489
21490
21493
21494
21495
21496
21496
21499
21500
21501
21501
21501
21502
21502
21502
21505
21509
21510
21510
21511
21512
21514
21515
21516
21517
21519
21519
21522
21524
21526
Saturday, June 13, 2009
Why I'm writing this blog -- my daughter g
I'm not sure why ... I suppose I have a dream. I have a daughter who I may never meet again, although I think of her every day. I can't be there for her, and maybe she will grow up happy and blissfully ignorant of my existence. Perhaps if she knew who I was, she wouldn't have any interest in meeting me or getting to know me better.
But if she does, then maybe this blog will be around to give her some idea of who I am, and perhaps if genetics has something to do with who she is, some idea of who she is, or might be, or might have been.
I'm sure Google is going to survive. And there are archival systems setup - I'm sure that either now or later someone is going to be able to make a time machine of the internet, so that you can visit the internet on any particular day, surf the web, see the posts. It's what scholars will be doing in the future -- how much easier than digging out notes on napkins from some obscure attic. The internet is a big enough space and changes enough over time that this should be enough to keep them busy ... unless Google or someone can create a really good search engine that can do this work automatically. Still, it is an interative process ... I'm getting way off track here, time for another post on this :)
Anyways, I'd like her to be able to meet me, even if I can never meet her. If you read this, Gracie, I love you.
But if she does, then maybe this blog will be around to give her some idea of who I am, and perhaps if genetics has something to do with who she is, some idea of who she is, or might be, or might have been.
I'm sure Google is going to survive. And there are archival systems setup - I'm sure that either now or later someone is going to be able to make a time machine of the internet, so that you can visit the internet on any particular day, surf the web, see the posts. It's what scholars will be doing in the future -- how much easier than digging out notes on napkins from some obscure attic. The internet is a big enough space and changes enough over time that this should be enough to keep them busy ... unless Google or someone can create a really good search engine that can do this work automatically. Still, it is an interative process ... I'm getting way off track here, time for another post on this :)
Anyways, I'd like her to be able to meet me, even if I can never meet her. If you read this, Gracie, I love you.
Free Societies and Good Government
I wrote a letter to my daughter Anne and had a few thoughts about free societies that have been running through my head. There were some further thoughts about how to structure self-adapting software at a higher level than neural networks in terms of a free society of software agents whose "government" can be setup to incentivize them realize the programming good.
Once I've got this paradigm down, I'll move to the God paradigm, where you create a universe where the software agents are incentivized to realize a more general program goal. I'll have to develop the ideas further, but so far the most promising approach seems to involve the design patterns "free will", "heaven", and "hell" :)
--------------------------------
was just thinking today about how one of our strengths is that we are a free society and that it works because it's structured so that if everyone does what they want then they fulfil the needs of the society. And how money is just a way of keeping track so that each person contributes their share to society ... and that entitles them to share in the contributions of others. But it doesn't work if people cheat .. for example, if they steal money then that money does not represent their contribution to society.
I was also thinking about the mechanisms for change in society .. in a democracy, we elect our government which keeps it in line. Regardless of whether we get Conservatives or Liberals, Republicans or Democrats, we still end up with a pool of intelligent, hard-working reasonably ethical people to direct our collective work. That's why I think political corruption such as trading favors and contracts for campaign contributions etc. is such a problem ... because of the theft issue above, and how it attracts the wrong people to steer the direction of our government.
Once I've got this paradigm down, I'll move to the God paradigm, where you create a universe where the software agents are incentivized to realize a more general program goal. I'll have to develop the ideas further, but so far the most promising approach seems to involve the design patterns "free will", "heaven", and "hell" :)
--------------------------------
was just thinking today about how one of our strengths is that we are a free society and that it works because it's structured so that if everyone does what they want then they fulfil the needs of the society. And how money is just a way of keeping track so that each person contributes their share to society ... and that entitles them to share in the contributions of others. But it doesn't work if people cheat .. for example, if they steal money then that money does not represent their contribution to society.
I was also thinking about the mechanisms for change in society .. in a democracy, we elect our government which keeps it in line. Regardless of whether we get Conservatives or Liberals, Republicans or Democrats, we still end up with a pool of intelligent, hard-working reasonably ethical people to direct our collective work. That's why I think political corruption such as trading favors and contracts for campaign contributions etc. is such a problem ... because of the theft issue above, and how it attracts the wrong people to steer the direction of our government.
Dong away with Interview, CV, Resume in Job Search
Someone suggeseted on Joel on software that we do away with the traditional CV/interview process.
http://discuss.joelonsoftware.com/default.asp?joel.3.757969.15
Here's my thoughts:
---------------------
I don't see anything wrong with having a CV and an interview, per se. Besides measuring confidence and appearance, the interview does the critical job of ensuring that the candidate has actually done and is capable of everything that they have written about in their resume. A sharp interviewer can figure this out by asking them questions about the resume.
And without a CV, how would you make a selection of individuals to bring in for an interview? Simply post a "people wanted" ad? Put on an online test that they have to pass in order to get in? Any kind of test can be gamed/cheated, so I would feel it is of little value.
Now, there would be some advantage to a formal test in the facility, but each position, at each point in time, has different requirements and it is difficult to design a test that accurately measures the needs of the moment. The Chinese Empire had a system called "the examination system" for selecting government officials and it had a lot of problems -- main one being it led to a structure of passive bureaucrats who were helpless against the invasion of more dynamic people and cultures like the British Empire.
http://discuss.joelonsoftware.com/default.asp?joel.3.757969.15
Here's my thoughts:
---------------------
I don't see anything wrong with having a CV and an interview, per se. Besides measuring confidence and appearance, the interview does the critical job of ensuring that the candidate has actually done and is capable of everything that they have written about in their resume. A sharp interviewer can figure this out by asking them questions about the resume.
And without a CV, how would you make a selection of individuals to bring in for an interview? Simply post a "people wanted" ad? Put on an online test that they have to pass in order to get in? Any kind of test can be gamed/cheated, so I would feel it is of little value.
Now, there would be some advantage to a formal test in the facility, but each position, at each point in time, has different requirements and it is difficult to design a test that accurately measures the needs of the moment. The Chinese Empire had a system called "the examination system" for selecting government officials and it had a lot of problems -- main one being it led to a structure of passive bureaucrats who were helpless against the invasion of more dynamic people and cultures like the British Empire.
Thursday, June 11, 2009
Everything is about Sex
It just struck me the other day how everything is about sex.
Take Mom and apple pie, for example. Well Mom ... how did she get to be your Mom? Because she and Dad had sex, and you're a direct product.
Apple pie .. well American pie, need I say more.
Family values .. what are families anyways but people who are connected by a sex act? Now, it may not be your sex act .. but your grandchildren are the product of your children having sex, your nieces, nephews, in-laws .. I'm sure you can work it out.
Take Mom and apple pie, for example. Well Mom ... how did she get to be your Mom? Because she and Dad had sex, and you're a direct product.
Apple pie .. well American pie, need I say more.
Family values .. what are families anyways but people who are connected by a sex act? Now, it may not be your sex act .. but your grandchildren are the product of your children having sex, your nieces, nephews, in-laws .. I'm sure you can work it out.
Optimizing Infinite Loops - Stack Overflow C, C++ question
There was a rather amusing question posted on Stack Overflow:
I am just wondering if there would be any loss of speed or efficiency if you did something like this:
int i = 0;
while(i < 100)
{
int var = 4;
}
which declares int var one hundred times. It seems to me like there would be, but I'm not sure. would it be more practical/faster to do this instead:
int i = 0;
int var;
while(i < 100)
{
var = 4;
}
My Answer: Both looks take 2 bytes of space and an infinite amount of time :)
I am just wondering if there would be any loss of speed or efficiency if you did something like this:
int i = 0;
while(i < 100)
{
int var = 4;
}
which declares int var one hundred times. It seems to me like there would be, but I'm not sure. would it be more practical/faster to do this instead:
int i = 0;
int var;
while(i < 100)
{
var = 4;
}
My Answer: Both looks take 2 bytes of space and an infinite amount of time :)
Source code as design - and UML, new languages
*sigh* more Microsoft security updates -- been installing for over an hour now.
On JOS someone (Arethuza) posted a very illuminating article -- basically saying that the only real design artifact in software is the source code.
http://www.developerdotstar.com/mag/articles/reeves_design.html
It's funny but from that perspective (source code is design) it becomes clear that one of the most important features of a language is readability and simplicity.
Perhaps what we need is a hierarchical language, where a high-level version can only specify certain constraints (much like an UML diagram does) and can be converted automatically into a visual syntax (this would automate generation of diagrammed design documents).
Later layers of implementation would allow the iterative design to be tested in greater detail, and the final layer would result in a working program.
You can do this to a certain extent in C++ - i.e. create a UML diagram, forward engineer it into C++ stubs, hand-off the stubs to a team of programmers -- but I would like something that is seamlessly integrated as part of the language.
On JOS someone (Arethuza) posted a very illuminating article -- basically saying that the only real design artifact in software is the source code.
http://www.developerdotstar.com/mag/articles/reeves_design.html
It's funny but from that perspective (source code is design) it becomes clear that one of the most important features of a language is readability and simplicity.
Perhaps what we need is a hierarchical language, where a high-level version can only specify certain constraints (much like an UML diagram does) and can be converted automatically into a visual syntax (this would automate generation of diagrammed design documents).
Later layers of implementation would allow the iterative design to be tested in greater detail, and the final layer would result in a working program.
You can do this to a certain extent in C++ - i.e. create a UML diagram, forward engineer it into C++ stubs, hand-off the stubs to a team of programmers -- but I would like something that is seamlessly integrated as part of the language.
Monday, June 8, 2009
Ruby/Python - Generate Code from my Domain Specific Languages - Visual Studio 2008
There's a new news item on Visual Studio Developer Center on how to generate code from a domain-specific language.
Is the equivalent of an eclipse plug-in for a new language? I know people rave about eclipse, especially for java development, but I used it's progenitor Visual Age, and an early java-based version of eclipse, and wasn't too impressed by the response times.
I'm running a Quad-core 2.2 GHZ computer now (how quaint and underpowered this will seem in the future! How many giga-processor do you have?) and it should be fast enough ... but like they say you only get one chance to make a first imperession. I wish Microsoft (or someone ..maybe I should just do it) would release an interface for Python and Ruby that is well-integrated with the existing runtime engines out there instead of only supporting the MS IronRuby, IronPython.
Why would Microsoft do this? Well IronPython and IronRuby don't have a large userbase anyways, and Microsoft would probably benefit more from directly supporting the existing userbase of Ruby/Python programmers (they could develop on windows and deploy on Linux ... but once the camel gets it's nose into the tent ..) and feeding on the migration of those developers to IronRuby and IronPython, if they are so inclined. Why would they be so inclined? Microsoft might fully support a general cross-platform runtime engine in it's silverlight that can be run in firefox and IE explorer, and make a really fast high-quality compiler that produces the fastest run-time code around, not to mention access to MPF from Python across platforms using silverlight.
Is the equivalent of an eclipse plug-in for a new language? I know people rave about eclipse, especially for java development, but I used it's progenitor Visual Age, and an early java-based version of eclipse, and wasn't too impressed by the response times.
I'm running a Quad-core 2.2 GHZ computer now (how quaint and underpowered this will seem in the future! How many giga-processor do you have?) and it should be fast enough ... but like they say you only get one chance to make a first imperession. I wish Microsoft (or someone ..maybe I should just do it) would release an interface for Python and Ruby that is well-integrated with the existing runtime engines out there instead of only supporting the MS IronRuby, IronPython.
Why would Microsoft do this? Well IronPython and IronRuby don't have a large userbase anyways, and Microsoft would probably benefit more from directly supporting the existing userbase of Ruby/Python programmers (they could develop on windows and deploy on Linux ... but once the camel gets it's nose into the tent ..) and feeding on the migration of those developers to IronRuby and IronPython, if they are so inclined. Why would they be so inclined? Microsoft might fully support a general cross-platform runtime engine in it's silverlight that can be run in firefox and IE explorer, and make a really fast high-quality compiler that produces the fastest run-time code around, not to mention access to MPF from Python across platforms using silverlight.
Friday, June 5, 2009
VB Call Stack
How do you bring up the VB or C# Call Stack window to debug?
It's in Debug -> Windows -> Call Stack, also available with Ctrl+L
Used to be you could right click in the bottom somewhere to bring it up - I guess they made it more explicit. However, keeping it in Windows option only under the Debug Menu option was kind of hard for me to find, for some reason.
I think it would make sense to provide all the Debug windows under
View -> Other Windows -> Debug
as well.
It's in Debug -> Windows -> Call Stack, also available with Ctrl+L
Used to be you could right click in the bottom somewhere to bring it up - I guess they made it more explicit. However, keeping it in Windows option only under the Debug Menu option was kind of hard for me to find, for some reason.
I think it would make sense to provide all the Debug windows under
View -> Other Windows -> Debug
as well.
Tuesday, June 2, 2009
Restoring an image to a different computer
1. Try to have the new c: drive the same size or bigger than the original image.
2. install the windows cd
3. format the c: drive to the correct size.
4.boot up with your norton cd, or image for dos/linux, this is what I use.
5. Restore image.
6. Do not boot up to windows now!!
7. Install Windows cd and reboot.
8. Enter recovery console.
9. Do a fix boot (fixboot)
10. Do a fixmbr
11. This is optional if you have trouble, you may not need to do this:
Do a Bootcfg /rebuild
Type in "Microsoft Windows XP Home Edition", if this is your platform.
/fastdetect (fastdetect)
You will have to find out more info on this as I am a little pressed for time. You might have to delete c:\boot.ini file first.
12 Reboot to cd
13 Install new XP (enter)
14 Repair existing Windows installation. (R)
*important otherwise you will lose everything and install a new installation. All this does is install windows over windows with the correct drivers for your system.
15. Let it reboot and pray.
16 Reactivate.
2. install the windows cd
3. format the c: drive to the correct size.
4.boot up with your norton cd, or image for dos/linux, this is what I use.
5. Restore image.
6. Do not boot up to windows now!!
7. Install Windows cd and reboot.
8. Enter recovery console.
9. Do a fix boot (fixboot)
10. Do a fixmbr
11. This is optional if you have trouble, you may not need to do this:
Do a Bootcfg /rebuild
Type in "Microsoft Windows XP Home Edition", if this is your platform.
/fastdetect (fastdetect)
You will have to find out more info on this as I am a little pressed for time. You might have to delete c:\boot.ini file first.
12 Reboot to cd
13 Install new XP (enter)
14 Repair existing Windows installation. (R)
*important otherwise you will lose everything and install a new installation. All this does is install windows over windows with the correct drivers for your system.
15. Let it reboot and pray.
16 Reactivate.
Subscribe to:
Posts (Atom)