find max - algorithmus optimieren

hi,

habe folgenden algo implementiert. dieser laueft in O(n * k) ?
wie kann ich ihn optimieren?

/*
Given an array and an integer k, find the maximum for each and every contiguous 
subarray of size k.

Examples:

Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6
*/

#include <vector>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

class node {
public:
	int index;
	int value;

	node(int index_, int value_): index(index_), value(value_) {}
};

struct Comparator {
	bool operator()(const node &lhs, const node &rhs) {
		return lhs.value < rhs.value;
	}
};

typedef priority_queue<node, vector<node>, Comparator> pq;

void removeIndex(pq &maxHeap, int index) {
	stack<node> copy;

	while (!maxHeap.empty()) {
		node n = maxHeap.top();
		maxHeap.pop();

		if (n.index == index) {
			break;
		}
		else {
			copy.push(n);
		}
	}

	while (!copy.empty()) {
		 maxHeap.push(copy.top());	
		 copy.pop();
	}

}

vector<int> getMax(vector<int> &vec, int k) {
	vector<int> out;
	pq maxHeap;

	for (int i = 0; i < vec.size(); i++) {
		if (i < k) {
			maxHeap.push(node(i, vec[i]));

			if (i == (k - 1)) {
				out.push_back(maxHeap.top().value);
			}
		}
		else {
			maxHeap.push(node(i, vec[i]));
			removeIndex(maxHeap, i - k);
			out.push_back(maxHeap.top().value);
		}			
	}

	return out;
}

int main() {
	vector<int> vec = {1,2,5,7,3,1,7,9,0};
    //k=2 [2,5,7,7,3,7,9,9]

    vector<int> out = getMax(vec, 2);

    for (auto e : out) {
    	cout << e << ' ';
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <set>

int main() {
  auto arr = std::vector<int>{1, 2, 3, 1, 4, 5, 2, 3, 6};
  auto k=size_t(3);

  std::cout << "Output:";

  auto active = std::multiset<int, std::greater<int> >();
  for (auto& elem : arr) {
    active.insert(elem);
    if (active.size() > k)
      active.erase(active.find(*(&elem-k)));
    if (active.size() == k)
    std::cout << ' ' << *active.begin();
  }
  std::cout << '\n';
}

camper

auto k=size_t(3);

wirklich?

camper schrieb:

auto k=size_t(3);
wirklich?

Ich nenne diesen Stil AAA: AAA ad absurdum.

Columbo

camper schrieb:

auto k=size_t(3);
wirklich?

Ich weiß! Ich dachte auch sofort an das fehlende std:: .

Nathan

camper schrieb:

auto k=size_t(3);
wirklich?

Kann doch mal passieren:

auto k=size_t{3};

welche laufzeit hat mein aktueller algo?

welche laufzeit hat dein algo welcher das multiset verwendet?

alen schrieb:

welche laufzeit hat mein aktueller algo?

$\mathcal{O}(nk\log k)$

alen schrieb:

welche laufzeit hat dein algo welcher das multiset verwendet?

$\mathcal{O}(n\log k)$

camper

#include <iostream>
#include <cstddef>

int main() {
  int arr[] = {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;
// vorwä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 ( arr[pos] >= arr[max_pos] || pos == max_pos + k )
      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 ( arr[pos] >= arr[max_pos] || pos == max_pos - k )
      max_pos = pos;
  }
  result[pos] = std::max(result[pos],arr[max_pos]);

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

lineare Laufzeit. Schöner Aufschreiben überlasse ich anderen.

@camper:
i optimized my function removeIndex, does it still run in O(k)?
are there any tricks i could get the removeIndex to O(1) using a heap?

void removeIndex(pq &maxHeap, int index) {
	while (!maxHeap.empty()) {
		node n = maxHeap.top();

		if (n.index > index) {
			break;
		} else {
			maxHeap.pop();
		}
	}
}

camper

alen schrieb:

@camper:
i optimized my function removeIndex, does it still run in O(k)?
are there any tricks i could get the removeIndex to O(1) using a heap?
void removeIndex(pq &maxHeap, int index) {
	while (!maxHeap.empty()) {
		node n = maxHeap.top();
		
		if (n.index > index) {
			break;
		} else {
			maxHeap.pop();
		}
	}
}

looks like O(1), but push isn't. Just consider the worst case: elements sorted in descending order.

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

i know push is log k

Swordfish

Nathan schrieb:

auto k=size_t{3};

auto k{ std::size_t{ 3 } };

gaah!

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 ?