Li Chen's Blog

  • Top k algorithm revisited

    3 years ago, I implemented top K operator in LINQ. I was asked recently why I chose Min Heap since there are faster algorithms. To recap, we try to select top k element from a sequence of n elements. A min-heap has the following property:

    1. find-min takes O(1) time.
    2. extract-min takes O(ln k) time where k is the size of the heap.
    3. insert takes O(ln k) time.

    For each number in the sequence, I first compare the number to find-min. If the number is smaller, the number is tossed away. If the number is bigger, we do a extract-min followed by an insert. So in the worst scenario, the algorithm runs with time complexity of O(n ln k) and the space complexity of O(k).

    If we use max-heap instead, we can heapify n elements in O(n) time. Then we do k extract-max so we have the total time complexity of O(n + k ln n) and a space complexity of O(n).

    We could also use Quick Select. It is very similar to Quick Sort that we randomly select a pivot and move it to the right position. Unlike Quick Sort, we can discard the left side of the pivot whenever we have greater then k elements on the right side. This algorithm converge fairly quickly and we have the average time complexity of O(n) and space complexity of O(n). In average case, the space requirement by Quick Select is less than the max heap approach.

    So both max-heap and quick select are likely faster than the min-heap approach. Why do I used min-heap then? The reason is that the min-heap approach uses minimum amount of memory and I assume that I will work with large dataset so . Also, if we work with a stream, the min-heap provides a running top k.

  • Ever wonder on which platform Amazon AWS Lambda in C# is running?

    In last December, AWS announced C# support for AWS Lambda using .NET Core 1.0 runtime. Ever wonder on which platform is it running? I am curious too and I did not see it in any official documentation. So I decided to write a small AWS Lambda function to detect the platform:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Threading.Tasks;
    using System.Runtime.InteropServices;
    using Amazon.Lambda.Core;
    using Amazon.Lambda.Serialization;
     
    // Assembly attribute to enable the Lambda function's JSON input to be converted into a .NET class.
    [assemblyLambdaSerializerAttribute(typeof(Amazon.Lambda.Serialization.Json.JsonSerializer))]
     
    namespace SysInfoLambda
    {
        public class Function
        {
     
            /// <summary>
            /// A simple function that takes a string and does a ToUpper
            /// </summary>
            /// <param name="input"></param>
            /// <param name="context"></param>
            /// <returns></returns>
            public RuntimeInfo FunctionHandler(ILambdaContext context)
            {
                return new RuntimeInfo()
                {
                    FrameworkDescription = RuntimeInformation.FrameworkDescription,
                    OSArchitecture = RuntimeInformation.OSArchitecture,
                    ProcessArchitecture = RuntimeInformation.ProcessArchitecture,
                    OSDescription = RuntimeInformation.OSDescription,
                    OSPlatform = RuntimeInformation.IsOSPlatform(OSPlatform.Linux) ? OS.Linux :
                        RuntimeInformation.IsOSPlatform(OSPlatform.OSX) ? OS.OSX : OS.Windows
                };
            }
     
        }
     
        public class RuntimeInfo
        {
            public string FrameworkDescription { getset; }
            public Architecture OSArchitecture { getset; }
            public string OSDescription { getset; }
            public Architecture ProcessArchitecture { getset; }
            public OS OSPlatform { getset; }
        }
     
        public enum OS
        {
            Linux,
            OSX,
            Windows
        }
     
    }
    

    The result? The AWS C# Lambda runs in 64 bit Linux. The extract OS description is: Linux 4.4.35-33.55.amzn1.x86_64 #1 SMP Tue Dec 6 20:30:04 UTC 2016.

  • NSession is quietly marching towards 1.0 release

    My open source project NSession has be around for several years. It allows ASP classic pages to access ASP.NET out-of-process session states the same way that ASP.NET pages access them. Recently, there are a large number of users migrating from Windows 2003 to Windows Server 2008/2012 and encountered an incompatibility with ASP.NET 4.5. I was contacted by users daily publicly or privately. I decided to make additional effort to put finishing touch on it to make it a 1.0 product.

    In 0.9.0.1 release, I had:

    • Fixed the compatibility issues with asp.net 4.5.
    • Improved the documents.
    • Reduced hacking to make it less likely to encounter compatibility problem with future versions of ASP.NET.

    In 0.9.1.2 release, I had:

    • Added support for SQL Server session state so that it supports all the built-in out-of-proc session states in ASP.NET and is feature complete for 1.0 release.
    • Added a diagnostic check list and a diagnostic tool.

    Before 1.0 release, I will continue improving installation experience, fixing bugs reported and will do some performance testing.

    Beyond 1.0, I will start designing adapter interface to support custom session states. Please visit the project site to propose custom session state providers to support in the work items area.

  • First look at the Visual Studio Tools for Apache Cordova CTP 3.1

    The company that I worked for had an old cross-platform mobile app developed by an outside contractor using PhoneGap 1.0. When I was asked to look at the app a few months ago, I had great difficulty collecting large number of moving pieces: PhoneGap, Android SDK and emulator. When I saw Visual Studio Tools for Apache Cordova (I will call it VSTAC in the remaining of this post), I decide to give it a try since it attempts to install a large number of third-party software for me.

    The journey is not exactly easy, but it is certainly far easier than collecting all the pieces myself with the excellent installation document from MSDN. The result is more than pleasant. Here are some of my findings:

    1) After the installation, I could not even get a hello world app to work. It turns out that I had an older version of Nods.js. VSTAC skipped node.js installation. After I uninstall the old node.js and reinstall with the one linked from the VSTAC installation page, I was able to get hello world to work.

    2) I was surprise to see the Ripple emulator which I was not aware of previously. The Ripple emulator is very fast and VSTAC provides excellent debugging experience.

    3) I had to clear my Apache Cordova cache a few times. This and some other useful items are documented in FAQ. Also visit known issues.

    4) The application connects to an old soap web services developed with WCF. It does not support CORS. So I had to use Ripple proxy to connect to it but I kept getting 400 error. Fortunately, I was able to hack Ripple proxy to make it work.

    5) I then tried to run the app in Google Android emulator. VSTAC supports this scenario as well. I had to uninstall and reinstall some Android SDK components following this and this directions. Then I had to run AVD Manager to create and start a device. Then I had to update my display driver to make sure I have compatible OpenGL ES driver installed. After that, the Google emulator ran beautifully. It was not as fast as Ripple but is acceptable.

    So at the end, I want to give a big thank you to the Microsoft VSTAC team. I know this is not easy but the excellent document got me through. It certainly saved me lots of time.

  • Missing methods in LINQ: MaxWithIndex and MinWithIndex

    The LINQ library has Max methods and Min methods. However, sometimes we are interested in the index location in the IEnumerable<T> rather than the actual values. Hence the MaxWithIndex and MinWithIndex methods.

    These methods return a Tuple. The first item of the Tuple is the maximum or minimum value just the the Max and Min methods. The second item of the Tuple is the index location.

    As usually, you might get my LINQ extension from NuGet:

    PM>Install-Package SkyLinq.Linq

    Usage examples in the unit test.

  • ASP Classic Compiler is now available in NuGet

    I know this is very, very late, but I hope it is better than never. To make it easy to experiment with ASP Classic Compiler, I made the .net 4.x binaries available in NuGet. So it is now extremely easy to try it:

    1. From the package console of any .NET 4.x web project, run “Install-Package Dlrsoft.Asp”.
    2. To switch from AspClassic to Asp Classic Compiler in the project, add the following section to the system.webServer handlers section:
        <system.webServer>
          <handlers>
            <remove name="ASPClassic"/>
            <add name="ASPClassic" verb="*" path="*.asp" type="Dlrsoft.Asp.AspHandler, Dlrsoft.Asp"/>
          </handlers>
        </system.webServer>
      Comment out the section to switch back.
    3. Add a test page StringBuilder.asp:
      <%
          imports system
          dim s = new system.text.stringbuilder()
          dim i
          
          s = s + "<table>"
          for i = 1 to 12
              s = s + "<tr>"
              s = s + "<td>" + i + "</td>"
              s = s + "<td>" + MonthName(i) + "</td>"
              s = s + "</tr>"
          next
          s = s + "</table>"
          response.Write(s)
       
      %>
      This code uses the .net extension so it will only work with Asp Classic Compiler.

    Happy experimenting!

  • SkyLinq binaries are available on NuGet

    After much hesitate, I finally published my SkyLinq binaries on NuGet. My main hesitation was that this is my playground so I am changing things at will. The main reason to publish is that I want to use these works myself so I need an easy way to get the latest binaries into my projects. NuGet is the easiest way to distribute and get updates, including my own projects. There are 3 packages:

  • Sky LINQPad, a minimum viable clone of LINQPad in the cloud

    A while ago, I blogged about a simple LINQPad query host. It is fairly easy to put a web face on it. The only change that I had to make is to set the ApplicationBase for the AppDomains that I create as asp.net is quite different to an .exe app. A playground is now running at http://skylinq.azurewebsites.net/SkyLINQPad. One can upload an existing .linq files designed in LINQPad or type some queries directly into the page:

     

    image

  • A simple LINQPad query host

    I am a big fan of LINQPad. I use LINQPad routinely during my work to test small, incremental ideas. I used it so much so that I bough myself a premium license.

    I always wish I can run queries designed in LINQPad in my own program. Before 4.52.1 beta, there was only a command line interface. In LINQPad v4.52.1 beta, there is finally a Util.Run method that allows me to run LINQPad queries in my own process. However, I felt that I did not have sufficient control on how I can dump the results. So I decided to write a simple host myself.

    As in the example below, a .linq file starts with an xml meta data section followed by a blank line and then the query or the statements.

    <Query Kind="Expression">
      <Reference>&lt;RuntimeDirectory&gt;\System.Web.dll</Reference>
      <Reference>&lt;ProgramFilesX86&gt;\Microsoft ASP.NET\ASP.NET MVC 4\Assemblies\System.Web.Mvc.dll</Reference>
      <Namespace>System.Web</Namespace>
      <Namespace>System.Web.Mvc</Namespace>
    </Query>
     
    HttpUtility.UrlEncode("\"'a,b;c.d'\"")

    The article “http://www.linqpad.net/HowLINQPadWorks.aspx” on the LINQPad website gives me good information on how to compile and execute queries.  LINQPad uses CSharpCodeProvider (or VBCodeProvider) to compile queries. Although I was tempted to use Roslyn like ScriptCS, I decided to use CSharpCodeProvider to ensure compatible with LINQPad.

    We only need 3 lines of code to the LINQPad host:

    using LINQPadHost;
    ...
    string file = @"C:\Users\lichen\Documents\LINQPad Queries\ServerUtility.linq";
    Host host = new Host();
    host.Run<JsonTextSerializer>(file);
    

    As I mentioned at the beginning. I would like to control the dumping of the results. JsonTextSerializer is one of the three serializers that I supplied. The other two serializers are IndentTextSerializer and XmlTextSerializer. Personally, I found that the JsonTextSerializer and IndentTextSerializer the most useful.

    The source code could be found here.

    Examples could be found here.

  • Why every .net developer should learn some PowerShell

    It has been 8 years since PowerShell v.1 was shipped in 2006. I have looked into PowerShell closely except for using it in the Nuget Console. Recently, I was forced to have a much closer look at PowerShell because we use a product that exposes its only interface in PowerShell.

    Then I realized that PowerShell is such a wonderful product that every .net developer should learn some. Here are some reasons:

    1. PowerShell is a much better language that the DOS batch language. PowerShell is real language with variable, condition, looping and function calls.
    2. According to Douglas Finke in Windows Powershell for Developers by O’Reilly, PowerShell is a stop ship event, meaning no Microsoft server products ship without a PowerShell interface.
    3. PowerShell now has a pretty good Integrated Scripting Environments (ISE). We can create, edit, run and debug PowerShell. Microsoft has release OneScript, a script browser and analyzer that could be run from PowerShell ISE.
    4. We can call .NET and COM objects from PowerShell. That is an advantage over VBScript.
    5. PowerShell has a wonderful pipeline model with which we can filter, sort and convert results. If you love LINQ, you would love PowerShell.
    6. It is possible to call PowerShell script from .net, even ones on a remote machine.

    Recently, I have to call some PowerShell scripts on a remote server. There are many piecewise information on the internet, but no many good examples. So I put a few pointers here:

    1. When connecting to remote PowerShell, the uri is : http://SERVERNAME:5985/wsman.
    2. It is possible to run PowerShell in a different credential using the optional credential.
    3. Powershell remoting only runs in PowerShell 2.0 or later. So download the PowerShell 2.0 SDK (http://www.microsoft.com/en-us/download/details.aspx?id=2560). When installed, it actually updates the 1.0 reference assemblies . On my machine, they are in: C:\Program Files (x86)\Reference Assemblies\Microsoft\WindowsPowerShell\v1.0

     

    So the complete code runs like:

    using System.Management.Automation; // Windows PowerShell namespace
    using System.Management.Automation.Runspaces; // Windows PowerShell namespace
    using System.Security; // For the secure password
    using Microsoft.PowerShell;
    
    	    Runspace remoteRunspace = null;
                //System.Security.SecureString password = new System.Security.SecureString();
                //foreach (char c in livePass.ToCharArray())
                //{
                //    password.AppendChar(c);
                //}
                //PSCredential psc = new PSCredential(username, password);
                //WSManConnectionInfo rri = new WSManConnectionInfo(new Uri(uri), schema, psc);
                WSManConnectionInfo rri = new WSManConnectionInfo(new Uri(""http://SERVERNAME:5985/wsman"));
                //rri.AuthenticationMechanism = AuthenticationMechanism.Kerberos;
                //rri.ProxyAuthentication = AuthenticationMechanism.Negotiate;
                remoteRunspace = RunspaceFactory.CreateRunspace(rri);
                remoteRunspace.Open();
    
    	    using (PowerShell powershell = PowerShell.Create())
                    {
                        powershell.Runspace = remoteRunspace;
                        powershell.AddCommand(scriptText);
                        Collection results = powershell.Invoke();
                        remoteRunspace.Close();
                        foreach (PSObject obj in results)
                        {
                            foreach (PSPropertyInfo psPropertyInfo in obj.Properties)
                            {
                                Console.Write("name: " + psPropertyInfo.Name);
                                Console.Write("\tvalue: " + psPropertyInfo.Value);
                                Console.WriteLine("\tmemberType: " + psPropertyInfo.MemberType);
                            }
                        }
                    }