Самый эффективный способ расчета лексикографического индекса

Кто-нибудь может найти потенциально более эффективные алгоритмы для решения следующей задачи ?:

Для любой данной перестановки целых чисел от 0 до 7, верните индекс, который описывает перестановку лексикографически (индексируется от 0, а не 1).

Например,

  • Массив 0 1 2 3 4 5 6 7 должен возвращать индекс 0.
  • Массив 0 1 2 3 4 5 7 6 должен возвращать индекс 1.
  • Массив 0 1 2 3 4 6 5 7 должен возвращать индекс 2.
  • Массив 1 0 2 3 4 5 6 7 должен возвращать индекс 5039 (это 7! -1 или factorial(7)-1).
  • Массив 7 6 5 4 3 2 1 0 должен возвращать индекс 40319 (это 8! -1). Это максимально возможное возвращаемое значение.

Мой текущий код выглядит так:

int lexic_ix(int* A){
int value = 0;
for(int i=0 ; i<7 ; i++){
int x = A[i];
for(int j=0 ; j<i ; j++)
if(A[j]<A[i]) x--;
value += x*factorial(7-i);  // actual unrolled version doesn't have a function call
}
return value;
}

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

Я уже пробовал заменить

if(A[j]<A[i]) x--;

с

x -= (A[j]<A[i]);

и я тоже пытался

x = A[j]<A[i] ? x-1 : x;

Обе замены фактически привели к ухудшению производительности.

И прежде чем кто-то скажет — ДА, это огромное узкое место в производительности: в настоящее время около 61% времени выполнения программы расходуется на эту функцию, и НЕТ, я не хочу иметь таблицу предварительно вычисленных значений.

Кроме того, любые предложения приветствуются.

9

Решение

Не знаю, помогает ли это, но вот другое решение:

int lexic_ix(int* A, int n){ //n = last index = number of digits - 1
int value = 0;
int x = 0;
for(int i=0 ; i<n ; i++){
int diff = (A[i] - x); //pb1
if(diff > 0)
{
for(int j=0 ; j<i ; j++)//pb2
{
if(A[j]<A[i] && A[j] > x)
{
if(A[j]==x+1)
{
x++;
}
diff--;
}
}
value += diff;
}
else
{
x++;
}
value *= n - i;
}
return value;
}

Я не смог избавиться от внутреннего цикла, поэтому сложность o (n log (n)) в худшем случае, но o (n) в лучшем случае, в отличие от вашего решения, которое во всех равно o (n log (n)) случаев.

В качестве альтернативы вы можете заменить внутренний цикл следующим, чтобы удалить некоторые худшие случаи за счет другой проверки во внутреннем цикле:

int j=0;
while(diff>1 && j<i)
{
if(A[j]<A[i])
{
if(A[j]==x+1)
{
x++;
}
diff--;
}
j++;
}

объяснение :

(или, скорее, «Как я закончил с этим кодом», я думаю, что он ничем не отличается от вашего, но может быть, у вас есть идеи, может быть)
(чтобы не было путаницы, я использовал символы вместо цифры и только четыре символа)

abcd 0  = ((0 * 3 + 0) * 2 + 0) * 1 + 0
abdc 1  = ((0 * 3 + 0) * 2 + 1) * 1 + 0
acbd 2  = ((0 * 3 + 1) * 2 + 0) * 1 + 0
acdb 3  = ((0 * 3 + 1) * 2 + 1) * 1 + 0
adbc 4  = ((0 * 3 + 2) * 2 + 0) * 1 + 0
adcb 5  = ((0 * 3 + 2) * 2 + 1) * 1 + 0 //pb1
bacd 6  = ((1 * 3 + 0) * 2 + 0) * 1 + 0
badc 7  = ((1 * 3 + 0) * 2 + 1) * 1 + 0
bcad 8  = ((1 * 3 + 1) * 2 + 0) * 1 + 0 //First reflexion
bcda 9  = ((1 * 3 + 1) * 2 + 1) * 1 + 0
bdac 10 = ((1 * 3 + 2) * 2 + 0) * 1 + 0
bdca 11 = ((1 * 3 + 2) * 2 + 1) * 1 + 0
cabd 12 = ((2 * 3 + 0) * 2 + 0) * 1 + 0
cadb 13 = ((2 * 3 + 0) * 2 + 1) * 1 + 0
cbad 14 = ((2 * 3 + 1) * 2 + 0) * 1 + 0
cbda 15 = ((2 * 3 + 1) * 2 + 1) * 1 + 0 //pb2
cdab 16 = ((2 * 3 + 2) * 2 + 0) * 1 + 0
cdba 17 = ((2 * 3 + 2) * 2 + 1) * 1 + 0
[...]
dcba 23 = ((3 * 3 + 2) * 2 + 1) * 1 + 0

