dotnet – Ticklish Techs https://www.ticklishtechs.net a mostly .NET but also some other cool techs blog Tue, 02 Jul 2024 19:18:19 +0000 en-US hourly 1 https://wordpress.org/?v=5.7.11 How to catch SqlExceptions and don’t get into trouble about aborted transactions by SQL Server (or: how is it possible that a transaction is only executed halfway) https://www.ticklishtechs.net/2016/07/31/how-to-catch-sqlexceptions-and-dont-get-into-trouble-about-aborted-transactions-by-sql-server-or-how-is-it-possible-that-a-transaction-is-only-executed-halfway/ Sun, 31 Jul 2016 20:26:21 +0000 http://www.ticklishtechs.net/?p=403 We witnessed a strange behavior in one of our projects that caused me some headache. Unfortunately, we could only observe it in production environment and never reproduce it. I took a look at the databases and could not imagine any circumstances that lead to such data. One day I said:

It looks like the transaction was only executed halfway or like a broken rollback.

But we were using Microsoft SQL Server and I could not imagine the existence of a bug that does such a thing and wasn’t already fixed to the current version.

By luck I got a clue and I could fix it in our code. Here is what happened:

The database

For the sake of simplicity let’s use this database with just two tables:

  • Table Data
    • Id (PK, int, not null)
    • Data (varchar(50), not null)
  • Table Log
    • Id (PK, uniqueidentifier, not null, autovalue)
    • Text (varchar(max), not null)

The code

try
{
 using (var transaction = new TransactionScope(TransactionScopeOption.Required))
 using (var connection = new SqlConnection(ConnectionString)) 
 {
 connection.Open();
    var insertDataCmd = connection.CreateCommand();
    insertDataCmd.CommandText = "INSERT INTO Data(Id, Data) VALUES(1, 'Foo')";
    try
    {
          insertDataCmd.ExecuteNonQuery();
    }
    catch (SqlException e)
    {
         Console.WriteLine(e.Message);
         // for some reason i don't care for this PK conflict
     }
    var insertLogCmd = connection.CreateCommand();
    insertLogCmd.CommandText = "INSERT INTO Log(Text) VALUES('this should not find its way to the database')";
    insertLogCmd.ExecuteNonQuery();     
    // don't commit this transaction       transaction.Complete();
 }
}
catch (Exception e)
{
    Console.WriteLine(e.Message);
}

 

We use TransactionScope to handle transactions. The first INSERT (with Id = 1) will throw an exception since a record with this id already exists. I don’t care about this exception, catch it and go on. Now I insert something into the log table. Finally, I will not commit the transaction at all.

This is a very artificial program to show just one event that has happened.

After running this piece of code I can find a new record in the log table even if the transaction was never committed! – That scared me!

The analysis

The first insert does not only throw a primary-key-already-exists-exception but the SQL Server itself aborted the transaction at this point. The following commands are executed without any transaction or transaction scope at all. I couldn’t imagine that this can happen with that code!

The reason for this behavior of SQL Server was a trigger like this:

CREATE TRIGGER InsteadOfInsertIntoData
 ON [Data]
 INSTEAD OF INSERT
 AS
 BEGIN
   INSERT INTO [Data] (Id, Data)
   SELECT
   Id,
   [Data]
   FROM inserted
 END
 GO

On tables without such a trigger my code works great. I can catch the exception and go on.

With this trigger, the PK error does not raise in user code but within the trigger. If an error happens within a trigger the transaction is always aborted.

(Please don’t start a discussion about this trigger itself. I don’t like it, but it was in the database. Cannot argue about it.)

Maybe with more explicated transaction handling

A colleague pointed out, that TransactionScope may be the problem and I should try explicit transaction handling with the pain old Transaction-class.

