Перечисление строк Qt C ++ 11 через пересечение подстрок - PullRequest
Новая
       19

Перечисление строк Qt C ++ 11 через пересечение подстрок

0 голосов
/ 10 января 2020

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

Основная проблема заключается в том, что мне нужно сравнивать их через подстроки, например, у меня есть это списки:

1 

111111
111222
222333
333444

2 

444111
555222
666333
777444
555111
222111
111555

Давайте предположим, что я использовал фильтр, который будет делать substr из первых 3 цифр из этих строк (например, Я просто уже сделал эту функцию). И в результате мне нужно получить это пересечение: 

111111
111222
111555
222111
222333

Теперь мой код выглядит так: 

QSharedPointer<QStringList> Intersection_Op::compute(QSharedPointer<QStringList> leftList,
                                                     QSharedPointer<QStringList> rightList,
                                                     QPair<int, int> filters)
{
    if (!leftList or !rightList)
        return QSharedPointer<QStringList>( nullptr );

    std::sort( leftList->begin(), leftList->end() );
    std::sort( rightList->begin(), rightList->end() );

    // std::string getCheckBody( const QString* str, QPair<int, int> filters )

    auto leftStdList = new std::list<QString>( leftList );
    auto rightStdList = new std::list<QString>( rightList );
    auto result = QSharedPointer<QStringList>( new QStringList() );

    std::set_intersection(leftStdList->begin(), leftStdList->end(),
                          rightStdList->begin(), rightStdList->end(), std::back_inserter( *result ),
                              [=] (const QString& one, const QString& two) -> bool {
         auto o = getCheckBody( one, filters );
         auto t = getCheckBody( two, filters );

         // got this condition from another thread here
         return  ( o.size() == t.size() )
                 ? (o < t)
                 : ( o.size() < t.size() );
    });

    delete leftStdList;
    delete rightStdList;

    return result;
}

И теперь я получаю этот результат: 

111111
222333

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

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

Что касается размеров данных, обычно это ~ 100 тыс. Списков строк, поэтому я действительно ищу, как оптимизировать эту задачу.

Может Вы помогаете мне найти решение, пожалуйста? И кто-нибудь может дать несколько советов для этой задачи?

Спасибо

1 Ответ

0 голосов
/ 10 января 2020

std::set_intersection неправильный метод для этого.

Если какой-либо элемент найден m раз в [first1, last1) и n раз в [first2, last2), первые std::min(m, n) элементы будут скопированы из первого диапазона в целевой диапазон.

У вас есть "111 ..." дважды в одном и один раз в другом и "222 ..." один раз в каждом.

Вам нужно что-то вроде 

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt my_intersection(InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,
                         OutputIt d_first, Compare comp)
{
    while (first1 != last1 && first2 != last2) {
        auto range1 = std::equal_range(first1, last1, *first2, comp);
        auto range2 = std::equal_range(first2, last2, *first1, comp);

        d_first = std::copy(range1.first, range1.second, d_first);
        d_first = std::copy(range2.first, range2.second, d_first);

        first1 = range1.second;
        first2 = range2.second;
    }
    return d_first;
}

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

...