Подскажите, пожалуйста, как можно пробежаться по массиву строк типа "text1\r\ntext2\ntext3..." на наличие дубликатов между \r\n и удалить их, оставив только оригиналы? Не сравнивать же в цикле каждый i-ый элемент со всеми остальными элементами?

Очень важна скорость (объем обрабатываемой информации ~ 10 Mb).

Мне что-то говорили про hashset. How to use? В MSDN все кратко и непонятно.

Есть ли еще какие-либо альтернативные варианты?

DA>Подскажите, пожалуйста, как можно пробежаться по массиву строк типа "text1\r\ntext2\ntext3..." на наличие дубликатов между \r\n и удалить их, оставив только оригиналы? Не сравнивать же в цикле каждый i-ый элемент со всеми остальными элементами?

DA>Очень важна скорость (объем обрабатываемой информации ~ 10 Mb).

DA>Мне что-то говорили про hashset. How to use? В MSDN все кратко и непонятно.

DA>Есть ли еще какие-либо альтернативные варианты?

Быстрее всего будет свалить все токены в одну большую кучу, после чего отсортировать. Как показывает практика, если пользоваться каким-либо set или map, (неважно hash или обычным), то количество сравнений на большом объеме будет раз в 10 больше, чем в случае простой qsort. Можно сделать примерно следующее. Всю строку бьем на токены типа:

struct token
{
   const char* ptr;
   unsigned    len;
};

Для этого создаем

std::vector<token> tok;

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

Далее создаем предикат для сравнения двух токенов с учетом их длины:

struct str_less
{
    bool operator () (const token& t1, const token& t2) const
    {
        unsigned l1 = t1.len;
        unsigned l2 = t2.len;
        unsigned s1 = t1.ptr;
        unsigned s2 = t2.ptr;
        while(l1 && l2)
        {
            int r = int(*s1) - int(*s2);
            if(r != 0) return r;
            ++s1; ++s2; --l1; --l2;
        }
        if(l1 && l2 == 0) return 1;
        if(l2 && l1 == 0) return -1;
        return 0;
    }
};

Далее

std::sort(tok.begin(), tok.end(), str_less);

После этого можно легко убрать дубликаты и сформировать результирующую строку в виде, отсортировагнном по токенам. Если же важен исходный порядок, то здесь придется поработать еще, но это уже на домашнее задание.

Прошу прощения, функтор должен выглядеть так

MS>

MS>struct str_less
MS>{
MS>    bool operator () (const token& t1, const token& t2) const
MS>    {
MS>        unsigned l1 = t1.len;
MS>        unsigned l2 = t2.len;
MS>        unsigned s1 = t1.ptr;
MS>        unsigned s2 = t2.ptr;
MS>        while(l1 && l2)
MS>        {
MS>            int r = int(*s1) - int(*s2);
MS>            if(r) return r < 0;
MS>            ++s1; ++s2; --l1; --l2;
MS>        }
MS>        return l2 && l1 == 0;
MS>    }
MS>};
MS>

Здравствуйте, McSeem2, Вы писали:

... про qsort....

Вычислительная сложность qsort — O(n*n) строковых сравнений!
Плюс еще выводить как-то в порядке поступления.

А например если делаем так:

hash_table<string,bool> ht;

while(!eof(in))
{
string s = gets(in);
if(ht.exist(s))
continue;
ht[s] = true;
puts(out);
}

Что в самом худшем случае даст O(n*log2(n)) если я все правильно понимаю.
И сравнения будут hash values а не строк. (в основном)

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, McSeem2, Вы писали:

CS>... про qsort....

CS>Вычислительная сложность qsort — O(n*n) строковых сравнений!

Наихудший случай. Средний — O(n*ln(n)). Используемые вариации quicksort оптимизированны так, что наихудший случай никогда не встречается.

CS>Плюс еще выводить как-то в порядке поступления.

CS>А например если делаем так:

CS>hash_table<string,bool> ht;

А чем hash_map не понравился?

CS>while(!eof(in))
CS>{
CS> string s = gets(in);
CS> if(ht.exist(s))
CS> continue;
CS> ht[s] = true;
CS> puts(out);
CS>}

CS>Что в самом худшем случае даст O(n*log2(n)) если я все правильно понимаю.

Наихудший случай — O(n^2) (так как для hash table нуихудший случай отдельной операции — O(n)). Средний — O(n) или немножко хуже, учитывая, что еще будет происходить rehashing. Кстати, rehashing — ключевой момент в реализации hash table. Я надеюсь, что в твоей hash_table<> это тоже есть.

CS>И сравнения будут hash values а не строк. (в основном)

Что влияет только на константный множитель и никак на общее поведение алгоритма. Когда мы последний раз в книжку по алгоритмам смотрели?

