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

Я пытаюсь отсортировать и найти медиану строки целых чисел, которая содержит только 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.

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

Источник

2 ответа

Решение

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

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;
};

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

Источник

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

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

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

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

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

Источник
Другие вопросы по тегам