LINUX.ORG.RU

сравнение двух массивов строк


0

0

Есть два массива строк вида vector<string>. Массивы эти достаточно большие: порядка 30000 элементов в каждом, причем строки как правило тоже относительно длинные - может и по 100-200 символов быть. Задача состоит в том, что надо вызывать функцию с параметром в виде строки из первого массива, но только если эта строка не содержится во втором массиве. Известно, что для каждого массива все строки различны (т.е. в одном массиве одинаковых строк нет). Я это реализовал примерно так:

bool doThis;
vector<string> str1 = getData(1);
vector<string> str2 = getData(2);
for (unsigned int i=0; i<str1.size(); ++i) {
    doThis=true;
    for (unsigned int y=0; y<str2.size(); ++y) {
        if (str1[i]==str2[y]) {
           doThis=false;
           break;
        }
    }
    if (doThis) doSomething(str1[i]);
}
Впринципе оно работает не очень медленно, но вот чувствую что можно быстрее, причем значительно. Что тут может сильно улучшить производительность? Да, и если есть - киньте ссылками на то, как в std::string реализован оператор сравнения.

Сделать строки второго массива ключами хэш-массива, и значениями для проверки в случае коллизий.
Далее тривиально.
С++ знаю не очень хорошо, не буду городить код =)

tzukko
()
Ответ на: комментарий от tzukko

> С++ знаю не очень хорошо, не буду городить код =)

А ничего не надо городить в TR1 есть unordered_map, его реализации есть в gcc и в Boost.

Begemoth ★★★★★
()
Ответ на: комментарий от Davidov

> А почему не хэш?

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

const86 ★★★★★
()
Ответ на: комментарий от const86

На хэш надо 1 цикл - заполнить его.
Потом просто проверять наличие ключей - это не цикл.
В перле могу показать:
@array1;
@array2;
%hash;
$hash{$_}=1 foreach (@array2); # заполняем хэш
if ( $hash($array[1024]) ) dosmthng(); # проверяем наличие строки 1024

tzukko
()
Ответ на: комментарий от const86

>скорости ничуть не сэкономится.

Зависит от задачи, конечно. Но во многих ситуациях экономия будет огромной.

Davidov ★★★★
()
Ответ на: комментарий от Davidov

> Зависит от задачи, конечно. Но во многих ситуациях экономия будет огромной.

с какой это стати? sort+sort+merge не отличается принципиально от цикла добавлений в дерево/хэш и цикла поисков в нем.

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

> sort+sort+merge не отличается принципиально от цикла добавлений в дерево/хэш и цикла поисков в нем.

Довольно грубая оценка, но более-менее отражает суть:
O(n*m)  vs  O(n*logn)+O(m*logm)+O(n)  vs  O(n)+O(m)  - есть разница, я считаю. :) (первый вариант - авторский, второй - сортировка + merge, третий - построение хеша по одному массиву + проход второго массива)
Разумеется, это при условии, что сложность операций сравнения строк, добавления строки в хеш и проверки наличия ее в хеше оценивается величиной O(1).

twosev ★★
()

Я бы воспользовался map.

smh ★★★
()
Ответ на: комментарий от twosev

> O(n*m) vs O(n*logn)+O(m*logm)+O(n) vs O(n)+O(m) - есть разница, я считаю. :) (первый вариант - авторский, второй - сортировка + merge, третий - построение хеша по одному массиву + проход второго массива)

set_difference это и есть в некотором смысле merge -- это линейный проход по отсортированным данным.

> Разумеется, это при условии, что сложность операций сравнения строк, добавления строки в хеш и проверки наличия ее в хеше оценивается величиной O(1).

нуну. Еще оцени какого размера должна для этого быть хэш-таблица.

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

> это линейный проход по отсортированным данным

Ну я и написал "+O(n)".

> какого размера должна для этого быть хэш-таблица

Нене, для столь грубой оценки это излишне.

twosev ★★
()
Ответ на: комментарий от twosev

> Ну я и написал "+O(n)".

ну так ты посмотри на что ты отвечал.

Восстановлю хронологию:
- предлагается решение sort+set_difference
- почему не хэш?
- блаблабла, и от хэша особой экономии не будет
- экономия может быть огромной
- с какой кстати?
- тут появляешься ты весь в белом и рассказываешь про О большое.

Логарифм очень близок к константе и запросто может быть задавлен плохой константой в другом алгоритме.

ты считаешь логарифм огромной разницей??
Тем более что сам считаешь оценку размера требуемой хэш-таблицы мелочью.

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

> и рассказываешь про О большое

Все верно: тут появляюсь я весь в белом и стараюсь изложить свою точку зрения на то, почему экономия может иметь место быть (во всяком случае очевидно, что разница есть). И только.

> Логарифм очень близок к константе и запросто может быть задавлен плохой константой в другом алгоритме.

Логарифм ни разу не близок к константе. Безусловно, он может быть задавлен константой на определенных сочетаниях "алгоритм/длина входных данных", в данном примере можно также облажаться и в реализации хеширования - чисто гипотетически всё это можно. Только не нужно.

> ты считаешь логарифм огромной разницей??

В общем случае, да, считаю. Кроме того, не имею представления о том, как реализована предлагаемая сортировка. Может быть, там и не логарифм, а нечто большее. Разумеется, не утверждаю. Тем не менее, да, при оценке сложности алгоритма я таки различаю O(n) и O(n*logn).

twosev ★★
()

Предлагаю бенч устроить ради интереса.
Сейчас имею:
30000 строк, каждая 100-300 символов рандомно(ни одной одинаковой в 2-х файлах).
doSomething - это простой инкремент.
1) методом автора
real 0m11.034s
user 0m11.001s
sys 0m0.024s
2) sort, sort, set_difference
real 0m0.184s
user 0m0.160s
sys 0m0.020s
Хэш пока ниасилел (ну плох я в крестах =)

tzukko
()
Ответ на: комментарий от tzukko

Померял каряво, но если правильно - то всё еще лучше в пользу второго способа.

tzukko
()
Ответ на: комментарий от twosev

> Логарифм ни разу не близок к константе.

В мирное время синус не превышает 2, а логарифм 40.

dilmah ★★★★★
()
Ответ на: комментарий от tzukko

Не, всё неправильно, вставил clock_gettime, итого:
100000 строк, каждая 100-300 символов рандомно(ни одной одинаковой в 2-х файлах).
doSomething - это простой инкремент.
Лучший заход из примерно 10 прогонов.
1) Способ автора:
168.187593604сек
real 2m48.425s
user 2m47.906s
sys 0m0.188s
2) sort, sort, set_difference
0.372900466сек
real 0m0.671s
user 0m0.616s
sys 0m0.052s
3) set
0.146735270сек
real 0m0.518s
user 0m0.468s
sys 0m0.052s

Сет рулит =)

tzukko
()
Ответ на: комментарий от dilmah

>с какой это стати? sort+sort+merge не отличается принципиально от цикла добавлений в дерево/хэш и цикла поисков в нем.

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

Ценой некоторого перерасхода памяти, естественно.

Davidov ★★★★
()
Ответ на: комментарий от Davidov

> Ценой некоторого перерасхода памяти, естественно.

Еще надо найти хорошую хэш-функцию, так что... предсказуемый set рулит.

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

> Еще надо найти хорошую хэш-функцию

А вот это действительно вопрос.

twosev ★★
()
Ответ на: комментарий от Davidov

> А разве set не на хеше основан?

Когда я еще работал на Си++, set делвлся на RB-tree. Если верить stl_set.h из GNU C++. там тоже самое :)

tailgunner ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.