Как сдвинуть все элементы массива на 1

@akeee · Регистрация: 11.05.2012

Студворк — интернет-сервис помощи студентам

Есть пустой массив (вектор) определенной длины. Он заполняется по событию. После заполнения с ним выполняются определенные манипуляции. При появлении нового объекта обработчик события "засовывает" новый элемент в конец массива, сдвинув все элементы на -1, удалив значение первого элемента.
Вопросы: Как сделать так, чтобы манипуляции с массивом выполнялись только после заполнения? Как сдвинуть все элементы массива на 1 быстрее времени, затраченного на итерации равные количеству элементов массива минус 1? И вообще возможно ли такое?

@I2um1 · 12.08.2012, 16:48

Сообщение от akeee

Как сдвинуть все элементы массива на 1 быстрее времени, затраченного на итерации равные количеству элементов массива минус 1? И вообще возможно ли такое?

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

C#
1
2
[DllImport("Kernel32.dll", EntryPoint="RtlMoveMemory", SetLastError=false)]
static extern void MoveMemory(IntPtr dest, IntPtr src, int size);

Лучше, конечно, не изобретать велосипед, а использовать стандартную функцию:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
using System;
 
namespace ConsoleApplication
{
    internal static class Program
    {
        private static void Main()
        {
            var arr = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
            Array.Copy(arr, 1, arr, 0, arr.Length - 1);
            Array.ForEach(arr, Console.WriteLine);
        }
    }
}

На функциональных языках это вообще разрезом делается в один символ.

Сообщение от akeee

Как сделать так, чтобы манипуляции с массивом выполнялись только после заполнения?

