From: Jeremy Bopp Date: 2010-09-24T06:41:11+09:00 Subject: Re: Sorting problem with an Array of Arrays On 9/23/2010 4:15 PM, (r.*n){2} wrote: > On Sep 23, 4:46 pm, Jeremy Bopp wrote: >> On 9/23/2010 9:20 AM, Paul wrote: >> >> >> >>> The arrays represent timesheet records for work done. Each person on >>> the crew submits their records but sometimes they work on projects >>> with others. The majority of the record labels will be for a single >>> person (e.g. the ABC-*) but from time to time a different label will >>> show up (AAA, DEF, ...) because they worked a project with someone >>> else. >> >>> The ruby script I have goes through the list of records and looks for >>> double-bookings and other mistakes made during data entry. For >>> example, sometimes someone writes 10 PM when it was 10 AM. That's why >>> the label order is primary - it represents the order in which the jobs >>> happened. The timestamps themselves might be wrong. >> >>> However, when a new/different label appears, the "best guess" scenario >>> is to insert it into the list according to timestamp and rerun the >>> analysis to check that the timestamps are correct (no double-bookings, >>> etc.) >> >>> I wrote a method that does a recursive analysis on the data using 2 >>> separately sorted arrays - one by label and one by timestamp. It's >>> weird and a bit complex but it works. If I could find a way to sort >>> the data properly in the first place, then I can simplify the code >>> checking that takes place after it. >> >> What you appear to be describing is actually an ordered insert operation >> rather than a strict sort operation. Array#sort is abstracted such that >> you cannot know at any given time what is already sorted in your array, >> so you cannot conditionally change your primary sort key from label to >> timestamp based upon what is currently the last entry of the sorted array. >> >> You need to define a custom insert function. Beware that your >> description of labels and how they "change" is ambiguous, so you may >> need to modify the label comparison logic in the function to capture >> what it really means to have different labels: >> >> def special_insert(arr, new_item) >> if arr.empty? || new_item[0] == arr.last[0] then >> # If the array is empty or the label of the new item is the same >> # as the label of the last item in the array, append the new item >> # to the array. >> arr << new_item >> else >> # Otherwise, insert the new item by its timestamp. >> idx = arr.index { |item| new_item[1] < item[1] } >> if idx.nil? then >> # The new item is the oldest, so append it. >> arr << new_item >> else >> # Otherwise, insert the new item before the first item younger >> # than it is. >> arr.insert(idx, new_item) >> end >> end >> end >> >> unsorted_arr = [ >> ["AAA-1", 1271862000, 2], >> ["ABC-1", 1271768400, 2], >> ["ABC-2", 1271773800, 1], >> ["ABC-3", 1271863200, 2], >> ["ABC-4", 1271869200, 2], >> ["DEF-1", 1271772000, 1] >> ] >> >> sorted_arr = [] >> >> unsorted_arr.each do |item| >> special_insert(sorted_arr, item) >> end >> >> puts sorted_arr.collect { |item| "[#{item.join(", ")}]" }.join("\n") > > Wonder what the performance of this would be if there were 10,000 > entries? Probably pretty poor overall. The big problem is that timestamp search in the ever-growing sorted array. Unfortunately, timestamps could well be out of order since they could be erroneous but ignored when the labels match up, so we can't do something more efficient like a binary search to find the insert location. Basically, this data is potentially pretty messy, and more effort should probably be spent earlier in the chain to ensure that high quality data is entered in the first place. That way the error detection heuristic which needs this ordered array would likely be unnecessary. -Jeremy