Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: смерджение векторов  (Прочитано 12735 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Bart
Новенький

ru
Offline Offline

« : 14-11-2017 18:19 » 

Есть код.
Объединяющий в один упорядоченный вектор
Код: (C++)
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;


int main(int argc, char** argv)
{
  vector<int> v1, v2, vMerged;
  v1.push_back(100);
  v1.push_back(300);
  v1.push_back(140);

  v2.push_back(2);
  v2.push_back(3);
  v2.push_back(4);


  vMerged.resize(v1.size() + v2.size());
  merge(v1.begin(), v1.end(), v2.begin(),v2.end(), vMerged.begin());

  cout << "Merged vector: \n";
  for(int i=0;i<vMerged.size();++i){
      cout << vMerged[i] << "\n";
  }

  return (0);
}
два Вопроса:
1. Возможно ли обойтись без буферного вектора, т.е. например расширить v1 или v2
2. Есть ли рациональные пути обойтись без merge().

СПАСИБО!
« Последнее редактирование: 14-11-2017 23:48 от Finch » Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #1 : 14-11-2017 20:58 » 

А кто мешает добавить значения v2 в v1?
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Bart
Новенький

ru
Offline Offline

« Ответ #2 : 14-11-2017 21:54 » 

Спасибо за внимание. Я вроде решил. Но не понимаю насколько правильно. Буду признателен если поправите/подскажите как улучшить

Код:

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

void print(int elem)
{
  cout << elem << " \n";
}
void mkmerge(const std::vector< int > &v1, std::vector< int > &v2)
{
    if(v1[v1.size()-1]<v2[0]){
        v2.insert( v2.begin(), v1.begin(), v1.end() );

    }
    else if(v2[v2.size()-1]<v1[0]){
        v2.insert( v2.end(), v1.begin(), v1.end() );

    } else {

    int i = 0, j = 0;
 
    while (i<v1.size() && j <v2.size())
    {
        if (v1[i] < v2[j]){
              v2.insert( v2.begin()+j, v1[i++] );
        }
j++;
    }
    }
}

int main(int argc, char** argv)
{
  vector<int> v1, v2,v3;
  v1.push_back(100);
  v1.push_back(140);
  v1.push_back(200);
  v1.push_back(200);
 v1.push_back(800);


  v2.push_back(200);
  v2.push_back(500);
  v2.push_back(300);
  v2.push_back(900);

  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());

  mkmerge(v1,v2);

 
  cout << "Merged vector: \n";
  for_each(v2.begin(), v2.end(), &print);
  return (0);
}
Записан
Bart
Новенький

ru
Offline Offline

« Ответ #3 : 14-11-2017 21:55 » 

Т.е. слияние двух отсортированных векторов в один засчет расширения одного из них
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #4 : 14-11-2017 23:08 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #5 : 14-11-2017 23:11 » 

А что мешает сначало слить два вектора в один а затем отсортировать
Код: (C++)
typedef std::vector<int> ListInt;
typedef ListInt::iterator ItrListInt;

ListInt v1, v2;
// Some action with vector

for(ItrListInt itr = v2.begin(); itr != v2.end(); ++itr) v1.push_back(*itr);
sort(v1.begin(), v1.end());

//C++11 notation
// for(auto x : v2) v1.push_back(x);
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #6 : 14-11-2017 23:15 » 

Сортировка слиянием более дешевая операция, однопроходная.
N против NlogN

И, Вить, push_back это очень медленно и очень неэффективно. Возможно неоднократное выделение памяти, возможно излишнее выделение памяти. Быстрее будет insert range: если место есть, только копирование, если нет, то одна переалокация с возможным перемещением данных.
« Последнее редактирование: 14-11-2017 23:28 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #7 : 14-11-2017 23:34 » 

Ром, насколько я разбирался с вектором. Если не вмешмватся в механизм работы. Сначало автоматически выделяется под 8 элементов место. Если происходит запрос на 9 место. То этот объем автоматически умножается на 2. Т.е. 16 мест. И так далее. Все время происходит умножение на два объема.

Добавлено через 11 минут:
В принципе в начале слияния можно сделать, что то типа
Код: (C++)
if (v1.size()+v2.size() > v1.capacity()) v1.resize(v1.size()+v2.size());
« Последнее редактирование: 14-11-2017 23:45 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #8 : 15-11-2017 05:32 » 


И, Вить, push_back это очень медленно и очень неэффективно.


reserve в помощь
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 15-11-2017 05:38 » 

