Здравствуйте. Есть список объектов. Он имеет разный размер: иногда это буквально пара элементов, иногда — пол сотни. По этому списку очень часто происходит поиск (точнее, по одному из полей хранимых объектов). Хотелось бы добиться максимальной скорости при небольших накладных расходах. Сама операция сравнения в поиске тривиальна (буквально два указателя), но поиск происходит очень и очень часто. По определенным причинам, организовать это в виде std::map не получится, контейнер должен оставаться листом.
Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list? Ведь поиск центра будет последовательным, а, значит, мы потеряем больше, чем приобретем. С другой стороны, зная, что последовательность отсортирована, мы можем прерывать линейный перебор, если текущий "ключ" уже больше искомого. Но это тоже сомнительное ускорение. Организовать параллельную мапу? Но это слишком прожорливо и трудно поддерживать синхронизацию, по-моему. Какие есть решения, заточенные под подобную проблему? Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?

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


W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск. Но как его организовать, если у нас list?
Skip list — стандартный подход для такой ситуации. Работает хорошо.

W>Организовать параллельную мапу? Но это слишком прожорливо
Отличный вариант. Да и прожорливого там особенно ничего нет — просто хранишь указатели/итераторы в ней на оригинальные элементы в списке.

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

W>и трудно поддерживать синхронизацию, по-моему.
Чтобы было легко — заверни в контейнер и работай через него.
Например, посмотри на boost::multi_index — там и список и словарь можно поднять над одними данными.

W> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.

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

W>Здравствуйте. Есть список объектов. Он имеет разный размер: иногда это буквально пара элементов, иногда — пол сотни. По этому списку очень часто происходит поиск (точнее, по одному из полей хранимых объектов). Хотелось бы добиться максимальной скорости при небольших накладных расходах. Сама операция сравнения в поиске тривиальна (буквально два указателя), но поиск происходит очень и очень часто. По определенным причинам, организовать это в виде std::map не получится, контейнер должен оставаться листом.

В дополнение к skip lists можно попробовать также рассмотреть и B+ tree (не путать с B tree)

In a B+ tree, leaf nodes data are ordered as a sequential linked list

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

Для такого количества я бы вектор указателей держал. При удалении просто бы обнулял указатели. Время от времени бы обслуживал контейнер, выбрасывая нулевые указатели. Искал бы линейным поиском.

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

W>Здравствуйте. Есть список объектов. Он имеет разный размер: иногда это буквально пара элементов, иногда — пол сотни. По этому списку очень часто происходит поиск (точнее, по одному из полей хранимых объектов). Хотелось бы добиться максимальной скорости при небольших накладных расходах. Сама операция сравнения в поиске тривиальна (буквально два указателя), но поиск происходит очень и очень часто. По определенным причинам, организовать это в виде std::map не получится, контейнер должен оставаться листом.

список + доп индекс (сортированный вектор (boost::flat_set) или мапа) <ключ (два указателя по твоим словам), list<T>::iterator (или указатель на объект)>
если указатели, составляющие ключ, меняются, то придется перестраивать индекс

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

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

W> splice за O(1)
Это ведь уже не актуально? В смысле, в свежем стандарте у списка size за константное время отрабатывать должен, а splice принесли в жертву.

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

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

W>> splice за O(1)
DE>Это ведь уже не актуально? В смысле, в свежем стандарте у списка size за константное время отрабатывать должен, а splice принесли в жертву.

Во-первых, это лишь ещё один довод в пользу vector.

Во-вторых, старые требования к сложности splice в новом стандарте (это же про C++11/C++14?) не изменились — где было константное время работы, там и осталось константное время работы (даже ещё пару новых перегрузок добавили, если формально). Верно, что константный size входит в противоречие с некоторыми оптимизациями splice, но никто и не гарантировал, что они будут всегда работать. И если в одной версии STL они использовались, то в других — нет. Тут ситуация аналогична COW или SSO для std::string — что-то где-то реализовано, но без гарантий, что на другой платформе внутренне поведение сохранится. Так в новом стандарте SSO всё ещё допустимо, а COW противоречит формальным требованиям.

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

W>Здравствуйте. Есть список объектов. Он имеет разный размер: иногда это буквально пара элементов, иногда — пол сотни.

Пол-сотни, говоришь... А std::list зачем тогда?

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

