Может ли кто-нибудь помочь мне сделать эту функцию более эффективной - PullRequest
Новая
       7

Может ли кто-нибудь помочь мне сделать эту функцию более эффективной

0 голосов
/ 24 февраля 2019

Итак, я пытаюсь перебрать контейнер unordered_map.Контейнер читает входные данные из файла, который представляет собой список людей.Каждая строка в файле будет выглядеть как rCB, bIA, и это будет сохранено как элемент на карте.Вторая строка в каждом элементе действует как указатель на следующего человека в списке, поэтому позже она снова появится в новой строке, в данном случае: bIA,TDV.

Пока что я могу отсортировать по порядку, создав итератор unordered_map и используя вторую строку в функции поиска, чтобы итератор мог перейти к следующему элементу.Моя проблема идет другим путем.Я могу разобраться в обратном направлении, но способ, которым я реализовал свое решение, означает, что в конечном итоге сортировка занимает очень много времени, поскольку у нас есть входные файлы 3 миллионов человек. 

list<string> SortEast(unordered_map<string, string> &TempUMap, unordered_map<string, string>::iterator IT, list<string> &TempList)
{
    IT = TempUMap.begin();
    while (TempList.size() != (TempUMap.size() + 1))
    {
        if (IT->second == TempList.front())
        {
            TempList.emplace_front(IT->first);
            IT = TempUMap.begin();
        }
        IT++;
    }
    return TempList;
}

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

Любая помощь будет оценена.

РЕДАКТИРОВАТЬ: Пример одного из наших входных данных:

rBC,biA vnN,CmR CmR,gnz Dgu,OWn lnh,Dgu OWn,YMO YMO,SIZ XbL,Cjj TDV,jew iVk,vnN wTb,rBC jew,sbE sbE,iVk Cjj,wTb AGn,XbL gnz,SMz biA,TDV SIZ,uvD SMz,lnh

Это всего 20 человек.В этом случае AGn является первым значением, а uvD является последним.Вывод, который я получаю в итоге:

AGn XbL Cjj wTb rBC biA TDV jew sbE iVk vnN CmR gnz SMz lnh Dgu OWn YMO SIZ uvD

Поскольку этот файл начинается с rBC, это точка, в которой мне нужно отсортировать в обратном направлении

1 Ответ

0 голосов
/ 24 февраля 2019

Не могли бы вы просто сделать что-то вроде этого: 

vector<string> orderAllTheNames(const unordered_map<string, string>& input, const string& begin)
{
  vector<string> result;
  result.reserve(input.size());
  string current = begin;

  result.push_back(current);
  while(result.size() < input.size())
  {
    current = input[current];
    result.push_back(std::move(current));
  }
  return result;
}

Возможно, я пропустил некоторые детали, когда набирал это на своем телефоне.Вы можете добавить несколько указателей и / или std :: move, если вас беспокоит слишком большое количество копий.

Полагаю, это то же самое, что и ваше решение, но без неудобного списка и emplace_front.

...