Первое «отражение» :

Энтропийная точка зрения. У abcd наименьшая «энтропия». Если персонаж находится в таком месте, каким он «не должен» быть, он создает энтропию, и чем раньше энтропия становится наибольшей, чем становится.

Например, для bcad лексикографический индекс равен 8 = ((1 * 3 + 1) * 2 + 0) * 1 + 0 и может быть рассчитан таким образом:

value = 0;
value += max(b - a, 0); // = 1; (a "should be" in the first place [to create the less possible entropy] but instead it is b)
value *= 3 - 0; //last index - current index
value += max(c - b, 0); // = 1; (b "should be" in the second place but instead it is c)
value *= 3 - 1;
value += max(a - c, 0); // = 0; (a "should have been" put earlier, so it does not create entropy to put it there)
value *= 3 - 2;
value += max(d - d, 0); // = 0;

Обратите внимание, что последняя операция всегда ничего не будет делать, поэтому «я

Первая проблема (pb1):

Например, для adcb первая логика не работает (это приводит к лексикографическому индексу ((0 * 3+ 2) * 2+ 0) * 1 = 4), потому что cd = 0, но это создает энтропию для помещения c до б. Я добавил x из-за этого, он представляет первую цифру / символ, который еще не размещен. С x, diff не может быть отрицательным.
Для АЦБ лексикографический индекс равен 5 = ((0 * 3 + 2) * 2 + 1) * 1 + 0 и может быть рассчитано следующим образом:

value = 0; x=0;
diff = a - a; // = 0; (a is in the right place)
diff == 0 => x++; //x=b now and we don't modify value
value *= 3 - 0; //last index - current index
diff = d - b; // = 2; (b "should be" there (it's x) but instead it is d)
diff > 0 => value += diff; //we add diff to value and we don't modify x
diff = c - b; // = 1; (b "should be" there but instead it is c) This is where it differs from the first reflexion
diff > 0 => value += diff;
value *= 3 - 2;

Вторая проблема (pb2):

Например, для cbda лексикографический индекс равен 15 = ((2 * 3 + 1) * 2 + 1) * 1 + 0, но первое отражение дает: ((2 * 3 + 0) * 2 + 1) * 1 + 0 = 13, и решение для pb1 дает ((2 * 3 + 1) * 2 + 3) * 1 + 0 = 17. Решение для pb1 не работает, потому что два последних символа для размещения — это d и a, поэтому d — «означает» 1 вместо 3. Я должен был посчитать символы, размещенные до того, как он предшествует символу на месте, но после x, поэтому мне пришлось добавить внутренний цикл.

Собираем все вместе :

Затем я понял, что pb1 был просто частным случаем pb2, и что если вы удалите x, и вы просто возьмете diff = A [i], мы получим непроверенную версию вашего решения (с факториальным вычислением понемногу, и мой дифференциал соответствует вашему х).

Так что, по сути, мой «вклад» (я думаю) состоит в том, чтобы добавить переменную x, которая может избежать внутреннего цикла, когда diff равен 0 или 1, за счет проверки, нужно ли увеличивать x, и выполнения этого, если так ,

Я также проверил, нужно ли увеличивать x во внутреннем цикле (if (A [j] == x + 1)), потому что, если вы возьмете, например, badce, x будет b в конце, потому что a следует после b, и вы войдем во внутренний цикл еще раз, встречая c. Если вы проверяете x во внутреннем цикле, когда вы сталкиваетесь с d, у вас нет выбора, кроме как выполнять внутренний цикл, но x будет обновляться до c, а когда вы сталкиваетесь с c, вы не будете входить во внутренний цикл. Вы можете удалить эту проверку, не нарушая программу

С альтернативной версией и проверкой во внутреннем цикле это делает 4 разных версии. Альтернативный вариант с проверкой — тот, в который вы входите, тем не менее, внутренний цикл, поэтому с точки зрения «теоретической сложности» он является лучшим, но с точки зрения производительности / количества операций, я не знаю.

Надеюсь, все это поможет (так как вопрос довольно старый, и я не прочитал все ответы в деталях). Если нет, мне все равно было весело. Простите за длинный пост. Также я новичок в Stack Overflow (как участник), и не являюсь носителем языка, поэтому, пожалуйста, будьте любезны, и не стесняйтесь, дайте мне знать, если я сделал что-то не так.

