Makeman 9 дек 2015 в 16:01

Циклические срезы, сдвиги и вращения коллекций

7 мин

8.3K

.NET*Ненормальное программирование*Программирование*Промышленное программирование*

-2

Комментарии 69

lair 9 дек 2015 в 16:21

Мне нравится, а вам?

А мне — нет.

либо искусственно использовать индексы за пределами массива

Что в этом искусственного?

запись Slice(5, 5) приведёт к тому, что мы получим исходную коллекцию циклически сдвинутую на пять индексов влево — 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E' — вот чудо [...] Для того, чтобы получить пустую выборку достаточно написать Slice(5, 6),

Это, гм, не интуитивно. То есть вот вообще.

Впрочем, дело даже не в этом. Дело в том, что — как видно из вашей реализации — вы не поняли, что такое слайс. Слайс — это «окно» в массив, не создающее его копии. Иными словами, когда я говорю arr.Slice(5), я ожидаю получить обертку поверх этого массива, которая нулевой элемент которой будет вести на пятый элемент исходного массива, с минимум дополнительных расходов. (Enter ArraySegment, ну да ладно...) Поверх последовательностей слайсы вообще особого смысла не имеют. А вы сначала делаете принудительную материализацию пришедшей вам коллекции в массив (даже для IList<T>, да). Мне страшно подумать, что происходит с производительностью.

Makeman 9 дек 2015 в 16:36

На вкус и цвет товарищей нет.
Возможно, да, это не совсем тот слайс, о котором вы думаете, но сам метод Slice не создаёт никаких копий, а только лишь выполняет итерацию. Назовём это модификацией, суть же очень схожа.

Шаг var items = collection as T[] ?? collection.ToArray() я оставил осознанно, поскольку метод расчитан в большинстве своём на материализованные коллекции, а если вас это пугает, то сделайте свою реализацию без отрицательных индексов и проверки длины. Не трудно.

lair 9 дек 2015 в 16:38

но сам метод Slice не создаёт никаких копий, а только лишь выполняет итерацию.

Как вы сделаете циклическую итерацию по бесконечной последовательности?

а если вас это пугает, то сделайте свою реализацию без отрицательных индексов и проверки длины

Меня не пугает, но вы же спрашиваете мнение про статью?

Makeman 9 дек 2015 в 16:49

Не знаю, как у вас, но в подавляющем большинстве случаев обрабатываются конечные коллекции. За всю мою практику ни разу не доводилось обрабатывать бесконечную. Разве что на собеседовании была задачка, как обнаружить возможную зацикленность в бесконечном однонаправленном списке.

Я же вас не спрашиваю, как вы вызовете метод Count() у бесконечной последовательности… Вопрос сродни вашему.

lair 9 дек 2015 в 16:53

Не знаю, как у вас, но в подавляющем большинстве случаев обрабатываются конечные коллекции.

… размер которой заранее не известен, а материализация которой может быть очень дорогой. Это в моем «подавляющем большинстве случаев».

Makeman 9 дек 2015 в 17:07

метод не рассчитан на такие коллекции. это то же самое, как случайно вызвать Count(), ToList() или ToArray() у запроса с милионами результатов. вы же не отказываетесь от использования этих методов только из-за того, что они несут в себе такую потенциальную опасность повесить ваше приложение.

lair 9 дек 2015 в 17:15

Не знаю, как у вас, но в подавляющем большинстве случаев обрабатываются конечные коллекции.

У меня, кстати, есть встречный вопрос: а зачем вам вообще в подавляющем большинстве случаев превращение коллекции в кольцо?

Makeman 9 дек 2015 в 17:24

Наглядные примеры в статье. Конечно, каждый день таких необходимотей возникать не будет, но сдвиги элементов в массивах — распостранённое явление и, как видим, это частный случай выполнения «среза», поэтому логично и красиво обобщить эти операции в один метод, на мой взгляд.

lair 9 дек 2015 в 17:35

Наглядные примеры в статье.

Не, в статье нет ни одного примера зачем — иными словами, какую бизнес-задачу это решает.

сдвиги элементов в массивах — распостранённое явление

Что вы понимаете под сдвигами элементов массивах?

Makeman 9 дек 2015 в 18:01

Тогда воспринимайте это как абстрактную математическую конструкцию, которой пока ещё не нашлось применения :)

Мне эта штука показалась стройной и красивой, заставила немного пошевелить мозгом, поэтому решил поделиться ею с другими людьми. Быть может, кто-то и найдёт для себя практическую ценность в ней.

