Коллекция, всегда содержит n [2..20] значений и поддерживает две операции:
1. прочитать минимальный элемент и остальные элементы, ему равные, без модификации коллекции. Например (1, 2, 3, 2, 1, 1) -> (1, 1, 1)
2. заменить элементы из п.1 на новые

С двоичной кучей знаком, но может можно лучше, учитывая небольшой размер коллекции и специфику?

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

scf>Коллекция, всегда содержит n [2..20] значений и поддерживает две операции:
scf>1. прочитать минимальный элемент и остальные элементы, ему равные, без модификации коллекции. Например (1, 2, 3, 2, 1, 1) -> (1, 1, 1)
scf>2. заменить элементы из п.1 на новые

Зачем двойная? Обычная куча, одинаковые элементы хранятся в виде списка. Чтение и модификация за O(log(N)), чтения одинаковых элементов за O(M). С трудом верится, что можно сделать быстрее. Кстати, если значений всего 20, то есть вероятность, что полный перебор, сможет быть быстрее из-за локальности данных и loop unrolling (если речь об x86-64).

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

scf>Коллекция, всегда содержит n [2..20] значений и поддерживает две операции:
scf>1. прочитать минимальный элемент и остальные элементы, ему равные, без модификации коллекции. Например (1, 2, 3, 2, 1, 1) -> (1, 1, 1)
scf>2. заменить элементы из п.1 на новые
Коллекция упорядоченная? Иначе можно хранить map<value, count>...

Хранить в виде отсортированного массива. Выбрать минимально допустимый тип данных. При вставке двоичным поиском находить место и копировать кусками память туда-сюда. Рассмотреть возможность хранения одинаковых значений в виде пары (значение, количество). Если это часто будет встречаться.

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

VF>Коллекция упорядоченная? Иначе можно хранить map<value, count>...
А если не упорядоченная, то unordered_map<value, count>...

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

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

VF>>Коллекция упорядоченная? Иначе можно хранить map<value, count>...
M>А если не упорядоченная, то unordered_map<value, count>...

Под "упорядоченная" я имел ввиду что порядок едиц, двоек, и т.д имеет значение.
То есть (1, 2, 3, 2, 1, 1) != (1, 1, 1, 2, 2, 3)

Здравствуйте, scf,
Я тут поигрался c двусвязным списком в c#

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

    public class SaveAndUpdate<TValue>
    {
        private readonly LinkedList<TValue> _store;
        private readonly Dictionary<TValue, LinkedListNode<TValue>> _links;

        public SaveAndUpdate() {
            _store = new LinkedList<TValue>();
            _links = new Dictionary<TValue, LinkedListNode<TValue>>();
        }

        public void Add(TValue value) {
            var newLink = new LinkedListNode<TValue>(value);
            if(_links.TryGetValue(value, out LinkedListNode<TValue> existingLink)) {
                _store.AddBefore(existingLink, newLink);
            } else {
                _store.AddLast(newLink);
            }
            _links[value] = newLink;
        }

        public void Update(TValue existingValue, TValue newValue) {
            if(!_links.TryGetValue(existingValue, out LinkedListNode<TValue> existingLink)) {
                throw new InvalidOperationException($"The given element '{existingValue}' does not exist.");
            }

            if(_links.TryGetValue(newValue, out LinkedListNode<TValue> existingNewValueLink)) {
                while (existingLink != null && existingLink.Value.Equals(existingValue)) {
                    var newLink = new LinkedListNode<TValue>(newValue);
                    _store.AddBefore(existingNewValueLink, newLink);
                    existingNewValueLink = newLink;
                    _links[newValue] = existingNewValueLink;
                    existingLink = existingLink.Next;
                    _store.Remove(existingLink.Previous);
                }
            } else {
                while (existingLink != null && existingLink.Value.Equals(existingValue)) {
                    existingLink.Value = newValue;
                    existingLink = existingLink.Next;
                }
            }
        }

        public IEnumerable<TValue> GetValues(TValue value) {
            if(!_links.TryGetValue(value, out LinkedListNode<TValue> existingLink)) {
                throw new InvalidOperationException($"The given element '{value}' does not exist.");
            }

            while (existingLink != null && existingLink.Value.Equals(value)) {
                yield return existingLink.Value;
                existingLink = existingLink.Next;
            }
        }

        public IEnumerable<TValue> GetValues() {
            return _store;
        }
    }

scf>Коллекция, всегда содержит n [2..20] значений и поддерживает две операции:

В коллекции 20 элементов максимум. Используем простой массив (отсортированный или нет значения не имеет).

Всего 20!!! элементов. Самый быстрый способ работы — проход по всем элементам, главное, чтобы они лежали рядом, т.е. последовательно, чтобы гарантированно попали в кеш при первом обращении (ну, или аппаратный предсказатель их туда положит).

Это все, расходимся.

P.S. 20 элементов, блин!!! О-нотации имеют значения для ассимптотик, т.е. когда элементы нельзя по пальцам пересчитать. А вроде тут грамотные люди, блин, даже преподы-старперы есть. Или мне так казалось. Я ф шоке.

P.P.S. Всякие map будут 100 пудов тормозить за счет рандомного обращения к памяти.

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

R>Всего 20!!! элементов. Самый быстрый способ работы — проход по всем элементам, главное, чтобы они лежали рядом, т.е. последовательно, чтобы гарантированно попали в кеш при первом обращении (ну, или аппаратный предсказатель их туда положит).

Для массива интов — может быть, но у меня массив разнотипных объектов по 4-20 байт. Конечно, можно попробовать их сериализовывать в плоский массив и сравнивать через а-ля memcmp, но уменьшение кол-ва сравнений выглядит более предпочтительно.

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

R>>Всего 20!!! элементов. Самый быстрый способ работы — проход по всем элементам, главное, чтобы они лежали рядом, т.е. последовательно, чтобы гарантированно попали в кеш при первом обращении (ну, или аппаратный предсказатель их туда положит).
scf>Для массива интов — может быть, но у меня массив разнотипных объектов по 4-20 байт. Конечно, можно попробовать их сериализовывать в плоский массив и сравнивать через а-ля memcmp, но уменьшение кол-ва сравнений выглядит более предпочтительно.
Это всего 400 байт максимум. Даже в регистры процессора поместится. Если это действительно узкое место твоей программы, то пробуй разные варианты и выбирай perf-тестами самый быстрый.
Для таких размеров разница в алгоритмике будет едва различима в микроскоп, т.к. все тут упомянутые алгоритмы будут O(1), по определению; большее влияние оказывает особенности железа.

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

scf>Коллекция, всегда содержит n [2..20] значений и поддерживает две операции:
scf>1. прочитать минимальный элемент и остальные элементы, ему равные, без модификации коллекции. Например (1, 2, 3, 2, 1, 1) -> (1, 1, 1)
scf>2. заменить элементы из п.1 на новые

scf>С двоичной кучей знаком, но может можно лучше, учитывая небольшой размер коллекции и специфику?

Упорядоченный по значению элемента массив пар {значение, количество}. Первая операция делается за O(1), вторая может потребовать переупорядочивания, а значит, она делается за O(N) (поиск занимает O(lnN), перетряска массива — O(N)).

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