快速访问随机元素的最有效结构+一个准则上的最后一个元素
快速访问随机元素的最有效结构+一个准则上的最后一个元素
提问于 2015-10-21 12:22:37
我们有一个功能，被告知我们收到了一个特定时间戳的项目。
这样做的目的是等待对于一个特定的时间戳，我们等待接收我们期望的每一个项目，然后在我们与所有项目“同步”后进一步推送通知。
目前，我们有一个Dictionary<DateTime, TimeSlot>来存储非同步的TimeSlot(TimeSlot =为特定时间戳接收的所有项目的列表)。
//Let's assume that this method is not called concurrently, and only once per "MyItem"
public void HandleItemReceived(DateTime timestamp, MyItem item){
TimeSlot slot;
//_pendingTimeSlot is a Dictionary<DateTime,TimeSlot>
if(!_pendingTimeSlot.TryGetValue(timestamp, out slot)){
slot = new TimeSlot(timestamp);
_pendingTimeSlot.Add(timestamp,slot );
//Sometimes we don't receive all the items for one timestamps, which may leads to some ghost-incomplete TimeSlot
if(_pendingTimeSlot.Count>_capacity){
TimeSlot oldestTimeSlot = _pendingTimeSlot.OrderBy(t=>t.Key).Select(t=>t.Value).First();
_pendingTimeSlot.Remove(oldestTimeSlot.TimeStamp);
//Additional work here to log/handle this case
}
}
slot.HandleItemReceived(item);
if(slot.IsComplete){
PushTimeSlotSyncronized(slot);
_pendingTimeSlot.Remove(slot.TimeStamp);
}
}对于不同的项目组，我们有几个“同步器”的并行实例。
它工作得很好，除非系统负载很重，我们有更多不完整的TimeSlot，并且应用程序使用了更多的CPU。分析器似乎表明LINQ查询的Compare花费了大量时间(大部分时间)。因此，我试图找到一些结构来保存这些引用(替换字典)
以下是一些衡量标准：
- 我们有几个(变量，但在10到20个之间)实例。
- 同步器的当前最大容量(
_capacity)为500项。 - 两种不同时间戳之间的最短间隔为100 is (因此，每个同步器每秒新增10条字典条目)(大多数情况下是1项/秒以上)
- 对于每一个时间戳，我们期望收到300-500个项目。
因此，对于一个同步器，每秒(最坏的情况)：
- 1加
- 500 Get
- 3-5种
我最好的选择是什么？我对SortedDictionary进行了思考，但没有找到任何说明如何根据密钥获取第一个元素的文档。
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-10-21 13:28:27
您可以尝试的第一件事是消除OrderBy --您所需要的只是最小键，不需要对其进行排序：
if (_pendingTimeSlot.Count > _capacity) {
// No Enumerable.Min(DateTime), so doing it manually
var oldestTimeStamp = DateTime.MaxValue;
foreach (var key in _pendingTimeSlot.Keys)
if (oldestTimeStamp > key) oldestTimestamp = key;
_pendingTimeSlot.Remove(oldestTimeStamp);
//Additional work here to log/handle this case
}当然，SortedDictionary是一个选项，尽管它会消耗更多的内存。因为它是排序的，所以您可以使用简单的sortedDictionary.First()来获取带有最小键的键值对(因此在您的情况下是最老的元素)。
更新:这里的是一种混合方法，它使用字典进行快速查找，并为其他场景排序双链接列表。
class MyItem
{
// ...
}
class TimeSlot
{
public readonly DateTime TimeStamp;
public TimeSlot(DateTime timeStamp)
{
TimeStamp = timeStamp;
// ...
}
public bool IsComplete = false;
public void HandleItemReceived(MyItem item)
{
// ...
}
// Dedicated members
public TimeSlot PrevPending, NextPending;
}
class Synhronizer
{
const int _capacity = 500;
Dictionary<DateTime, TimeSlot> pendingSlotMap = new Dictionary<DateTime, TimeSlot>(_capacity + 1);
TimeSlot firstPending, lastPending;
//Let's assume that this method is not called concurrently, and only once per "MyItem"
public void HandleItemReceived(DateTime timeStamp, MyItem item)
{
TimeSlot slot;
if (!pendingSlotMap.TryGetValue(timeStamp, out slot))
{
slot = new TimeSlot(timeStamp);
Add(slot);
//Sometimes we don't receive all the items for one timestamps, which may leads to some ghost-incomplete TimeSlot
if (pendingSlotMap.Count > _capacity)
{
// Remove the oldest, which in this case is the first
var oldestSlot = firstPending;
Remove(oldestSlot);
//Additional work here to log/handle this case
}
}
slot.HandleItemReceived(item);
if (slot.IsComplete)
{
PushTimeSlotSyncronized(slot);
Remove(slot);
}
}
void Add(TimeSlot slot)
{
pendingSlotMap.Add(slot.TimeStamp, slot);
// Starting from the end, search for a first slot having TimeStamp < slot.TimeStamp
// If the TimeStamps almost come in order, this is O(1) op.
var after = lastPending;
while (after != null && after.TimeStamp > slot.TimeStamp)
after = after.PrevPending;
// Insert the new slot after the found one (if any).
if (after != null)
{
slot.PrevPending = after;
slot.NextPending = after.NextPending;
after.NextPending = slot;
if (slot.NextPending == null) lastPending = slot;
}
else
{
if (firstPending == null)
firstPending = lastPending = slot;
else
{
slot.NextPending = firstPending;
firstPending.PrevPending = slot;
firstPending = slot;
}
}
}
void Remove(TimeSlot slot)
{
pendingSlotMap.Remove(slot.TimeStamp);
if (slot.NextPending != null)
slot.NextPending.PrevPending = slot.PrevPending;
else
lastPending = slot.PrevPending;
if (slot.PrevPending != null)
slot.PrevPending.NextPending = slot.NextPending;
else
firstPending = slot;
slot.PrevPending = slot.NextPending = null;
}
void PushTimeSlotSyncronized(TimeSlot slot)
{
// ...
}
}其他一些用法：
从最老的到最新的：
for (var slot = firstPending; slot != null; slot = slot.NextPending)
{
// do something
}从最老到最新的迭代，并根据标准删除项：
for (TimeSlot slot = firstPending, nextSlot; slot != null; slot = nextSlot)
{
nextSlot = slot.NextPending;
if (ShouldRemove(slot))
Remove(slot);
}反向场景也是如此，但是使用lastPending和PrevPending成员代替。
Stack Overflow用户
发布于 2015-10-22 12:23:57
这是简单的样本。列表中的insert方法消除了交换元素。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
List<Data> inputs = new List<Data>() {
new Data() { date = DateTime.Parse("10/22/15 6:00AM"), data = "abc"},
new Data() { date = DateTime.Parse("10/22/15 4:00AM"), data = "def"},
new Data() { date = DateTime.Parse("10/22/15 6:30AM"), data = "ghi"},
new Data() { date = DateTime.Parse("10/22/15 12:00AM"), data = "jkl"},
new Data() { date = DateTime.Parse("10/22/15 3:00AM"), data = "mno"},
new Data() { date = DateTime.Parse("10/22/15 2:00AM"), data = "pqr"},
};
Data data = new Data();
foreach (Data input in inputs)
{
data.Add(input);
}
}
}
public class Data
{
public static List<Data> sortedData = new List<Data>();
public DateTime date { get; set; }
public string data { get; set;}
public void Add(Data newData)
{
if(sortedData.Count == 0)
{
sortedData.Add(newData);
}
else
{
Boolean added = false;
for(int index = sortedData.Count - 1; index >= 0; index--)
{
if(newData.date > sortedData[index].date)
{
sortedData.Insert(index + 1, newData);
added = true;
break;
}
}
if (added == false)
{
sortedData.Insert(0, newData);
}
}
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33259223
复制相关文章
相似问题
腾讯云开发者
