Party affiliation and general outlook 1991-2011

The proportions of Americans who are politically affiliated with one of the two major parties has been very stable over the last 20 years, at about 60% with a slight downward trend (+ marks and thick trend line in the chart below). Over the same period, the general outlook of the public has fluctuated wildly, with those who say the country is “going in the right direction” reaching over 50% at one point and falling 5 years later to 20% (circles and thin trend line). The public mood seems to be optimistic immediately following presidential elections (vertical dashed lines), and pessimistic immediately before them.

Data source: New York Times/CBS poll, April 15-20, 2011.

Advertisement

Sliding window statistics calculation complexity

The following C++ code takes a sequence of n elements, a₁, a₂, …, a_n, and outputs a sequence of n – k + 1 elements. The i-th output element is a maximal element in the subsequence a_i, a_{i + 1}, …, a_{i + k – 1}. The runtime complexity of the code is O(n).

template <typename T>
void insert(std::list< std::pair<T,unsigned int> > &l, T v)
{
    unsigned int sp = 0;
    while (!l.empty() && l.back().first < v)
    {
        sp++;
        l.pop_back();
    }
    l.push_back(std::pair<T,unsigned int>(v,sp));
}

template <typename T>
void advance(std::list< std::pair<T,unsigned int> > &l)
{
    if (l.front().second > 0)
        l.front().second--;
    else
        l.pop_front();
}

template <typename T>
void max_in_window(T const *in, T *out, size_t n, size_t k)
{
    std::list< std::pair<T,unsigned int> > l;
    unsigned int i;
    for (i = 0; i < k - 1 && i < n; i++)
        insert(l,in[i]);

    for (; i < n; i++)
    {
        insert(l,in[i]);
        out[0] = l.front().first;
        out++;
        advance(l);
    }
}

Interestingly, an algorithm for the median in a sliding window will have runtime of at least O(n log k), since such an algorithm can be used to sort O(n / k) sequences of length O(k) each:

Let a₁, a₂, …, a_n be a sequence of numbers in a known interval, say (0, 1). Create a sequence of length 3n – 2 by padding the sequence with a prefix of (n – 1) 0‘s and a suffix of (n – 1) 1‘s. Now execute the sliding window median algorithm with the padded sequence as input, and with k = 2n – 1.

The i-th output element will be the median of a sequence that is made of the entire sequence a₁, a₂, …, a_n, n – i zeros, and i – 1 ones. That median is a_(i), the i-th smallest elements of the sequence a₁, a₂, …, a_n. Thus, the output of the algorithm will be the sorted sequence a₍₁₎, a₍₂₎, …, a_(n).