Здравствуйте, Аноним, Вы писали:

А>Требуется отображать последние 10000 элементов. Записи порождаются достаточно быстро — около 1000 в минуту их нужно логировать.

А>Пока вижу варант с Dictionary<int, MeasureData > и переменной с индексом как курсор текущей позиции.
А>Но есть несколько проблем — для новых значений создается новый MeasureData со своим DateTime что может съесть память. А также выборка из такого списка не очень удобна учитывая что нужно еще по дате в обратном порятке сортировать — лишние расчеты.

А>Есть ли готовые списки для этого ?

Это называется Circular Buffer. Можно либо написать, либо взять кем-то написанный.

На стандартных контейнерах наиболее разумное решение — LinkedList<>.

Quene — From Old English cwen "woman, wife, queen," or cwene "woman, wife, prostitute".

Особенно забавно в контексте этого значения выглядят идентификаторы TestQuene и MyQuene.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, LaptevVV, Вы писали:

LVV>>Здравствуйте, Аноним, Вы писали:
А>>>>>Пока вижу варант с Dictionary<int, MeasureData > и переменной с индексом как курсор текущей позиции.
D>>>>Не совсем понятно, почему не подходит обыкновенный List<>?
А>>>тормозить будет при вставке элемента в начало или наоборот при удалении из начала.
LVV>>Читайте матчасть. Вставка и удаление из списка выполняются за константное время.
S>Речь о дотнете, в нем List-ом называется динамический массив. Соответственно время вставки/удаления линейное.

LVV>>Требует синхронизации доступа к буферу-контейнеру. Это — средствами API — в С++ стандартных средств пока нет.
S>Тема ведь в донтене
Да, я потом заметил, когда отослал...
Но ИМХО — это безобразие: вводить программеров в заблуждение такими названиями...
Повбывав бы!...

Здравствуйте, Аноним, Вы писали:

    /// <summary>
    /// Очередь с ограничением по кол-ву элементов
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal sealed class LimitedQueue<T> : Queue<T>
    {
        /// <summary>
        /// Максимальная емкость очереди
        /// </summary>
        private int MaxCapacity;

        /// <summary>
        /// Конструктор только такой
        /// </summary>
        /// <param name="_MaxCapacity">максимальное кол-во элементов в очереди</param>
        public LimitedQueue(int _MaxCapacity)
            : base(_MaxCapacity)
        {
            this.MaxCapacity = _MaxCapacity;
        }

        /// <summary>
        /// Заменяем базовую реализацию. Если очередь заполнена, то удаляем первый в ней элемент
        /// </summary>
        /// <param name="_item"></param>
        public new void Enqueue(T _item)
        {
            if( base.Count == this.MaxCapacity )
                base.Dequeue();

            base.Enqueue(_item);
        }
    }

Здравствуйте, Kerbadun, Вы писали:

K>Здравствуйте, Аноним, Вы писали:

А>>Требуется отображать последние 10000 элементов. Записи порождаются достаточно быстро — около 1000 в минуту их нужно логировать.

А>>Пока вижу варант с Dictionary<int, MeasureData > и переменной с индексом как курсор текущей позиции.
А>>Но есть несколько проблем — для новых значений создается новый MeasureData со своим DateTime что может съесть память. А также выборка из такого списка не очень удобна учитывая что нужно еще по дате в обратном порятке сортировать — лишние расчеты.

А>>Есть ли готовые списки для этого ?

K>Это называется Circular Buffer. Можно либо написать, либо взять кем-то написанный.
и
K>На стандартных контейнерах наиболее разумное решение — LinkedList<>.

K>

Quene — From Old English cwen "woman, wife, queen," or cwene "woman, wife, prostitute".

K>Особенно забавно в контексте этого значения выглядят идентификаторы TestQuene и MyQuene.

Quene потому что спать пора
Что-то LinkedList как-то вяло отработал , еще я заменил int на object т.к. придется именно объекты добавлять.