А что мешает сначало слить два вектора в один а затем отсортировать
Код: (C++)

ListInt v1, v2;
// Some action with vector

for(ItrListInt itr = v2.begin(); itr != v2.end(); ++itr) v1.push_back(*itr);

а я бы вот так "слил"

Код: (C++)
v1.insert(v1.end(),v2.begin(),v2.end());
Записан

Bart
Новенький

ru
Offline Offline

« Ответ #10 : 15-11-2017 07:30 » 

Спасибо за ответы. Использование 2х векторов - это условие задачи.
Так в итоге, у меня получилось найти самый быстрый путь:)?  Или есть лучше варианты, или можно как-то улучшить?

Добавлено через 9 минут и 50 секунд:
Я наверно плохо сформулировал.
Есть два упорядоченных вектора. Нужно за минимальное время объединить их в один отсортированный вектор, причем это должен быть один из них(т.е. не создавая третий).
« Последнее редактирование: 15-11-2017 07:40 от Bart » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 15-11-2017 07:56 » 

Ром, насколько я разбирался с вектором. Если не вмешмватся в механизм работы. Сначало автоматически выделяется под 8 элементов место. Если происходит запрос на 9 место. То этот объем автоматически умножается на 2. Т.е. 16 мест. И так далее. Все время происходит умножение на два объема.

Зависит от реализации. Тесты на gcc/libstdc++ показывают, что нет изначального избыточного выделения. При нехватке емкость вектора удваивается с релокацией. По этому один push_back при отсутствии резерва даст почти двухкратный перерасход памяти. Если еще есть оптимизация с алокаторами, это просто ад и потеря памяти.
И да, ручное задание нужного размера — лучшая тут оптимизация. А по сумме совершенных микродействий оказывается, что все это было лишним, можно было прочто выделить новый вектор и слить в него. Исключение, если место уже было.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #12 : 15-11-2017 08:00 » 

Нужно за минимальное время

По тому, что я писал выше, быстрее именно с третьим вектором. Merge ищет разницу и копирует сериями, это быстрее, чем поштучное копирование при сортировке.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Aether
Специалист

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 15-11-2017 09:25 » new

Есть два упорядоченных вектора.

Код: (C++)
  v1.push_back(100);
  v1.push_back(300);
  v1.push_back(140);

  v2.push_back(2);
  v2.push_back(3);
  v2.push_back(4);
Что-то не похожи они на упорядоченные массивы, или я не прав?

Я считаю, что эффективнее было бы увеличить один из массивов до размера второго, а затем производить сравнение элементов с конца к началу и прописывать хвост с сортировкой сразу.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #14 : 15-11-2017 20:35 » 

Полагаю это опечатка.

Увеличение вектора веротянее всего даст реалокацию и копирование в новое место. Уже устал повторять. Читать не надо, я еще раз повторю Улыбаюсь
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Aether
Специалист

ru
Offline Offline
Пол: Мужской

« Ответ #15 : 15-11-2017 20:48 » 

Увеличение вектора веротянее всего даст реалокацию и копирование в новое место. Уже устал повторять. Читать не надо, я еще раз повторю Улыбаюсь
Я то это понимаю, но что поделаешь, если его, наверное, преподаватель хочет:
Есть два упорядоченных вектора. Нужно за минимальное время объединить их в один отсортированный вектор, причем это должен быть один из них(т.е. не создавая третий).
То есть, создание третьего вектора будет в неявном виде, хотя может быть и резерв у менеджера памяти. Он не всегда плотно компонует выделяемые блоки.

Я о самом алгоритме подумал, в принципе, если оба массива заранее отсортированы, то можно создать указатели сканирования, которые будут искать обрывы в блоках, то есть когда значение одного массива превышает значение из анализируемого блока другого - в этот момент можно копировать весь найденный блок в хвост. В общем, это быстрее простой сортировки однозначно, на сколько - не знаю. А задом наперёд разворачивать, чтобы голова не болела о возможной потере данных при копировании в увеличенный массив, то есть такая возможность полностью исключается без дополнительных проверок. Как-то так.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #16 : 15-11-2017 22:45 » 

Алгоритм писать не нужно, все давно написано до нас. Нужно лишь правильно применить. Библиотеки существуют именно для этого.

С заданием он, вроде, справился (я не учитель, не не проверял). Главное не задание, а самостоятельность, умение думать и использовать инструменты. И еще понимание, что велосипеды не стоит тащить на работу.
« Последнее редактирование: 15-11-2017 22:53 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines