Эффективный способ получить первое значение больше, чем х в списке?

Question

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

Например:

double [] dHaystack = { 1.2, 2.6, 7.0, 9.3, 19.4 }
double [] dNeedles  = { 1.4, 6.4, 6.5, 7.0, 10.3 }

//  expected indices     0    1    1    2    3    

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

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

Но часть моего мозга кричит "пополам!" Будет ли бисекция на самом деле здесь быстрее, так как компилятору будет сложнее оптимизировать, чем простое чтение и итерация блока? Нужно ли иметь невероятно длинный стог сена, чтобы быть стоящим?

Answer 1

Нужно рассмотреть сценарий,

n * lg (м) ,

Где n - размер иголки, а m - размер стога сена.

Следовательно, все зависит от комбинации значений n и m.

Answer 2

Используйте std :: upper_bound, который является O (log n) для итераторов произвольного доступа и обеспечивает именно то, что вам нужно в самом коротком и простом коде.

Прежде чем беспокоиться о минимальной производительности, протестируйте свой текущий код (и, возможно, протестируйте альтернативы) вместо того, чтобы делать предположения . В частности, обратите внимание, что вы можете начать поиск (с первого параметра upper_bound) по последнему найденному индексу на каждой итерации.

// Available in Boost, C++0x, and many other places.  Implementation copied
// here for the sake of the example.
template<class T, int N>
T* end(T (&a)[N]) {
  return a + N;
}

void example() {
  double haystack[] = {1.2, 2.6, 7.0, 9.3, 19.4};
  double needles[] = {1.4, 6.4, 6.5, 7.0, 10.3};
  double *begin = haystack;
  for (double *n = needles; n != end(needles); ++n) {
    double *found = std::upper_bound(begin, end(haystack), *n);
    if (found == end(haystack)) break;
    std::cout << *n << " at index " << (found - haystack) << '\n';
    begin = found;
  }
}

Answer 3

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

Да.

Но часть моего мозга кричит «пополам!».Будет ли бисекция на самом деле здесь быстрее, так как компилятору будет сложнее оптимизировать, чем простое чтение и итерация блока?Нужно ли иметь невероятно длинный Haystack, чтобы быть стоящим?

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

Answer 4

std :: upper_bound даст вам итератор для строго большего элемента первого элемента, или "конец" коллекции, если ни один из них не применяется

upper_bound принимает итераторы для начала и конца, конец - один после концаколлекции.Если вы перебираете растущий список значений поиска, вам, конечно, не нужно проходить всю коллекцию, но ваше «начало» может сместиться дальше вправо.

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

Это ситуация, когда ондействительно имеет значение оба размера.Например, если ваше пространство поиска N велико, но количество искомых элементов (M) мало, тогда O (M log N) действительно намного меньше.(например, M = 20, N = 16K, тогда log N = 15 и M log N равно 300) по сравнению с O (M + N), которое в этом случае составляет 16K.Если размер M приблизительно равен размеру N, тогда O (M log N) намного хуже, чем O (N).

Поэтому в зависимости от размеров ваших коллекций вы можете выбрать, какой алгоритм использовать.