Как более эффективно рассчитать оценку несоответствия между n количеством строк?

Question

Предположим, у меня есть вектор, содержащий n строк, где строки могут быть длиной 5 ... n. Каждая строка должна сравниваться с каждой строкой символ за символом. Если есть несоответствие, оценка увеличивается на единицу. Если есть совпадение, оценка не увеличивается. Затем я буду хранить полученные результаты в матрице.

Я реализовал это следующим образом:

for (auto i = 0u; i < vector.size(); ++i)
{
  // vector.size() x vector.size() matrix
  std::string first = vector[i]; //horrible naming convention
  for (auto j = 0u; j < vector.size(); ++j)
  {
    std::string next = vector[j];
    int score = 0;
    for (auto k = 0u; k < sizeOfStrings; ++k)
    {
      if(first[k] == second[k])
      {
        score += 0;
      }
      else
      {
        score += 1;
      }
    }
    //store score into matrix
  }
}

Я не доволен этим решением, потому что оно O(n^3). Поэтому я пытался придумать другие способы сделать это более эффективным. Я думал о написании другой функции, которая заменила бы внутренности нашего цикла j, однако это все равно было бы O(n^3), так как функция все еще нуждалась бы в цикле k.

Я также думал об очереди, поскольку меня волнует только string[0] по сравнению с string[1] до string[n]. String[1] по сравнению с string[2] до string[n]. String[2] по сравнению с string[3] до string[n] и т. Д. Поэтому в моих решениях есть ненужные вычисления, поскольку каждая строка сравнивается с любой другой строкой. Проблема с этим, я не совсем уверен, как построить мою матрицу из этого.

Я наконец-то заглянул в библиотеку шаблонов std, однако std::mismatch, похоже, не то, что я ищу, или std::find. Какие еще идеи у вас есть?

Answer 1

Другие ответы, которые говорят, что это как минимум O (mn ^ 2) или O (n ^ 3), неверны. Это можно сделать за время O (mn), где m - размер строки, а n - количество строк.

Для простоты начнем с предположения, что все символы являются ascii.

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

int counts[m][255]

где count [x] [y] - количество строк, имеющих символ ascii y с индексом x в строке.

Теперь, если вы не ограничиваетесь ascii, вам нужно использовать std :: map

map counts[m]

Но это работает так же, при индексах m ​​в счетчиках у вас есть карта, в которой каждая запись в карте y, z сообщает вам, сколько строк z использует символ y в индексе m. Вы также хотели бы выбрать карту с постоянным временем поиска и постоянным временем вставки, чтобы соответствовать сложности.

Возвращаясь к ascii и массиву

int counts[m][255] // start by initializing this array to all zeros

Сначала инициализируйте структуру данных:

м - размер струн, vec - это std :: vector со строками

for (int i = 0; i < vec.size(); i++) {
    std::string str = vec[i];
    for(int j = 0; j < m; j++) {
        counts[j][str[j]]++;
    }
}

Теперь, когда у вас есть эта структура, вы можете легко вычислить баллы:

for (int i = 0; i < vec.size(); i++) {
    std::string str = vec[i];
    int score = 0;
    for(int j = 0; j < m; j++) {
            score += counts[j][str[j]] - 1; //subtracting 1 gives how many other strings have that same char at that index
    }
    std::cout << "string \"" << str << "\" has score " << score;
}

Как видно из этого кода, это O (m * n)

Answer 2

Я не думаю, что вы легко сможете уйти от O (n ^ 3) сравнений, но вы можете легко реализовать изменения, о которых вы говорите. Поскольку сравнения нужно выполнять только одним способом (то есть сравнение строки [1] со строкой [2] аналогично сравнению строки [2] со строкой [1]), как вы указали, вам не нужно повторять через весь массив каждый раз и может изменить начальное значение вашего внутреннего цикла на текущий индекс вашего внешнего цикла:

for (auto i = 0u; i < vector.size(); ++i) {
    // vector.size() x vector.size() matrix
    std::string first = vector[i]; //horrible naming convention
    for (auto j = i; j < vector.size(); ++j) {

Чтобы сохранить ее в матрице, настройте матрицу i x j, инициализируйте ее для всех нулей и просто сохраните каждый счет в M[i][j]

for (auto k = 0u; k < sizeOfStrings; ++k) {
    if (first[k] != second[k]) {
        M[i][j]++;
    }
}

Answer 3

• Общий комментарий:

Вам не нужно сравнивать одни и те же строки друг с другом. И что более важно, вы начинаете с начала каждый раз во втором цикле, пока вы уже вычислили эти различия, поэтому измените второй цикл, чтобы начать с i+1. При этом ваша сложность уменьшится, так как вы не будете проверять строку, которую вы уже проверили или не изменились.

• Улучшение

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

Answer 4

Если у вас есть n строк длиной m, то независимо от того, что (даже с вашей идеей очереди), вы должны сделать как минимум (n-1) + (n-2) + ... + (1) = n (n-1) / 2 сравнения строк, поэтому вам придется выполнять (n (n-1) / 2) * m сравнения символов. Так что, несмотря ни на что, ваш алгоритм будет O (mn ^ 2).