我有一个描述在某些时间发生的事件的元素列表,这些时间在对象上表示为Datetime属性“ StartTime”.我现在希望提取这些事件的子集,其中包含放置在两个DateTime实例A,B之间的时间间隔/中的那些元素,以使StartTime> = A&& StartTime< =B.目前,这是通过一个简单的Linq查询完成的,但是由于我必须运行很多查询以提取列表的一小部分,因此效率很低.
曾希望标准SortedList类在键上具有某种子集功能,但事实并非如此.如果可以使用现有框架类将其存档相对简单,是否有任何想法,或者我是否必须基于SortedList进行某种自定义二进制搜索？
解决方法:
如果可能的话,我会将实例保存在数组中,并按StartTime排序,然后调用BinarySearch以确定边界在数组中的索引.
然后,鉴于此,您可以轻松地根据日期范围快速访问子集.
我已经完成了一个通用类,该类也可以帮助您：
public class BinarySearcher<T>
{
// Possibly passed to the call to BinarySort.
private class ComparisonComparer : Comparer<T>
{
Comparison<T> comparison;
internal static IComparer<T> Create(Comparison<T> comparison)
{
// If comparison is null, return the default comparer for T.
if (comparison == null)
{
// Return the default.
return Comparer<T>.Default;
}
// Return a new implementation.
return new ComparisonComparer(comparison);
}
private ComparisonComparer(Comparison<T> comparison)
{
this.comparison = comparison;
}
public override int Compare(T x, T y)
{
return comparison(x, y);
}
}
// The elements.
T[] elements;
// The IComparable implementation.
IComparer<T> comparer;
// Do not assume sorting.
public BinarySearcher(IEnumerable<T> elements) :
this(elements, false, (IComparer<T>) null) { }
// Use default comparer.
public BinarySearcher(IEnumerable<T> elements, bool sorted) :
this(elements, sorted, (IComparer<T>) null) { }
// Assume no sorting.
public BinarySearcher(IEnumerable<T> elements,
Comparison<T> comparer) :
this(elements, false,
ComparisonComparer.Create(comparer)) { }
// Convert to IComparable<T>.
public BinarySearcher(IEnumerable<T> elements, bool sorted,
Comparison<T> comparer) :
this(elements, sorted,
ComparisonComparer.Create(comparer)) { }
// No sorting.
public BinarySearcher(IEnumerable<T> elements,
IComparer<T> comparer) :
this(elements, false, comparer) { }
// Convert to array.
public BinarySearcher(IEnumerable<T> elements, bool sorted,
IComparer<T> comparer) :
this(elements.ToArray(), sorted, comparer) { }
// Assume no sorting.
public BinarySearcher(T[] elements) : this(elements, false) { }
// Pass null for default comparer.
public BinarySearcher(T[] elements, bool sorted) :
this(elements, sorted, (IComparer<T>) null) { }
// Assume not sorted.
public BinarySearcher(T[] elements, Comparison<T> comparer) :
this(elements, false, ComparisonComparer.Create(comparer)) { }
// Create IComparable<T> from Comparable<T>.
public BinarySearcher(T[] elements, bool sorted,
Comparison<T> comparer) :
this(elements, sorted, ComparisonComparer.Create(comparer)) { }
// Assume the elements are not sorted.
public BinarySearcher(T[] elements, IComparer<T> comparer) :
this(elements, false, comparer) { }
public BinarySearcher(T[] elements, bool sorted,
IComparer<T> comparer)
{
// If the comparer is null, create the default one.
if (comparer == null)
{
// Set to the default one.
comparer = Comparer<T>.Default;
}
// Set the comparer.
this.comparer = comparer;
// Set the elements. If they are sorted already, don't bother,
// otherwise, sort.
if (!sorted)
{
// Sort.
Array.Sort(elements, this.comparer);
}
// Set the elements.
this.elements = elements;
}
public IEnumerable<T> Between(T from, T to)
{
// Find the index for the beginning.
int index = Array.BinarySearch(this.elements, from, comparer);
// Was the item found?
bool found = (index >= 0);
// If the item was not found, take the bitwise
// compliment to find out where it would be.
if (!found)
{
// Take the bitwise compliment.
index = ~index;
}
// If the item was found, cycle backwards from
// the index while there are elements that are the same.
if (found)
{
// Cycle backwards.
for (; index >= 0 &&
comparer.Compare(from, elements[index]) == 0;
--index) ;
// Add one to the index, since this is on the element
// that didn't match the comparison.
index++;
}
// Go forward now.
for ( ; index < elements.Length; index++)
{
// Return while the comparison is true.
if (comparer.Compare(elements[index], to) <= 0)
{
// Return the element.
yield return elements[index];
}
else
{
// Break
yield break;
}
}
}
}
这里的大多数是用来初始化该类的助手,这将需要一种比较两个项目的方法(此处采用IComparer< T&Comparable>).该类还允许您接收已排序的原始数组,以防您以后想要自己在适当位置添加/删除/更新元素(而不必一直求助于数组).
该类的主要内容是“之间”的呼叫.它采用from值,该值将传递给Array类的静态BinarySearch方法,并传递此实例使用的IComparer实现(如果未传入默认值,则假定为默认值).
如果该值不存在,它将找出该值在数组中的位置,然后在数组中存在多个具有相同值的元素的情况下向后循环.
然后,它向前循环,在当前元素小于或等于to值时返回枚举中的项目.
在您的特定情况下,假设您有这样的课程：
public class Task
{
public string Name;
public DateTime StartTime;
}
您可以执行以下操作：
// Create tasks.
Task[] tasks =
{
new Task() { Name = "Task 1", StartTime = new DateTime(2009, 02, 18) },
new Task() { Name = "Task 2", StartTime = new DateTime(2009, 02, 16) },
new Task() { Name = "Task 3", StartTime = new DateTime(2009, 02, 12) },
new Task() { Name = "Task 4", StartTime = new DateTime(2009, 02, 11) },
new Task() { Name = "Task 5", StartTime = new DateTime(2009, 02, 10) },
new Task() { Name = "Task 6", StartTime = new DateTime(2009, 02, 01) },
new Task() { Name = "Task 7", StartTime = new DateTime(2009, 02, 09) }
};
// Now create the indexer.
BinarySearcher<Task> searcher = new BinarySearcher<Task>(tasks,
(x, y) => Comparer<DateTime>.Default.Compare(x.StartTime, y.StartTime));
foreach (Task t in searcher.Between(
new Task() { StartTime = new DateTime(2009, 02, 13) },
new Task() { StartTime = new DateTime(2009, 02, 10) }))
{
// Write.
Console.WriteLine(t);
}