С++ оптимизировать вложенный цикл

05 февраля 2022, 11:10

Суть задания: есть список покупок по дням. Список является вектором векторов. Нужен цикл, который ищет товары, купленные более одного раза + число дней между покупками (разница между i). Ответ должен быть в типе MAP. Ключевое слово - название товара, вектор - число дней между покупками. Я написал программу целиком, и она работает без проблем. Как можно упростить и убыстрить цикл прохода по словам и строкам ?

i=0 bread butter milk
i=1 cherry apple yogurt bread curd
i=2 milk tea shampoo washingpowder
i=3 soap bread meat peach
i=4 bread cucumber
i=5 radish curd milk
i=6 yogurt peach chocolate puff
i=7 butter lemon cucumber
int n=0; //число дней
vector<vector<string> > arr; //вектор векторов для хранения товаров (по дням)
for(int i = 0; i < n-1; i++)   //цикл, который ищет товары, купленные более одного раза + число дней между покупками
{
  for(int k = 0; k < arr[i].size(); k++)
   {
     for(int r = i+1; r < n; r++)
      {
       for(int j = 0; j < arr[r].size(); j++)
        {
          if (arr[i][k]==arr[r][j])
            {const auto found = ANS.find(arr[i][k]);
            if (found!=ANS.cend()) {ANS[arr[i][k]].push_back(r-i);} else {ANS.insert(pair<string, vector<int> > (arr[i][k],{r-i}));}
            }
        }
      }
   }
}

Answer 1

Вот посмотрите такой вариант.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <numeric>
int main()
{
    //Это искомый контейнер 
    typedef map<string, vector<int>>  mapT;
    vector<vector<string> > arr; //вектор векторов для хранения товаров (по дням)
    //Заполняем данными
    vector<string> temp;
    arr.push_back(getItems("bread butter milk"));
    arr.push_back(getItems("cherry apple yogurt bread curd"));
    arr.push_back(getItems("milk tea shampoo washingpowder"));
    arr.push_back(getItems("soap bread meat peach"));
    arr.push_back(getItems("bread cucumber"));
    arr.push_back(getItems("radish curd milk"));
    arr.push_back(getItems("yogurt peach chocolate puff"));
    arr.push_back(getItems("butter lemon cucumber"));
    mapT  res;
    mapT::iterator  it;
    //Проходим по массиву
    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr[i].size(); j++) {
            //Ищем ключ
            it = res.find(arr[i][j]);
            if (it != res.end()) {
                //Ключ найден,тогда
                //суммируем предыдущие значения
                int z= accumulate(res[arr[i][j]].begin(), res[arr[i][j]].end(), 0);
                //Добавляем разность в днях
                res[arr[i][j]].push_back(i - z);
            }
            else {
                //Не найден
                //Добавляем новый
                vector<int> temp;
                temp.push_back(i);
                res[arr[i][j]] = temp;  
            }
        }
    }
    //вывод на экран
    auto itMap = res.begin();///создаем итератор на начало res
    for (itMap = res.begin(); itMap != res.end(); itMap++)
    {
        cout << itMap->first << " ";
        for (int n : itMap->second) {
            std::cout << n << ' ';
        }
        cout << endl;
    }

    getchar();
    return 0;
}

Answer 2

//сделаем это в течении 10 дней
//и допустим количество наименований товаров < 10
constexpr unsigned days = 10;
vector<vector<string>> products(days);
map<string, vector<unsigned>> Map;  
//инициализация
for (unsigned i = 0; i < days; ++i) {
    unsigned q = 5 + rand() % 5;
    for (size_t j = 0; j <= q; ++j) {
        string product = "pr" + to_string(rand() % 10);
        products[i].push_back(product);         
        Map[product].push_back(i);          
        cout << product << ' ';
    }       
    cout << endl;
}
//вывод    
unsigned day = 0;
for (const auto& p : Map) {
    cout << p.first << '\t';
    for (unsigned i : p.second) {           
        cout << i - day << ' ';
        day = i;
    }
    day = 0;
    cout << endl;
}