Наиболее эффективный способ найти индекс совпадающих значений в двух отсортированных массивах с использованием C++

Question

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

У меня есть два массива (например, std :: векторы). Оба массива содержат только уникальные целочисленные значения, которые сортируются, но являются разреженными по значению, то есть: 1,4,12,13 ... Что я хочу спросить, так это быстрый способ найти INDEX для одного из массивов, где значения одинаковы. Например, массив 1 имеет значения 1,4,12,13, а array2 имеет значения 2,12,14,16. Первый индекс совпадающего значения равен 1 в массиве2. Индекс в массив - это то, что важно, поскольку у меня есть другие массивы, содержащие данные, которые будут использовать этот индекс, который «соответствует».

Я не ограничены использованием массивов, возможны карты. Я только сравниваю два массива один раз. Они не будут повторно использоваться повторно после первого совпадения. В любом массиве может быть небольшое или большое количество значений (300 000+), но НЕ всегда иметь одинаковое количество значений (что значительно упростило бы работу)

Худший случай - линейный поиск O (N^2). Использование карты поможет мне лучше O (log N), но я бы все же преобразовал массив в карту значений, пары индексов.

То, что я в настоящее время не должен делать, конвертирует тип контейнера. Перемещайтесь по меньшему из двух массивов. Сравните текущий элемент малого массива (array1) с текущим элементом большого массива (array2). Если значение элемента array1 больше, чем значение элемента array2, увеличьте индекс для массива2 до тех пор, пока он больше не будет больше значения элемента array1 (while loop). Затем, если значение элемента array1 меньше, чем элемент array2, перейдите к следующей итерации цикла и начните снова. В противном случае они должны быть равны, и у меня есть индекс для массивов соответствующего значения.

Итак, в этом цикле я в лучшем случае O (N), если все значения имеют совпадения и хуже O (2N), если они не совпадают. Поэтому мне интересно, есть ли что-то быстрее? Трудно точно знать, как часто будут совпадать два массива, но я бы предпочел бы больше ориентироваться на большинство массивов, в основном будет иметь совпадения, чем нет.

Надеюсь, я достаточно хорошо объяснил проблему, и я ценю любые отзывы или советы по улучшению этого.

Пример кода:

std::vector<int> array1 = {4,6,12,34}; 
std::vector<int> array2 = {1,3,6,34,40}; 

for(unsigned int i=0, z=0; i < array1.size(); i++) 
{ 
    int value1 = array1[i]; 
    while(value1 > array2[z] && z < array2.size()) 
     z++; 

    if (z >= array2.size()) 
     break; // reached end of array2 

    if (value1 < array2[z]) 
     continue; 

    // we have a match, i and z indices have same value 

} 

Результат будет соответствие индексов для array1 = [1,3], а для массив2 = [2,3]

Answer 1

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

Для распределений, аналогичных ^†, он имеет сложность O (n), но в тех случаях, когда распределения сильно различаются, он должен выполняться ниже линейного приближающегося O (log n) в оптимальных случаях. Однако я не смог доказать, что худший случай не лучше O (n log n). С другой стороны, я тоже не смог найти этот худший случай.

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

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

#include <algorithm> 
#include <iterator> 
#include <utility> 

// helper structure for the search 
template<class Range, class Out> 
struct search_data { 
    // is any there clearer way to get iterator that might be either 
    // a Range::const_iterator or const T*? 
    using iterator = decltype(std::cbegin(std::declval<Range&>())); 
    iterator curr; 
    const iterator begin, end; 
    Out out; 
}; 

template<class Range, class Out> 
auto init_search_data(const Range& range, Out out) { 
    return search_data<Range, Out>{ 
     std::begin(range), 
     std::begin(range), 
     std::end(range), 
     out, 
    }; 
} 

template<class Range, class Out1, class Out2> 
void match_indices(const Range& in1, const Range& in2, Out1 out1, Out2 out2) { 
    auto search_data1 = init_search_data(in1, out1); 
    auto search_data2 = init_search_data(in2, out2); 

    // initial order is arbitrary 
    auto lesser = &search_data1; 
    auto greater = &search_data2; 

    // if either range is exhausted, we are finished 
    while(lesser->curr != lesser->end 
      && greater->curr != greater->end) { 
     // difference of first values in each range 
     auto delta = *greater->curr - *lesser->curr; 

     if(!delta) { // matching value was found 
      // store both results and increment the iterators 
      *lesser->out++ = std::distance(lesser->begin, lesser->curr++); 
      *greater->out++ = std::distance(greater->begin, greater->curr++); 
      continue; // then start a new iteraton 
     } 

     if(delta < 0) { // set the order of ranges by their first value 
      std::swap(lesser, greater); 
      delta = -delta; // delta is always positive after this 
     } 

     // next crossing cannot be farther than the delta 
     // this assumption has following pre-requisites: 
     // range is sorted, values are integers, values in the range are unique 
     auto range_left = std::distance(lesser->curr, lesser->end); 
     auto upper_limit = 
      std::min(range_left, static_cast<decltype(range_left)>(delta)); 

     // exponential search for a sub range where the value at upper bound 
     // is greater than target, and value at lower bound is lesser 
     auto target = *greater->curr; 
     auto lower = lesser->curr; 
     auto upper = std::next(lower, upper_limit); 
     for(int i = 1; i < upper_limit; i *= 2) { 
      auto guess = std::next(lower, i); 
      if(*guess >= target) { 
       upper = guess; 
       break; 
      } 
      lower = guess; 
     } 

     // skip all values in lesser, 
     // that are less than the least value in greater 
     lesser->curr = std::lower_bound(lower, upper, target); 
    } 
} 