Здравствуйте, DmitriAl, Вы писали:

DA>Подскажите, пожалуйста, как можно пробежаться по массиву строк типа "text1\r\ntext2\ntext3..." на наличие дубликатов между \r\n и удалить их, оставив только оригиналы? Не сравнивать же в цикле каждый i-ый элемент со всеми остальными элементами?

[]

DA>Есть ли еще какие-либо альтернативные варианты?

Альтернатива — написать простенький парсер, заюзав boost::spirit;

////////////////////////////////////////////////////////////////////////////////

#include <string>
#include <cassert>

#include <boost/spirit.hpp>

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/if.hpp>

////////////////////////////////////////////////////////////////////////////////

using std::string;

char const* test_input = "\r\naaa bbb\r\n\r\n\r\nccc\r\nddd eee\r\n\r\n";
char const* test_output = "\r\naaa bbb\r\nccc\r\nddd eee\r\n";

////////////////////////////////////////////////////////////////////////////////

template<class F1, class F2>
boost::spirit::rule<> make_unique_substring_rule(string const& substring, F1 f1, F2 f2)
{
    using namespace boost::spirit;

    return  
        *(
               (*str_p(substring.begin(), substring.end()))[f1]
            >> (+(anychar_p - str_p(substring.begin(), substring.end()) - ch_p(0)))[f2]
         );
}

////////////////////////////////////////////////////////////////////////////////

struct add_string
{
    add_string(string& r)
        : r_(&r)
    {}
    
    template<class Iterator>
    void operator()(Iterator a, Iterator b) const
    {
        r_->append(a, b);
    }
    
    string* const r_;
};

struct add_unique
{
    add_unique(string& r, string const& u)
        : r_(&r)
        , u_(u)
    {}
    
    template<class Iterator>
    void operator()(Iterator a, Iterator b) const
    {
        if(a != b)
            r_->append(u_);
    }

    string* const r_;
    string const u_;
};

string unique_substring(string const& input, string const& substring)
{
    string result;
    result.reserve(input.size());

    // gcc 3.3.1 fails to compile it
    /*
    parse(
          input.begin()
        , input.end()
        , make_unique_substring_rule(
              substring
            , add_unique(result, substring)
            , add_string(result)
            )
        );
    */
    // workaround
    parse(
          input.c_str()
        , make_unique_substring_rule(
              substring
            , add_unique(result, substring)
            , add_string(result)
            )
        );

    return result;
}

void test_unique_substring()
{
    assert(unique_substring(test_input, "\r\n") == test_output); 
}

////////////////////////////////////////////////////////////////////////////////

string unique_substring_lambda(string const& input, string const& substring)
{
    string result;
    result.reserve(input.size());
    
    using namespace boost::lambda;
    // gcc 3.3.1 fails to compile it
    /*
    parse(
          input.begin()
        , input.end()
        , make_unique_substring_rule(
              substring
            , if_then(_1 != _2,
                  bind(static_cast<string&(string::*)(string const&)>(&string::append), var(result), var(substring))
              )
            , bind(static_cast<string&(string::*)(char const*, char const*)>(&string::append), var(result), _1, _2)
            )
        );
    */
    // workaround
    parse(
          input.c_str()
        , make_unique_substring_rule(
              substring
            , if_then(_1 != _2,
                  bind(static_cast<string&(string::*)(string const&)>(&string::append), var(result), var(substring))
              )
            , bind(static_cast<string&(string::*)(char const*, char const*)>(&string::append), var(result), _1, _2)
            )
        );

    return result;
}

void test_unique_substring_lambda()
{
    assert(unique_substring_lambda(test_input, "\r\n") == test_output); 
}

////////////////////////////////////////////////////////////////////////////////

int main()
{
    test_unique_substring();
    test_unique_substring_lambda();
    return 0;
}

////////////////////////////////////////////////////////////////////////////////

Здравствуйте, c-smile, Вы писали:

CS>Вычислительная сложность qsort — O(n*n) строковых сравнений!
CS>Плюс еще выводить как-то в порядке поступления.

О! Это была провокация

Проверял я все эти дела, причем на реально больших объемах. GenBank, 50 гиг текста (сейчас уже наверное под сотню). Так вот, на практике qsort рулез. Да, теоретически O(N*N), в случае уже отсортированных данных. Такие случаи тоже бывали и решались, как это ни смешно, простым однопроходным shuffle. Любые хеш-таблицы, заполняемые на лету сводятся к TreeSort, что в приведенном ниже коде действительно дает O(N*log(N)). Но это очень медленно. У qsort большая дисперсия, но при равномерном распределении время близко к O(N). Во всяком случае, один из наиболее раальных способов залить в Oracle контекстный индекс по словам объемом в 50 гиг — это отсортировать по кусочкам, сколько влезет в память, слить отсортированные куски в отдельные файлы, после чего в один проход собрать и залить в базу. Вся работа занимает часа 2-3. Oracle interMedia в аналогичных условиях трудится пару недель, после чего падает
Да, словарь получается большой, порядка 30 миллионов уникальных слов, может именно это интермедию и срубает.

