По существу, следующий вопрос к моему старому вопросу здесь: Выбор конкретных объектов, удовлетворяющих условиям
У меня есть объекты, называемые переменными, которые могут быть назначены или не назначены. Каждая переменная имеет домен, что означает значения, которым может быть назначена переменная. Например, переменная может принимать значения от 1 до 32. Я могу запросить размер переменной в постоянное время очень высокооптимизированным методом.
Одна важная операция - найти диапазон неназначенных элементов с наименьшими размерами доменов. Для этого у меня есть вектор указателей на все переменные-объекты. Бухгалтерия ведется для того, чтобы поддерживать инвариант, который говорит, что указатели на все неназначенные переменные появляются в первую очередь перед всеми присвоенными.
С течением времени переменные динамически изменяются, изменяются размеры их доменов, и неназначенные переменные могут назначаться, и наоборот. Когда состояния переменных меняются, они меняются местами, так что инвариант снова сохраняется. Это означает, что размер вектора остается неизменным на протяжении всего выполнения программы.
Затем возникает мой вопрос: найти эффективный диапазон неназначенных переменных, имеющих наименьший размер домена. Что я делаю сейчас: поддерживаю инвариант с вектором указателей. Затем, когда мне нужно найти диапазон элементов, я полностью сортирую часть вектора, содержащую указатели, на неназначенные переменные.
Это невероятно медленно. Согласно профайлеру Visual Studio, я использую около 50% общего времени сортировки. Эти диапазоны элементов указателя, которые я сортирую, довольно малы, не более 500-600 сотен элементов. Есть ли возможная причина для этого?
На самом деле до этой схемы я использовал метод, который не основывался на сортировке. Это чувствуется должно быть медленнее и даже асимптотически так и было. Я вижу очень большое негативное влияние на производительность моей новой схемы, и сортировка - это та, которая выполняет большую часть работы.
Могу ли я попробовать что-нибудь? Сортировка 500-600 элементов должна быть ничем на современном оборудовании, верно (и с std :: sort)? std :: частичная_сортировка на самом деле тоже не меняет ситуацию.
Я немного не уверен, смогу ли я предоставить вам более полезную информацию, но, пожалуйста, дайте мне знать, если что-то есть. Я действительно ошеломлен этим явлением, что бы оно ни вызывало. Я использую C ++, если это имеет значение, но я полагаю, что это также можно рассматривать как независимый от языка вопрос.
РЕДАКТИРОВАТЬ: Вот упрощенный пример:
Ноль в этом векторе обозначает назначенные переменные, ненулевые элементы означают неназначенные переменные с таким размером домена. Допустим, мой вектор выглядит так:
{1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 0, 0, 0, 0, 0}
Тогда мой алгоритм делает один шаг и изменяет состояния переменных. Вектор выглядит как
{2, 0, 3, 3, 3, 4, 4, 3, 3, 3, 4, 5, 0, 0, 1, 0, 0}
Прямо сейчас инвариант нарушается: в передней части находятся неназначенные переменные. Мне нужно что-то сделать, чтобы исправить это. Затем мне нужно найти диапазон элементов с наименьшими значениями. Исправление и сортировка производит, например:
{1, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 0, 0, 0, 0, 0}
EDIT2:
Дополнительные сведения о проблеме. Для неназначенных переменных не так много потенциально разных диапазонов значений. Я знаю это заранее, и максимальное значение всегда составляет максимум 32, причем 1 всегда является самым низким значением. Изменения значений могут происходить в любом месте набора элементов, но когда это происходит, за один шаг каждое изменяющееся значение изменяется не более чем на 1. И да, мне нужно найти все элементы с наименьшим значением.
Да, я считаю, что изменение порядка может быть выполнено, когда ведется бухгалтерия.Мы можем предположить, что мы начинаем с отсортированного диапазона и инвариант имеет место.Но тогда возникает вопрос, как на самом деле можно сделать переупорядочение?Хорошо, наверное, я должен проверить, какие элементы изменились, и каким-то образом позволить им всплыть на свои места.Есть идеи, как это сделать (на уровне кода)?Является ли сама структура данных хорошей идеей?
Первый EDIT немного вводил в заблуждение, теперь он исправлен.Таким образом, диапазоны всегда составляют не более 500-600 элементов, с множеством концептуальных значений в небольшом диапазоне (максимум от 1 до 32).
EDIT3:
Если кто-либоЛюбопытно, я объясню предыдущий подход, который был намного быстрее и не полагался на сортировку.Я считаю, что все это можно сделать еще более эффективно, поэтому я хотел попробовать перейти на другую схему.
Идея была в следующем: в каждой точке у меня будет вектор указателей, содержащий только элементы с наименьшим значением домена.Затем алгоритм выполняет свою работу, и что-то происходит с переменными.Сначала я делаю линейное сканирование всех переменных и проверяю, изменилось ли наименьшее значение домена.Если это так, я перестраиваю вектор элементов.Если это не так, я проверяю небольшой диапазон указателей и либо добавляю, либо удаляю элементы, чтобы снова удерживать инвариант (контейнер содержит все неназначенные переменные с наименьшим доменом).
У меня такое чувствоможет быть быстрее с моей новой схемой, так как размер вектора остается постоянным, элементы в нем только меняются местами или поворачиваются.Хотя я могу быть совершенно неправ, очень сложно сказать, что действительно эффективно для оборудования.