Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# How to do a running median in n*log2(n)?

Tags:
  1. Jan 28, 2017 #1
    So I came up with the following solution which is n*log2(n) since the input is n elements and I use a binary insertion and calculating the median is constant time. This is passes all the test cases in the tests that don't time out. I need to figure out how to make it faster so I beat the timeouts. I'm pretty much out of ideas.

    Code (Text):

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    using System.Diagnostics.Contracts;

    namespace Solution
    {
        static class Extensions
        {
            public static void BinaryInsertion(this List<int> list, int val)
            {
                int index = list.BinarySearch(val);
                if(index < 0) index = ~index;
                list.Insert(index, val);  
            }
           
            public static double Median(this List<int> list)
            {
                Contract.Requires(list.Count > 0, "Method only valid for non-empty lists");
                int i = list.Count / 2;
                double d = list.Count % 2 == 1 ? (double)list[i] : (double)(list[i-1] + list[i]) / 2.0;
                return Math.Round(d, 1);
            }
        }
       
        class Solution
        {
            static void Main(string[] args)
            {
                int n = Int32.Parse(Console.ReadLine());
                List<int> list = new List<int>();
                for(int i = 0; i < n; ++i)
                {
                    int val = Int32.Parse(Console.ReadLine());
                    list.InsertInOrder(val);
                    Console.WriteLine(list.Median());
                }
            }
        }
    }
     
     
  2. jcsd
  3. Jan 28, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    How early does it time out? How much do you have to speed up the program?

    Where is this InsertInOrder method and where does your BinaryInsertion get used?
     
  4. Jan 28, 2017 #3
    It's a HackerRank problem, so I don't know exactly how much I need to speed it up. I did figure out that the Insert method is O(n), so in fact my program is O(n2)
     
  5. Jan 28, 2017 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    A log(n) insertion method should work then.
    Note that the base of the logarithm doesn't matter for the complexity class, as it just changes the prefactor.
     
  6. Jan 28, 2017 #5
    What type of data structure allows for log(n) insertion?
     
  7. Jan 28, 2017 #6

    Filip Larsen

    User Avatar
    Gold Member

    Indexable skiplist seems to be an efficient way forward [1]. Note that some people interpret "running" as "rolling" in which case the median on a long series is calculated as the median over a sliding window of fixed size.

    [1] https://rhettinger.wordpress.com/tag/running-median/
     
  8. Jan 28, 2017 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    A binary heap can do insertion in O(log(n)) in the worst case.

    Heapsort is O(n log(n)), and similar to your problem.
     
  9. Jan 28, 2017 #8
    Ok, I think I've figured out a way to keep track of the median(s) while building a binary tree. I'll have to handroll a class though. I'll let you know if it works.
     
  10. Jan 31, 2017 #9

    Svein

    User Avatar
    Science Advisor

  11. Jan 31, 2017 #10

    StoneTemplePython

    User Avatar
    Gold Member

    The simplest answer to this problem would seem to be have two different heaps, each with k items (or if you have an odd number of total items then one heap has k items, and the other has k + 1). I call this having two balanced heaps.

    Have one heap be a min heap, with all the 'big items', and the other be a max heap, with all the 'small items'. So long as your heaps are balanced you can get the median in O(1) at any given point in time. As a items comes in, you can insert and re-balance the heaps in O(log(n)) time.

    Explicit Binary trees can work as well, though heaps are simpler and use less memory (i.e. they are actually an array that we think of as a binary tree).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to do a running median in n*log2(n)?
Loading...