По крайней мере, как задачка для развития логики мышления, она очень подходит…

lair 9 дек 2015 в 18:18

Тогда воспринимайте это как абстрактную математическую конструкцию, которой пока ещё не нашлось применения

А для абстрактной математической конструкции она недостаточно строга. В особенности по сравнению с совершенно банальной и напрашивающейся здесь работой по модулю.

Makeman 9 дек 2015 в 18:21

Ок, назовём это всё интеллектуальным упражнением, а не математической моделью ;)

qw1 9 дек 2015 в 18:48

Было бы математически красиво, если бы любая композиция слайсов arr.Slice(a,b).Slice(c,d)... сводилась бы по сложности и потребляемой памяти к одному слайсу, и чтобы оптимально работали Last(), LastOrDefault() за время O(1).

Была бы достойная библиотека. Наивная реализация из статьи никому не нужна.

Oxoron 9 дек 2015 в 19:24

А разве extension метод Slice(a,b) с теми же Linq.Skip(), Linq.Take() внутри не решит проблему за O(1)? Они же не сразу вычисляются, а по запросу.
Создать аналог Last() для массива не проблема, для List — можно, в общем случае невозможно.

Makeman 9 дек 2015 в 19:38

Вот именно, что решит. Только пропадут отрицательные индексы и возможность зацикливания, да и не намного лучше будет выглядеть, чем items.Skip(i).Take(n). =)

qw1 9 дек 2015 в 19:41

В этом и претензия, что методы из LINQ умеют оптимально работать в композициях, а также умеют оптимально вычислять Last() и Count() в специальных случаях. Автор упоминает Aero Framework, если это framework, он должен удовлетворять самым высоким стандартам качества.

Makeman 9 дек 2015 в 19:51

Конечно, если мы пишем свою реализацию IEnumerable, которая при выполнении Last() и Count() вместо того, чтобы загружать весь список с данных с сервера или БД, будет транслировать это в соответствующий запрос (например, атомарный для Count) и загружать только нужную часть (виртуализация), то да — это будет оптимально. Но стандартные реализации List, Array и прочие ничего подобного не могут.

Или вы что-то другое подразумеваете под специальными случаями?

qw1 9 дек 2015 в 20:38

Я хочу, пользуясь фрейворком, вызывать Slice и дальше take/last/count на любых enumerables, и чтобы на массивах и списках работал оптимальный для них вариант. А на остальных, пусть даже бесконечных генераторах, пессимистичный, но корректный.

Ведь что мешает вызвать Slice(100, 200) на бесконечной выборке, если я хочу получить конечное «окно»

Makeman 10 дек 2015 в 01:01

Ведь что мешает вызвать Slice(100, 200) на бесконечной выборке, если я хочу получить конечное «окно»

Именно в этом случае, на мой взгляд, проще и лучше использовать связку skip-take.

Каждый метод имеет свои преимущества и недостатки в зависимости от условий и целей использования, но когда мы стремимся сделать единый совершенно универсальный метод на все случаи жизни, то зачастую излишне усложняем реализацию, теряем контроль и гибкость, получая лишь сомнительный выигрыш в распространённых ситуациях, но значительный проигрыш в предельных, по моему мнению.

lair 9 дек 2015 в 23:45

А разве extension метод Slice(a,b) с теми же Linq.Skip(), Linq.Take() внутри не решит проблему за O(1)?

А он после этого позволит индексацию за O(1)?

Oxoron 10 дек 2015 в 09:35

Что Вы подразумеваете под индексацией? Создание индекса? Поиск по индексу? Вы про какую-то конкретную коллекцию .NET, любую IEnumerable, или данные, которые будут вытягиваться из БД?
Плюс, в комментарии выше не было упоминания про индексацию.

lair 10 дек 2015 в 09:37


arr[i]

Oxoron 10 дек 2015 в 09:42

Не понял.
IEnumerable collection = GetNewCollection(); // Берем мы произвольную коллекцию
string anyString = collection.Take(n)[0]; // А вот тут ошибка, ибо какой нафиг индекс на IEnumerable?

lair 10 дек 2015 в 12:25

Вот поэтому Slice — это не Take. Если быть совсем педантом, определять Slice поверх последовательностей вообще не надо. Но если очень хочется обобщенной версии, то надо поддерживать хотя бы ElementAt за O(1) (чего LINQ «из коробки» не делает).

Oxoron 10 дек 2015 в 15:28