W>Здравствуйте. Есть список объектов. Он имеет разный размер: иногда это буквально пара элементов, иногда — пол сотни. По этому списку очень часто происходит поиск (точнее, по одному из полей хранимых объектов). Хотелось бы добиться максимальной скорости при небольших накладных расходах. Сама операция сравнения в поиске тривиальна (буквально два указателя), но поиск происходит очень и очень часто. По определенным причинам, организовать это в виде std::map не получится, контейнер должен оставаться листом.
W>Единственная идея — отсортировать элементы по возрастанию и организовать бинарный поиск.

В 50 элементах искать хочешь ?
Как бы не так чтобы очень много...



W> Но как его организовать, если у нас list?

сделай внутри или где-то сбоку параллельный vector например ссылок на ноды списка, и его держи отсортированным, и по нему ищи.
Главное, чтобы это всё менялось не часто, а то ведь перестраивать надо.


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

Здравствуйте, watchmaker, Вы писали:
W>Skip list — стандартный подход для такой ситуации. Работает хорошо.
Таких списков — сотни и тысячи. Подавляющее большинство из них маленькие. Если я начну использовать нетривиальные и избыточные контейнеры в каждом из них, польза от ускорения будет похоронена вредом от перерасходом памяти.
Или я неправильно понял идею?

W>Отличный вариант. Да и прожорливого там особенно ничего нет — просто хранишь указатели/итераторы в ней на оригинальные элементы в списке.
То же самое. Параллельные контейнеры исключаются из-за оверхеда.

W>>но поиск происходит очень и очень часто.
W>А изменения насколько часты? Если их мало, а исходный список вообще никак трогать не хочется, то заводи параллельный вектор из указателей на элементы списка: его сортируй и по нему ищи. Дополнительной памяти совсем мало требуется, а стоимость поддержания сортированности будет мала, если изменения исходного списка будут редки.
Изменения очень редки. Фактически, это константная справочная таблица свойств. Просто оооочень большая и вложенная.

W>> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
W>Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.
Вот мне это кажется наилучшей идеей. При инициализации словаря происходит слияние множества небольших словарей в единую структуру. Поэтому splice за O(1) очень полезен. Но с другой стороны, если воспользоваться move-семантикой, мне кажется, издержки при перераспределении вектора будут минимальны. В этом случае, те множества, которые я хочу "ускорить", я буду спокойно сортировать (единожды, после слияния) и использовать бинарный поиск. Логично?

Здравствуйте, T4r4sB, Вы писали:
TB>Пол-сотни, говоришь... А std::list зачем тогда?
Потому, что элементы могут оказаться сверхтяжелыми. Иметь десяток вложенных уровней иерархии. Как я написал выше, можно попытаться воспользоваться семантикой переноса, чтобы операции над вектором были не столь мучительны.

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

MZ>В 50 элементах искать хочешь ?
MZ>Как бы не так чтобы очень много...
Но очень часто

MZ>сделай внутри или где-то сбоку параллельный vector например ссылок на ноды списка, и его держи отсортированным, и по нему ищи.
MZ>Главное, чтобы это всё менялось не часто, а то ведь перестраивать надо.
MZ>Можно сделать также мап или хэштаблицу ключей на ссылки на элементы списка, и тоже получить поиск автоматом быстрым.
Ничего "сбоку" делать не могу, оверхед будет колоссальным.

В моей структуре есть еще одно узкое место.
Как я уже написал, имеется громадная вложенная система узлов, по принципу "каждый узел хранит список узлов, у которых свои узлы и т.п." Так вот часть узлов — пустые, просто идентификатор имени узла и контейнер для дочерних узлов. Но в части узлов есть дополнительные данные: множество имен, от которых наследован узел, значение узла, пометка узла и т.п. В 99% случаев эти данные пустуют, но создают ненужный балласт как в памяти, так и в операциях копирования, удаления и т.п. Если какой-то хитроумный паттерн, чтобы избавиться от подобного оверхеда?
1. Узел не полиморфен, я не могу сделать "базовый пустой узел" и "узел с данными". Тем более, что вариаций "с тем данным, с другим, с обоими" и т.п. будет слишком много.
2. std::optional не пойдет, потому что, не избавит от оверхеда по памяти. И опять же, делать std::optional на каждый отдельный элемент данных не выгодно, а на все вместе — слишком редко у узла нет ничего вообще.
3. Сделать сторонний словарь для каждого данного, использовав this узла как ключ? Боюсь, проигрыш по скорости доступа будет больше, чем выигрыш от экономии памяти.
Есть еще идеи?

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

W>Здравствуйте, T4r4sB, Вы писали:
TB>>Пол-сотни, говоришь... А std::list зачем тогда?
W>Потому, что элементы могут оказаться сверхтяжелыми.
А, плохо. Тогда вектор юников.

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