try
{
 using (var connection = new SqlConnection(ConnectionString))
 {
   connection.Open();
   var transaction = connection.BeginTransaction();
   var insertDataCmd = connection.CreateCommand();
   insertDataCmd.CommandText = "INSERT INTO Data(Id, Data) VALUES(1, 'Foo')";
   insertDataCmd.Transaction = transaction;
   try
   {
       insertDataCmd.ExecuteNonQuery();
   }
   catch (SqlException e)
   {
       Console.WriteLine(e.Message);
       // for some reason i don't care for this PK conflict
   }
    
    var insertLogCmd = connection.CreateCommand();
    insertLogCmd.CommandText = "INSERT INTO Log(Text) VALUES('this should not find its way to the database')";
    insertLogCmd.Transaction = transaction;
    insertLogCmd.ExecuteNonQuery();
    transaction.Rollback();
  }
}
catch (Exception e)
{
      Console.WriteLine(e.Message);
}

But it does not change much: the INSERT INTO Log got written to the database even with the Rollback() call at the end.

 

But you can observe something interesting on the transaction instance after SQL Server has aborted the transaction: The transaction-object got a private (!) property names “IsZombied” that got true afterwards. Buts its private, so I cannot access it in my code.

At the same moment the public property Connection of transaction lost its value and got null. A clue one could check but not very explicit and I don’t like to check for such a property every time I want to call ExectuteNonQuery().

A better solution (?)

I figured out that I can dig deeper into the SqlException and check if this exception aborted my transaction:

private static bool WasTransactionAborted(SqlException ex)
{
  foreach (SqlError error in ex.Errors)
  {
     // The statement has been terminated.
     if (error.Number == 3621)
        return true;
  }
  return false;
}

If any of the SqlErrors within the SqlException was of number 3621 then the transaction is dead and I don’t want to run any more code against my SQL Server connection.

The code from above can be changed at the point where I catch (and ignore) the exception to check for the described condition and don’t ignore that one.

 try
 { 
    cmd.ExecuteNonQuery();
 }
 catch (SqlException e) when (WasTransactionAborted(e))
 {
    Console.WriteLine("That's it - sorry - over and out");
    throw;
 }
 catch(SqlException e)
 {
    Console.WriteLine(e.Message);
    // for some reason I don't care for this PK conflict
 }

 

If the transaction was aborted we re-throw the exception end quit this method. Otherwise I can safely ignore the exception and go on.

]]>
Developing R#-PlugIns with a little comfort? https://www.ticklishtechs.net/2011/01/03/developing-r-plugins-with-a-little-comfort/ Mon, 03 Jan 2011 12:44:16 +0000 http://www.ticklishtechs.net/?p=342 I am playing around with R#-plugins these days. I have started off with this nice introduction. Unfortunately it silences about some problems that may occur to you in the beginning.

1) When trying to copy the given source code you’ll mention that all the classes are unknown to Visual Studio, because all a lot of references are missing. So far I have no clue about the R#-class-architecture. So I started .NET Reflector, open ALL the .dlls in the R#/bin-folder into Reflector and use the search to find the .dlls to reference in my project.

2) When you have your first R#-plugin ready you want to test it. To do so you have to copy the dll containing your plugin in the R#-plugin folder. You may want to do this in a post-build event like this:


copy $(TargetPath) "C:\Program Files (x86)\JetBrains\ReSharper\v5.1\Bin\PlugIns\WobTest"

When you build your project with this post-build event it fails. This doesn’t work for two reasons. First: Win 7 denies access to that folder. Second: after another start of Visual Studio R# has loaded the plugin so you can’t copy a newer version over it.

My solution to this is a .cmd that starts Visual Studio without R# (devenv /safemode). I run this .cmd as administrator.

Now at least I can debug my plugins by starting another instance of Visual Studio (not in safemode!)

This solution is not cool, because developing R#-plugin without using R# in the development-process sucks…. any ideas?

a better solution…

Some minutes after I published this post, Benjamin pointed me to this page. Forget about my lines to 2). You don’t need a silly .cmd run as administrator not a post-build event. All you need to do is to start your debugging Visual Studio the the command line option /ReSharper.Plugin followed by the path to your plugin-dll.

