Здравствуйте, Sinix, Вы писали:
S>Народ, ай нид хелп! S>Наконец добил черновой вариант CompositeRange<T> — штуки для операций над составными диапазонами.
А можно сразу вопрос — чем это лучше просто Range<T>[]?
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>А можно сразу вопрос — чем это лучше просто Range<T>[]?
Только готовыми операциями над наборами диапазонов, больше ничем. А, ну и null ref exception не будет
Понятно, что то же самое можно сделать и методами-расширениями поверх Range<T>[], но тогда операции получаются дороговастыми.
Для CompositeRange можно срезать кучу углов, т.к. поддиапазоны отсортированы + известны общие границы всего диапазона, для массива всё скатывается к полному перебору и к O(n^2) в самом запущенном случае.
Здравствуйте, Sinix, Вы писали:
AVK>>А можно сразу вопрос — чем это лучше просто Range<T>[]? S>Только готовыми операциями над наборами диапазонов, больше ничем.
Известное правило Мейера говорит, что все методы, которые можно сделать свободными функциями, нужно сделать свободными функциями.
S>Для CompositeRange можно срезать кучу углов, т.к. поддиапазоны отсортированы
Ну то есть фишка в том, что внутри диапазоны всегда отсортированы? Тогда понятно.
Из того что мне требовалось:
1) Мне нужен механизм ассоциаций с диапазонами некоей допинформации. Т.е. Range<T, TValue>
2) Алгоритм, который гарантирует отсутствие наложения диапазонов, но при этом все границы должны сохраняться, т.е. это не просто мердж. К этому еще необходимо склеивать допинформацию (Т.е. на входе Range<T, TValue>[], на выходе Range<T, TValue[]>[]). Вот как оно выглядит у меня (я, вроде, уже постил):
internal static IEnumerable<RangeDescriptor> NormalizeRanges(IEnumerable<Transition> source)
{
var ranges =
source
.SelectMany(t => t.Ranges.Select(r => new {r.Start, r.End, t.Target}))
.ToArray();
var points =
ranges
.SelectMany(
r =>
new[]
{
new {Pos = (int)r.Start, Targets = new List<State>()},
new {Pos = r.End + 1, Targets = new List<State>()}
})
.OrderBy(p => p.Pos)
.ToArray();
foreach (var range in ranges)
foreach (var point in
points
.SkipWhile(p => p.Pos < range.Start)
.TakeWhile(p => p.Pos <= range.End))
point.Targets.Add(range.Target);
return
points
.Zip(points.Skip(1), (p1, p2) => new {Start = p1, End = p2})
.Where(r => r.Start.Targets.Any() && r.Start.Pos < r.End.Pos)
.Select(
r =>
new RangeDescriptor(
new CharRange(
(ushort) r.Start.Pos,
(ushort) (r.End.Pos - 1)),
r.Start.Targets.ToArray()));
}
AVK>Из того что мне требовалось: AVK>1) Мне нужен механизм ассоциаций с диапазонами некоей допинформации. Т.е. Range<T, TValue>
Уже есть, прям в стартовом сообщении пример.
AVK>2) Алгоритм, который гарантирует отсутствие наложения диапазонов, но при этом все границы должны сохраняться, т.е. это не просто мердж.
Для проверки — тоже есть, свойство IsMerged.
Для получения всех взаимопересечений поддиапазонов есть GetIntersections(), если не оно — подумаю позже (вечер, влом уже).
Здравствуйте, Sinix, Вы писали:
S>Уже есть, прям в стартовом сообщении пример.
Прекрасно.
S>Для получения всех взаимопересечений поддиапазонов есть GetIntersections(), если не оно — подумаю позже (вечер, влом уже).
Посмотри по последней ссылке, там более полное объяснение требований. Можно ли их реализовать через GetIntersections я так сходу не могу сказать. Так вроде похоже, хотя неплохо было бы вариант добавить с проекцией вместо готовой структурки RangeIntersections. Ну и мой алгоритм (он основан на том что Коля предложил
Здравствуйте, AndrewVK, Вы писали:
S>>Для получения всех взаимопересечений поддиапазонов есть GetIntersections(), если не оно — подумаю позже (вечер, влом уже). AVK>Посмотри по последней ссылке, там более полное объяснение требований.
Я посмотрел — оно и есть по-моему.
Результаты вот тут.
AVK>Ну и мой алгоритм (он основан на том что Коля предложил
) вроде бы покороче, не?
Я в него пока не вьехал (и не пытался мозг уже всё), но по-моему он не будет работать с произвольными типами границ.
Ну и твой O(n^2) (если я нигде не протупил) против моего варианта (O(n*log(n)) и +log(n) по памяти) тож как-то не ок. Но это уже десятый-сотый вопрос, сначала надо с поведением определиться, а затем уже код ускорять.
А то некоторые требования (например, разрешать кучу одинаковых диапазонов с разными ключами и не учитывать порядок ключей при сравнении) здорово по производительности бьют и ничего с этим не сделаешь.
