Как быстро получить отсортированный субвектор из отсортированного вектора - PullRequest
Новая
       17

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

11 голосов
/ 30 ноября 2010

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

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 <<strong> N (примерно в 0,8 раза N )), fast (память не является проблемой, и это будет повторяться многократно, поэтому создаются справочные таблицы (вспомогательные данные ) из параметров функции) или что-то еще, что выполняется только один раз, вполне нормально).

Мое решение до сих пор:
Построить справочную таблицу lut , содержащую id -> смещение в значениях (подготовка, поэтому постоянное время выполнения)
создать std::vector<X> tmp, размер N, заполненный недействительными идентификаторами (линейные в N )
для каждого идентификатора скопируйте values[lut[id]] в tmp[lut[id]] (линейный в M )
зацикливание tmp , копирование элементов в out (линейное в N )

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

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

Ответы [ 3 ]

2 голосов
/ 30 ноября 2010

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

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 - это постоянное ожидаемое время (при условии, чтоу нас нет проблем с хэшированием целых).Однако я подозреваю, что на практике это может быть не так быстро, как подход, который вы первоначально описали с использованием векторов.

1 голос
/ 30 ноября 2010

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

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

Должен работать алгоритм * или 100 * * разбиение .

0 голосов
/ 30 ноября 2010

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

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

Лучшее, что вы могли бы сделать, это отсортировать значения (вы нашли на карте) с помощью метода быстрой сортировки (O (MlogM), например, быстрой сортировки, слияния и т. Д.) Для небольших значений 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).

...