дали такую вот задачку:

Надо реализовать ф-цию, максимально быстро работающую и оценить ее сложность O(?).

tepedef std::pair<std::string /*name*/, int /*value*/> Entry;
tepedef std::vector< Entry > Entries;

/**
@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
*/
void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
{
}

У кого есть какие варианты?

Здравствуйте, Аноним, Вы писали:

А>дали такую вот задачку:

А>Надо реализовать ф-цию, максимально быстро работающую и оценить ее сложность O(?).

А>tepedef std::pair<std::string /*name*/, int /*value*/> Entry;
А>tepedef std::vector< Entry > Entries;

А>/**
А>@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
А>@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
А>@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
А>*/
А>void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
А>{
А>}

А>У кого есть какие варианты?

А как данные хранятся в векторе? Отсортированы или нет?

Здравствуйте, Аноним, Вы писали:

Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
Заполняешь его данными из src, счётчик делаешь равным нулю.
Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).

Здравствуйте, Аноним, Вы писали:

А>дали такую вот задачку:

А>Надо реализовать ф-цию, максимально быстро работающую и оценить ее сложность O(?).

А>tepedef std::pair<std::string /*name*/, int /*value*/> Entry;
А>tepedef std::vector< Entry > Entries;

А>/**
А>@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
А>@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
А>@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
А>*/
А>void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
А>{
А>}

А>У кого есть какие варианты?


а что должна делать функция? составить последние 3 множества? если да, то почему merge?

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

S>Здравствуйте, Аноним, Вы писали:

S>А как данные хранятся в векторе? Отсортированы или нет?
нет

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

NBN>Здравствуйте, Аноним, Вы писали:

NBN>Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
— Это не очень понял, src каждому имени соотв только 1 Entry. Аналогично в dest
NBN>Заполняешь его данными из src, счётчик делаешь равным нулю.
NBN>Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).
— А сложность вставки в хеш тут учитывается?

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

I>а что должна делать функция? составить последние 3 множества?
да
если да, то почему merge?
не знаю, так назвали, суть не в этом

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

NBN>Здравствуйте, Аноним, Вы писали:

NBN>Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
NBN>Заполняешь его данными из src, счётчик делаешь равным нулю.
NBN>Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).

Вообще то 2 хэша понадобиться..

А>У кого есть какие варианты?

Сортируешь оба массива, находишь нужные данные двухпутевым слиянием. Получится O(N * log N + M * log M + N + M).

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


А>>У кого есть какие варианты?

sch>Сортируешь оба массива, находишь нужные данные двухпутевым слиянием. Получится O(N * log N + M * log M + N + M).

А если оба массива изначально отсортерованы по убыванию??? Если я не ошибаюсь у QuickSort в таком случае ассимптотика не N*log(N), а N^2 — худший случай..

Здравствуйте, Аноним, Вы писали:

А>У кого есть какие варианты?

Чтобы особенно не мудрить я бы сделал нечто подобное

typedef std::pair<std::string /*name*/, int /*value*/> Entry;
typedef std::vector< Entry > Entries;

/**
@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
*/
void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
{
    struct VecSorter : public std::binary_function<Entry, Entry, bool >
    {
        bool operator() ( const Entry &lhs,  const Entry &rhs ) const 
        {
            return lhs.first < rhs.first;
        }
    };

    Entries dest_sorted = dest;
    std::sort( dest_sorted.begin(),  dest_sorted.end(), VecSorter() );


    for( unsigned int src_idx = 0; src_idx < src.size(); src_idx ++ )
    {
        Entries::iterator pos = std::lower_bound( dest_sorted.begin() , dest_sorted.end(), src[src_idx] );

        if( pos == dest_sorted.end() )
        {
            removed.push_back(src[src_idx]);    
        }
        else
        {
            if( pos->second != src[src_idx].second )
                updated.push_back (src[src_idx]);

            dest_sorted.erase (pos); // exclude item existing in both, so remaining items in dest will be "added"
        }
    }

    added = dest_sorted;
}


