Нахождение медианы из более чем 20 миллионов от 3 до 4 различных целых чисел за 1,5 секунды

Question

Я пытаюсь отсортировать и найти медиану строки целых чисел, которая содержит только от 3 до 4 различных целых чисел.

Количество чисел, с которыми я имею дело, составляет приблизительно от 20 до 25 миллионов, и я должен сортировать вектор и находить медиану каждый раз, когда в вектор добавляется новое целое число, и медиана добавляется в отдельный " Общая переменная, которая суммирует все медианы каждый раз, когда генерируется медиана.

1                   Median: 1              Total: 1
1 , 2               Median: (1+2)/2 = 1    Total: 1 + 1 = 2
1 , 2 , 3           Median: 2              Total: 2 + 2 = 4
1 , 1 , 2 , 3       Median: (1+2)/2 = 1    Total: 4 + 1 = 5
1 , 1 , 1 , 2 , 3   Median: 1              Total: 5 + 1 = 6

Я пытаюсь найти способ дальнейшей оптимизации моего кода, потому что он просто недостаточно эффективен. (Нужно обрабатывать до 2 с или около того) Кто-нибудь знает, как еще больше ускорить мою логику кода?

В настоящее время я использую 2 кучи или очереди приоритетов в C ++. Один функционирует как максимальная куча, а другой - как минимальная куча.

Получил идею от Структура данных, чтобы найти медиану

You can use 2 heaps, that we will call Left and Right.
Left is a Max-Heap.
Right is a Min-Heap.
Insertion is done like this:

If the new element x is smaller than the root of Left then we insert x to 
Left.
Else we insert x to Right.
If after insertion Left has count of elements that is greater than 1 from 
the count of elements of Right, then we call Extract-Max on Left and insert 
it to Right.
Else if after insertion Right has count of elements that is greater than the 
count of elements of Left, then we call Extract-Min on Right and insert it 
to Left.
The median is always the root of Left.

So insertion is done in O(lg n) time and getting the median is done in O(1) 
time.

но это не достаточно быстро ...

Answer 1

Если у вас есть только три-четыре целых числа в строке, вы можете просто отслеживать, сколько раз каждое из них появляется, пройдя строку один раз. Добавление (и удаление элементов) из этого представления также возможно в постоянное время.

class MedianFinder
{
public:
  MedianFinder(const std::vector<int>& inputString)
  {
    for (int element : inputString)
      _counts[element]++; // Inserts 0 into map if element is not in there.
  }

  void addStringEntry(int entry)
  {
    _counts[entry]++;
  }

  int getMedian() const
  {
    size_t numberOfElements = 0;
    for (auto kvp : _counts)
      numberOfElements += kvp.second;

    size_t cumulativeCount = 0;
    int lastValueBeforeMedian;
    for (auto kvp : _counts)
    {
      cumulativeCount += kvp.second;
      if (cumulativeCount >= numberOfElements/2)
        lastValueBeforeMedian = kvp.first;
    }

    // TODO! Handle the case of the median being in between two buckets.
    //return ...
  }

private:
  std::map<int, size_t> _counts;
};

Тривиальная задача суммирования медиан здесь не показана.

Answer 2

Я бы не стал так сильно оптимизировать, как уменьшить сложность с O(n * log n) до O(n).

Ваш алгоритм O(n * log n), потому что вы делаете n вставки, каждая стоимость амортизируется O(log n) раз.

Существует хорошо известный O(n) алгоритм для поиска медианы . Я предлагаю использовать это.

Обычно log n не имеет большого значения, но для 20 миллионов элементов он может сделать ваш алгоритм ~ в 25 раз быстрее.

О, мой плохой. Я не знал, что есть только 3-4 разных целых числа ...