/ReSharper.Plugin "R:\sandbox\ReSharperPlugInTest\PublicGoesVirtual\PublicGoesVirtual\bin\Debug\PublicGoesVirtual.dll"

]]>
Be careful with certain ctors of XmlSerializer https://www.ticklishtechs.net/2010/07/23/be-careful-with-certain-ctors-of-xmlserializer/ Fri, 23 Jul 2010 06:07:49 +0000 http://www.ticklishtechs.net/2010/07/23/be-careful-with-certain-ctors-of-xmlserializer/ In my current project we’re using XmlSerializer a lot. At some point I need to write about 400 files with the XmlSerializer. For some reason I created a new XmlSerializer for each of these files.

I discovered during debugging a lot of debug messages in Visual Studio output window like:

'Application.vshost.exe' (Managed (v4.0.30319)): Loaded 'm0dayvr5'
'Application.vshost.exe' (Managed (v4.0.30319)): Loaded 'oxxqw1rq'
'Application.vshost.exe' (Managed (v4.0.30319)): Loaded 'dgh3mgtl'
'Application.vshost.exe' (Managed (v4.0.30319)): Loaded '00sdpqlv'
'Application.vshost.exe' (Managed (v4.0.30319)): Loaded 'yokpozj4'

 

Then I remembered that the XmlSerializer creates dynamic assemblies during runtime and loaded them into the AppDomain (and never unloads these assemblies since you cannot unload from an AppDoamin). In the MSDN article I found a solution that explains this behavior:

Dynamically Generated Assemblies

To increase performance, the XML serialization infrastructure dynamically generates assemblies to serialize and deserialize specified types. The infrastructure finds and reuses those assemblies. This behavior occurs only when using the following constructors:

XmlSerializer.XmlSerializer(Type)

XmlSerializer.XmlSerializer(Type, String)

If you use any of the other constructors, multiple versions of the same assembly are generated and never unloaded, which results in a memory leak and poor performance. The easiest solution is to use one of the previously mentioned two constructors. Otherwise, you must cache the assemblies in a Hashtable, as shown in the following example.

Of course you can use any other data structure to do the caching. But you have to do it on your own if you do not use the two mentioned constructors. I’ve got no idea why Microsoft builds caching into the code for some constructors and not for others, but that’s the way it is.

Some performance measurements

I didn’t build a great benchmark, but at least I got a few numbers. Serializing multiple files without caching takes on my machine about 140ms in debug mode and 130ms in release mode. Each time. With caching only the first file takes this 140 / 130ms and every additional file took about 8ms (debug) or 6ms (release).

That’s a speedup of about 17x to 20x!

And you do not produce memory leaks!

]]>
Creating a Setup with Visual Studio 2010 for an application that needs the full .net 4.0 framework https://www.ticklishtechs.net/2010/06/09/creating-a-setup-with-visual-studio-2010-for-an-application-that-needs-the-full-net-4-0-framework/ https://www.ticklishtechs.net/2010/06/09/creating-a-setup-with-visual-studio-2010-for-an-application-that-needs-the-full-net-4-0-framework/#comments Wed, 09 Jun 2010 12:50:48 +0000 http://www.ticklishtechs.net/2010/06/09/creating-a-setup-with-visual-studio-2010-for-an-application-that-needs-the-full-net-4-0-framework/ When using Visual Studio 2010 or any other version to create msi setups you can define prerequisites that need to be installed before the application will install. For most .NET applications this will be at least the .NET Framework itself. But from version 3.5 on there are two editions of this framework: the Client Profile and the Full Framework.

I created a setup and changed the prerequisites from Client Profile to the Full Framework. When testing this on a virgin machine the setup told me that I need to install the .NET 4.0 framework (that’s right) but then it directs me to the download of the Client Profile only.

To fix this, you have to change the InstallUrl of the .NET Framework Launch Condition:

  • right-click on the setup project in solution explorer and choose View –> Launch Conditions
  • here you will find a Launch Condition for the .NET Framework
  • select this Launch Condition and open the Properties Window
  • there you will find the InstallUrl property