2

Другие решения

Линейный обход памяти, уже находящейся в кеше, на самом деле совсем не занимает много времени. Не беспокойся об этом. Вы не пройдете достаточное расстояние до того, как factorial () переполнится.

Переместить 8 в качестве параметра.

int factorial ( int input )
{
return input ? input * factorial (input - 1) : 1;
}

int lexic_ix ( int* arr, int N )
{
int output = 0;
int fact = factorial (N);
for ( int i = 0; i < N - 1; i++ )
{
int order = arr [ i ];
for ( int j = 0; j < i; j++ )
order -= arr [ j ] < arr [ i ];
output += order * (fact /= N - i);
}
return output;
}

int main()
{
int arr [ ] = { 11, 10, 9, 8, 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 };

const int length = 12;
for ( int i = 0; i < length; ++i )
std::cout << lexic_ix ( arr + i, length - i  ) << std::endl;
}
0

Скажем, для перестановки последовательностей из М-цифр из вашего кода вы можете получить лексикографическую формулу SN, которая выглядит примерно так: Am-1 * (m-1)! + Ам-2 * (м-2)! + … + A0 * (0)! где Aj находится в диапазоне от 0 до j. Вы можете вычислить SN из A0 * (0) !, затем A1 * (1) !, …, затем Am-1 * (m-1) !, и сложить их вместе (предположим, что ваш целочисленный тип не переполняется), поэтому вам не нужно вычислять факториалы рекурсивно и многократно. Номер SN находится в диапазоне от 0 до M! -1 (потому что Sum (n * n !, n в 0,1, … n) = (n + 1)! — 1)

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

Извините за публикацию кода с небольшим опозданием, я только что провел небольшое исследование и нашел это:
http://swortham.blogspot.com.au/2011/10/how-much-faster-is-multiplication-than.html
Согласно этому автору, целочисленное умножение может быть в 40 раз быстрее, чем целочисленное деление. Плавающие числа не так уж драматичны, но здесь есть целое число.

int lexic_ix ( int arr[], int N )
{
// if this function will be called repeatedly, consider pass in this pointer as parameter
std::unique_ptr<int[]> coeff_arr = std::make_unique<int[]>(N);
for ( int i = 0; i < N - 1; i++ )
{
int order = arr [ i ];
for ( int j = 0; j < i; j++ )
order -= arr [ j ] < arr [ i ];
coeff_arr[i] = order; // save this into coeff_arr for later multiplication
}
//
// There are 2 points about the following code:
// 1). most modern processors have built-in multiplier, \
//    and multiplication is much faster than division
// 2). In your code, you are only the maximum permutation serial number,
//     if you put in a random sequence, say, when length is 10, you put in
//     a random sequence, say, {3, 7, 2, 9, 0, 1, 5, 8, 4, 6}; if you look into
//     the coeff_arr[] in debugger, you can see that coeff_arr[] is:
//     {3, 6, 2, 6, 0, 0, 1, 2, 0, 0}, the last number will always be zero anyway.
//     so, you will have good chance to reduce many multiplications.
//     I did not do any performance profiling, you could have a go, and it will be
//     much appreciated if you could give some feedback about the result.
//
long fac = 1;
long sn = 0;
for (int i = 1; i < N; ++i) // start from 1, because coeff_arr[N-1] is always 0
{
fac *= i;
if (coeff_arr[N - 1 - i])
sn += coeff_arr[N - 1 - i] * fac;
}
return sn;
}

int main()
{
int arr [ ] = { 3, 7, 2, 9, 0, 1, 5, 8, 4, 6 }; // try this and check coeff_arr

const int length = 10;
std::cout << lexic_ix(arr, length ) << std::endl;
return 0;
}
0

Это весь код профилирования, я запускаю тест только в Linux, код был скомпилирован с использованием G ++ 8.4, с опциями компилятора ‘-std = c ++ 11 -O3’. Если честно, я немного переписал твой код, предварительно рассчитав N! и передать его в функцию, но, похоже, это не очень помогает.

Профилирование производительности для N = 9 (362880 перестановок):

  • Продолжительность времени: 34, 30, 25 миллисекунд
  • Продолжительность времени: 34, 30, 25 миллисекунд
  • Продолжительность времени: 33, 30, 25 миллисекунд

Профилирование производительности для N = 10 (3628800 перестановок):

  • Продолжительность времени: 345, 335, 275 миллисекунд.
  • Продолжительность времени: 348, 334, 275 миллисекунд
  • Продолжительность времени: 345, 335, 275 миллисекунд.

