find max - algorithmus optimieren

camper

alen schrieb:

@camper:
why should it look like O(1) now?

i know push is log k

armortized O(1) to be precise. Every element is pushed and poped exactly once. pop and top have constant complexity.

If you were to write

void removeIndex(pq &maxHeap, int index) {
            maxHeap.pop();
}

the algorithm would be broken but its easy to see that the complexity wouldn't change. The loop and index-check do not change the total amount of pop, they only shift them around to another invocation of removeIndex.

@camper: Dein Algorithmus hat einen Bug (Eingabe {9,1,1,1,8,1,1,1,9} ) und ich sehe auf die Schnelle nicht, wie man ihn reparieren könnte.

Daher hier meine O(n)-Version:

#include <iostream>
#include <cstddef>
#include <array>

int main() {
  auto&& arr = std::remove_reference_t<int[]>{
    9,1,1,1,8,1,1,1,9,1,2,3,1,4,5,2,3,6,11,12,13,14,15,16,15,14,13,12,11,10,9};
  constexpr auto n = sizeof(arr)/sizeof(*arr);
  constexpr auto k = std::size_t(5); static_assert(k < n, "");
  auto forward = std::array<int, n>{};
  auto backward = std::array<int, n>{};

  for (auto i = std::size_t(0); i<n; ++i)
    forward[i]  = i%k ? std::max(forward[i-1], arr[i]) : arr[i];
  backward[n-1] = arr[n-1];
  for (auto i = n-2; i --> 0;)
    backward[i]  = i%k ? std::max(backward[i+1], arr[i]) : arr[i];

  std::cout << "Output:";
  for (auto i = std::size_t(0); i+k-1<n; ++i)
    std::cout << ' ' << std::max(forward[i+k-1], backward[i]);
  std::cout << '\n';
}

camper

élève eleven schrieb:

@camper: Dein Algorithmus hat einen Bug (Eingabe {9,1,1,1,8,1,1,1,9} ) und ich sehe auf die Schnelle nicht, wie man ihn reparieren könnte.

Doofe off-by-1 Fehler

#include <iostream>
#include <cstddef>

int main() {
  int arr[] = {9,1,1,1,8,1,1,1,9,9,1,1,1,8,1,1,1,9,1,2,3,1,4,5,2,3,6,11,12,13,14,15,16,15,14,13,12,11,10,9};
  constexpr std::size_t n = sizeof(arr)/sizeof(*arr);
  constexpr std::size_t k = 5;
  int result[n-k+1]={};

  for (auto& elem : arr) {
    std::cout << ' ' << elem;
  }

  std::cout << "\nOutput:\n";

  std::size_t pos = 0, max_pos = 0;
// forwärts
  for (; pos != k; ++pos) {
    if ( arr[pos] >= arr[max_pos] )
        max_pos = pos;
  }
  for (; pos != n; ++pos) {
    result[pos-k] = arr[max_pos];
    if ( pos == max_pos + k )
      max_pos = pos - 1; // ++max_pos funktioniert genauso, max_pos muss nur in (pos-k,pos) liegen
    if ( arr[pos] >= arr[max_pos] )
      max_pos = pos;
  }
  result[pos-k] = arr[max_pos];
// rückwärts
  for (; pos != n - k; ) {
    --pos;
    if ( arr[pos] >= arr[max_pos] )
        max_pos = pos;
  }
  for (; pos != 0; ) {
    result[pos] = std::max(result[pos],arr[max_pos]);
    --pos;
    if ( pos == max_pos - k )
      max_pos = pos + 1;
    if ( arr[pos] >= arr[max_pos] )
      max_pos = pos;
  }
  result[pos] = std::max(result[pos],arr[max_pos]);

  for (auto& elem : result) {
    std::cout << ' ' << elem;
  }
  std::cout << '\n';
}

élève eleven schrieb:

Daher hier meine O(n)-Version:
...

Clever.

camper schrieb:

élève eleven schrieb:

@camper: Dein Algorithmus hat einen Bug (Eingabe {9,1,1,1,8,1,1,1,9} ) und ich sehe auf die Schnelle nicht, wie man ihn reparieren könnte.

Doofe off-by-1 Fehler

Immer noch nicht ganz ( {9,1,1,8,1,1,9} ).

camper schrieb:

élève eleven schrieb:
Daher hier meine O(n)-Version:
...
Clever.

Ist weniger optimiert wie deines, dafür etwas weniger anfällig auf Off-by-one-Fehler.

@camper:

wie waers mit folgenden algo, der muesste auch in O (n) laufen.

vector<int> getMax(vector<int> &vec, int k) {
	vector<int> out;
	deque<int> d; // stores the indices, sorted from max value to min value within the window k

	for (int i = 0; i < vec.size(); i++) {
		if (i < k) {
			while (!d.empty() && vec[i] >= vec[d.back()]) {
				d.pop_back();
			}

			d.push_back(i);
		} 
		else {
			out.push_back(vec[d.front()]);

			while (!d.empty() && vec[i] >= vec[d.back()]) {
				d.pop_back();
			}

			while (!d.empty() && d.front() <= (i - k)) {
				d.pop_front();
			}

			d.push_back(i);
		}
	}

	out.push_back(vec[d.front()]);

	return out;
}

camper

Neuer Versuch. Wobei das irgendwie falsch aussieht.

Edit: ist es auch..

Columbo

Worum geht's hier eigentlich? nth_element ?

@camper: warum falsch?

camper

Ich glaube mein Algorithmus ist nicht zu retten.

alen schrieb:

@camper:

wie waers mit folgenden algo, der muesste auch in O (n) laufen.
...

Das kommt dem nahe, was man wahrscheinlich tun würde, wenn man die Aufgabe mechanisch selbst zu lösen hätte.
Ist wahrscheinlich auch die effizienteste Methode (für d könnte man einen Ringpuffer mit max k Elementen verwenden).

camper

alen schrieb:

@camper: warum falsch?

Das bezog sich auf den Code, den ich ursprünglich in dem Post gezeigt hatte.