Выполнять манипуляции после заполнения. (:

Как вариант, можно вообще не сдвигать массив. А хранить его в некой структуре, в которой будет дополнительно целочисленное значение, указывающее конец массива. В таком случае сдвиг будет происходить со сложностью O(1).

Psilon · 12.08.2012, 16:48

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

@I2um1 · 12.08.2012, 16:53

Psilon, почитай внимательнее задачу - размер массива не изменяется.

Psilon · 12.08.2012, 17:01

Blood-Angel, какая разница? Тут скорее очередь подойдет, если нужно запихнуть с одного конца и выпихнуть с другого. А очередь это частный случай линейного списка. А массив без пузырькового копирования такое не реализует, а это очень долго и муторно. Конечно, динамическую структуру реализовывать с помощью статической получается хреново...

@akeee · 12.08.2012, 17:16 **[ТС]**

Blood-Angel,
Дело в том, что нужно определенное количество элементов для последующих манипуляций. т.е. если int[10] и он заполнен наполовину, то "параметров" недостаточно. Я думал
поставить условие на проверку каждого элемента, но учитывая возможное количество элементов, хочется по-быстрее.
Psilon,
Если под списками имеется в виду что-то относящиеся к дженерикам - к сожалению пока не дошел до них. Но обязательно приму во внимание ваш совет.

@I2um1 · 12.08.2012, 17:24

Сообщение от Psilon

какая разница?

В линейном списке произвольный доступ осуществляется со сложностью O(n) в отличии от массива, да и памяти список в разы больше занимает. И что такое "пузырьковое копирование"?

Сообщение от akeee

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

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

Psilon · 12.08.2012, 17:32

Blood-Angel, нам нужен не весь массив, а только начало и конец, насколько я понял ТЗ.

akeee, я имею ввиду динамические структуры, списки в частности, и их частные случаи: стек, очередь... Если вы работаете только с концами вашего массива, то гораздо проще работать с их помощью: стек если с одним концом (не ваш случай), очередь - с двумя. Если имеется доступ к ячейкам напрямую (то есть к центральным), тогда да, массив может и лучше (если операции работы с ними происходят чаще, чем добавление-удаление), в противном случае лучше использовать динамические структуры.
http://ru.wikipedia.org/wiki/%... 8%D0%B5%29
http://msdn.microsoft.com/ru-r... 00%29.aspx

@kolorotur · 12.08.2012, 17:38

Сообщение от Psilon

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

Под списками вы, я так понимаю, подразумеваете связные списки?
Если да, то с каких пор очередь и стек являются частными случаями именно связных списков?
"Классические" их реализации - как раз через массивы.

akeee, вам обязательно надо самопал делать или есть возможность пользоваться готовыми классами в .NET?

@akeee · 12.08.2012, 17:49 **[ТС]**

kolorotur,

Есть возможность. Программирую для себя.

Psilon · 12.08.2012, 17:51

kolorotur, их классическая реализация - на указателях.

алсо википедия (по ссылке выше):

Связный список

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

@akeee · 12.08.2012, 18:51 **[ТС]**

Psilon,

А если потребуется например каждый последующий элемент списка и предыдущий сложить и разделить на 2 (для примера), такое можно реализовать? Или после "обновления" списка придется копировать его в массив?

Psilon · 12.08.2012, 19:07

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

@akeee · 12.08.2012, 23:28 **[ТС]**

Blood-Angel,
"Вводишь дополнительную переменную, которая будет говорить о том, на сколько элементов заполнен массив. А далее просто проверяешь факт того, что оно равно длине массива."

т.е. нужно каждый раз при обращении к обработчику события, который добовляет новый элемент в массив, сделать count++ и затем проверить if(cout>10) (если длина массива 10)... ? А можно ли как-то сделать чтобы программа не проверяла каждый раз это условие? Массив заполнился и программа начинает выполнять какие-то действия.

Psilon · 13.08.2012, 03:44

akeee, без условий что-то проверить невозможно в принципе, а условие равенства какому-то числу самое простое.

@akeee · 13.08.2012, 12:32 **[ТС]**

В голову пришла идея. Обработчик события (добавление нового элемента в массив, и подсчет элементов) после заполнения массива elseif(count==10) вызывает метод, который удаляет этот обработчик и вешает на событие появления нового элемента другой обработчик. В котором выполняется основная функциональность (добавление со сдвигом и подсчеты). Такое решение имеет место на существование? Есть что-то, что нужно учесть при таком подходе?

@kolorotur · 13.08.2012, 13:01

Сообщение от Psilon

их классическая реализация - на указателях.

Ну ладно, пусть будут указателями - мне не жалко

Но, получается, нам в ВУЗе врали, когда при разборе структур данных классической реализацией называли ту, которая через массив

akeee, а в чем заключается ваша задача, требующая всех этих манипуляций? Может опишете как есть? Проще будет подходящее решение найти - а их много.

Psilon · 13.08.2012, 15:58

kolorotur, не то, что врали, просто классика меняется, если 100 тыс лет назад люди делали квадратные колеса, это не значит, что это классика. Все-таки классически считают, что колесо круглое. Вот и тут также: во времена этих ваших фортранов, алголов и PL/1, когда реализовывали динамические структуры с помощью статических, может это и было классикой, но это равнозначно квадратным колесам

@novi4ok · 13.08.2012, 16:06

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

@diman891 · 13.08.2012, 19:45

А если так: есть массив из 10 (условно) элементов, и есть 2 указателя (индекса) на первый элемент и на последний. В начале оба указателя равны 0. Постепенно указатель на последний элемент доходит до 9. В следующей итерации (чтобы выкинуть самый старый элемент) инкрементируем указатель на первый элемент, а указатель на последний обнуляем. И так далее, как только один из указателей достигает предельного значения, обнуляем его. Получается что-то вроде циклического буфера, нужно только следить чтобы указатели не "обгоняли" друг друга.

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@akeee 4 / 4 / 0 Регистрация: 11.05.2012 Сообщений: 53

	Как сдвинуть все элементы массива на 1 12.08.2012, 16:27. Показов 11281. Ответов 20 Метки нет (Все метки) Есть пустой массив (вектор) определенной длины. Он заполняется по событию. После заполнения с ним выполняются определенные манипуляции. При появлении нового объекта обработчик события "засовывает" новый элемент в конец массива, сдвинув все элементы на -1, удалив значение первого элемента. Вопросы: Как сделать так, чтобы манипуляции с массивом выполнялись только после заполнения? Как сдвинуть все элементы массива на 1 быстрее времени, затраченного на итерации равные количеству элементов массива минус 1? И вообще возможно ли такое? 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	12.08.2012, 16:48
	akeee, для операций редактирования/добавления в начало/середину нужно использовать линейные списки, а не массив... 1

@I2um1 Злой няш 2136 / 1505 / 565 Регистрация: 05.04.2010 Сообщений: 2,881
	12.08.2012, 16:53
	Psilon, почитай внимательнее задачу - размер массива не изменяется. 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	12.08.2012, 17:01
	Blood-Angel, какая разница? Тут скорее очередь подойдет, если нужно запихнуть с одного конца и выпихнуть с другого. А очередь это частный случай линейного списка. А массив без пузырькового копирования такое не реализует, а это очень долго и муторно. Конечно, динамическую структуру реализовывать с помощью статической получается хреново... 1

@akeee 4 / 4 / 0 Регистрация: 11.05.2012 Сообщений: 53
	12.08.2012, 17:16 [ТС]
	Blood-Angel, Дело в том, что нужно определенное количество элементов для последующих манипуляций. т.е. если int[10] и он заполнен наполовину, то "параметров" недостаточно. Я думал поставить условие на проверку каждого элемента, но учитывая возможное количество элементов, хочется по-быстрее. Psilon, Если под списками имеется в виду что-то относящиеся к дженерикам - к сожалению пока не дошел до них. Но обязательно приму во внимание ваш совет. 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	12.08.2012, 17:32
	Blood-Angel, нам нужен не весь массив, а только начало и конец, насколько я понял ТЗ. akeee, я имею ввиду динамические структуры, списки в частности, и их частные случаи: стек, очередь... Если вы работаете только с концами вашего массива, то гораздо проще работать с их помощью: стек если с одним концом (не ваш случай), очередь - с двумя. Если имеется доступ к ячейкам напрямую (то есть к центральным), тогда да, массив может и лучше (если операции работы с ними происходят чаще, чем добавление-удаление), в противном случае лучше использовать динамические структуры. http://ru.wikipedia.org/wiki/%... 8%D0%B5%29 http://msdn.microsoft.com/ru-r... 00%29.aspx 1

@akeee 4 / 4 / 0 Регистрация: 11.05.2012 Сообщений: 53
	12.08.2012, 17:49 [ТС]
	kolorotur, Есть возможность. Программирую для себя. 0

@akeee 4 / 4 / 0 Регистрация: 11.05.2012 Сообщений: 53
	12.08.2012, 18:51 [ТС]
	Psilon, А если потребуется например каждый последующий элемент списка и предыдущий сложить и разделить на 2 (для примера), такое можно реализовать? Или после "обновления" списка придется копировать его в массив? 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	12.08.2012, 19:07
	akeee, если работа предполагает работу с определенными индексами, не являющимися начальным или конечным, то лучше использовать массив, во всех остальных случаях следует использовать список. 1

@akeee 4 / 4 / 0 Регистрация: 11.05.2012 Сообщений: 53
	12.08.2012, 23:28 [ТС]
	Blood-Angel, "Вводишь дополнительную переменную, которая будет говорить о том, на сколько элементов заполнен массив. А далее просто проверяешь факт того, что оно равно длине массива." т.е. нужно каждый раз при обращении к обработчику события, который добовляет новый элемент в массив, сделать count++ и затем проверить if(cout>10) (если длина массива 10)... ? А можно ли как-то сделать чтобы программа не проверяла каждый раз это условие? Массив заполнился и программа начинает выполнять какие-то действия. 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	13.08.2012, 03:44
	akeee, без условий что-то проверить невозможно в принципе, а условие равенства какому-то числу самое простое. 0

@akeee 4 / 4 / 0 Регистрация: 11.05.2012 Сообщений: 53
	13.08.2012, 12:32 [ТС]
	В голову пришла идея. Обработчик события (добавление нового элемента в массив, и подсчет элементов) после заполнения массива elseif(count==10) вызывает метод, который удаляет этот обработчик и вешает на событие появления нового элемента другой обработчик. В котором выполняется основная функциональность (добавление со сдвигом и подсчеты). Такое решение имеет место на существование? Есть что-то, что нужно учесть при таком подходе? 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	13.08.2012, 15:58
	kolorotur, не то, что врали, просто классика меняется, если 100 тыс лет назад люди делали квадратные колеса, это не значит, что это классика. Все-таки классически считают, что колесо круглое. Вот и тут также: во времена этих ваших фортранов, алголов и PL/1, когда реализовывали динамические структуры с помощью статических, может это и было классикой, но это равнозначно квадратным колесам 0

@novi4ok 556 / 510 / 25 Регистрация: 23.07.2009 Сообщений: 2,359 Записей в блоге: 1
	13.08.2012, 16:06
	aleee, такое впечатление, что ты все еще неправильно понимаешь свою задачу. попробуй сформулировать здесь попроще. без употребления слов "массив", "обработчик" и т.д. на булках и стульях. иногда другому расскажешь - и до самого доходит. 0

@diman891 1 / 1 / 0 Регистрация: 21.11.2011 Сообщений: 13
	13.08.2012, 19:45
	А если так: есть массив из 10 (условно) элементов, и есть 2 указателя (индекса) на первый элемент и на последний. В начале оба указателя равны 0. Постепенно указатель на последний элемент доходит до 9. В следующей итерации (чтобы выкинуть самый старый элемент) инкрементируем указатель на первый элемент, а указатель на последний обнуляем. И так далее, как только один из указателей достигает предельного значения, обнуляем его. Получается что-то вроде циклического буфера, нужно только следить чтобы указатели не "обгоняли" друг друга. 1