Первое число — ваша исходная функция, второе — переписанная функция, которая получает N! прошло, последний номер мой результат. Функция генерации перестановок очень примитивна и работает медленно, но до тех пор, пока она генерирует все перестановки в качестве тестового набора данных, это нормально. Кстати, эти тесты выполняются на Quad-Core 3,1 ГГц, 4 ГБ на рабочем столе под управлением Ubuntu 14.04.

РЕДАКТИРОВАТЬ: я забыл фактор, что первой функции может потребоваться расширить вектор lexi_numbers, поэтому я поставил пустой вызов до времени. После этого времена составляют 333, 334, 275.

РЕДАКТИРОВАТЬ: Еще один фактор, который может повлиять на производительность, я использую длинное целое число в моем коде, если я изменю эти 2 «длинные» на 2 «int», время выполнения станет: 334, 333, 264.

#include <iostream>
#include <vector>
#include <chrono>
using namespace std::chrono;

int factorial(int input)
{
return input ? input * factorial(input - 1) : 1;
}

int lexic_ix(int* arr, int N)
{
int output = 0;
int fact = factorial(N);
for (int i = 0; i < N - 1; i++)
{
int order = arr[i];
for (int j = 0; j < i; j++)
order -= arr[j] < arr[i];
output += order * (fact /= N - i);
}
return output;
}

int lexic_ix1(int* arr, int N, int N_fac)
{
int output = 0;
int fact = N_fac;
for (int i = 0; i < N - 1; i++)
{
int order = arr[i];
for (int j = 0; j < i; j++)
order -= arr[j] < arr[i];
output += order * (fact /= N - i);
}
return output;
}

int lexic_ix2( int arr[], int N , int coeff_arr[])
{
for ( int i = 0; i < N - 1; i++ )
{
int order = arr [ i ];
for ( int j = 0; j < i; j++ )
order -= arr [ j ] < arr [ i ];
coeff_arr[i] = order;
}
long fac = 1;
long sn = 0;
for (int i = 1; i < N; ++i)
{
fac *= i;
if (coeff_arr[N - 1 - i])
sn += coeff_arr[N - 1 - i] * fac;
}
return sn;
}

std::vector<std::vector<int>> gen_permutation(const std::vector<int>& permu_base)
{
if (permu_base.size() == 1)
return std::vector<std::vector<int>>(1, std::vector<int>(1, permu_base[0]));

std::vector<std::vector<int>> results;
for (int i = 0; i < permu_base.size(); ++i)
{
int cur_int = permu_base[i];
std::vector<int> cur_subseq = permu_base;
cur_subseq.erase(cur_subseq.begin() + i);
std::vector<std::vector<int>> temp = gen_permutation(cur_subseq);
for (auto x : temp)
{
x.insert(x.begin(), cur_int);
results.push_back(x);
}
}
return results;
}

int main()
{
#define N 10
std::vector<int> arr;
int buff_arr[N];
const int length = N;
int N_fac = factorial(N);
for(int i=0; i<N; ++i)
arr.push_back(N-i-1); // for N=10, arr is {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
std::vector<std::vector<int>> all_permus = gen_permutation(arr);

std::vector<int> lexi_numbers;
// This call is not timed, only to expand the lexi_numbers vector
for (auto x : all_permus)
lexi_numbers.push_back(lexic_ix2(&x[0], length, buff_arr));

lexi_numbers.clear();
auto t0 = high_resolution_clock::now();
for (auto x : all_permus)
lexi_numbers.push_back(lexic_ix(&x[0], length));
auto t1 = high_resolution_clock::now();
lexi_numbers.clear();
auto t2 = high_resolution_clock::now();
for (auto x : all_permus)
lexi_numbers.push_back(lexic_ix1(&x[0], length, N_fac));
auto t3 = high_resolution_clock::now();
lexi_numbers.clear();
auto t4 = high_resolution_clock::now();
for (auto x : all_permus)
lexi_numbers.push_back(lexic_ix2(&x[0], length, buff_arr));
auto t5 = high_resolution_clock::now();

std::cout << std::endl << "Time durations are: " << duration_cast<milliseconds> \
(t1 -t0).count() << ", " << duration_cast<milliseconds>(t3 - t2).count() << ", " \
<< duration_cast<milliseconds>(t5 - t4).count() <<" milliseconds" << std::endl;
return 0;
}
0
По вопросам рекламы [email protected]