W>Здравствуйте, watchmaker, Вы писали:
W>>Skip list — стандартный подход для такой ситуации. Работает хорошо.
W>Таких списков — сотни и тысячи. Подавляющее большинство из них маленькие. Если я начну использовать нетривиальные и избыточные контейнеры в каждом из них, польза от ускорения будет похоронена вредом от перерасходом памяти.

Странно это немного выглядит.
Тысяча списков по полсотни элементов — это всего-то 50K записей. Если даже продолжать всё хранить в std::list и ничего с этим не делать, то дополнительные расходы на индекс через вектор указателей будут состоять из, собственно, хранилища 50K указателей и по 2 указателя (для начала и длины) на каждый список, всё. В сумме на 64-битной платформе получится примерно 400 килобайт. На десктопе это и в кеш влезет, и ещё место останется. Тем более, что если большинство списков по паре элементов, то и памяти в разы меньше потребуется. Что за задача такая, что 400 килобайт уже много?

W>>>но поиск происходит очень и очень часто.
W>>А изменения насколько часты? Если их мало, а исходный список вообще никак трогать не хочется, то заводи параллельный вектор из указателей на элементы списка: его сортируй и по нему ищи. Дополнительной памяти совсем мало требуется, а стоимость поддержания сортированности будет мала, если изменения исходного списка будут редки.
W>Изменения очень редки. Фактически, это константная справочная таблица свойств. Просто оооочень большая и вложенная.
Вообще, иногда бывает полезным разделить этапы модификации структуры и этапы поиска. Тем более, когда точно известно, что таблица потом используется без модификаций. Какой-нибудь алгоритм построения суффиксного дерева прекрасно может это иллюстрировать: пока дерево строится и модифицируется, то в нём хранится куча вспомогательных, но необходимых данных. Когда оно построено, то по нему можно эффективно искать, но все оставшиеся данные для этого не нужны. И можно просто нужные поля скопировать в компактный массив, улучшив и потребление памяти, и производительность — такое дерево уже нельзя модифицировать, но с поиском оно справляется даже лучше.

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

W>>> Попытаться заменить лист на вектор? Или на таких размерах коллекций я ничего не выиграю вообще?
W>>Ну если тебе не нужно операций и свойств, которые специфичны для списков, вроде splice за O(1) или персистентности итераторов, то вектор часто лучше.
W>Вот мне это кажется наилучшей идеей. При инициализации словаря происходит слияние множества небольших словарей в единую структуру. Поэтому splice за O(1) очень полезен.
Интересно, то есть splice уже используется? Не часто этот метод можно встретить: либо сценарий слияний неподходящий, либо массивы всё равно быстрее оказываются :)

W>Но с другой стороны, если воспользоваться move-семантикой, мне кажется, издержки при перераспределении вектора будут минимальны. В этом случае, те множества, которые я хочу "ускорить", я буду спокойно сортировать (единожды, после слияния) и использовать бинарный поиск. Логично?
В целом, да. Тем более, что если искать нужно часто, а менять редко, то почему бы просто не выделить время на предобработку — а в ней хоть копируй элементы, хоть перемещай. Главное чтобы многоразовый поиск быстро потом работал, а не одноразовое действие по сортировке.

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

W>Как я уже написал, имеется громадная вложенная система узлов, по принципу "каждый узел хранит список узлов, у которых свои узлы и т.п." Так вот часть узлов — пустые, просто идентификатор имени узла и контейнер для дочерних узлов. Но в части узлов есть дополнительные данные: множество имен, от которых наследован узел, значение узла, пометка узла и т.п. В 99% случаев эти данные пустуют, но создают ненужный балласт как в памяти, так и в операциях копирования, удаления и т.п. Если какой-то хитроумный паттерн, чтобы избавиться от подобного оверхеда?
Если они прямо разом в 99% пустуют, то казалось бы достаточно просто вынести их в отдельную структуру, а в родительской отставить указатель на неё, который в 99% случаев будет равен nullptr. А если даже не разом, то всё равно, вероятно, найдётся одно или несколько подмножеств полей, которые так можно разделить.

W>2. std::optional не пойдет, потому что, не избавит от оверхеда по памяти. И опять же, делать std::optional на каждый отдельный элемент данных не выгодно, а на все вместе — слишком редко у узла нет ничего вообще.
W>3. Сделать сторонний словарь для каждого данного, использовав this узла как ключ? Боюсь, проигрыш по скорости доступа будет больше, чем выигрыш от экономии памяти.
W>Есть еще идеи?
Идей не мало придумали, но выбор зависит как раз от баланса между скоростью и производительностью — можно сильно сжать, но получить неудобный доступ, а можно и не сжимать, но зато обращаться по прямым адресам.