For the full .net 4.0 Framework change this URL to http://go.microsoft.com/fwlink/?LinkId=186913

For the Client Profile of the .net 4.0 Framework the URL can stay as it is: http://go.microsoft.com/fwlink/?LinkId=131000

]]>
https://www.ticklishtechs.net/2010/06/09/creating-a-setup-with-visual-studio-2010-for-an-application-that-needs-the-full-net-4-0-framework/feed/ 3
Be careful when using GetCallingAssembly() and always use the release build for testing https://www.ticklishtechs.net/2010/03/04/be-careful-when-using-getcallingassembly-and-always-use-the-release-build-for-testing/ https://www.ticklishtechs.net/2010/03/04/be-careful-when-using-getcallingassembly-and-always-use-the-release-build-for-testing/#comments Thu, 04 Mar 2010 17:46:24 +0000 http://www.ticklishtechs.net/2010/03/04/be-careful-when-using-getcallingassembly-and-always-use-the-release-build-for-testing/ This looks like such a innocent method but it lead to big trouble in one of my projects. But lets start with when someone would use this method that is declared as a static method in the Assembly class. In the MSDN you can read:

Returns the Assembly of the method that invoked the currently executing method.

In our project we had an assembly with a lot of helper methods. On of these gets resources from the calling assembly. In various places of our code we called this method to get icons or other resources. This method used exactly this GetCallingAssembly() method to figure out what assembly to look for resources.

That worked pretty good in debug mode but exceptions were thrown in release mode. We could not understand what is going on. It became even worse: when we build a release version and tried to debug that version (using Visual Studio Debugger) in worked again. It looked like a heisenbug.

It took us some time to figure out what is also written in MSDN:

If the method that calls the GetCallingAssembly method is expanded inline by the compiler (that is, if the compiler inserts the function body into the emitted Microsoft intermediate language (MSIL), rather than emitting a function call), then the assembly returned by the GetCallingAssembly method is the assembly containing the inline code. This might be different from the assembly that contains the original method. To ensure that a method that calls the GetCallingAssembly method is not inlined by the compiler, you can apply the MethodImplAttribute attribute with MethodImplOptions.NoInlining.

The JIT compiler moves code around to optimize for performance. Small methods (up to about 56 Byte IL-Code if I remember it right) can be inlined where the method call was before. But the compiler does this only in release, not in debug mode. Also when attaching the debugger to our release build the JIT compiler stopped inlining to enable debugging and our bug was gone.

After understanding this, the fix is easy. Just don’t allow the compiler to inline that particular method that calls Assembly.GetCallingAssembly(). Then the method stays in the assembly where the source code is written and everything will be fine.

[MethodImplAttribute(MethodImplOptions.NoInlining)]
public void SomeFunction(int i)
{
    // ...
    var a = Assembly.GetCallingAssembly();
    // ...
}

This attribute does the trick and I recommend to use it on all methods that call GetCallingAssembly() and can be called form another assembly and need the real calling assembly.

]]>
https://www.ticklishtechs.net/2010/03/04/be-careful-when-using-getcallingassembly-and-always-use-the-release-build-for-testing/feed/ 1
A Change event for Dependency Properties https://www.ticklishtechs.net/2010/02/15/a-change-event-for-dependency-properties/ Mon, 15 Feb 2010 11:38:16 +0000 http://www.ticklishtechs.net/2010/02/15/a-change-event-for-dependency-properties/ WPF comes with Dependency Properties and everybody using WPF will know about these new kind of properties. When you define your own Dependency Properties in your own class you can pretty easy add a property change event handler:

public int MyProperty
{
    get { return (int)GetValue(MyPropertyProperty); }
    set { SetValue(MyPropertyProperty, value); }
}
public static readonly DependencyProperty MyPropertyProperty =
    DependencyProperty.Register("MyProperty",
                        typeof(int),
                        typeof(MainWindow),
                        new UIPropertyMetadata(0,
                            MyPropertyvalueChangeCallback));

