Programming contest!
The prize is a bag-o-marshmallows to whomever can come up with the most efficient way to solve the "Write, efficient code for extracting unique elements from a sorted list" problem.
Apparently everyone else on the web is content to post the question as a possible interview question. Well, I'm not interviewing for anything. I actually need better way to do this. Sure, I have some ideas, but I can't help thinking there is an optimal way to do this (my head keeps going back to the 2 bowling balls being dropped from the building... I can't help thinking there is a logical connection...).
Some quick background so you understand that the half-arsed check-every-item-in-the-array solution is not what I'm looking for. I'm looking for something that minimizes the number of reads I have to do since this algorithm will actually be applied to reading off a file, not an in memory array. I can guarantee you that the list is in order and that I can traverse the list like an array. So we can treat this particular problem like searching an array.
Consider also that I have to read 339,712 records. So think of an array that long with at least 100 duplicates per unique value. The actual number of duplicates per value is of course unknown. I want to avoid reading as many of those duplicates as I can. The one thing in my favor is that I know that they are all in order. Another thing that is clear to me is that I know the high and low values, so I should be able to deduce the maximum number of unique values. Of course you yourself probably saw that too.
Treat this contest like a C++ or VB contest of course. Answers like “SELECT DISTINCT column_name FROM table_name” will be laughed at and will owe me a bag of marshmallows.
Just to give you a head start (since I actually want the darned answer ASAP), I think that since I know the maximum number of unique elements, there must be an optimal number of jumps I can make through the array. I should compare at those jump points and decide whether or not to investigate the areas in-between my jumps based on the comparison result. Just the same as there was an optimal number of floors to skip in the bowling ball problem, I think there is an optimal number of records to skip here. How do I get that value? Following that, what is the most efficient way to search in-between my jumps? Or am I way off?
Please enlighten me and receive a bag of marshmallows in exchange.
I thought the binary search had been proven to be the fastest way of finding a value in an ordered array.
ReplyDeleteYou know,
pos1 = 0
pos2 = array.ubound
do
val = array[(pos1 + pos2) / 2]
if (ValToFind < val)
pos2 = (pos1 + pos2) / 2
else
pos1 = (pos1 + pos2) / 2
end if
while (val != ValToFind)
Also, is there a cost to traversing the array?
binary search is the fastest way to search for a specific value, but I need all the unqiue values in the array. There is a cost to accessing the array. Every element you read costs me time due to disc access (and cost of string convertion, etc).
ReplyDeleteBut on the drive home I had thought something up related to the binary search. I was thinking of a recursive binary comparison. I would compare the two end values, if they were different, go to the middle. If the middle was not equivalent to either of the end values then add it to my unsorted list of unqiue values. Then I go check the mid point between the low and middle points, and I do the same to the middle and high points. It'd be recursive and would only call itself again if it was comparing two values whose difference was greater than 1 and who also had elements between them. I have to scratch up some pseudo code I suppose, but that's what I'm thinking now.
Ooo... you need a RANGE of values.
ReplyDeleteUm...
1) Copy data into Excel/Access
2) Use a VB ODBC/OLEDB connection to connect to spreadsheet/database
3) Umm... rs.OpenRecordset(“SELECT DISTINCT column_name FROM table_name”)... or something? Like that?
I know it's possible to do SQL queries from VB. Just can't remember the method to use, and I don't have MSDN library on my home computer.
I think I got it.
ReplyDeletePublic Function GetUniqueInts(byref records() as integer) As integer()
Dim uniqueInts As New List(Of Integer)
If records isnot nothing andalso records.length > 0 Then
uniqueInts.Add(records(records.length - 1))
If records.length > 1 Then
If records(0) <> records(records.length - 1) Then
uniqueInts.Add(records(0))
End If
If records.length > 2 Then
GetUniqueIntsRecursive(0, records.length - 1, uniqueInts, records)
End If
End If
End If
uniqueInts.Sort()
Return uniqueInts.ToArray
End Function
Private Sub GetUniqueIntsRecursive(ByVal lowIndex As Integer, ByVal highIndex As Integer, ByRef intList As List(Of Integer), byref records() as integer)
Dim middleIndex As Integer
middleIndex = CInt((lowIndex + highIndex) / 2)
If records(lowIndex) <> records(middleIndex) AndAlso records(highIndex) <> records(middleIndex) Then
dateList.Add(records(middleIndex))
End If
If records(lowIndex) <> records(middleIndex) AndAlso middleIndex - lowIndex > 1 Then
GetUniqueIntsRecursive(lowIndex, middleIndex, intList, records)
End If
If records(highIndex) <> records(middleIndex) AndAlso highIndex - middleIndex > 1 Then
GetUniqueIntsRecursive(middleIndex, highIndex, intList, records)
End If
End Sub
Let me know if you can think of a better way. Or even if you can shave off some time on my recursive calls.
Anyone? Anything? No suggestions? Alternatives? I guess we're havin' smores tonight.
ReplyDeleteI am indifferent to your suffering
ReplyDelete