#include <iostream> 
#include <vector> 

int main() { 
    std::vector<int> array1 = {4,6,12,34}; 
    std::vector<int> array2 = {1,3,6,34}; 

    std::vector<std::size_t> indices1; 
    std::vector<std::size_t> indices2; 

    match_indices(array1, array2, 
        std::back_inserter(indices1), 
        std::back_inserter(indices2)); 

    std::cout << "indices in array1: "; 
    for(std::vector<int>::size_type i : indices1) 
     std::cout << i << ' '; 

    std::cout << "\nindices in array2: "; 
    for(std::vector<int>::size_type i : indices2) 
     std::cout << i << ' '; 
    std::cout << std::endl; 
} 

Answer 2

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

Это O (n) и самый быстрый, который вы можете сделать для произвольных ударов. С некоторыми кластеризованными распределениями можно использовать подход «пропустить вперед», а не всегда смотреть на следующий элемент. Это может привести к лучшему времени работы O (n) для определенных распределений. Например, с учетом массивов 1,2,3,4,5 и 10,11,12,13,14 алгоритм мог определить, что совпадений не было найдено всего за одно сравнение (5 < 10).

Answer 3

Каков диапазон сохраненных номеров?

Я имею в виду, что вы говорите, что числа являются целыми, отсортированными и разреженными (то есть непоследовательными) и что их может быть более 300 000, но каков их фактический диапазон?

Причина, по которой я спрашиваю, что, если есть достаточно маленький верхний предел, у, (скажем, у = 500000), самое быстрое и наиболее целесообразное решение может быть просто использовать значение в качестве индексов , Да, вы можете тратить память, но есть 4 * u действительно много памяти? Это зависит от вашего приложения и вашей целевой платформы (т. Е. Если это для встроенной системы с ограниченным объемом памяти, то она вряд ли будет хорошей идеей, чем если бы у вас был ноутбук с 32-гигабайтной ОЗУ).

Конечно, если значения более или менее равномерно распределены по 0-2^31-1, эта грубая идея не привлекательна, но, возможно, есть свойства входных значений, которые вы можете использовать для других просто чем диапазон. Возможно, вы сможете вручную написать довольно простую хеш-функцию.

Еще одна важная вещь, которую стоит рассмотреть - нужно ли вам быстро получить индекс или, если это поможет просто узнать, существует ли индекс в другом массиве быстро. Независимо от того, существует ли какое-либо значение в определенном индексе, требуется только один бит, поэтому вы можете иметь растровое изображение диапазона входных значений с использованием 32-кратной памяти (т. Е. Маскировать 5 младших разрядов и использовать это как битную позицию, а затем сдвинуть оставшиеся 27 бит 5 мест справа и использовать это как индекс массива).

Наконец, можно подумать о гибридном подходе, в котором вы решите, сколько памяти вы готовы использовать (скажем, вы решили 256KiB, что соответствует 64Ki 4-байтным целым), тогда используйте это как таблицу поиска для на гораздо меньшие под-проблемы. Скажем, у вас есть 300 000 значений, чьи LSB довольно равномерно распределены. Затем вы можете использовать 16 младших разрядов в качестве индексов в таблицу поиска списков, которые (в среднем) содержат только 4 или 5 элементов, которые затем можно искать другими способами. Пару лет назад я работал над некоторым программным обеспечением для моделирования, в котором было ~ 200 000 000 ячеек, каждый с идентификатором ячейки; некоторые функции полезности использовали двоичный поиск для идентификации ячеек по идентификатору. Мы смогли значительно ускорить его и не навязчиво с этой стратегией. Не идеальное решение, но большое улучшение. (Если LSB распределены неравномерно, возможно, это свойство, которое вы можете использовать, или, может быть, вы можете выбрать диапазон бит или сделать немного хеширования.)

Я предполагаю, что результат «рассмотрим вопрос хэширования », даже« хэш-идентификация »или простое маскирование/модуляция с небольшим« ваше решение не обязательно должно быть абсолютно общим »на стороне, а некоторые« ваше решение не должно быть идеально эффективным с точки зрения пространства » Вверх.