ElementAt за O(1) невозможен на IEnumerable в общем случае. Как пример, наш Next возвращает случайное число.
В итоге да, определять Slice с Вашими требованиями не получится.
Другое дело, что изначально разговор шел о

Было бы математически красиво, если бы любая композиция слайсов arr.Slice(a,b).Slice(c,d)… сводилась бы по сложности и потребляемой памяти к одному слайсу, и чтобы оптимально работали Last(), LastOrDefault() за время O(1).

Я хочу, пользуясь фрейворком, вызывать Slice и дальше take/last/count на любых enumerables, и чтобы на массивах и списках работал оптимальный для них вариант. А на остальных, пусть даже бесконечных генераторах, пессимистичный, но корректный.

Оптимальность Last недостижима в общем случае. Сложность композиции Take-Skip слайсов равна сложности одного слайса. Насчет памяти сомневаюсь, тут зависит от упрощения Expression Tree, но она скорее всего это требование не важно.

Сделать Slice индексированным на массивах и списках можно. В общем случае — невозможно.

Идея с замыканием массива в кольцо известна, её применение сильно зависит от логики. Если не ошибаюсь, Вы уже упоминали про остатки по модулю. В итоге, если и добавлять закольцовку, то под контролем отрицательного по умолчанию аргумента.

Думаю, на этом стоит закончить. Или продолжить в личке.

lair 10 дек 2015 в 15:31

Оптимальность Last недостижима в общем случае. Сложность композиции Take-Skip слайсов равна сложности одного слайса. Насчет памяти сомневаюсь, тут зависит от упрощения Expression Tree, но она скорее всего это требование не важно. Сделать Slice индексированным на массивах и списках можно. В общем случае — невозможно.

Но — и это важно — можно написать такую реализацию, которая будет O(1) для коллекций, которые это позволяют, и «столько, сколько в обычном Enumerable» для всех остальных коллекций; причем это будет происходить прозрачно для пользователя. Собственно, это единственный смысл писать Slice, а не пользоваться Skip/Take.

Makeman 9 дек 2015 в 16:39

Насчёт же интуитивности, достаточно один раз принять зацикленность (замкнутость) коллекции и всё становится на свои места, причём автоматически устраняются многие противоречия, возникающие без этого положения, а функционал метода только расширяется ничего не утрачивая.

lair 9 дек 2015 в 16:51

достаточно один раз принять зацикленность (замкнутость) коллекции

Особенно это для IEnumerable легко принять, ага.

Но вообще, круто.

(1) Сначала вы пишете, что «хвост удобно не включать, поскольку длина выборки тогда легко вычисляется по индексам без лишнего инкремента на единицу и не вызывает путаницы», а потом делаете такой механизм, при котором длина выборки вообще не вычислима из индексов (какова длина выборки (5,5)?).

(2) Как именно из вашей реализации получается, что (5,6) вернет пустую выборку?

            if (head < tail)
            {
                foreach (var item in items.Skip(head).Take(tail - head))
                {
                    yield return item;
                }
            }

Я, наверное, чего-то не понимаю, но будет выбран ровно один элемент.

(3) предположим, что я не понимаю чего-то в предыдущем коде, и там не будет выбрано ни одного элемента. Как тогда выбрать один элемент?

Makeman 9 дек 2015 в 16:55

Спасибо, разобрались, заметили ошибку! Мой косяк, исправлю. Да, будет один элемент. Пустого результата нет.

lair 9 дек 2015 в 16:57

… а как же получить пустой слайс?

Makeman 9 дек 2015 в 17:00

а он нужен?
вот так

Enumerable.Empty<T>()

теперь всё становится логично?

lair 9 дек 2015 в 17:08

а он нужен?

Нужен, конечно. Это базовый случай для алгоритма.

теперь всё становится логично?

Конечно, нет. Вы придумали новую нотацию для интервалов на последовательности, но, как обычно, забыли про базовый случай.

Makeman 9 дек 2015 в 17:54

Я знаю, что вас не убедить :)

Но спасибо, что приняли участие и указали на неточность в статье!

Соглашусь с вами, что это больше напоминает способ нотации и понятие «пустой слайс» в нём не определено. Но и такая нотация даёт некоторые преимущества. Конечно, довольно просто добавить нужный флаг (useShift по умолчанию равный true) и в случае Slice(5, 5, false) возвращать вместо сдвига пустое значение, если это нужно.

Makeman 9 дек 2015 в 19:41

Сходил в магазин, поразмыслил, и на ум пришла идея:

var enumerator = i == j ? items.Take(0) : items.Slice(i, j);

Быть может, это решит вашу проблему? Не вижу ничего плохого в таком способе =)

lair 9 дек 2015 в 23:43

Нет, не решит. А плохого в этом способе то, что теперь я должен использовать две разных нотации, и помнить, что я сам между ними переключаюсь.

poemmuse 10 дек 2015 в 00:49

del

lair 10 дек 2015 в 01:09

Ого, виртуал makeman?

poemmuse 10 дек 2015 в 01:12

Извиняюсь, poemmuse — это старый аккаунт, случайно под ним оставил комментарий.

Makeman 10 дек 2015 в 00:50

Хорошенько подумал над вашим замечанием и понял, что оно из разряда вещей подобных флагу RemoveEmptyEntries у метода string.Split() либо квантификаторам «ленивого» и «жадного» захвата в регулярных выражениях, указывающим, наибольшее или наименьшее по длине вхождение нужно искать. Поэтому, чтобы метод Slice стал функционально полным, достаточно ввести

    [Flags]
    public enum SliceOptions
    {
        None = 0,
        Lazy = 1,
    }

И слегка модифицировать сам метод

Slice

        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;
                }
            }
        }

Благодарю за констуктивную критику, это помогает в стремлении к совершенству.

lair 10 дек 2015 в 01:10

Угу, теперь внезапно флаг влияет на поведение в граничном случае, когда индексы совпадают, и ни в каком другом. Флаги сами по себе-то зло, а уж неконсистентные флаги — так и точно.

Makeman 10 дек 2015 в 01:19

По-моему, ничего в этом страшного нет. Как вы, например, без флага-квантификатора разрулите в регулярном выражении «жадный» захват использовать или «ленивый», а тут очень похожая ситуация — выбрать все элементы или ни одного.

lair 10 дек 2015 в 01:27

По-моему, ничего в этом страшного нет.

В неконсистентности-то?

Как вы, например, без флага-квантификатора разрулите в регулярном выражении «жадный» захват использовать или «ленивый»

Вообще-то, в регулярках жадный или ленивый захват — это не флаг, а символ в выражении.

Makeman 10 дек 2015 в 01:34

А это по сути не одно и то же?

При создании регулярного выражения мы можем указать флаг RegexOptions.IgnoreCase, вместе с тем можем не указывать, а использовать inline character i — результат тот же.

Конечно, если вы видите другие пути к консистентности, то можете их предложить, я со своей колокольни рассуждаю :)

lair 10 дек 2015 в 01:43

А это по сути не одно и то же?

Конечно, нет.

При создании регулярного выражения мы можем указать флаг RegexOptions.IgnoreCase, вместе с тем можем не указывать, а использовать inline character i — результат тот же.

Флаг хуже. Если вам интересно, почему — вот статья Фаулера.

Конечно, если вы видите другие пути к консистентности

Конечно, вижу. Либо использовать полуоткрытые интервалы и не пытаться сделать из последовательности кольцо, либо использовать старт+длину и тогда ходите по кольцу сколько хотите.

Makeman 10 дек 2015 в 11:02

Хорошо, соглашусь, что с флагами нужно быть осторожным.

Обдумал идею насчёт длины в качестве второго параметра, и понимаю, что это отличный подход. В статье я взял за ориентир индексацию слайсов языка Питон, что наложило некоторые ограничения. С длиной же можно вывести ещё дополнительный ряд обобщений, например, проходить коллекцию по несколько раз и копировать её, а также использовать отрицательную длину для обхода в обратном направлении.