250005000
Queue Time:00:00:02.1280462
250005000
List Time:00:00:00.9180821
250005000
LinkedList Time:00:00:02.3005547

   class Program
    {


        static void Testqueue()
        {
            var queue = new Queue<object>();
            int cnt = 0;

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            for (int i = 0; i < 30000; i++)
            {
                queue.Enqueue(new object());
                if (queue.Count > 10000)
                    queue.Dequeue();

                var array = queue.ToArray();
                Array.Reverse(array);
                cnt += array.Length;
            }

            sw.Stop();

            Console.WriteLine(cnt);
            Console.WriteLine("Queue Time:" + sw.Elapsed);

        }

        static void TestList()
        {
            var queue = new List<object>();
            int cnt = 0;

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            for (int i = 0; i < 30000; i++)
            {
                queue.Insert(0, new object());
                if (queue.Count > 10000)
                    queue.RemoveAt(10000);

                cnt += queue.ToArray().Count();
            }

            sw.Stop();

            Console.WriteLine(cnt);
            Console.WriteLine("List Time:" + sw.Elapsed);

        }


        static void TestLinkedList()
        {
            var queue = new LinkedList<object>();
            int cnt = 0;

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            for (int i = 0; i < 30000; i++)
            {
                queue.AddFirst(new object());
                if (queue.Count > 10000)
                    queue.RemoveLast();

                cnt += queue.ToArray().Count();
            }

            sw.Stop();

            Console.WriteLine(cnt);
            Console.WriteLine("LinkedList Time:" + sw.Elapsed);

        }

        static void Main(string[] args)
        {
            Testqueue();
            TestList();
            TestLinkedList();
            Console.ReadKey();
        }
    }

Здравствуйте, Аноним, Вы писали:

А>        static void TestLinkedList()
А>        {
А>            var queue = new LinkedList<object>();
А>            int cnt = 0;

А>            var sw = new System.Diagnostics.Stopwatch();
А>            sw.Start();
А>            for (int i = 0; i < 30000; i++)
А>            {
А>                queue.AddFirst(new object());
А>                if (queue.Count > 10000)
А>                    queue.RemoveLast();

А>                cnt += queue.ToArray().Count();
А>            }

А>            sw.Stop();

А>            Console.WriteLine(cnt);
А>            Console.WriteLine("LinkedList Time:" + sw.Elapsed);

А>        }
А>    }

Собственно вопрос — а что данный тест меряет?
Обрати внимание, что в тесте обычного списка и связного списка есть строка

cnt += queue.ToArray().Count();

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

Далее совсем не понятно зачем вообще эти все подсчеты. Если хочешь, чтобы было быстро подумай, и убери все эти преобразования.

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

Про ToArray() верно заметили.

LinkedList<> я имел в виду для того, что его можно не переворачивать.

Если бы переворачивать не нужно было, можно было бы использовать Queue<>.

Интересно, что Queue<> внутри реализована как кольцевой буфер на массиве, который автоматически растет (за O(N), ага). И еще ее нельзя обойти задом наперед. Все-таки, в дотнете дебиловатые контейнеры.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, samius, Вы писали:

S>>Здравствуйте, Аноним, Вы писали:

А>>>Здравствуйте, samius, Вы писали:

А>>>>>Есть ли готовые списки для этого ?
S>>>>Есть стандартный FIFO контейнер — Queue<T>. Сортировать не надо, если складывать по мере порождения данных.

А>>>Не совсем то. Ниже тестовый пример, может я неправильно с ней работаю.
А>>>Dequene будет съедать элемент, и второму потоку оно не достанется. самое старое значение должно вытесняться при вставке нового элемента а не при чтении.
S>>В стартовом сообщении ничего о потоках не было...

А>>>Т.е. допустим нам не 10000 нужно записей а иметь "окно" только 5 последних записей.
А>>>Соотвественно сначала должно вывестись :

А>>>5,4,3,2,1 потом 6,5,4,3,2 , потом 7,6,5,4,3
А>>>в обоих потоках.

S>>Не понял. Требуется что бы один и тот же контейнер, изменяемый в одном потоке отыграл все свои состояния в других потоках, которые выводят в консоль элементы?
S>>Если так, то мне неясно, как здесь поможет Dictionary...