Популярный подход — хранить опциональные поля в массиве переменной длины прямо в основной структуре. В стандартном С это делается через flexible array member, в С++ чуть менее удобным способом через placement new.
То есть фактически все узлы представляют из себя структуру переменной длины, у которой в начале идёт общая для всех часть, продолжающаяся массивом переменным массивом.
И вот формат хранения данных в этом массиве уже задаёт соотношение между скоростью доступа и компактностью хранения.

Например, есть вариант с тегами: когда массив представляет собой последовательность пар из тега, за которым следует соответствующая ему структура, тип которой однозначно определяется тегом. Встретить такой подход можно много где: от опций в TCP до полей в protobuf. Он прост и легко разбирается программно. Главный недостаток тоже очевиден — последовательный доступ к полям. Очень просто проитерироваться по всей структуре, но поиск конкретного поля по типу или тегу обычно сводится к линейному просмотру.

Впрочем, от линейного просмотра можно избавится, если хранить сразу битовую маску, в которой заданы порядковые номера полей, имеющие значение не равное значению по умолчанию. А уже за битовой маской будет идти список значений установленных полей (тут уже можно даже теги не хранить, если соблюдать однозначный порядок между битами и полями). Таким образом памяти будет расходоваться только по одному биту на поле + непосредственно занимаемый размер только для присутствующих полей. При таком подходе можно как очень быстро проверить наличие поля (через проверку одного бита в маске), так и достаточно быстро находить смещение поля относительно начала структуры (посчитав биты, для чего у cpu даже бывают специальные инструкции).
Конечно, всё это не очень приятно программировать вручную (не редкая ситуация с placement new), что отчасти объясняет почему так популярны кодогенераторы для задания таких структур. И если все поля не устроены одинаково (например, не представляют из себя одиночный указатель), то, действительно, стоит переложить всю эту скучную работу по подсчёту смещений на скрипт.

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

W>В моей структуре есть еще одно узкое место.
Это граф?

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

W>В моей структуре есть еще одно узкое место.
W>Как я уже написал, имеется громадная вложенная система узлов, по принципу "каждый узел хранит список узлов, у которых свои узлы и т.п." Так вот часть узлов — пустые, просто идентификатор имени узла и контейнер для дочерних узлов. Но в части узлов есть дополнительные данные: множество имен, от которых наследован узел, значение узла, пометка узла и т.п. В 99% случаев эти данные пустуют, но создают ненужный балласт как в памяти, так и в операциях копирования, удаления и т.п. Если какой-то хитроумный паттерн, чтобы избавиться от подобного оверхеда?
W>1. Узел не полиморфен, я не могу сделать "базовый пустой узел" и "узел с данными". Тем более, что вариаций "с тем данным, с другим, с обоими" и т.п. будет слишком много.

можно схематичный код глянуть, чтобы понять о чем речь?

Здравствуйте, Kernan, Вы писали:
K>Это граф?
Дерево.

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

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

W>>В моей структуре есть еще одно узкое место.
W>>Как я уже написал, имеется громадная вложенная система узлов, по принципу "каждый узел хранит список узлов, у которых свои узлы и т.п." Так вот часть узлов — пустые, просто идентификатор имени узла и контейнер для дочерних узлов. Но в части узлов есть дополнительные данные: множество имен, от которых наследован узел, значение узла, пометка узла и т.п. В 99% случаев эти данные пустуют, но создают ненужный балласт как в памяти, так и в операциях копирования, удаления и т.п. Если какой-то хитроумный паттерн, чтобы избавиться от подобного оверхеда?
W>>1. Узел не полиморфен, я не могу сделать "базовый пустой узел" и "узел с данными". Тем более, что вариаций "с тем данным, с другим, с обоими" и т.п. будет слишком много.

NB>можно схематичный код глянуть, чтобы понять о чем речь?

class SKIN_API SkinNode final
{
  typedef std::pair<StrCache, SkinNode> Child;
  typedef std::list<
    Child, 
    boost::fast_pool_allocator<
      Child,
      boost::default_user_allocator_new_delete,
      boost::details::pool::null_mutex,
      1024>> Childs;

  // Все поля ниже зачастую пусты, но редко пусты все одновременно.
  NodeValue   m_value;
  Childs      m_childs;
  Parents     m_parents;
  StrCache    m_mark;
  StrCache    m_config;
}