int _tmain(int argc, _TCHAR* argv[])
{

    Entries src;
    src.push_back ( Entry( "a", 1 ) );
    src.push_back ( Entry( "b", 2 ) );
    src.push_back ( Entry( "c", 3 ) );
    src.push_back ( Entry( "d", 4 ) );
    src.push_back ( Entry( "f", 0 ) );
    
    Entries dest;
    dest.push_back ( Entry( "b", 4 ) );
    dest.push_back ( Entry( "a", 1 ) );
    dest.push_back ( Entry( "e", 4 ) );
    dest.push_back ( Entry( "d", 4 ) );
    dest.push_back ( Entry( "c", 5 ) );
   
    Entries added, updated, removed; 

    merge( src, dest, added, updated, removed );

    return 0;
}

сложность:

N — Src
M — Dest

O( M*log(M)) — sort
O( N*log(M) ) — поиск
----
O( (M+N)*log(M))

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

S>А если оба массива изначально отсортерованы по убыванию??? Если я не ошибаюсь у QuickSort в таком случае ассимптотика не N*log(N), а N^2 — худший случай..

А кто велит использовать Quick sort?

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

NBN>>Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
NBN>>Заполняешь его данными из src, счётчик делаешь равным нулю.
NBN>>Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).

S>Вообще то 2 хэша понадобиться..

Зачем? После того как src захеширован — мы можем просто пройтись в цикле по всем элементам dst:
если данный элемент dst не найден в хеше — помещаем в аддед.
иначе увеличиваем счётчик хешзначения на единицу.
и помещаем данный элемент dst в упдейтед.

когда цикл пройден — проходимся по всем элементам хеша, если счётчик равен нулю — помещаем элемент в removed, иначе в updated.

O(N(src)) на добавление в хеш
O(N(dst)) на цикл
O(N(src)) на постобработку

Итого O(N(src + dst)).

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

Это все будет работать если мало коллизий для hash-функции, это сильно зависит какие данные и какая функция.

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

S>Это все будет работать если мало коллизий для hash-функции, это сильно зависит какие данные и какая функция.

Ну и что?
1. В условиях задачи оговорены какие-то условия на данные.
2. хеш со строками обычно работает великолепно
3. хешфункцию можно подбирать под почти любые данные.

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

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

NBN>1. В условиях задачи оговорены какие-то условия на данные.
нет, как раз поэтому нужно предпологать наихудщие случаи. Т.к природа данных не указана, то выбор хеш-функции затруднен.

NBN>2. хеш со строками обычно работает великолепно
смотря какой хеш. Конечно, можно использовать SHA256, но это будет очень медленно.

NBN>3. хешфункцию можно подбирать под почти любые данные.
подбор хеш функции сделает твое решение не универсальным: одни данные — одна хеш-функция, другие данные — другая хеш-функция.

S>А как данные хранятся в векторе? Отсортированы или нет?
А вроде они всегда отсортированы? Или я ошибся?

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

NBN>>1. В условиях задачи оговорены какие-то условия на данные.
S>нет, как раз поэтому нужно предпологать наихудщие случаи. Т.к природа данных не указана, то выбор хеш-функции затруднен.
Для большого количества строк? Не шути, хеш в таком случае стандартное и проверенное решение.

NBN>>2. хеш со строками обычно работает великолепно
S>смотря какой хеш. Конечно, можно использовать SHA256, но это будет очень медленно.
Нет необходимости.

NBN>>3. хешфункцию можно подбирать под почти любые данные.
S>подбор хеш функции сделает твое решение не универсальным: одни данные — одна хеш-функция, другие данные — другая хеш-функция.
Подбор в данном случае необходим чтобы успокоить для особо нервных. В реальности никто ничего подбирать не будет.

Здравствуйте, Аноним, Вы писали:

А>У кого есть какие варианты?

хмм, это похоже на алгоритм синхронизации файлов. как раз пригодится.

1) я б их зверски пересортировал и пробежался по этим двум массивам.
можно не сортировать а выписывать по 1,2 начальных буквы(если так проще) из двух массивов. и тоже пересортировать.

2) пробегаем по полученным массивам. так как все идет по порядку можем определять выполняются ли наши условия и в каких массивах можно переходить к следующему элементы.

// блин, вот только щас заметил эти слова: added updated removed

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

Аноним 469 пишет:

> У кого есть какие варианты?

0) sort по name, O( 2 * log N ) , где N — объем наборов. положим они
приблизительно равны.
1) merge join O( N )

Стоимость вставок в результирующие контейнеры не учитываем — берём например
список или вектор пре-выделяем на N.