var letters = new [] {'A', 'B, 'C', 'D'};
letters.Slice(1, 9); // BCDABCDAB
letters.Slice(-2, -9); // CBADCBADC

lair 10 дек 2015 в 12:25

Теперь это окончательно перестало иметь какое-то отношение к слайсам. Ну и да, зачем вам нужны все эти кольца, я так и не понимаю.

lair 10 дек 2015 в 12:29

BTW, реализовать «кольцо вперед» можно с помощью Skip/Take и одного тривиального расширения RepeatInfinite.

Makeman 10 дек 2015 в 12:53

Меня больше интересуют не сами слайсы, а обобщённые алгоритмы. Как вам такая реализация?
В ней слайсы и сдвиги лишь частные случаи колец с прямым и обратным обходом.

Ring

        public static IEnumerable<T> Ring<T>(this IList<T> items, int skip)
        {
            var reverse = skip < 0;
            var count = items.Count;
            skip = reverse ? count + skip : skip;
            var take = reverse ? -skip - 1 : count - skip;
            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.Ring(3).ToList().ForEach(Console.Write);
            Console.WriteLine();

            // 'A', 'B', 'C', 'D'
            bodyLetters.Ring(-5).ToList().ForEach(Console.Write);
            Console.WriteLine();

            Console.ReadKey();
        }

lair 10 дек 2015 в 12:59

Меня больше интересуют не сами слайсы, а обобщённые алгоритмы

Я не вижу смысла в обобщенных алгоритмах до тех пор, пока не определен круг задач, решаемых алгоритмом. Предварительное обобщение — грех не лучше предварительной оптимизации.

(Ну и да, делать из IList IEnumerable — это плохой обобщенный алгоритм. Особенно когда вы потом всегда делаете ToList. И заранее закладывать в операцию Ring сдвиги — тоже плохой обобщенный алгоритм, он противоречит принципу функциональной композиции, заложенной в LINQ.)

Makeman 10 дек 2015 в 13:13

ToList я делаю лишь для того, чтобы сэкономить строчки кода в тестовом примере и только (встроенный метод ForEach() есть только у List), поэтому он здесь не обязателен.

Если изложенный метод и нарушает функциональную композицию, то вы можете скрыть (инкапсулировать) его, а предоставить несколько открытых методов-обёрток, которые работают на обобщённом алгоритме, поэтому сам алгоритм нисколько не теряет своей ценности.

lair 10 дек 2015 в 13:18

Если изложенный метод и нарушает функциональную композицию, то вы можете скрыть (инкапсулировать) его

Это не решит проблему того, что нижний метод некомпонуем. Вот наоборот, когда базовый метод компонуем, вокруг него можно писать любые врапперы, используя нужную композицию.

сам алгоритм нисколько не теряет своей ценности

Это если предположить, что она у него есть. В вашем случае это неочевидно дважды: во-первых, непонятно, какую задачу вы решаете, во-вторых, ваша текущая реализация все равно неоптимальна.

Makeman 10 дек 2015 в 13:37

Конечно, у вас может быть своё мнение, но я сторонник написания одного метода пригодного для решения обобщённой задачи, чем нескольких методов для каждого родственного частного случая.

Понимаю, что в обобщённой версии есть несколько дополнительных булевых проверок, но всё же их влияние не столь велико на производительность.

Разве что

var index = reverse ? skip - j : skip + j;

в цикле, возможно, имеет смысл разделить на два цикла, хотя это лучше проверить на практике.

lair 10 дек 2015 в 13:59

Конечно, у вас может быть своё мнение, но я сторонник написания одного метода пригодного для решения обобщённой задачи, чем нескольких методов для каждого родственного частного случая.

Вы серьезно не понимаете, как работает функциональная композиция? arr.Ring().Skip(5).Take(2) лучше чем arr.Ring(5, 2).

Понимаю, что в обобщённой версии есть несколько дополнительных булевых проверок, но всё же их влияние не столь велико на производительность.

Ну да, а тот маленький факт, что на входе у вас был IList, по которому работал ElementAt за O(1), а на выходе у вас IEnumerable, где та же операция стоит O(n), никого, конечно, не волнует.

(при этом это можно реализовать за O(1), причем даже не очень сложно)

Makeman 10 дек 2015 в 14:49

Решения я генерирую в реальном времени, поэтому появление недочётов вполне закономерно.

Вы можете предложить свои оптимизации, мне самому интересно. Менять тип возвращаемого значения я не вижу смысла, так как сам метод Ring внутри срабатывает за O(1), а на выходе при необходимости можно сделать как ToList(), так и ToArray().

Также придумал последнее обобщение с количеством оборотов =)

        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);
        }

Если число оборотов 0, то берётся срез от элемента до конца либо в обратном направлении до начала коллекции, в зависимости от типа отсчёта.
Если число оборотов не 0, то берётся несколько оборотов от элемента в прямом либо обратном направлении, в зависимости от знака числа оборотов.

lair 10 дек 2015 в 14:54

Решения я генерирую в реальном времени, поэтому появление недочётов вполне закономерно.

Так может надо подумать немножко дольше, чтобы недочетов не было?

Менять тип возвращаемого значения я не вижу смысла

А зря.

так как сам метод Ring внутри срабатывает за O(1), а на выходе при необходимости можно сделать как ToList(), так и ToArray().

