插入到有序數組中的計算效率最高的方法？

我有一個包含時間序列數據數組的數組如下：插入到有序數組中的計算效率最高的方法？

var timeseries = [ 
    [Tue Dec 31 2013 00:00:00 GMT+0000 (GMT Standard Time), 3, 2], 
    [Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 1.2, 3], 
    [Tue Dec 31 2013 02:00:00 GMT+0000 (GMT Standard Time), 4, 2] 
]

嵌套數組中的第一項是一個JavaScript日期。

我有一個包含獨特的javascript日期列表的第二陣列，但可能會或可能不會已經在時間序列存在陣列：

var newTimes = [ 
    Tue Dec 31 2013 00:13:00 GMT+0000 (GMT Standard Time), 
    Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 
    Tue Dec 31 2013 01:40:00 GMT+0000 (GMT Standard Time) 
]

對於每個項目在新時代陣列，我需要檢查數組是否存在與時間序列數組一起存儲的數組中。如果沒有，我想在時間序列數組中插入一個正確位置（時間順序）的新數組，並且 - 關鍵地 - 從前面的數組中複製其他數組值。例如，兩個以上陣列合成所描述的將一代產量：

var newTimeseries = [ 
    [Tue Dec 31 2013 00:00:00 GMT+0000 (GMT Standard Time), 3, 2], 
    [Tue Dec 31 2013 00:13:00 GMT+0000 (GMT Standard Time), 3, 2], 
    [Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 1.2, 3], 
    [Tue Dec 31 2013 01:40:00 GMT+0000 (GMT Standard Time), 1.2, 3], 
    [Tue Dec 31 2013 02:00:00 GMT+0000 (GMT Standard Time), 4, 2] 
]

我應該注意到兩個陣列已經排序。另外，newTimes中的項目將存在於時間序列的範圍內。最後，原始時間序列數組每小時都有一個入口。

我嘗試了幾種不同的方法，但我對計算最有效的方法感興趣。如果有幫助，我很樂意使用任何適當的良好的第三方庫，如underscore.js。

來源

2014-01-06 jtromans

鏈表想到... – oerkelens

好，鏈表會給你'O（1）'用於插入的複雜性和'O（N）'進行搜索。我認爲你會發現「最高效」將取決於你碰到多少次碰撞。 – Basic

根據列表大小的不同，您可能會插入所有內容，然後橫向列表一次以複製額外數據或刪除雙重條目。只是在這裏集思廣益:) – oerkelens

考慮到二進制搜索（由評論中的techfoobar建議）以及Bubble Sort（friendzis），到目前爲止我所提出的最優解決方案是遵循這個邏輯。

與使用二進制搜索相反，請考慮以下事項。

因爲我們知道兩個數組已經排序; newTimes內的日期落在timeseries日期範圍內;並且初始timeseries條目是在小時，每小時，我們可以在幾小時內找到時間序列[0] [0]日期和newTimes [0]之間的差異。這是啓動氣泡排序方法所需的初始偏移量（更像只是上面評論中討論的標準循環和切片）。這使用Moment.js庫。

代碼介紹如下，請隨時提出修改建議：

var firstEvent = moment(newTimes[0]); 
var firstTime = moment(timeseries[0][0]) ; 
var offset = firstEvent.diff(firstTime, 'hours') - 1; 


for (var i = offset; i < timeseries.length;i++) { 
    while (newTimes.length > 0 && typeof moment(timeseries[i+1]) !== "undefined" && moment(newTimes[0]) > moment(timeseries[i][0]) && moment(newTimes[0]) < moment(timeseries[i+1][0])) { 
     var newElement = timeseries[i].slice(0); 
     newElement[0] = moment(newTimes[0]).toDate(); 
     timeseries.splice(i+1, 0, newElement); 
     newTimes.splice(0,1); 
     i++; 
    } 
}

重要的是，這科佩斯與邊緣的情況下，當有在newTimes陣列中的兩個或多個條目都屬於只有一個timeseries條目內內，例如：

var timeseries = [ 
    [Tue Dec 31 2013 00:00:00 GMT+0000 (GMT Standard Time), 3, 2], 
    [Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 1.2, 3] 
] 

var newTimes = [ 
    Tue Dec 31 2013 00:13:00 GMT+0000 (GMT Standard Time), 
    Tue Dec 31 2013 00:16:00 GMT+0000 (GMT Standard Time) 
]

來源

2014-01-06 16:32:45 jtromans

插入到有序數組中的計算效率最高的方法？

回答

相關問題