private static void MyPropertyvalueChangeCallback
                        (DependencyObject d,
                         DependencyPropertyChangedEventArgs e)
{
}

But how to add such a event handler to an already existing Dependency Property or somewhere else then in the defining class? E.g. to an property of a WPF-Control that was not build by you. Take a standard WPF-TextBox; both the Text and the FontSize properties are Dependency Properties but the TextBox-class only provides a change event for the Text-property. Nevertheless you can get a change event for any Dependency Property:

DependencyPropertyDescriptor dpd =
    DependencyPropertyDescriptor.FromProperty
        (Control.FontSizeProperty, typeof (TextBox));
dpd.AddValueChanged(someTextBox, SomeTextBoxFontSizeChanged);

Every time the FontSizeProperty on the instance someTextBox changes the given method is called. It’s that easy and you can implement this code everywhere not only within the class that defines the property.

]]>
Shell-Lib reloaded: Another OS, another bug. https://www.ticklishtechs.net/2010/01/10/shell-lib-reloaded-another-os-another-bug/ Sun, 10 Jan 2010 14:38:06 +0000 http://www.ticklishtechs.net/2010/01/10/shell-lib-reloaded-another-os-another-bug/ Some time ago we blogged about a nifty little .net assembly that enables you to access the basic Windows shell operations in shell32.dll . You may want to do so especially in Win7 because your file operations integrate with the fancy Win7 dialogs, the flashing progress bar etc.

The problem we blogged about in the former post was a missing "Pack"-instruction in the marshalling-description of a structure. I guess we didn’t test it with WinXP64… but some days ago we tests it with Win7/64 and it failed. We figured out that we introduced a new bug that occurred on 64 bit machines only. After some more testing we found out that:

  • The original code (without Pack-value) crashes on 32 bit machines (as described in the former post).
  • The original code (without Pack-value) works fine on 64 bit machines (but we don’t think the original developer had 64 bits 7 years ago 😉 ).
  • Our fixed code (with Pack=2) works fine on 32 bit machines.
  • Our fixed code (with Pack=2) crashes on 64 bit machines.

It seems that the "SHFILEOPSTRUCT" structure in shell32.dll has different layouts in Win7/64 and Win7/32. I guess the guys at MS aim for performance and tell the compiler to optimize. The compiler optimizes by assuming the optimal Pack-value, which usually is the byte-width of the processor; 4 for 32bit, 8 for 64bit.

What effect does the Pack-value have at all?

The "Pack"-value controls the alignment of the starting addresses of each single member of a structure (often called "offset").

Let’s say you have this struct:

struct MammaMia
{
    public int16 sweet16;
    public byte bite;
    public string tanga;
}

Usually you don’t care for the exact way your data is stored in memory, but when you pass it from .NET to the Win-API you have to make sure Win-API receives and returns exactly the right format. This process is called "Marshalling".

One crucial instruction for doing so is the StructLayout attribute.

[StructLayout(LayoutKind.Sequential, Pack = 1)]
struct MammaMia
{
    public int16 sweet16;
    public byte bite;
    public string tanga;
}

(Note: There are a lot more options for the StructLayout attribute and a lot more attributes that help you at marshalling.)

LayoutKind.Sequential means that your data is represented in memory in the same order as you declared it: First "sweet16", than "bite" and then "tanga".

Pack=1 tells .NET that every byte can be the starting point of the next member. So .NET produces this structure in memory:

Pack=1  
byte data
0 sweet16
1 sweet16
2 bite
3 tanga
4 tanga
20 last character of tanga

 

 

Now Pack=2 makes sure that only every 2nd byte can be the starting point of the next member. That leads – of course – to unused bytes in memory:

Pack=2  
byte data
0 sweet16
1 sweet16
2 bite
3 ??? (unused)
4 tanga
5 tanga
21 last character of tanga

 

 

The higher the Pack-value, the more unused bytes you get:

Pack=4  
byte data
0 sweet16
1 sweet16
2 ??? (unused)
3 ??? (unused)
4 bite
5 ??? (unused)
6 ??? (unused)
7 ??? (unused)
8 tanga
9 tanga
25 last character of tanga

 

Is this a waste of memory? Sure. But processors can access those addresses a bit faster than other addresses. So it’s an performance/memory tradeoff.

After some more testing, I figured out that the correct Pack-value for Win7/64 is 8, while the correct Pack-value for Win7/32 is 2 (see former post). Why 2? I’d expect 4 here. I don’t know and Microsoft wouldn’t provide the source code I guess.
Maybe in former Windows version they preferred a middle-course between performance and saving memory.

The simple solution

Now it was obvious how to make die ShellLib-assembly work with 32 and 64bit: Check what machine we run on and use a different marshalling. Since I had to declare different structs here, the major code is copying data back and forth, not very interesting.

The only interesting part here is: How do you check on what kind of machine you run? I was looking for some property at System.Environment, but didn’t find anything. Then Andreas pointed me to this post and the solution is too simple to cross one’s mind:

“Just do a IntPtr.Size (static method) and since IntPtr is designed to be an integer whose size is platform specific, it will be 8 if you are on a 64-bit machine and 4 if you are on a 32-bit machine.“

You can find more information and our fixed code soon at the codeproject.com .

Epilog

You can also do the marshalling all by yourself, starting with memory allocation and ending with freeing memory, just like in the old times. But this is another story and will be told later.

Maybe.

]]>
How to get a IWin32Window from a WPF Window? https://www.ticklishtechs.net/2009/12/22/how-to-get-a-iwin32window-from-a-wpf-window/ https://www.ticklishtechs.net/2009/12/22/how-to-get-a-iwin32window-from-a-wpf-window/#comments Tue, 22 Dec 2009 12:53:34 +0000 http://www.ticklishtechs.net/2009/12/22/how-to-get-a-iwin32window-from-a-wpf-window/ When building applications that mix WPF and Winforms windows (e.g. because you are using a Winforms dialog within a WPF application) you will sometimes need a System.Windows.Forms.IWin32Window interface from an WPF System.Windows.Window. This will be useful when using the WinForms OpenFileDialog and wanting to provide a parent window to the ShowDialog() method that only accepts IWin32Window as parent.

The IWin32Window interface declares only one read-only property named Handle that must be provided by the WPF Window.

Implementing the Interface

It is very simple to just add this interface to an existing WPF Window and implementing the single property:

public partial class Window1 : Window, IWin32Window
{
   public IntPtr Handle
   {
      get
      {
         var interopHelper = new WindowInteropHelper(this);
         return interopHelper.Handle;
      }
   }
}

 

Using a wrapper class

It does not look as a very good solution to add such an interface to each and every Window in you whole application only to be able to be the parent of a dialog. So instead of implementing the interface directly you could build a wrapper class that implements this interface and use this wrapper when opening a dialog:

public class Wpf32Window : IWin32Window
{
    public IntPtr Handle { get; private set; }

    public Wpf32Window(Window wpfWindow)
    {
        Handle = new WindowInteropHelper(wpfWindow).Handle;
    }
}

Opening the dialog will now look like:

d.ShowDialog( new Wpf32Window(this) );

The grand solution to this problem

I like the wrapper solution more than implementing an interface to each and every window but I do not like the changed ShowDialog() call. It just does not look natural any more. To solve this I created an extension Method to be used with the wrapper class:

public static class CommonDialogExtensions
{
    public static DialogResult ShowDialog
                               (this CommonDialog dialog, 
                                     Window parent)
    {
        return dialog.ShowDialog(new Wpf32Window(parent));
    }
}

Now the call to open a WinForms dialog with an WPF parent looks as it should look like:

d.ShowDialog(this);

]]>
https://www.ticklishtechs.net/2009/12/22/how-to-get-a-iwin32window-from-a-wpf-window/feed/ 3
Isn’t one OpenFileDialog enough? https://www.ticklishtechs.net/2009/12/22/isnt-one-openfiledialog-enough/ Tue, 22 Dec 2009 12:53:25 +0000 http://www.ticklishtechs.net/2009/12/22/isnt-one-openfiledialog-enough/ In fact one OpenFileDialog is enough but the .net framework provides two of them:

  1. System.Windows.Forms.OpenFileDialog in System.Windows.Forms.dll
  2. Microsoft.Win32.OpenFileDialog in PresentationFramework.dll (that is WPF)

With such a setup one would use the first for WinForms applications and the second for WPF apps. In fact if you create a WPF application and just type in OpenFileDialog you will get number 2.

But the 2nd one (even if it is part of the newer part of the framework) is an old dialog where the 1st will use the new and shiny Windows 7 dialog on Win7. Just look at the following screenshots.

a

b

Only the first class uses the Windows 7 dialog and comes with proper support for Libraries etc. Even if the second shows the Libraries in its left part it does not fully support this new Windows 7 feature.

I have no idea why the WPF class uses the old windows API but it does. For best compatibility with all Windows versions (including 7) you should always use the Winforms Dialog even when building WPF apps! It does not hurt to reference the System.Windows.Forms.dll (it is installed an every machine running the .net framework) and you can use that dialog from WPF without any trouble.

You should only know about one little disadvantage when using the WinForms dialog. It only accepts WinForms as a parent window no WPF windows. To overcome this limitation please read my other article about the IWin32Window interface and how to implement / provide it in WPF at http://www.ticklishtechs.net/2009/12/22/how-to-get-a-iwin32window-from-a-wpf-window/

]]>
Hunting high and low https://www.ticklishtechs.net/2009/07/14/hunting-high-and-low/ https://www.ticklishtechs.net/2009/07/14/hunting-high-and-low/#comments Tue, 14 Jul 2009 11:48:31 +0000 http://www.ticklishtechs.net/2009/07/14/hunting-high-and-low/ Here is a nice little challenge, Benjamin came up with some months ago: “From a list of numbers find the smallest and the largest one – but do not use more than 1,5 comparisons per number.”

Dear reader: Try it!

The solution is simple, straight forward and very nice. And I didn’t find it.

I found something else. My approach was to look at the largest-number-so-far (max) and the smallest-number-so-far (min) as the boundaries of a region. A number outside this region must be larger than max or smaller than min and causes that boundary to change.

To check if a number (a) was outside that region a little computation came to my mind:

check = (max - a)*(min - a);

You would expect n to be smaller than max, so (max-n) should be positive.

You would expect n to be larger than min, so (n-min) should be positive, too.

Two positive numbers multiplied result in a positive number again.

So, if n was outside the boundaries, check would become negative. I only had to check which boundary was exceeded and that’s it:

if (check < 0)
    if (a > max)
        max = a;
    else
        min = a;

Using this approach the number of comparisons  converges to 1 when the length of the list grows. So I found a solution that is way better than 1,5 comparisons per number, didn’t I?

Boooooh

No, I didn’t. I cheated. In fact  (max-a) and (min-a) are comparisons, they just don’t use > or <.

(Actually it’s the other way around: To compute < or > most processors do a subtraction and compare the result to 0.)

So – if you count the subtractions as well you get 3+ comparisons per number…

The intended solution to the challenge (and the code you should provide in your exam) is:

a = list[count++];
b = list[count++];

if (a<b)
{
    if (a<min) min = a;
    if (b>max) max = b;
}
else
{
    if (b < min) min = b;
    if (a > max) max = a;                    
}

 

So – what’s the point of this post?

The point is: My silly approach can be faster than the standard solution. Depending on the type and range of the numbers in the list calculating and probing check needs less time than the comparisons in the standard solution.

It may not be much, but sometimes small advantages matter.  For example: For an integer-list of length 10^8 with values from -10.000 to 10.000 my approach is 0.02 seconds faster (on my current laptop). And has less code.

So if you feel like using it – I won’t charge you.

]]>
https://www.ticklishtechs.net/2009/07/14/hunting-high-and-low/feed/ 6