… которые тоже будут работать за O(n), только теперь n — не порядковый номер элемента, а общее число элементов, плюс еще и займет O(n) дополнительной памяти.

Также придумал последнее обобщение с количеством оборотов

А смысл? Лучше не стало, все предыдущие проблемы остались в полный рост.

Серьезно, посмотрите на то, как работает функциональная композиция.

Makeman 10 дек 2015 в 15:07

Так может надо подумать немножко дольше, чтобы недочетов не было?

Тогда бы я отвечал на ваши комментарии раз в день и прогресс шёл значительно медленнее.

Кстати, придумал практическое приложение методам Ring и Turn. К примеру, вы делаете UI, и у вас есть коллекция-заглушка с n-элементами, вдруг вы захотели проверить, как работает UI при 2n, 3n, ...mn элементах. Вам достаточно написать что-то вроде Items = _testItems.Ring(0, m).ToList() и всё.

Удобно же, не находите? )

lair 10 дек 2015 в 15:14

огда бы я отвечал на ваши комментарии раз в день и прогресс шёл значительно медленнее.

Зато возможно с первого раза бы все правильно сделали, и не надо было бы из пустого в порожнее переливать.

К примеру, вы делаете UI, и у вас есть коллекция-заглушка с n-элементами, вдруг вы захотели проверить, как работает UI при 2n, 3n, ...mn элементах.

Когда я что-то тестирую, я обычно использую AutoFixture. Проще и надежнее. Но даже если нет, то:

Items = Enumerable.Repeat(_testItems, m).SelectMany(n => n);

Если очень хочется, можно свернуть в extension-метод (поверх чистого Enumerable).

Собственно, наглядная разница между кольцом и простым повтором.

Makeman 14 дек 2015 в 19:31

Как вам такой способ?

        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();
        }

Имплементация

        // 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;
            }
        }

lair 14 дек 2015 в 23:39

Да все так же. Вы, похоже, не понимаете, что все, что касается колец, должно исчерпываться

var ring = smth.ToRing();

После чего мы получаем бесконечную закольцованную последовательность (обычный IEnumerable). Бонусные баллы получит та реализация, в которой результат будет позволять «быстрые» (O(1)) операции там, где это позволяла исходная (например, если стартом был массив, то ElementAt, Skip и так далее должны быть «быстрыми»).

Соответственно, про слайсы я уже все говорил: особого смысла делать слайсы по последовательностям нет. Но если очень хочется, то надо реализовывать такой вариант, при котором для «обычных» последовательностей слайс будет эквивалентен Skip/Take, а для «индексированных» — ArraySegment.

Makeman 14 дек 2015 в 19:39

Замечу насчёт композиции функций, что SkipByRing(x).TakeByRing(y) в кольцевом обобщении не равнозначно SliceByRing(x,y), хотя в простых случаях, когда нет полного обхода кольца, они дают идентичный результат.

Iceg 9 дек 2015 в 17:21

Выбор элементов с четвёртого по шестой включительно можно осуществить несколькими способами:

// хвост не включается в результат
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'

Словами по шестой, а в коде по седьмой?

Для того, чтобы получить пустую выборку достаточно написать Slice(5, 6)

Почему пустая будет, а не 'F'?
items.Skip(5).Take(1);

И соглашусь с lair, совсем не интуитивно, даже хуже — запутанно. Вы же сами и запутались :)

Makeman 9 дек 2015 в 17:29

Про пустую выборку я соврал, извините, будет один элемент.
Уже это исправил, надеюсь, теперь всё стало на свои места.

Словами по шестой, а в коде по седьмой?

По шестой включительно (или по седьмой, не включая, как в коде)

Спасибо, что внимательно читаете и обнауживаете неточности!

Iceg 9 дек 2015 в 18:07

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 };

var humanizedOrder = new[] {"первый", "второй", "третий", "четвёртый", "пятый", "шестой", "седьмой", "восьмой"};

По шестой включительно

Да, по седьмой. Включительно.

Makeman 9 дек 2015 в 18:18

Да, снова моя неточность. Исправил, спасибо! Но теперь уж, думаю, всё точно :)

IL_Agent 9 дек 2015 в 17:40

Хвост удобно не включать, поскольку длина выборки тогда легко вычисляется по индексам без лишнего инкремента на единицу и не вызывает путаницы (5-2 = 3 вместо 5-2+1 = 4)

А где тут путаница? Голову включаем, а хвост нет — это скорее ведёт к путанице. Написанное далее в статье является тому подтверждением.