WingNews logo WingNews GitHub [2]

dzorz's comments

dzorz | 15 years ago | on: Finding the top K items in a list efficiently

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.

dzorz | 15 years ago | on: Finding the top K items in a list efficiently

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.

dzorz | 15 years ago | on: Google paper comparing performance of C++, Java, Scala, and Go [PDF]

If you compile recent clang, it supports range based for loops.

Using https://github.com/Rip-Rip/clang_complete you can use smart context-aware completion with vim/emacs.

For example if you had this code:

vector<string> vec; for (auto &x : vec) { x

and then if you typed period (.), it would show members from std::string. I'd say it works better than Intellisense (it's very precise and you use the same parser for code completion and final compilation).

dzorz | 15 years ago | on: N-Queen Problem: Python 2.6.5 vs PyPy 1.5.0

I managed to compile the program using shedskin, but it throws a runtime error after it finds the first solution:

    ==== solution 1 =====
    (0, 2, 5, 7, 9, 4, 8, 1, 3, 6)
    terminate called after throwing an instance of '__shedskin__::TypeError*'
    Aborted

dzorz | 15 years ago | on: N-Queen Problem: Python 2.6.5 vs PyPy 1.5.0

I think this is an example where C++ really shines. The code is not much longer (44 vs 33 lines, although the output in python version is much nicer) than the python code and on my computer it is about 140x faster than python 2.7.1.

dzorz | 15 years ago | on: The Dark Side of C++ (2007)

Wow, that is amazing. I honestly never tried that and assumed (because of short circuiting) that it can't be overloaded.
page 1
more