А зачем работать напильником? Можно самому написать класс, который будет отвечать этим требованиям. Если емкость очереди задается, то чтобы не тратить время на удаление, можно выделить сразу нужную память и просто при необходимости перезаписывать элементы массива. Вот набросок:

    class LimitedQueue 
    {
        object[] m_elements;
        int m_indexPosition;

        public LimitedQueue(int _capacity)
        {
            Capacity = _capacity;
            m_elements = new object[Capacity];
            m_indexPosition = 0;
            Count = 0;
        }

        public void Add(object _element)
        {
            m_elements[m_indexPosition] = _element;
            m_indexPosition++;
            if (m_indexPosition == Capacity)
                m_indexPosition = 0;
            if (Count != Capacity)
                Count++;
        }

        public object this[int _index]
        {
            get
            {
                if (_index >= Count || _index < 0)
                    throw new IndexOutOfRangeException();
                int indexPositionToArray;
                indexPositionToArray = (m_indexPosition + _index) % Capacity;
                return m_elements[indexPositionToArray];
            }
        }

        public int Capacity
        {
            get;
            private set;
        }

        public int Count
        {
            get;
            private set;
        }
    }

Можно также наследоваться от IEnumerable и уже здесь сделать потокобезопасность
Или задача состоит в том, чтобы использовать уже готовые списки

Здравствуйте, Аноним, Вы писали:

А>Вполне шустро работает. Меньше миллисекунды..196 тиков всего.
А>А он не двигает все элементы при удаленни чтоли ?

Ну он как-то блоками работает. Заводится блок, скажем, длиной 100 позиций, в нём помнится, где конец и где начало. При удалении с головы сдвигается указатель на начало, при добавлении в хвост -- на конец. Если элементов становится больше, то происходит реорганизация. Я думаю как-то так. В любом случае, это внутренняя кухня. Мы должны руководствоваться мануалом:

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

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

Это -- самое эффективное решение, когда надо одновременно и обращаться по индексу и быстро добавлять/удалять элементы. Если не нужно обращаться по индексу, то можно использовать LinkedList -- это ещё быстрее.

This method is an O(1) operation.

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

Здравствуйте, Аноним, Вы писали:

А>>> public MeasureData[] GetMeasures()
А>>> {
А>>> return
А>>> quene.Skip( currentItem ).Take( queneCapacity — currentItem).
А>>> Union( quene.Take( currentItem ) )
А>>> .Select ( i => i.Value).Reverse().ToArray();
А>>> }
А>>>}

S>>*) записи не упорядоченны и берутся не последние
А>записи как раз упорядочены по Index в порядке добавления, допустим index текущий = 5000, соотвественно запрос выберет с 5001-10000 и сделает union с 1-5000 записи — получится список в хронологическом порядке — ему делается reverse().

Это тоже вызывает сомнение. В этом коде Вы зачем-то перекопируете кусок списка, причём как-то даже нечитабельно.

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

Здравствуйте, SanyaVB, Вы писали:

SVB>Здравствуйте, Аноним, Вы писали:

А>>>>Не совсем то. Ниже тестовый пример, может я неправильно с ней работаю.
А>>>>Dequene будет съедать элемент, и второму потоку оно не достанется. самое старое значение должно вытесняться при вставке нового элемента а не при чтении.
Да, кстати, что по выделенному (вопрос к ТС-у). RemoveAt у списка тоже съедает элемент, и он тоже не достанется другим потокам...

SVB>А зачем работать напильником? Можно самому написать класс, который будет отвечать этим требованиям. Если емкость очереди задается, то чтобы не тратить время на удаление, можно выделить сразу нужную память и просто при необходимости перезаписывать элементы массива. Вот набросок:

SVB>

SVB>    class LimitedQueue 
SVB>    {
SVB>    }
SVB>

Все это кроме индексированного доступа предоставляет Queue из коробки.

SVB>Можно также наследоваться от IEnumerable и уже здесь сделать потокобезопасность
Как именно, кроме блокирования всей структуры во время записи/перебора?

SVB>Или задача состоит в том, чтобы использовать уже готовые списки
А свой чем лучше?

Здравствуйте, dims12, Вы писали:

D>Здравствуйте, Аноним, Вы писали:

А>>Вполне шустро работает. Меньше миллисекунды..196 тиков всего.
А>>А он не двигает все элементы при удаленни чтоли ?

D>Ну он как-то блоками работает. Заводится блок, скажем, длиной 100 позиций, в нём помнится, где конец и где начало. При удалении с головы сдвигается указатель на начало, при добавлении в хвост -- на конец. Если элементов становится больше, то происходит реорганизация. Я думаю как-то так. В любом случае, это внутренняя кухня.
Это не о List<T>.
D>Мы должны руководствоваться мануалом:

D>If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.
Речь о сложности операции удаления, а List<T> при удалении элемента передвигает весь хвост, а значит сложность O(n).

Здравствуйте, samius, Вы писали:

