C ++ дизайн: учитывая список баллов студентов, приведите последовательность баллов в порядке

Question

У меня вопрос на C ++:

Учитывая список баллов студентов, приведите частоту баллов по порядку. [используйте карту контейнера c ++]

Моя идея: поместить список баллов в карту с баллом в качестве ключа и частотой в качестве значения. Прежде чем добавить ключ, найдите его. Если ключ новый, добавьте его и установите его freq как 1. Если нет, обновите его freq на ++ 1. O (nlgn)

Затем поменяйте ключ и значение на новой карте, на которой в качестве значения установите freq, а в качестве значения - его оценку. O (nlgn), потому что карта выполняет сортировку сама.

память: O (n)

Это не очень эффективно, потому что мне нужно использовать 2 карты и делать сортировку 2 раза.

Любые комментарии или идеи приветствуются.

Спасибо

---

  My code


    #include <iostream>
    #include <map>
    #include <algorithm>

    #include <time.h>

  using namespace std;
  const int M =10;
  int A[M] ;
  bool myFunc(pair<int, int> p1 , pair<double, int> p2)
  {
    //return p1.second > p2.second;
  }

   int scoreMap(int *A, const int& N)
   {
    if (A == NULL)
            return 1;
    map<int, int> map1;
    map<int, int>::iterator itr;
    int j = 0 ;
    while(j < N)
    {
            int myKey = (A[j]) ;
            itr = map1.find(myKey);
            if (itr == map1.end())
            {
                    map1.insert(pair<int, int>(myKey, 1));
            }
            else
            {
                    ++(itr->second);
            }
            ++j;
    }
    // print map1
    cout << "socre \t freq " << endl;
    for(itr = map1.begin(); itr != map1.end(); ++itr )
    {
            cout << itr->first << "\t" << itr->second << endl;
    }
    // use multimap
    multimap<int, int> map2;
    multimap<int, int>::iterator itr2;
    for (itr = map1.begin() ; itr != map1.end() ; ++itr )
    {
            map2.insert(pair<int, int>((*itr).second, (*itr).first)) ;
    }

    // print map2
    cout << "after sort " << endl;
    cout << "freq \t socre " << endl;
    for(itr2 = map2.begin(); itr2 != map2.end(); ++itr2 )
    {
            cout << (double)(itr2->first)/N << "\t" << itr2->second << endl;
    }
    return 0;
   }

   int main()
   {
    int N = 10;  int range=10;
    for (int i = 0 ; i < M ; ++i)
    {
            srand(time(NULL)+rand());
            //A[i] = rand()%range + (double)rand()/INT_MAX;
            A[i] = rand()%range ; // + (double)rand()/INT_MAX;
    //      sleep(1);
    }
    scoreMap(A, M);
    return 0;
   }

// EOF

время O (nlgn), пространство O (n), есть ли более эффективные решения? спасибо

Answer 1

Предположим, что оценка является узким целочисленным диапазоном (1-100)

Накопление баллов сохраняется в массиве [range-range] пар с вашей идеей ++ [score].

Извлечение частот производится путем итерационного перемещения вниз по списку баллов.O (N + M) N диапазон баллов + M количество результатов / баллов.Сортировать результат.

Пример псевдо:

const size_t MAX_SCORE = 100; //  Min is assumed 0.
void scoreFrequencies(int [] scores, size_t N){
    pair<int,int> score_counts[MAX_SCORES];
    for(size_t i = 0; i < N; i++){
        score_counts[i].first++;
        score_counts[i].second = i;
    }
    sort( score_counts, score_counts+MAX_SCORES );
    for(size_t score_decreasing = MAX_SCORES-1; 
             score_counts[score_decreasing].first!=0 && score_decreasing >=0; 
             score_decreasing--)
         cout<< (score_counts.second) <<": " << 
                 ( score_counts.first*1.0/N ) << endl;
}

Как видно, с помощью этого метода упорядочение Score_counts перед сортировкой (...) не требуется, поэтому map не поможет.

Answer 2

Вместо того, чтобы использовать карту, просто определите гистограмму всех оценок, используя тип массива std::pair<int, int>. Один участник будет баллами, а другой - частотой. Первоначально оценки будут иметь то же значение, что и индекс массива, в котором они находятся, но эту инициализацию следует выполнять только при попытке доступа к каждому конкретному индексу оценки, в противном случае вы в конечном итоге инициализируете группу оценок, которых не существует. Затем отсортируйте массив на основе частоты результатов после того, как вы заполнили гистограмму для самих результатов. Поскольку оценки в гистограмме в основном действуют как очень простой поиск по хешу, общее время должно быть очень быстрым (... O (1) для каждого просмотра оценки и соответствующего приращения частоты и O (n log n) для сортировки) .

Вот немного кода, чтобы помочь объяснить:

std::pair<int, int> scores[SCORE_RANGE] = {0}; //zero-out the entire array

//...iterate through your score data
for (int i=0; i < SCORE_DATA_SIZE; i++)
{
    int score_val = raw_score_data[i];

    if (scores[score_val].first == 0)
    {
        scores[score_val].first = score_val;
    }

    scores[score_val].second++;
}

//now sort your scores array based on the frequency which is stored in the second
//member of the std::pair structure

Answer 3

Моя идея: поместить список баллов в карту с баллом в качестве ключа и частотой в качестве значения.

Пока все хорошо,

Прежде чем добавить ключ, найдите его. Если ключ новый, добавьте его и установите его freq как 1. Если нет, обновите его freq на ++ 1. O (nlgn)

Проверка на наличие записи карты не нужна и расточительна. Запись появится (со значением по умолчанию) в первый раз, когда на нее ссылаются. Просто сделайте это:

++scoreMap[score];

Это не меняет твоего биг-о, но заставляет его идти быстрее.

Затем поменяйте ключ и значение на новой карте, на которой в качестве значения установите freq, а в качестве значения - его оценку. O (nlgn), потому что карта сама выполняет сортировку.

Вы не можете использовать новую карту, потому что оценка не обязательно будет уникальной. Но вы могли бы использовать set<pair>.

В честь правильной установки Ubuntu 11.10 (и g ++ 4.6!) На мой компьютер, вот как можно использовать лямбда-выражения для решения этой проблемы:

  map<int, int> scoreMap;
  for_each(istream_iterator<int>(cin), istream_iterator<int>(),
    [&scoreMap] (int i) { ++scoreMap[i]; } );
  set<pair<int,int>> freqMap;
  for_each(scoreMap.begin(), scoreMap.end(),
    [&freqMap] (const pair<int,int>& p) {
      freqMap.insert(make_pair(p.second, p.first));
    } );
  for_each(freqMap.rbegin(), freqMap.rend(),
    [] (const pair<int,int>& p) {
      cout << p.second << "/" << p.first << "\n";
    } );