CS>А например если делаем так:

CS>hash_table<string,bool> ht;

CS>while(!eof(in))
CS>{
CS> string s = gets(in);
CS> if(ht.exist(s))
CS> continue;
CS> ht[s] = true;
CS> puts(out);
CS>}

CS>Что в самом худшем случае даст O(n*log2(n)) если я все правильно понимаю.
CS>И сравнения будут hash values а не строк. (в основном)

Для 10 мег этот вариант более чем сгодится. Правда памяти нажрет еще столько же, на всякие там деревья, но кто ж ее сейчас считает?

Здравствуйте, alexkro, Вы писали:

A>Наихудший случай — O(n^2) (так как для hash table нуихудший случай отдельной операции — O(n)). Средний — O(n) или немножко хуже, учитывая, что еще будет происходить rehashing. Кстати, rehashing — ключевой момент в реализации hash table. Я надеюсь, что в твоей hash_table<> это тоже есть.

CS>>И сравнения будут hash values а не строк. (в основном)

A>Когда мы последний раз в книжку по алгоритмам смотрели?



А вы Алекс?

Вообще-то computational complexity of hash tables is O(1) без учета rehash.
Это с утра было. Не знаю может к вечеру что изменилось?

Мой вариант конечного выражения O() в общем случае учитывает rehash.
Если карта ляжет хорошо то имеем просто O(1*log2(n)). И это очень вероятно.

A>Что влияет только на константный множитель и никак на общее поведение алгоритма.
Ну иногда этот самый *константый множетель* такой что как говорят в преферансе "за той горой все спрячется".

Не встречалось такое в практике?

Немного в сторону:
Мысли по поводу эффективной имплементации hash и списков.
http://www.kalinin.ru/programming/opt/08_08_01.shtml

Здравствуйте, McSeem2, Вы писали:

MS>Для 10 мег этот вариант более чем сгодится. Правда памяти нажрет еще столько же, на всякие там деревья, но кто ж ее сейчас считает?

Угу. И делается за пять минут.

А какие такие 'деревья', можно узнать?

Здравствуйте, McSeem2, Вы писали:

Макс, я не про деревья... я про hash tables...
Вот например http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html

Здравствуйте, c-smile, Вы писали:


мой самодельный hash_table примеррно в два раза медленнее qsort на данной задаче.
соотношение не зависит от количества строк.
Т.е. вычислительная сложность алгоритмов идентичная = O(n).

Cтроки формировались сугубо случайно. Если порядок строк не случайный то может вылезти O(n*n) в случае qsort.
hash_table в этом случае более устойчив.

Если надо могу привести исходники теста.

Здравствуйте, c-smile, Вы писали:

CS>Макс, я не про деревья... я про hash tables...
CS>Вот например http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html

Да я понял. Я просто со своей колокольни смотрел — мне надо было строить индекс в виде inverted list. Но и хеш-таблицы тоже были, для составления словаря. В конце концов я от них отказался, поскольку либо размер получался немерянный, либо коллизии все съедали. В общем, когда словарь сравним с самим текстом (дубликатов мало), хеш-таблицы тоже дохнут. Ну и потом, в 2 раза медленнее — это 4 часа взамест 2х

Здравствуйте, McSeem2, Вы писали:

MS>Да я понял. Я просто со своей колокольни смотрел — мне надо было строить индекс в виде inverted list. Но и хеш-таблицы тоже были, для составления словаря. В конце концов я от них отказался, поскольку либо размер получался немерянный, либо коллизии все съедали. В общем, когда словарь сравним с самим текстом (дубликатов мало), хеш-таблицы тоже дохнут. Ну и потом, в 2 раза медленнее — это 4 часа взамест 2х

А если по условию задачи тебе надо их выводить в порядке поступления — то вот тебе еще одна сортировка.

Здравствуйте, c-smile, Вы писали:

CS>А если по условию задачи тебе надо их выводить в порядке поступления — то вот тебе еще одна сортировка.

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

Здравствуйте, c-smile, Вы писали:

A>>Что влияет только на константный множитель и никак на общее поведение алгоритма.
CS>Ну иногда этот самый *константый множетель* такой что как говорят в преферансе "за той горой все спрячется".

CS>Не встречалось такое в практике?

Что-то мне говорит, что воду ты мутишь хорошо.

CS>Немного в сторону:
CS>Мысли по поводу эффективной имплементации hash и списков.
CS>http://www.kalinin.ru/programming/opt/08_08_01.shtml

Популистская статейка...