Как получить отсортированный подвектор из отсортированного вектора, быстро

У меня есть структура данных вроде этого:

struct X {
  float value;
  int id;
};

вектор тех (размер N (думаю, 100000), отсортированный по значению (остается постоянным во время выполнения программы):

std::vector<X> values;

Теперь я хочу написать функцию

void subvector(std::vector<X> const& values, 
               std::vector<int> const& ids, 
               std::vector<X>& out /*, 
               helper data here */);

который заполняет параметр out с помощью отсортированного подмножества значений, заданного пройденными идентификаторами (размер M < N (около 0,8 раза N)), быстро (память не проблема, и это будет сделано многократно, поэтому построение lookuptables (вспомогательные данные из параметров функции) или что-то еще, что выполняется только один раз, полностью в порядке).

Мое решение до сих пор:
Создайте lookuptable lut, содержащий id → offset в значениях (подготовка, так что постоянное время исполнения)
создайте std::vector<X> tmp, размер N, заполненный недействительными идентификаторами (линейный в N)
для каждого id, скопируйте values[lut[id]] в tmp[lut[id]] (линейный в M)
loop over tmp, копирование элементов на выход (линейный в N)

это линейно в N (как это больше, чем M), но временная переменная и повторное копирование меня задевают. Есть ли способ сделать это быстрее, чем это? Обратите внимание, что M будет близок к N, поэтому вещи, которые являются O (M log N), являются неблагоприятными.

Изменить: http://ideone.com/xR8Vp - пример реализации упомянутого алгоритма, чтобы сделать желаемый вывод ясным и доказать, что он выполним в линейном времени - вопрос заключается в возможности избежать временной переменной или ускорить ее каким-то другим способом, то, что не является линейным, происходит не быстрее:).

Ответ 1

Альтернативный подход, который вы можете попробовать, - использовать хеш-таблицу вместо вектора для поиска идентификаторов в:

void subvector(std::vector<X> const& values, 
               std::unordered_set<int> const& ids, 
               std::vector<X>& out) {

    out.clear();
    out.reserve(ids.size());
    for(std::vector<X>::const_iterator i = values.begin(); i != values.end(); ++i) {
        if(ids.find(i->id) != ids.end()) {
            out.push_back(*i);
        }
    }
}

Это выполняется в линейном времени, так как unordered_set::find является постоянным ожидаемым временем (при условии, что у нас нет проблем с хешированием ints). Однако я подозреваю, что это может быть не так быстро на практике, как описанный вами подход с использованием векторов.

Ответ 2

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

Почему бы просто не использовать find_if() дважды. Однажды найдите начало диапазона, который вы хотите, и один раз, чтобы найти конец диапазона. Это даст вам начальные и конечные итераторы суб-вектора. Создайте новый вектор, используя эти итераторы. Одна из векторных конструкторов перегружает два итератора.

Этот алгоритм или partition должен работать.

Ответ 3

Если я правильно понял вашу проблему, вы фактически попытаетесь создать алгоритм линейной сортировки времени (с учетом размера ввода чисел M). Это невозможно.

Ваш текущий подход состоит в том, чтобы иметь отсортированный список возможных значений. Это приводит к линейному времени к числу возможных значений N (теоретически, учитывая, что поиск по карте занимает время O (1)).

Лучшее, что вы могли бы сделать, это отсортировать значения (вы нашли на карте) с помощью метода быстрой сортировки (O (MlogM) fe quicksort, mergesort и т.д.) для небольших значений M и, возможно, сделать этот линейный поиск для более крупных значения M. Например, если N - 100000, а M - 100, то гораздо проще использовать алгоритм сортировки.

Надеюсь, вы поймете, что я говорю. Если у вас все еще есть вопросы, я постараюсь ответить на них:)

изменить: (комментарий) Я объясню, что я имею в виду. Скажите, что вы знаете, что ваши номера будут варьироваться от 1 до 100. Вы их отсортировали где-то (на самом деле они "естественно" отсортированы), и вы хотите получить их подмножество в отсортированной форме. Если бы это было возможно сделать быстрее, чем O (N) или O (MlogM), алгоритмы сортировки просто использовали бы этот метод для сортировки.

F.e. имея набор чисел {5,10,3,8,9,1,7}, зная, что они являются подмножеством отсортированного набора чисел {1,2,3,4,5,6,7,8, 9,10}, вы по-прежнему не можете сортировать их быстрее, чем O (N) (N = 10) или O (MlogM) (M = 7).