быстрый способ сравнить два вектора, содержащие строки - PullRequest
Новая
       8

быстрый способ сравнить два вектора, содержащие строки

0 голосов
/ 02 октября 2018

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

Следующий фрагмент кода показывает, что мне нужно сделать (это то, как я это делаю, но какой самый быстрый способ сделать это): 

bool compare(vector<string> input1,vector<string> input2)
{
   if(input1.size() != input2.size()
   {
      return false;
   }
   for(int i=0;i<input1.siz();i++)
   {
       if(input1[i] != input2[i])
       {
            return false;
       }
   }
   return true; 

}
int compare(vector<string> inputData)
{
     if (compare(inputData,{"Apple","Orange","three"}))
     {
          return 129;
     }
     if (compare(inputData,{"A","B","CCC"}))
     {
          return 189;
     }
     if (compare(inputData,{"s","O","quick"}))
     {
          return 126;
     }
     if (compare(inputData,{"Apple","O123","three","four","five","six"}))
     {
          return 876;
     }
     if (compare(inputData,{"Apple","iuyt","asde","qwe","asdr"}))
     {
          return 234;
     }
     return 0;
}

Edit1

Могу ли я сравнить два вектора следующим образом: 

 if(inputData=={"Apple","Orange","three"})
 {
     return 129;
 }

Ответы [ 6 ]

0 голосов
/ 02 октября 2018

Могу ли я сравнить два вектора следующим образом

Ответ: Нет, вам нужно сравнить вектор с другим вектором, например: 

vector<string>data = {"ab", "cd", "ef"};

if(data == vector<string>{"ab", "cd", "efg"})
    cout << "Equal" << endl;
else
    cout << "Not Equal" << endl;

Какой самый быстрый способ сделать это?

Я не эксперт по асимптотическому анализу, но:

Использование оператора реляционного равенства ( == ) у вас есть ярлык для сравнения двух векторов, во-первых, для проверки размера и, во-вторых, для каждого элемента на них.Этот способ обеспечивает линейное выполнение ( T (n) , где n - размер вектора), которое сравнивает каждый элемент вектора, но каждая строка должна сравниваться и, как правило,это другое линейное сравнение ( T (m) , где m - размер строки).

Предположим, что каждая строка имеет одинаковый размер ( m )и у вас есть вектор размером n , каждое сравнение может иметь поведение T (нм) .

Итак:

  • Если вы хотите использовать ярлык для сравнения двух векторов, вы можете использовать реляционный оператор равенства .
  • Если вам нужна программа, которая выполняет быстрое сравнение, вам следует поискать алгоритм сравнения строк.
0 голосов
/ 02 октября 2018

Если вам нужен быстрый способ сделать это там, где векторы для сравнения не известны заранее, но используются повторно, поэтому могут иметь небольшие начальные накладные расходы во время выполнения, вы можете построить древовидную структуру, аналогичную версии во время компиляцииДирк Херрманн имеет.Это будет выполняться в O(n), просто перебирая ввод и следуя дереву.

В простейшем случае вы можете построить дерево для каждой буквы / элемента.Частичная реализация может быть: 

typedef std::vector<std::string> Vector;
typedef Vector::const_iterator Iterator;
typedef std::string::const_iterator StrIterator;
struct Node
{
    std::unique_ptr<Node> children[256];
    std::unique_ptr<Node> new_str_child;
    int result;
    bool is_result;
};

Node root;
int compare(Iterator vec_it, Iterator vec_end, StrIterator str_it, StrIterator str_end, const Node *node);
int compare(const Vector &input)
{
    return compare(input.begin(), input.end(), input.front().begin(), input.front().end(), &root);
}
int compare(Iterator vec_it, Iterator vec_end, StrIterator str_it, StrIterator str_end, const Node *node)
{
    if (str_it != str_end)
    {
        // Check next character
        auto next_child = node->children[(unsigned char)*str_it].get();
        if (next_child)
            return compare(vec_it, vec_end, str_it + 1, str_end, next_child);
        else return -1; // No string matched
    }
    // At end of input string
    ++vec_it;
    if (vec_it != vec_end)
    {
        auto next_child = node->new_str_child.get();
        if (next_child)
            return compare(vec_it, vec_end, vec_it->begin(), vec_it->end(), next_child);
        else return -1; // Have another string, but not in tree
    }
    // At end of input vector
    if (node->is_result)
        return node->result; // Got a match
    else return -1; // Run out of input, but all possible matches were longer
}

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

"A"
 |-"pple" - new vector - "O" - "range" - new vector - "three" - ret 129
 |                    |- "i" - "uyt"   - new vector - "asde" ... - ret 234
 |                    |- "0" - "123"   - new vector - "three" ... - ret 876
 |- new vector "B" - new vector - "CCC" - ret 189
"s" - new vector "O" - new vector "quick" - ret 126
0 голосов
/ 02 октября 2018

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

if (inputData.size() != 3) return 0;
if (inputData[0].size() == 0) return 0;
const char inputData_0_0 = inputData[0][0];
if (inputData_0_0 == 'A') {
   // possibly "Apple" or "A"
   ...
} else if (inputData_0_0 == 's') {
   // possibly "s"
   ...
} else {
   return 0;
}
0 голосов
/ 02 октября 2018

Одним из ключей к эффективности является устранение ненужного распределения.

Таким образом, оно становится: 

bool compare(
    std::vector<std::string> const& a,
    std::initializer_list<const char*> b
) noexcept {
    return std::equal(begin(a), end(a), begin(b), end(b));
}

В качестве альтернативы, сделайте их static const и примите небольшие накладные расходы.

Кроме того, используя C ++ 17 std::string_view ( посмотрите на boost ), C ++ 20 std::span (ищите Библиотека поддержки директив (GSL) ) также допускает более приятную альтернативу: 

bool compare(std::span<std::string> a, std::span<std::string_view> b) noexcept {
    return a == b;
}

Другая - минимизация количества сравнений.Вы можете использовать хеширование, двоичный поиск или ручное упорядочение сравнений.

К сожалению, прозрачные компараторы - это C ++ 14, поэтому вы не можете использовать std::map.

0 голосов
/ 02 октября 2018

вы можете использовать функцию std :: equal, как показано ниже: 

bool compare(vector<string> input1,vector<string> input2)
{
   if(input1.size() != input2.size()
   {
      return false;
   }

   return std::equal(input1.begin(), input2.end(), input2.begin())
}
0 голосов
/ 02 октября 2018

Слабость вашего подхода заключается в его линейности.Вы хотите двоичный поиск для speedz.

Используя сортировку map, двоичность нахождения в одном и тот факт, что эквивалентность между vector s уже определена для вас (нет необходимостидля этой первой функции compare!) вы можете сделать это довольно легко: 

std::map<std::vector<std::string>, int> lookup{
   {{"Apple","Orange","three"}, 129},
   {{"A","B","CCC"}, 189},
   // ...
};

int compare(const std::vector<std::string>& inputData)
{
    auto it = lookup.find(inputData);
    if (it != lookup.end())
       return it->second;
    else
       return 0;
}

Обратите внимание также на передачу ссылки для дополнительной скорости z.

(у меня нетпроверил это на предмет точной синтаксической корректности, но вы поняли.)

Однако! Как всегда, мы должны учитывать контекст в наших проектах.Такой подход более полезен в более широком масштабе.На данный момент у вас есть только несколько опций, поэтому добавление динамического выделения и сортировки и всего этого джаза может на самом деле замедлить ход событий.В конечном счете, вы захотите принять мое решение и ваше решение и измерить результаты для типичных входных данных и еще много чего.

Как только вы это сделаете, если вам все еще нужно больше скорости дляпо какой-то причине, подумайте над поиском путей уменьшения динамического распределения, присущего как векторам, так и самим строкам.

Чтобы ответить на ваш дополнительный вопрос: почти;вам нужно указать тип: 

//                   new code is here
//               ||||||||||||||||||||||||
if (inputData == std::vector<std::string>{"Apple","Orange","three"})
{
   return 129;
}

Как было рассмотрено выше, пусть std::map::find сделает это за вас.Это лучше.

...