Hacker News Reader

Comment by veyron | Hacker News Reader

if K is fixed, as in the example from the article, this can be done in O(N) ...

Here is a solution in C++. It reads K and then N numbers from stdin and then prints K largest.

The complexity of nth_element is O(N).

    #include <algorithm>
    #include <vector>
    #include <iostream>
    #include <iterator>

    using namespace std;

    int main() {
        int K;
        cin >> K;
        vector<int> numbers((istream_iterator<int>(cin)),
                            istream_iterator<int>());
        nth_element(numbers.begin(), numbers.begin() + K, numbers.end(),
                    greater<int>());
        for (int i = 0; i < K; ++i) {
            cout << numbers[i] << ' ';
        }
        cout << '\n';
    }

Input:

    5
    1 9 1 3 7 8 2 11 2 5 5 9 1 7

Output:

    7 9 9 11 8

Note: the output is not sorted.

Personally the implementation of nth_element is a much more interesting thing to see than just knowing it exists.

It's STL-implementation specific. look in your c++ kit.

in mine (osx 10.6.7, g++ 4.2.1), it's in

/usr/include/c++/4.2.1/bits/stl_algo.h

and it uses an algorithm very similar to the original article

The original article uses heap to get top K numbers. It's runtime complexity is O(N*log(K)) and nth_element is O(N), so the algorithms are not similar at all.

scorchin posted the implementation of nth_element, except he forgot to look at how the gnu implementation of __introselect behaves.

If you look there, you will see it internally uses a heap.

It uses heap only as a fallback if maximum recursion depth is reached. The key difference between __introselect and the posted article is that __introselect uses pivoting to (ideally) "throw" away half of the array during each step.

    template<typename _RandomAccessIterator>
    inline void
    nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
                _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
 
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
      __glibcxx_requires_valid_range(__first, __nth);
      __glibcxx_requires_valid_range(__nth, __last);

      if (__first == __last || __nth == __last)
        return;

      std::__introselect(__first, __nth, __last,
                         std::__lg(__last - __first) * 2);
    }

you should look at how std::__introselect is defined (hint: its in /usr/include/c++/4.2.1/bits/stl_algo.h )

I don't know what the protocol is on HN, but I would be interested to see it.

It seems to me that if you know the K'th largest, it's O(N); but otherwise, it's harder.

> It seems to me that if you know the K'th largest, it's O(N); but otherwise, it's harder.

Finding the kth largest element can be done in O(N) time.

http://en.wikipedia.org/wiki/Selection_algorithm

The parent poster was making a joke. A simple such method is to scan the entire list, take the largest item, remove it from the list (or give it a fake value). Do this k times. k is fixed, so it's O(k*O(n))=O(n).

Obviously, as k approaches n, this algorithm is in reality O(n^2)

I'd recommend you start from Sipser [http://www.amazon.com/Introduction-Theory-Computation-Michae...] or Papadimitriou [http://www.amazon.com/Computational-Complexity-Christos-H-Pa...] to learn more about complexity theory (then we can discuss why your response is nonsense)

http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k...

I suspect your parent poster is being facetious (if we fix k, then just keep a buffer of the k largest elements we've seen so far. For any new element we see, check if it's larger than the smallest element in the buffer and if so remove the smallest and insert the new one. This takes O(k) time, so the algorithm overall takes O(kn), which, since k is constant, is O(n)).

In fact, this can be done in O(n) time even if k isn't constant: use the selection algorithm to find the k'th largest element (in O(n) time) and then go through the list again and output every number that's k or larger.

Doesn't this only work if the elements are unique? say you wanted the top three from [1,2,3,2,3,3,4,3,3,3,3,4,3], then the kth largest element would be 3, and we'd end up outputting [3,3,3,4,3,3,3,3,4,3], which is obviously not k elements.

For these types of problems you usually assume that every element is unique. The fix is just making two passes through the array instead of one, so it's still O(n).

It's typically easy to reduce solving such a problem with duplicates allowed into a very similar one without duplicates. Just replace every element x by the ordered pair (x, the position in the array where x came from) and then use a modified comparison function that sorts according to the second element in the pair if two ordered pairs are equal in the first element.

high level: you keep track of the K largest elements (call this array A). Every time you read an element (call it x), you compare it to the smallest element in A. if x is bigger than the smallest element of A, then remove the smallest element from A and add x to the list (and sort).

There are N elements in the sequence, and you can arrange for the sorting to be a single-step bubble sort, so that the total cost is O(K) operations per element --> O(NK) overall. Noting that K is constant, it's O(N).

Note that this really assumes K is constant. If K is depends on N, then the array A will expand

Reply on news.ycombinator.com