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

Question

Кто-нибудь может порекомендовать хороший и опрятный способ добиться этого:

float CalculateGoodness(const Thing& thing);

void SortThings(std::vector<Thing>& things)
{
    // sort 'things' on value returned from CalculateGoodness, without calling CalculateGoodness more than 'things.size()' times
}

Очевидно, я мог бы использовать std::sort с функцией сравнения, которая вызывает CalculateGoodness, но тогда она будет вызываться несколько раз за Thing по сравнению с другими элементами, что не хорошо, если CalculateGoodness стоит дорого , Я мог бы создать еще один std::vector, чтобы хранить оценки и std::sort, и таким же образом переставить things, но я не вижу аккуратного способа сделать это. Есть идеи?

Редактировать: Извинения, я должен был сказать, не изменяя Thing, иначе это довольно легко решить проблему:)

Answer 1

Я могу придумать простое преобразование (ну, два), чтобы получить то, что вы хотите. Вы можете использовать std::transform с подходящими предикатами.

• std::vector<Thing> до std::vector< std::pair<Result,Thing> >
• отсортировать второй вектор (работает, потому что пара сортируется по первому члену)
• обратное преобразование

Тадаам:)

РЕДАКТИРОВАТЬ : Минимизация количества копий

• std::vector<Thing> до std::vector< std::pair<Result,Thing*> >
• сортировка по второму вектору
• преобразовать обратно во вторичный вектор (локальный)
• поменять местами оригинальные и локальные векторы

Таким образом, вы будете копировать каждый Thing только один раз. Следует помнить, что sort выполняет копии, чтобы его можно было использовать.

И потому что я чувствую себя дарованным:

typedef std::pair<float, Thing*> cached_type;
typedef std::vector<cached_type> cached_vector;

struct Compute: std::unary_function< Thing, cached_type >
{
  cached_type operator()(Thing& t) const
  {
    return cached_type(CalculateGoodness(t), &t);
  }
};

struct Back: std::unary_function< cached_type, Thing >
{
  Thing operator()(cached_type t) const { return *t.second; }
};


void SortThings(std::vector<Thing>& things)
{
  // Reserve to only allocate once
  cached_vector cache; cache.reserve(things.size());

  // Compute Goodness once and for all
  std::transform(things.begin(), things.end(),
                 std::back_inserter(cache), Compute());

  // Sort
  std::sort(cache.begin(), cache.end());

  // We have references inside `things` so we can't modify it
  // while dereferencing...
  std::vector<Thing> local; local.reserve(things.size());

  // Back transformation
  std::transform(cache.begin(), cache.end(),
                 std::back_inserter(local), Back());

  // Put result in `things`
  swap(things, local);
}

При условии обычного предостережения emptor: от макушки головы может убить котят ...

Answer 2

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

Еще одна возможность, если вы не можете изменить свой тип, - это сохранение какого-то std::map для ваших объектов и их ранее вычисленных значений. Ваша функция сортировки будет использовать ту карту, которая действует как кеш.

Answer 3

Я проголосовал Ответ Брайана , потому что он, безусловно, лучше всего соответствует тому, что вы ищете. Но другое решение, которое вы должны рассмотреть, это , просто напишите его простым способом . Процессоры становятся все мощнее с каждым днем. Сделайте это правильно и двигайтесь дальше. Вы можете профилировать его позже, чтобы увидеть, является ли CalculateGoodness узким местом.

Answer 4

Возможно, аккуратный способ сделать отдельную вещь vector - это на самом деле создать vector< pair<float, Thing*> >, где второй элемент указывает на объект Thing с соответствующим значением float. Если вы сортируете это vector по значениям float, вы можете выполнить итерацию по нему и прочитать объекты Thing в правильном порядке, возможно воспроизведя их в другой vector или list, чтобы они в конечном итоге были сохранены в порядке .

Answer 5

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

. Другой вариант - кэшировать CalculateGoodness в самой вещи как простое поле или сделать CalculateGoodness методом Thing (убедитесь, что кэшизменчив, поэтому const все еще работает)