Одна из типовых задач при работе с коллекциями и массивами — выборка n элементов, начиная с i-того индекса, или же, как вариант, выборка элементов с i-того по j-й индекс. На языке C# с использованием методов-расширений библиотеки Linq решается она очень просто:
Для строк предусмотрен специальный метод Substing:
Часто начинающие разработчики изобретают свои велосипеды для подобных целей из-за недостающих знаний, поэтому на собеседованиях технические интервьюверы иногда задают вопросы по этой теме. В некоторых языках программирования также существует родственная и весьма интересная концепция срезов (slices), детальное пояснение которой с примерами следует далее.
Пускай дан массив букв, упорядоченных по алфавиту. Каждой букве соответствует не только привычный положительный индекс исчисляемый слева-направо (от головы), но и отрицательный, исчисляемый справа-налево (от хвоста):
UPDATE
Изначально был взят за основу способ индексации языка Python (второй параметр метода — индекс хвоста), однако в ходе обсуждений выяснилось, что это не оптимальное решение (использование длины [в том числе отрицательной] в качестве второго параметра даёт больше преимуществ), поэтому материал был обновлён.
Final Update
Implementation
Вот и пригодился нам yield. И совсем немного кода получилось. Мне нравится, а вам?
P.S. И это не всё, данная статья написана намеренно. Метод Slice — это маленькая часть из синтаксического сахара мощной и функциональной библиотеки Aero Framework, которая предоставляет абстракции и концепции более высокого уровня настолько филигранно согласованные между собой, что при должном терпении в изучении эта стройность вас поразит… Правда, код Aero Framework — это самое совершенное, что мне посчастливилось написать в жизни на текущий момент. А эта статья про циклические срезы и сдвиги только лишь замануха! Изучайте Aero Framework и вы его обязательно оцените.
var selectedItems = items.Skip(i).Take(n).ToArray();
var selectedItems = items.Skip(i).Take(j - i).ToArray();
Для строк предусмотрен специальный метод Substing:
var target = source.Substing(i, n);
var target = source.Substing(i, j - i);
var target = source.Substing(i); // from i to end
Часто начинающие разработчики изобретают свои велосипеды для подобных целей из-за недостающих знаний, поэтому на собеседованиях технические интервьюверы иногда задают вопросы по этой теме. В некоторых языках программирования также существует родственная и весьма интересная концепция срезов (slices), детальное пояснение которой с примерами следует далее.
Пускай дан массив букв, упорядоченных по алфавиту. Каждой букве соответствует не только привычный положительный индекс исчисляемый слева-направо (от головы), но и отрицательный, исчисляемый справа-налево (от хвоста):
var bodyLetters = new[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I'};
var headIndexes = new[] { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 };
var tailIndexes = new[] {-8 , -7 , -6 , -5 , -4 , -3 , -2 , -1 };
UPDATE
Изначально был взят за основу способ индексации языка Python (второй параметр метода — индекс хвоста), однако в ходе обсуждений выяснилось, что это не оптимальное решение (использование длины [в том числе отрицательной] в качестве второго параметра даёт больше преимуществ), поэтому материал был обновлён.
Вариант метода Slice с индексацией языка Python (второй параметр - индекс хвоста)
Выбор элементов с четвёртого по седьмой включительно можно осуществить несколькими способами:
Хвост удобно не включать, поскольку длина выборки тогда легко вычисляется по индексам без лишнего инкремента на единицу и не вызывает путаницы (5-2 = 3 вместо 5-2+1 = 4)
Но возникает вопрос, как в таком случае включить последний элемент исходной коллекции в результирующую выборку, ведь элемента с индексом 8 нет, а отрицательного соответствия ему даже не найти (разве что целочисленный -0, который не отличить от +0)? Тут возникает некоторая рассогласованность. Конечно, можно сделать включение хвоста, усложнив вычисление длины, либо искусственно использовать индексы за пределами массива, как поступили, например, в языке Python.
Чтобы принять оптимальное решение, давайте рассмотрим и другие моменты, как должен вести себя метод, когда индекс хвоста находится раньше индекса головы?
Самые элементарные решения — выдать пустую выборку, бросить исключение или же толерантно поменять индексы хвоста и головы местами, а затем продолжить обработку, быть может, вывести результирующую выборку в обратном порядке?
А как поступить, когда индексы хвоста и головы совпадают? По нашим правилам мы включаем голову, но исключаем хвост, однако в таком случае хвост и голова — это одно и то же! Возникает логическое противоречие. Возвращаться к случаю с включением хвоста?
Давайте подумаем… Что если замкнуть, зациклить массив сам на себя? То есть предположить, что сразу за последним индексом 7 идёт снова 0, и если передать в метод, скажем, параметры 6 и 2, то вывести следующий результат 'G', 'I', 'A', 'B'. Тогда чтобы включить последний элемент исходной коллекции в выборку достаточно написать Slice(6, 0) // 'G' 'I', а запись Slice(5, 5) приведёт к тому, что мы получим исходную коллекцию циклически сдвинутую на пять индексов влево — 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E' — вот чудо!
Для того чтобы получить один элемент нужно написать Slice(5, 6), плюс никаких трудностей с отрицательными индексами, а если вдруг выйдем за границы массива, то получим ожидаемое исключение. Как красиво всё получилось! Если же вдруг потребуется вывести срезанную выборку в обратном порядке, то метод Reverse в помощь. Мы нашли общее решение сразу для двух классов задач лишённое противоречий и очень естественное…
Что ж, осталось его реализовать!
// хвост не включается в результат
bodyLetters.Slice(3, 7); // 'D', 'E', 'F', 'G'
bodyLetters.Slice(-5, 7); // 'D', 'E', 'F', 'G'
bodyLetters.Slice(3, -1); // 'D', 'E', 'F', 'G'
bodyLetters.Slice(-5, -1); // 'D', 'E', 'F', 'G'
Хвост удобно не включать, поскольку длина выборки тогда легко вычисляется по индексам без лишнего инкремента на единицу и не вызывает путаницы (5-2 = 3 вместо 5-2+1 = 4)
Но возникает вопрос, как в таком случае включить последний элемент исходной коллекции в результирующую выборку, ведь элемента с индексом 8 нет, а отрицательного соответствия ему даже не найти (разве что целочисленный -0, который не отличить от +0)? Тут возникает некоторая рассогласованность. Конечно, можно сделать включение хвоста, усложнив вычисление длины, либо искусственно использовать индексы за пределами массива, как поступили, например, в языке Python.
Чтобы принять оптимальное решение, давайте рассмотрим и другие моменты, как должен вести себя метод, когда индекс хвоста находится раньше индекса головы?
bodyLetters.Slice(7, 3); // ???
bodyLetters.Slice(-1, -5); // ???
Самые элементарные решения — выдать пустую выборку, бросить исключение или же толерантно поменять индексы хвоста и головы местами, а затем продолжить обработку, быть может, вывести результирующую выборку в обратном порядке?
А как поступить, когда индексы хвоста и головы совпадают? По нашим правилам мы включаем голову, но исключаем хвост, однако в таком случае хвост и голова — это одно и то же! Возникает логическое противоречие. Возвращаться к случаю с включением хвоста?
Давайте подумаем… Что если замкнуть, зациклить массив сам на себя? То есть предположить, что сразу за последним индексом 7 идёт снова 0, и если передать в метод, скажем, параметры 6 и 2, то вывести следующий результат 'G', 'I', 'A', 'B'. Тогда чтобы включить последний элемент исходной коллекции в выборку достаточно написать Slice(6, 0) // 'G' 'I', а запись Slice(5, 5) приведёт к тому, что мы получим исходную коллекцию циклически сдвинутую на пять индексов влево — 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E' — вот чудо!
Для того чтобы получить один элемент нужно написать Slice(5, 6), плюс никаких трудностей с отрицательными индексами, а если вдруг выйдем за границы массива, то получим ожидаемое исключение. Как красиво всё получилось! Если же вдруг потребуется вывести срезанную выборку в обратном порядке, то метод Reverse в помощь. Мы нашли общее решение сразу для двух классов задач лишённое противоречий и очень естественное…
// хвост не включается в результат
bodyLetters.Slice(6, 2); // 'G', 'I', 'A', 'B'
bodyLetters.Slice(5, 5); // 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E'
bodyLetters.Slice(5, 5, SliceOptions.Lazy); // {empty}
bodyLetters.Slice(5, 6); // 'F'
bodyLetters.Slice(5, 0); // 'F', 'G', 'I'
bodyLetters.Slice(5); // 'F', 'G', 'I'
Что ж, осталось его реализовать!
[Flags]
public enum SliceOptions
{
None = 0,
Lazy = 1,
}
public static IEnumerable<T> Slice<T>(
this IEnumerable<T> collection,
int head,
int tail = 0,
SliceOptions options = SliceOptions.None)
{
var items = collection as T[] ?? collection.ToArray();
var count = items.Count();
head = head < 0 ? count + head : head;
tail = tail < 0 ? count + tail : tail;
if (head < 0 || count - 1 < head) throw new ArgumentOutOfRangeException("head");
if (tail < 0 || count - 1 < tail) throw new ArgumentOutOfRangeException("tail");
if (head == tail && (options & SliceOptions.Lazy) == SliceOptions.Lazy)
{
yield break;
}
if (head < tail)
{
foreach (var item in items.Skip(head).Take(tail - head))
{
yield return item;
}
}
else
{
foreach (var item in items.Skip(head))
{
yield return item;
}
foreach (var item in items.Skip(0).Take(tail))
{
yield return item;
}
}
}
Update 2
public static IEnumerable<T> Turn<T>(this IList<T> items, int skip, int turnsCount = 0)
{
var reverse = skip < 0;
var count = items.Count;
skip = reverse ? count + skip : skip;
var take = turnsCount == 0
? reverse ? -skip - 1 : count - skip
: count*turnsCount;
return items.Ring(skip, take);
}
public static IEnumerable<T> Ring<T>(this IList<T> items, int skip, int take)
{
var reverse = take < 0;
var count = items.Count;
skip = skip < 0 ? count + skip : skip;
skip = skip < count ? skip : skip%count;
take = reverse ? -take : take;
for (var i = 0; i < take; i++)
{
var j = i < count ? i : i%count;
var index = reverse ? skip - j : skip + j;
index = index < 0 ? count + index : index;
index = index < count ? index : index%count;
yield return items[index];
}
}
private static void Main(string[] args)
{
var bodyLetters = new[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I'};
var headIndexes = new[] { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 };
var tailIndexes = new[] {-8 , -7 , -6 , -5 , -4 , -3 , -2 , -1 };
// 'C', 'D', 'E', 'F', 'G', 'I', 'A', 'B',
bodyLetters.Ring(2, 8).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'C', 'B', 'A', 'I', 'G', 'F', 'E', 'D',
bodyLetters.Ring(2, -8).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'D', 'E', 'F', 'G'
bodyLetters.Ring(3, 4).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'D', 'E', 'F', 'G'
bodyLetters.Ring(-5, 4).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'D', 'C', 'B', 'A'
bodyLetters.Ring(-5, -4).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'D', 'E', 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I', 'A', 'B', 'C'
bodyLetters.Ring(3, 16).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'D', 'C', 'B', 'A', 'I', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'G', 'F', 'E'
bodyLetters.Ring(-5, -16).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'D', 'E', 'F', 'G', 'I'
bodyLetters.Turn(3).ToList().ForEach(Console.Write);
Console.WriteLine();
// 'D', 'C', 'B', 'A'
bodyLetters.Turn(-5).ToList().ForEach(Console.Write);
Console.WriteLine();
Console.ReadKey();
}
Final Update
private static void Main(string[] args)
{
var bodyLetters = new[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I'};
var headIndexes = new[] { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 };
var tailIndexes = new[] {-8 , -7 , -6 , -5 , -4 , -3 , -2 , -1 };
// CDEFGICDEF
bodyLetters.SkipByRing(18).TakeByRing(10).ToList().ForEach(Console.Write);
Console.WriteLine();
// FEDCBAFEDC
bodyLetters.SkipByRing(-18).TakeByRing(10).ToList().ForEach(Console.Write);
Console.WriteLine();
// IGFEDCIGFE
bodyLetters.SkipByRing(18).TakeByRing(-10).ToList().ForEach(Console.Write);
Console.WriteLine();
// ABCDEFABCD
bodyLetters.SkipByRing(-18).TakeByRing(-10).ToList().ForEach(Console.Write);
Console.WriteLine();
Console.WriteLine();
// CDEFGIABCD
bodyLetters.SliceByRing(18, 10).ToList().ForEach(Console.Write);
Console.WriteLine();
// GIABCDEFGI
bodyLetters.SliceByRing(-18, 10).ToList().ForEach(Console.Write);
Console.WriteLine();
// BAIGFEDCBA
bodyLetters.SliceByRing(18, -10).ToList().ForEach(Console.Write);
Console.WriteLine();
// FEDCBAIGFE
bodyLetters.SliceByRing(-18, -10).ToList().ForEach(Console.Write);
Console.WriteLine();
Console.ReadKey();
}
Implementation
// ReSharper disable PossibleMultipleEnumeration
// ReSharper disable LoopCanBePartlyConvertedToQuery
public static IEnumerable<T> SkipByRing<T>(this IEnumerable<T> source, int count)
{
var originalCount = 0;
var reverse = count < 0;
count = reverse ? -count : count;
source = reverse ? source.Reverse() : source;
while (true)
{
if (originalCount > 0) count %= originalCount;
foreach (var item in source)
{
originalCount++;
if (count > 0)
{
count--;
continue;
}
yield return item;
}
if (count == 0) yield break;
}
}
public static IEnumerable<T> TakeByRing<T>(this IEnumerable<T> source, int count)
{
var reverse = count < 0;
count = reverse ? -count : count;
source = reverse ? source.Reverse() : source;
while (true)
{
foreach (var item in source)
{
if (count > 0)
{
count--;
yield return item;
}
}
if (count == 0) yield break;
}
}
public static IEnumerable<T> SliceByRing<T>(this IEnumerable<T> source, int skipCount, int takeCount)
{
var originalCount = 0;
var skipReverse = skipCount < 0;
var takeReverse = takeCount < 0;
skipCount = skipReverse ? -skipCount : skipCount;
takeCount = takeReverse ? -takeCount : takeCount;
source = takeReverse ? source.Reverse() : source;
if (skipReverse ^ takeReverse)
{
var count = source.Count();
skipCount = count - skipCount % count;
}
while (true)
{
if (originalCount > 0) skipCount %= originalCount;
foreach (var item in source)
{
originalCount++;
if (skipCount > 0)
{
skipCount--;
continue;
}
if (takeCount > 0)
{
takeCount--;
yield return item;
}
}
if (takeCount == 0) yield break;
}
}
Вот и пригодился нам yield. И совсем немного кода получилось. Мне нравится, а вам?
P.S. И это не всё, данная статья написана намеренно. Метод Slice — это маленькая часть из синтаксического сахара мощной и функциональной библиотеки Aero Framework, которая предоставляет абстракции и концепции более высокого уровня настолько филигранно согласованные между собой, что при должном терпении в изучении эта стройность вас поразит… Правда, код Aero Framework — это самое совершенное, что мне посчастливилось написать в жизни на текущий момент. А эта статья про циклические срезы и сдвиги только лишь замануха! Изучайте Aero Framework и вы его обязательно оцените.
lair
А мне — нет.
Что в этом искусственного?
Это, гм, не интуитивно. То есть вот вообще.
Впрочем, дело даже не в этом. Дело в том, что — как видно из вашей реализации — вы не поняли, что такое слайс. Слайс — это «окно» в массив, не создающее его копии. Иными словами, когда я говорю
arr.Slice(5), я ожидаю получить обертку поверх этого массива, которая нулевой элемент которой будет вести на пятый элемент исходного массива, с минимум дополнительных расходов. (Enter ArraySegment, ну да ладно...) Поверх последовательностей слайсы вообще особого смысла не имеют. А вы сначала делаете принудительную материализацию пришедшей вам коллекции в массив (даже дляIList<T>, да). Мне страшно подумать, что происходит с производительностью.Makeman
На вкус и цвет товарищей нет.
Возможно, да, это не совсем тот слайс, о котором вы думаете, но сам метод Slice не создаёт никаких копий, а только лишь выполняет итерацию. Назовём это модификацией, суть же очень схожа.
Шаг var items = collection as T[] ?? collection.ToArray() я оставил осознанно, поскольку метод расчитан в большинстве своём на материализованные коллекции, а если вас это пугает, то сделайте свою реализацию без отрицательных индексов и проверки длины. Не трудно.
lair
Как вы сделаете циклическую итерацию по бесконечной последовательности?
Меня не пугает, но вы же спрашиваете мнение про статью?
Makeman
Не знаю, как у вас, но в подавляющем большинстве случаев обрабатываются конечные коллекции. За всю мою практику ни разу не доводилось обрабатывать бесконечную. Разве что на собеседовании была задачка, как обнаружить возможную зацикленность в бесконечном однонаправленном списке.
Я же вас не спрашиваю, как вы вызовете метод Count() у бесконечной последовательности… Вопрос сродни вашему.
lair
… размер которой заранее не известен, а материализация которой может быть очень дорогой. Это в моем «подавляющем большинстве случаев».
Makeman
метод не рассчитан на такие коллекции. это то же самое, как случайно вызвать Count(), ToList() или ToArray() у запроса с милионами результатов. вы же не отказываетесь от использования этих методов только из-за того, что они несут в себе такую потенциальную опасность повесить ваше приложение.
lair
У меня, кстати, есть встречный вопрос: а зачем вам вообще в подавляющем большинстве случаев превращение коллекции в кольцо?
Makeman
Наглядные примеры в статье. Конечно, каждый день таких необходимотей возникать не будет, но сдвиги элементов в массивах — распостранённое явление и, как видим, это частный случай выполнения «среза», поэтому логично и красиво обобщить эти операции в один метод, на мой взгляд.
lair
Не, в статье нет ни одного примера зачем — иными словами, какую бизнес-задачу это решает.
Что вы понимаете под сдвигами элементов массивах?
Makeman
Тогда воспринимайте это как абстрактную математическую конструкцию, которой пока ещё не нашлось применения :)
Мне эта штука показалась стройной и красивой, заставила немного пошевелить мозгом, поэтому решил поделиться ею с другими людьми. Быть может, кто-то и найдёт для себя практическую ценность в ней.
По крайней мере, как задачка для развития логики мышления, она очень подходит…
lair
А для абстрактной математической конструкции она недостаточно строга. В особенности по сравнению с совершенно банальной и напрашивающейся здесь работой по модулю.
Makeman
Ок, назовём это всё интеллектуальным упражнением, а не математической моделью ;)
qw1
Было бы математически красиво, если бы любая композиция слайсов
arr.Slice(a,b).Slice(c,d)...сводилась бы по сложности и потребляемой памяти к одному слайсу, и чтобы оптимально работалиLast(),LastOrDefault()за время O(1).Была бы достойная библиотека. Наивная реализация из статьи никому не нужна.
Oxoron
А разве extension метод Slice(a,b) с теми же Linq.Skip(), Linq.Take() внутри не решит проблему за O(1)? Они же не сразу вычисляются, а по запросу.
Создать аналог Last() для массива не проблема, для List — можно, в общем случае невозможно.
Makeman
Вот именно, что решит. Только пропадут отрицательные индексы и возможность зацикливания, да и не намного лучше будет выглядеть, чем items.Skip(i).Take(n). =)
qw1
В этом и претензия, что методы из LINQ умеют оптимально работать в композициях, а также умеют оптимально вычислять Last() и Count() в специальных случаях. Автор упоминает Aero Framework, если это framework, он должен удовлетворять самым высоким стандартам качества.
Makeman
Конечно, если мы пишем свою реализацию IEnumerable, которая при выполнении Last() и Count() вместо того, чтобы загружать весь список с данных с сервера или БД, будет транслировать это в соответствующий запрос (например, атомарный для Count) и загружать только нужную часть (виртуализация), то да — это будет оптимально. Но стандартные реализации List, Array и прочие ничего подобного не могут.
Или вы что-то другое подразумеваете под специальными случаями?
qw1
Я хочу, пользуясь фрейворком, вызывать Slice и дальше take/last/count на любых enumerables, и чтобы на массивах и списках работал оптимальный для них вариант. А на остальных, пусть даже бесконечных генераторах, пессимистичный, но корректный.
Ведь что мешает вызвать Slice(100, 200) на бесконечной выборке, если я хочу получить конечное «окно»
Makeman
Именно в этом случае, на мой взгляд, проще и лучше использовать связку skip-take.
Каждый метод имеет свои преимущества и недостатки в зависимости от условий и целей использования, но когда мы стремимся сделать единый совершенно универсальный метод на все случаи жизни, то зачастую излишне усложняем реализацию, теряем контроль и гибкость, получая лишь сомнительный выигрыш в распространённых ситуациях, но значительный проигрыш в предельных, по моему мнению.
lair
А он после этого позволит индексацию за O(1)?
Oxoron
Что Вы подразумеваете под индексацией? Создание индекса? Поиск по индексу? Вы про какую-то конкретную коллекцию .NET, любую IEnumerable, или данные, которые будут вытягиваться из БД?
Плюс, в комментарии выше не было упоминания про индексацию.
lair
arr[i]Oxoron
Не понял.
IEnumerable collection = GetNewCollection(); // Берем мы произвольную коллекцию
string anyString = collection.Take(n)[0]; // А вот тут ошибка, ибо какой нафиг индекс на IEnumerable?
lair
Вот поэтому
Slice— это неTake. Если быть совсем педантом, определятьSliceповерх последовательностей вообще не надо. Но если очень хочется обобщенной версии, то надо поддерживать хотя быElementAtза O(1) (чего LINQ «из коробки» не делает).Oxoron
ElementAt за O(1) невозможен на IEnumerable в общем случае. Как пример, наш Next возвращает случайное число.
иВ итоге да, определять Slice с Вашими требованиями не получится.
Другое дело, что изначально разговор шел о
Оптимальность Last недостижима в общем случае. Сложность композиции Take-Skip слайсов равна сложности одного слайса. Насчет памяти сомневаюсь, тут зависит от упрощения Expression Tree, но она скорее всего это требование не важно.
Сделать Slice индексированным на массивах и списках можно. В общем случае — невозможно.
Идея с замыканием массива в кольцо известна, её применение сильно зависит от логики. Если не ошибаюсь, Вы уже упоминали про остатки по модулю. В итоге, если и добавлять закольцовку, то под контролем отрицательного по умолчанию аргумента.
Думаю, на этом стоит закончить. Или продолжить в личке.
lair
Но — и это важно — можно написать такую реализацию, которая будет O(1) для коллекций, которые это позволяют, и «столько, сколько в обычном Enumerable» для всех остальных коллекций; причем это будет происходить прозрачно для пользователя. Собственно, это единственный смысл писать Slice, а не пользоваться Skip/Take.
Makeman
Насчёт же интуитивности, достаточно один раз принять зацикленность (замкнутость) коллекции и всё становится на свои места, причём автоматически устраняются многие противоречия, возникающие без этого положения, а функционал метода только расширяется ничего не утрачивая.
lair
Особенно это для
IEnumerableлегко принять, ага.Но вообще, круто.
(1) Сначала вы пишете, что «хвост удобно не включать, поскольку длина выборки тогда легко вычисляется по индексам без лишнего инкремента на единицу и не вызывает путаницы», а потом делаете такой механизм, при котором длина выборки вообще не вычислима из индексов (какова длина выборки (5,5)?).
(2) Как именно из вашей реализации получается, что (5,6) вернет пустую выборку?
Я, наверное, чего-то не понимаю, но будет выбран ровно один элемент.
(3) предположим, что я не понимаю чего-то в предыдущем коде, и там не будет выбрано ни одного элемента. Как тогда выбрать один элемент?
Makeman
Спасибо, разобрались, заметили ошибку! Мой косяк, исправлю. Да, будет один элемент. Пустого результата нет.
lair
… а как же получить пустой слайс?
Makeman
а он нужен?
вот так
теперь всё становится логично?
lair
Нужен, конечно. Это базовый случай для алгоритма.
Конечно, нет. Вы придумали новую нотацию для интервалов на последовательности, но, как обычно, забыли про базовый случай.
Makeman
Я знаю, что вас не убедить :)
Но спасибо, что приняли участие и указали на неточность в статье!
Соглашусь с вами, что это больше напоминает способ нотации и понятие «пустой слайс» в нём не определено. Но и такая нотация даёт некоторые преимущества. Конечно, довольно просто добавить нужный флаг (useShift по умолчанию равный true) и в случае Slice(5, 5, false) возвращать вместо сдвига пустое значение, если это нужно.
Makeman
Сходил в магазин, поразмыслил, и на ум пришла идея:
Быть может, это решит вашу проблему? Не вижу ничего плохого в таком способе =)
lair
Нет, не решит. А плохого в этом способе то, что теперь я должен использовать две разных нотации, и помнить, что я сам между ними переключаюсь.
poemmuse
del
lair
Ого, виртуал makeman?
poemmuse
Извиняюсь, poemmuse — это старый аккаунт, случайно под ним оставил комментарий.
Makeman
Хорошенько подумал над вашим замечанием и понял, что оно из разряда вещей подобных флагу RemoveEmptyEntries у метода string.Split() либо квантификаторам «ленивого» и «жадного» захвата в регулярных выражениях, указывающим, наибольшее или наименьшее по длине вхождение нужно искать. Поэтому, чтобы метод Slice стал функционально полным, достаточно ввести
И слегка модифицировать сам метод
lair
Угу, теперь внезапно флаг влияет на поведение в граничном случае, когда индексы совпадают, и ни в каком другом. Флаги сами по себе-то зло, а уж неконсистентные флаги — так и точно.
Makeman
По-моему, ничего в этом страшного нет. Как вы, например, без флага-квантификатора разрулите в регулярном выражении «жадный» захват использовать или «ленивый», а тут очень похожая ситуация — выбрать все элементы или ни одного.
lair
В неконсистентности-то?
Вообще-то, в регулярках жадный или ленивый захват — это не флаг, а символ в выражении.
Makeman
А это по сути не одно и то же?
При создании регулярного выражения мы можем указать флаг RegexOptions.IgnoreCase, вместе с тем можем не указывать, а использовать inline character i — результат тот же.
Конечно, если вы видите другие пути к консистентности, то можете их предложить, я со своей колокольни рассуждаю :)
lair
Конечно, нет.
Флаг хуже. Если вам интересно, почему — вот статья Фаулера.
Конечно, вижу. Либо использовать полуоткрытые интервалы и не пытаться сделать из последовательности кольцо, либо использовать старт+длину и тогда ходите по кольцу сколько хотите.
Makeman
Хорошо, соглашусь, что с флагами нужно быть осторожным.
Обдумал идею насчёт длины в качестве второго параметра, и понимаю, что это отличный подход. В статье я взял за ориентир индексацию слайсов языка Питон, что наложило некоторые ограничения. С длиной же можно вывести ещё дополнительный ряд обобщений, например, проходить коллекцию по несколько раз и копировать её, а также использовать отрицательную длину для обхода в обратном направлении.
lair
Теперь это окончательно перестало иметь какое-то отношение к слайсам. Ну и да, зачем вам нужны все эти кольца, я так и не понимаю.
lair
BTW, реализовать «кольцо вперед» можно с помощью Skip/Take и одного тривиального расширения RepeatInfinite.
Makeman
Меня больше интересуют не сами слайсы, а обобщённые алгоритмы. Как вам такая реализация?
В ней слайсы и сдвиги лишь частные случаи колец с прямым и обратным обходом.
lair
Я не вижу смысла в обобщенных алгоритмах до тех пор, пока не определен круг задач, решаемых алгоритмом. Предварительное обобщение — грех не лучше предварительной оптимизации.
(Ну и да, делать из
IListIEnumerable— это плохой обобщенный алгоритм. Особенно когда вы потом всегда делаетеToList. И заранее закладывать в операциюRingсдвиги — тоже плохой обобщенный алгоритм, он противоречит принципу функциональной композиции, заложенной в LINQ.)Makeman
ToList я делаю лишь для того, чтобы сэкономить строчки кода в тестовом примере и только (встроенный метод ForEach() есть только у List), поэтому он здесь не обязателен.
Если изложенный метод и нарушает функциональную композицию, то вы можете скрыть (инкапсулировать) его, а предоставить несколько открытых методов-обёрток, которые работают на обобщённом алгоритме, поэтому сам алгоритм нисколько не теряет своей ценности.
lair
Это не решит проблему того, что нижний метод некомпонуем. Вот наоборот, когда базовый метод компонуем, вокруг него можно писать любые врапперы, используя нужную композицию.
Это если предположить, что она у него есть. В вашем случае это неочевидно дважды: во-первых, непонятно, какую задачу вы решаете, во-вторых, ваша текущая реализация все равно неоптимальна.
Makeman
Конечно, у вас может быть своё мнение, но я сторонник написания одного метода пригодного для решения обобщённой задачи, чем нескольких методов для каждого родственного частного случая.
Понимаю, что в обобщённой версии есть несколько дополнительных булевых проверок, но всё же их влияние не столь велико на производительность.
Разве что
в цикле, возможно, имеет смысл разделить на два цикла, хотя это лучше проверить на практике.
lair
Вы серьезно не понимаете, как работает функциональная композиция?
arr.Ring().Skip(5).Take(2)лучше чемarr.Ring(5, 2).Ну да, а тот маленький факт, что на входе у вас был IList, по которому работал ElementAt за O(1), а на выходе у вас IEnumerable, где та же операция стоит O(n), никого, конечно, не волнует.
(при этом это можно реализовать за O(1), причем даже не очень сложно)
Makeman
Решения я генерирую в реальном времени, поэтому появление недочётов вполне закономерно.
Вы можете предложить свои оптимизации, мне самому интересно. Менять тип возвращаемого значения я не вижу смысла, так как сам метод Ring внутри срабатывает за O(1), а на выходе при необходимости можно сделать как ToList(), так и ToArray().
Также придумал последнее обобщение с количеством оборотов =)
Если число оборотов 0, то берётся срез от элемента до конца либо в обратном направлении до начала коллекции, в зависимости от типа отсчёта.
Если число оборотов не 0, то берётся несколько оборотов от элемента в прямом либо обратном направлении, в зависимости от знака числа оборотов.
lair
Так может надо подумать немножко дольше, чтобы недочетов не было?
А зря.
… которые тоже будут работать за O(n), только теперь n — не порядковый номер элемента, а общее число элементов, плюс еще и займет O(n) дополнительной памяти.
А смысл? Лучше не стало, все предыдущие проблемы остались в полный рост.
Серьезно, посмотрите на то, как работает функциональная композиция.
Makeman
Тогда бы я отвечал на ваши комментарии раз в день и прогресс шёл значительно медленнее.
Кстати, придумал практическое приложение методам Ring и Turn. К примеру, вы делаете UI, и у вас есть коллекция-заглушка с n-элементами, вдруг вы захотели проверить, как работает UI при 2n, 3n, ...mn элементах. Вам достаточно написать что-то вроде Items = _testItems.Ring(0, m).ToList() и всё.
Удобно же, не находите? )
lair
Зато возможно с первого раза бы все правильно сделали, и не надо было бы из пустого в порожнее переливать.
Когда я что-то тестирую, я обычно использую AutoFixture. Проще и надежнее. Но даже если нет, то:
Если очень хочется, можно свернуть в extension-метод (поверх чистого Enumerable).
Собственно, наглядная разница между кольцом и простым повтором.
Makeman
Как вам такой способ?
lair
Да все так же. Вы, похоже, не понимаете, что все, что касается колец, должно исчерпываться
После чего мы получаем бесконечную закольцованную последовательность (обычный IEnumerable). Бонусные баллы получит та реализация, в которой результат будет позволять «быстрые» (O(1)) операции там, где это позволяла исходная (например, если стартом был массив, то ElementAt, Skip и так далее должны быть «быстрыми»).
Соответственно, про слайсы я уже все говорил: особого смысла делать слайсы по последовательностям нет. Но если очень хочется, то надо реализовывать такой вариант, при котором для «обычных» последовательностей слайс будет эквивалентен Skip/Take, а для «индексированных» — ArraySegment.
Makeman
Замечу насчёт композиции функций, что SkipByRing(x).TakeByRing(y) в кольцевом обобщении не равнозначно SliceByRing(x,y), хотя в простых случаях, когда нет полного обхода кольца, они дают идентичный результат.
Iceg
Почему пустая будет, а не 'F'?
items.Skip(5).Take(1);
И соглашусь с lair, совсем не интуитивно, даже хуже — запутанно. Вы же сами и запутались :)
Makeman
Про пустую выборку я соврал, извините, будет один элемент.
Уже это исправил, надеюсь, теперь всё стало на свои места.
По шестой включительно (или по седьмой, не включая, как в коде)
Спасибо, что внимательно читаете и обнауживаете неточности!
Iceg
Да, по седьмой. Включительно.
Makeman
Да, снова моя неточность. Исправил, спасибо! Но теперь уж, думаю, всё точно :)
IL_Agent
А где тут путаница? Голову включаем, а хвост нет — это скорее ведёт к путанице. Написанное далее в статье является тому подтверждением.
Makeman
Почему же в реализации Питона хвост не включается? ) Кто-то тоже напутал?
IL_Agent
Не знаю. Расскажите, пожалуйста. Неужели только для того, чтобы «вызывающий путаницу» инкремент не делать? ))
Makeman
Я это вижу так, но ваш вопрос лучше задать архитекторам языка Питон, зачем ещё такое могло понадобиться? )
Makeman
Материал обновлён.