D>>If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.
S>Речь о сложности операции удаления, а List<T> при удалении элемента передвигает весь хвост, а значит сложность O(n).

Да, Вы правы.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, SanyaVB, Вы писали:

SVB>>Здравствуйте, Аноним, Вы писали:


S>Все это кроме индексированного доступа предоставляет Queue из коробки.

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

SVB>>Можно также наследоваться от IEnumerable и уже здесь сделать потокобезопасность
S>Как именно, кроме блокирования всей структуры во время записи/перебора?
Можно залочить статическую переменную... вообщем все зависит от того где применяется эта очередь. Но это уже вопрос по другой теме

SVB>>Или задача состоит в том, чтобы использовать уже готовые списки
S>А свой чем лучше?
человек хочет ограничить емкость и при добавлении нового элемента затирать старый, если очередь вся заполнилась. Конечно мы можем использовать такие методы как Enqueue() и Dequeue() чтобы получить ожидаемое. Кстати Dequeue() возвращает элемент, котором в этом случае использовать нет смысла(когда нет смысла — меня коробит ), т.к. задача удалить элемент И так! мы удаляем элемент, а потом добавляем элемент. В моем случае мы только добавляем элементы и затираем старые. но возможно Queue при изъятия элемента его не удаляет, а просто теряется возможность обратиться к этому элементу. Вот только лень лезть в Reflector

Здравствуйте, SanyaVB, Вы писали:

SVB>Здравствуйте, samius, Вы писали:

S>>Здравствуйте, SanyaVB, Вы писали:

SVB>>>Здравствуйте, Аноним, Вы писали:


S>>Все это кроме индексированного доступа предоставляет Queue из коробки.

SVB>Не знал что Queue имеет ограничение по элементам
Отсутстввие такого ограничения это проблема, ради которой нужно мопедировать свой контейнер?

SVB>Емкость коллекции Queue — это количество элементов, которое может вместить коллекция Queue. Когда в коллекцию Queue добавляются элементы, ее емкость автоматически увеличивается должным образом посредством перераспределения.
Выглядит как вступление к некому умозаключению, но вот заключения нет...

SVB>>>Можно также наследоваться от IEnumerable и уже здесь сделать потокобезопасность
S>>Как именно, кроме блокирования всей структуры во время записи/перебора?
SVB>Можно залочить статическую переменную... вообщем все зависит от того где применяется эта очередь. Но это уже вопрос по другой теме
Можно, но это уже походит на блокировку не одной очереди, а всех очередей в домене

SVB>>>Или задача состоит в том, чтобы использовать уже готовые списки
S>>А свой чем лучше?
SVB>человек хочет ограничить емкость и при добавлении нового элемента затирать старый, если очередь вся заполнилась. Конечно мы можем использовать такие методы как Enqueue() и Dequeue() чтобы получить ожидаемое. Кстати Dequeue() возвращает элемент, котором в этом случае использовать нет смысла(когда нет смысла — меня коробит ), т.к. задача удалить элемент И так! мы удаляем элемент, а потом добавляем элемент. В моем случае мы только добавляем элементы и затираем старые. но возможно Queue при изъятия элемента его не удаляет, а просто теряется возможность обратиться к этому элементу. Вот только лень лезть в Reflector
Ради того что бы получить метод, не возвращающий элемент при удалении писать свой контейнер?

Здравствуйте, samius, Вы писали:

S>Здравствуйте, SanyaVB, Вы писали:

SVB>>Здравствуйте, samius, Вы писали:

S>>>Здравствуйте, SanyaVB, Вы писали:

SVB>>>>Здравствуйте, Аноним, Вы писали:

S>Ради того что бы получить метод, не возвращающий элемент при удалении писать свой контейнер?
Контейнер все равно придется писать, даже если он будет использовать Queue — теория чистого кода
Поэтому кто как хочет. по строчкам кода не большое различие...

Здравствуйте, SanyaVB, Вы писали:

SVB>Здравствуйте, samius, Вы писали:

S>>Ради того что бы получить метод, не возвращающий элемент при удалении писать свой контейнер?
SVB>Контейнер все равно придется писать, даже если он будет использовать Queue — теория чистого кода
Что за теория такая?

SVB>Поэтому кто как хочет. по строчкам кода не большое различие...
между тем писать свой или нет? Я так не считаю.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, SanyaVB, Вы писали:

SVB>>Здравствуйте, samius, Вы писали:

S>>>Ради того что бы получить метод, не возвращающий элемент при удалении писать свой контейнер?
SVB>>Контейнер все равно придется писать, даже если он будет использовать Queue — теория чистого кода
S>Что за теория такая?
чистый код

SVB>>Поэтому кто как хочет. по строчкам кода не большое различие...
S>между тем писать свой или нет? Я так не считаю.
Может быть, может быть... но если контейнер свой делать то придется скорее всего наследовать его от IEnumerable<T>, IEnumerator<T>. Тут больше строчек уйдет на фигурные скобочки и названия методов...

Здравствуйте, SanyaVB, Вы писали:

SVB>Здравствуйте, samius, Вы писали:

S>>Здравствуйте, SanyaVB, Вы писали:

SVB>>>Здравствуйте, samius, Вы писали:

S>>>>Ради того что бы получить метод, не возвращающий элемент при удалении писать свой контейнер?
SVB>>>Контейнер все равно придется писать, даже если он будет использовать Queue — теория чистого кода
S>>Что за теория такая?
SVB>чистый код
Я не понимаю. Ты предлагаешь не использовать очередь потому как Dequeue возвращает элемент, и отсылаешь к Бобу Мартину за объяснениями? Давай конкретнее, главу, страницу и т.п.

SVB>>>Поэтому кто как хочет. по строчкам кода не большое различие...
S>>между тем писать свой или нет? Я так не считаю.
SVB>Может быть, может быть... но если контейнер свой делать то придется скорее всего наследовать его от IEnumerable<T>, IEnumerator<T>. Тут больше строчек уйдет на фигурные скобочки и названия методов...
А ради чего собственно свой-то?

Здравствуйте, samius, Вы писали:

S>Здравствуйте, SanyaVB, Вы писали:

SVB>>Здравствуйте, samius, Вы писали:

S>>>Здравствуйте, SanyaVB, Вы писали:

SVB>>>>Здравствуйте, samius, Вы писали:


S>Я не понимаю. Ты предлагаешь не использовать очередь потому как Dequeue возвращает элемент, и отсылаешь к Бобу Мартину за объяснениями? Давай конкретнее, главу, страницу и т.п.

Конечно не из-за этого. Задача контейнера Queue немного отличается от поставленной задачи => нужно делать обертку в результате которой получаем контейнер для поставленной задачи. Такой код хорошо читаем. Мы знаем что этот контейнер отвечает таким требованиям и у него есть метод Add(...) и при необходимости можем прогнать по циклу.
PS: Была бы у меня книга под рукой — написал бы номер глав, но как припоминается с первой по последнюю про это говорится, т.к. учат писать так, чтобы легко можно было код без комментариев прочитать
Я не говорю что твой вариант неверный. кто-то вообще переменные называют a,b,c,d...

Здравствуйте, SanyaVB, Вы писали:

SVB>Здравствуйте, samius, Вы писали:

S>>Я не понимаю. Ты предлагаешь не использовать очередь потому как Dequeue возвращает элемент, и отсылаешь к Бобу Мартину за объяснениями? Давай конкретнее, главу, страницу и т.п.

SVB>Конечно не из-за этого. Задача контейнера Queue немного отличается от поставленной задачи => нужно делать обертку в результате которой получаем контейнер для поставленной задачи.
Про обертку очень неочевидный переход. Вообще необходимость спецконтейнера под вопросом.

SVB>Такой код хорошо читаем. Мы знаем что этот контейнер отвечает таким требованиям и у него есть метод Add(...) и при необходимости можем прогнать по циклу.
Код мопедного контейнера лучше читаем чем код использования стандартного?

SVB>PS: Была бы у меня книга под рукой — написал бы номер глав, но как припоминается с первой по последнюю про это говорится, т.к. учат писать так, чтобы легко можно было код без комментариев прочитать
Про то что учат что бы код можно было легко читать без комментариев — это верно. Но необходимость самописного контейнера для такой задачи из этого не вытекает.
Давай по-другому. Представим что такой контейнер написан. Откуда по-твоему читающий код должен понять, нафига этот контейнер нужен? (особенно без комментариев)

SVB>Я не говорю что твой вариант неверный. кто-то вообще переменные называют a,b,c,d...
Угу, а кто-то мопедирует контейнеры что бы чего лишнего не вернули.