Saturday, July 20, 2019

Testing (and Timing) String Reversal Functions

So Sarah Chima wrote an article about reversing a string, done four different ways. A few folk wrote in with other solutions. I wrote in with some too.

Then it was suggested that we try to work out which really is the fastest. What follows is me trying.

So I need first of all to mention my working environment. It's call Lychen and it's a wrapping of the V8 JavaScript engine in a C# command line application with access to some C# objects, methods and properties. Lychen is «not supposed to be cutting-edge. Rather, it's on the spine of the blade, about as far from the cutting-edge as one can get without leaving the blade altogether.» (see the Wiki).

You might say to me, "Hey, what about node?" My response is usually along the lines of "I just can't get my head around the promises and the asynchrony. Maybe one day."

So here's the code.
 
const Console = CS.System.Console;

CS. exposes a large number of C# core and third party objects into the Lychen (V8) environment. Rather than keep typing CS.System.Console we create an abbreviation.
 
if (CSSettings.ContainsKey("/D")) {
  debugger;
}

On launch, CSSettings (a Dictionary) receives all the command line parameters. In this case, if it's /D we debug.

const times = CSSettings.ContainsKey("/TIMES") ? parseInt(CSSettings("/TIMES"), 10) : 1000;

Similarly, here we check for the presence of /TIMES and if it's, say, /TIMES:123 then times is set to 123. Otherwise times defaults to 1000. /TIMES exists because we want to be able to run each test many times.

The first test of any routine usually takes a bit longer than subsequent runs due to operating system caching. We'll take many measurements and then average them in the hope of getting a better idea of how long things really take.
 
var original;
if (CSSettings.ContainsKey("/RANDOM")) {
  original = Array(12500)
    .fill(0)
    .map(function () {
      return String.fromCharCode(Math.floor(Math.random() * 256));
    }).join("");
} else {
  original = Array(500).join("lewd did i live - evil i did dwel").substr(0, 12500);
}

If the command-line contains /RANDOM we generate a test string of 12500 random ASCII characters. Otherwise we fill an array with some text and then truncate it to 12500 characters. 12500 was chosen because larger numbers caused the recursive functions to fail impolitely.
 
var reversed = Sarah_ForOf(original);

We use one of the following reversal functions to reverse the original test string so that we can double check that the reversal actually WAA (Works As Advertised).
 
function TimeTest(name, fn, original) {
  var Stopwatch = new CS.System.Diagnostics.Stopwatch();
  Stopwatch.Start();
  var answer = fn(original);
  Stopwatch.Stop();
  var ts = Stopwatch.Elapsed;
  return {
    name: name,
    ticks: ts.Ticks,
    reversed: answer
  };
}

We use C#'s System.Diagnostics.Stopwatch to track the run time of the function being tested. The parameters are: the name of the function, the function's reference, and the string to be tested. The Ticks of the Elapsed result of the run are returned along with the name and the results of the reversal. More about Ticks at the end.
 
function EmptyFunction(string) {
  return string;
}

We want to account for the cost of actually making the call, so we will time how long it takes just to load run an empty function that returns a string.

Next come the contributed routines.
 
const Sarah_SplitReverseJoin = (string) => string.split("").reverse().join('');

const Nathanael_SplitReverseJoin = (string) => [...string].reverse().join('');

function Sarah_ForOf(string) {
  let reverseString = "";
  for (let character of string) {
    reverseString = character + reverseString;
  }
  return reverseString;
}

const Sarah_Reduce = (string) => string.split('').reduce((rev, char) => char + rev, '')

function Sarah_Recursive(string) {
  return string ? Sarah_Recursive(string.substring(1)) + string[0] : string;
}

function Theophanis_SplitFor(string) {
  let result = string.split('');
  for (let i = 0, j = string.length - 1; i < j; i++, j--) {
    result[i] = string[j];
    result[j] = string[i];
  }
  return result.join('');
}

function Theophanis_SplitFor_Bruced(string) {
  let result = string.split('');
  for (let i = 0, j = string.length - 1; i < j; i++, j--) {
    const string_i = string[i];
    const string_j = string[j];
    if (result[i] !== string_j) {
      result[i] = string_j;
    }
    if (result[j] !== string_i) {
      result[j] = string_i;
    }
  }

  return result.join('');
}

I thought that checking for the need to swap before actually swapping would be a good optimisation. I was wrong, especially with respect to random data
 
function Bruce_ArrayApplyMap(string) {
  return Array.apply(null, new Array(string.length).fill(0).map(function (_, i) {
      return string.charAt(string.length - 1 - i);
    })).join("");
}

function Bruce_MapSortMap(string) {
  return Array(string.length)
  .fill({})
  .map(function (item, index) {
    return {
      index: index,
      character: string.charAt(index)
    };
  }).sort(function (a, b) {
    return a.index > b.index ? -1 : (a.index === b.index ? 0 : 1);
  }).map(function (item) {
    return item.character;
  }).join("");
}

function Bruce_Recursive1(string) {
  return (string.length === 1)
   ? string
   : Bruce_Recursive1(string.substr(1)) + string.substr(0, 1);
}

function Bruce_Recursive2(string) {
  if (1 >= string.length)
    return string;
  return (
    string.substr(-1) +
    Bruce_Recursive2(string.substr(1, string.length - 2)) +
    string.substr(0, 1));
}

function Bruce_CharAt(string) {
  const result = Array(string.length);
  for (let i = string.length - 1, j = 0; i >= 0; i--, j++) {
    result[j] = string.charAt(i);
  }
  return result.join("");
}

function Bruce_CharAt2(string) {
    const result = Array(string.length).fill(1);
    result.map(function (item,index) {
        let rhs = string.length - 1 - index;
        result[index] = string.charAt(index);
    });
    return result.join("");
}

That's all the contributed functions.

const namesAndCodes = [{
    name: "Sarah_SplitReverseJoin",
    code: Sarah_SplitReverseJoin
  }, {
    name: "Sarah_ForOf",
    code: Sarah_ForOf
  }, {
    name: "Sarah_Reduce",
    code: Sarah_Reduce
  }, {
    name: "Sarah_Recursive",
    code: Sarah_Recursive
  }, {
    name: "Theophanis_SplitFor",
    code: Theophanis_SplitFor
  }, {
    name: "Theophanis_SplitFor_Bruced",
    code: Theophanis_SplitFor_Bruced
  }, {
    name: "Nathanael_SplitReverseJoin",
    code: Nathanael_SplitReverseJoin
  }, {
    name: "Bruce_ArrayApplyMap",
    code: Bruce_ArrayApplyMap
  }, {
    name: "Bruce_MapSortMap",
    code: Bruce_MapSortMap
  }, {
    name: "Bruce_Recursive1",
    code: Bruce_Recursive1
  }, {
    name: "Bruce_Recursive2",
    code: Bruce_Recursive2
  }, {
    name: "Bruce_CharAt",
    code: Bruce_CharAt
  }, {
    name: "Bruce_CharAt2",
    code: Bruce_CharAt2
  }
];

The names and functions to be tested.
 
var gathering = {};

for (let i = 0; i < times; i++) {
  namesAndCodes.forEach(function (item) {
    const eps = TimeTest("EmptyFunction", EmptyFunction, original).ticks;
    const result = TimeTest(item.name, item.code, original);
    if (!gathering[result.name]) {
      gathering[result.name] = [];
    }
    gathering[result.name].push(result.ticks - eps);
  });
}

Here we do the testing, looping from zero to whatever value times holds. We forEach through the namesAndCodes structure. We calculate the time it takes to run an empty function and then we subtract that from the ticks of the result of the test. gathering holds the result of each test in an array keyed to the name of the function.
 
const average = arr => arr.reduce((p, c) => p + c, 0) / arr.length;

Object.keys(gathering).map(function (item) {
  return [item, average(gathering[item])];
}).sort(function (a, b) {
  return a[1] > b[1] ? 1 : a[1] === b[1] ? 0 : -1;
}).forEach(function (item) {
  Console.WriteLine("{0,-28}{1} ticks", item[0], item[1]);
});
""

Report on the results: Convert the gathering object into array[,] of name and averge, sort on the second item so that fastest comes first, write the results to the console with the name left-justified in a 28 character field, followed by the ticks.
And the results?
 
>timer.ly  /TIMES:1000
Sarah_ForOf                 2141.86 ticks
Sarah_SplitReverseJoin      2444.758 ticks
Sarah_Reduce                2805.243 ticks
Bruce_CharAt                2842.139 ticks
Nathanael_SplitReverseJoin  3035.17 ticks
Theophanis_SplitFor         3142.142 ticks
Bruce_Recursive1            3319.84 ticks
Bruce_Recursive2            3451.674 ticks
Theophanis_SplitFor_Bruced  3616.858 ticks
Sarah_Recursive             4645.366 ticks
Bruce_ArrayApplyMap         5637.1 ticks
Bruce_MapSortMap            9754.566 ticks
Bruce_CharAt2               13721.967 ticks


>timer.ly  /TIMES:1000 /RANDOM
Sarah_ForOf                 1850.582 ticks
Sarah_SplitReverseJoin      2655.574 ticks
Theophanis_SplitFor         2815.478 ticks
Nathanael_SplitReverseJoin  2832.566 ticks
Bruce_CharAt                2842.439 ticks
Sarah_Reduce                2845.746 ticks
Bruce_Recursive2            3224.578 ticks
Bruce_Recursive1            3306.136 ticks
Theophanis_SplitFor_Bruced  3428.827 ticks
Sarah_Recursive             4258.6 ticks
Bruce_ArrayApplyMap         5421.202 ticks
Bruce_MapSortMap            9748.012 ticks
Bruce_CharAt2               13477.231 ticks

On my computer there are 10,000,000 ticks per second (using CS.System.Diagnostics.Stopwatch.Frequency). According do the documentation "Each tick in the ElapsedTicks value represents the time interval equal to 1 second divided by the Frequency."

The bottom line? Sarah's ForOf and SplitReverseJoin are by far the fastest. Theophanis's SplitFor is also really good. That said, the differences are in microseconds or less.

NOTE: All suggestions on how to improve this testing regime gratefully received. Thanks in advance.

Please note: this blog post was originally published at Dev.to on 2019-07-20.

Wednesday, July 17, 2019

Do I really want to write a Google Keep tool?

After writing so many wrappers and so many scraping tools over the last few years, I'm now asking myself: "Do I really want to write tools for Google Keep?" There's been a few folk calling for a Google Keep API but nothing has materialized as yet (AFAICT.)

I do use Keep a lot as a general catchall for interesting web content. Mind you, I use Pocket as well. And PearlTrees. And Zim.

Fiddling with my Keep collection in Firefox Developer sees me trying to spot some structures that could be targeted in Selenium. One item of interest is via document.querySelectorAll(".RNfche"). At this point I don't know if the RNfche class is specific to my collection or to everyone's, but it's on every containing DIV. The number of results of the querySelectAll() increases as one scrolls down the page. Thus, to find every one of them one would have to script Selenium to scroll right down to the bottom of the collection before pulling up the list of RNfche-class elements.

Can I really be bothered?

Please note: this blog post was originally published at Dev.to on 2019-07-17.

Tuesday, July 16, 2019

ScriptProperties Gotcha in Google Apps Script

For reasons of insanity I have wrapped the ScriptProperties of the PropertiesService in a object with get, set, forget and getKeys methods, viz:

function ScptProps() {
  this.scriptProperties = PropertiesService.getScriptProperties();
}

ScptProps.prototype.get = function (name) {
  return this.scriptProperties.getProperty(name);
};

ScptProps.prototype.set = function (name, value) {
  return this.scriptProperties.setProperty(name, value);
};

ScptProps.prototype.forget = function (name) {
  return this.scriptProperties.deleteProperty(name);
};

ScptProps.prototype.getKeys = function () {
  return this.scriptProperties.getKeys();
};

Using the REPL from my previous posting, I issued the following commands:
 
(new ScptProps).set('goose',58);
typeof (new ScptProps).get('goose');
(new ScptProps).forget('goose');

Goose is me and 58 my age for those interested.

And the gotcha? Well, I was a little taken aback recently, while debugging a number to number comparison issue, to discover that when I store a number I don't get one back. I get a string back and have to do a parseInt() on it to get its original value. The result of typeof (new ScptProps).get('goose'); is, you guessed it, string!

Please note: this blog posting was originally published in Dev.to on 2019-07-16

Thursday, July 11, 2019

REP and almost L in Google Apps Script

It's been quite a while since I blogged about computing (I usually blog about baking) but here goes.

Lately I've been climbing a steep learning curve, trying to get my head around Google Apps Script (GAS). Now a few spreadsheets later, I'm on a trajectory that should see me crash-land on Planet Add-On in a month or two.

REPL (read-evaluate-print-loop) has been a big thing for a long time with all manner of programming languages. So why not GAS? (Okay, it's more REP than REPL as the looping doesn't happen, but it's close.)

In my Code.gs I have the following (among other things)

function onOpen() { 
  var ui = SpreadsheetApp.getUi();
  ui.createMenu('Debugging')
  .addItem('REPL', 'REPL')
  .addToUi();  
}

This adds a custom menu to the menubar and populates it with one entry, namely 'REPL' which, when selected, runs a function called 'REPL'.
 
function REPL() {
  var code = Browser.inputBox('code');
  if (code !== 'cancel') {
    Browser.msgBox(eval(code));
  }
}

Also in there, for demonstration purposes, is a function that totals the ASCII values of the characters in the parameter string.
 
function TotalAscii(str) {
  return str.split("").reduce(function (result, item, index) {
    return result + item.charCodeAt(0)
  }, 0)
}
 
Visually there we are selecting the REPL option from the Debugging menu

 

entering something to be evaluated and getting a response.



I'd like at some stage to put together an HTML form with a TEXTAREA. Maybe after I crawl out of the crater.

Please note: This blog posting was first published at Dev.to on 2019-07-11

Monday, December 24, 2018

[tbas] Chinese Year of the ...

The author of tbas, Antonio Maschio, loves DATA and READ statements, and after putting together a Chinese Zodiac submission for RosettaCode, I can see why. And then there's TAB() which is also very helpful.

DATA "甲","乙","丙","丁","戊","己","庚","辛","壬","癸"
 DECLARE celestial$(10)
 MAT READ celestial$
 
 DATA "子","丑","寅","卯","辰","巳","午","未","申","酉","戌","亥"
 DECLARE terrestrial$(12)
 MAT READ terrestrial$
 
 DATA "Rat","Ox","Tiger","Rabbit","Dragon","Snake","Horse","Goat","Monkey","Rooster","Dog","Pig"
 DECLARE animals$(12)
 MAT READ animals$
 
        DATA "Wood","Fire","Earth","Metal","Water"
 DECLARE elements$(5)
 MAT READ elements$
 
 DATA "yang","yin"
 DECLARE aspects$(2)
 MAT READ aspects$
 
 DATA "jiă","yĭ","bĭng","dīng","wù","jĭ","gēng","xīn","rén","gŭi"
 DATA "zĭ","chŏu","yín","măo","chén","sì","wŭ","wèi","shēn","yŏu","xū","hài"
 DECLARE celestialpinyin$(UBOUND(celestial$(),1))
 DECLARE terrestrialpinyin$(UBOUND(terrestrial$(),1))
 MAT READ celestialpinyin$
 MAT READ terrestrialpinyin$
 
 DATA 1935,1938,1931,1961,1963,1991,1993,1996,2001
 DECLARE years(9)
 MAT READ years
 
 DECLARE _base = 4  
 DECLARE _year 
 DECLARE cycleyear 
 DECLARE stemnumber 
 DECLARE stemhan$    
 DECLARE stempinyin$ 
 DECLARE elementnumber 
 DECLARE element$       
 DECLARE branchnumber 
 DECLARE branchhan$    
 DECLARE branchpinyin$ 
 DECLARE animal$       
 DECLARE aspectnumber 
 DECLARE aspect$       
 DECLARE index 
 
 DECLARE i 
 DECLARE top = UBOUND(years(),1)
 FOR i = 1 TO top
  _year = years(i)
  cycleyear = _year - _base
  stemnumber = MOD(cycleyear, 10) 
  stemhan$    = celestial$(stemnumber + 1)
  stempinyin$ = celestialpinyin$(stemnumber + 1)
  elementnumber = div(stemnumber, 2) + 1
  element$       = elements$(elementnumber)
  branchnumber = MOD(cycleyear, 12)  
  branchhan$    = terrestrial$(branchnumber + 1)
  branchpinyin$ = terrestrialpinyin$(branchnumber + 1)
  animal$       = animals$(branchnumber + 1)
  aspectnumber = MOD(cycleyear, 2)
  aspect$       = aspects$(aspectnumber + 1)
  index = MOD(cycleyear, 60) + 1  
  PRINT _year; 
  PRINT TAB(5);stemhan$+branchhan$;
  PRINT TAB(12);stempinyin$;"-";branchpinyin$;
  PRINT TAB(25);element$;" ";animal$;" ("+aspect$+")";
  PRINT TAB(50);"year";index;"of the cycle"  
 NEXT
Running the program gives
$ tbas chinZod.bas
 1935 乙亥 yĭ-hài     Wood Pig (yin)           year 12 of the cycle
 1938 戊寅 wù-yín     Earth Tiger (yang)       year 15 of the cycle
 1931 辛未 xīn-wèi    Metal Goat (yin)         year 8 of the cycle
 1961 辛丑 xīn-chŏu   Metal Ox (yin)           year 38 of the cycle
 1963 癸卯 gŭi-măo    Water Rabbit (yin)       year 40 of the cycle
 1991 辛未 xīn-wèi    Metal Goat (yin)         year 8 of the cycle
 1993 癸酉 gŭi-yŏu    Water Rooster (yin)      year 10 of the cycle
 1996 丙子 bĭng-zĭ    Fire Rat (yang)          year 13 of the cycle
 2001 辛巳 xīn-sì     Metal Snake (yin)        year 18 of the cycle
© Copyright Bruce M. Axtens, 2018

Thursday, March 15, 2018

[PHP] Include a data structure once

Today's job at work was to get some data into GravityForms, a forms tool for WordPress.

So one page has a postcode entry, and the next page has some hidden postcode-specific fields that are used to calculate values later in the form-set, in this case freight costs on goods delivered by
TNT (no relation to the song by AC/DC).

The documentation for GravityForms suggests putting code into functions.php in the active theme. I'm a little wary of doing that given that changes there can work or not work in a rather catastrophic way.

Nevertheless, I ended up coding against the gform_field_input hook
add_filter('gform_field_input', 'update_hidden', 10, 5);
function update_hidden($input, $field, $value, $lead_id, $form_id)
{
}
So then the was the issue of how to include the postcode-to-charges array (PCA) (stored in an external php file) once rather than each time gform_field_input fired, which is once per control. With the PCA being just shy of a megabyte in length, I wasn't particularly interested in having it load repeatedly.

The PCA looks like this
<?php
return array(
 '0221' => array(
  'BasicChrg' => 9.982, 
  'KgChrg' => 0.5405, 
  'MinChrg' => 15.3755, 
  'RemotAreaChrg' => 0, 
  'ResidChrg' => 5, 
  '0to15Chrg' => 0, 
  '15to199Chrg' => 10, 
  '200to299Chrg' => 30, 
  '300to399Chrg' => 40, 
  '400to499Chrg' => 150, 
  '500to599Chrg' => 250, 
  '600plusChrg' => 300, 
  'FuelSurchrg' => 0.07)
  ...
);
StackOverflow did offer a suggestion on how to deal with this but I had no joy with it. So I went with using include_once. That, however, also had problems. According to the documentation, include_once returns a boolean true when it gets called the second time for the same file. So one must use a temporary variable to hold the result rather than committing it immediately to your PCA variable.

So the code I have ended up with is (some omitted for brevity's sake):
function update_hidden($input, $field, $value, $lead_id, $form_id)
{
 global $TNTFreightPrices, $PostCode;

 $path = $_SERVER['DOCUMENT_ROOT'] . '/wp-content/uploads/tntfreightprices/TNTFreightPrices.php';
 $tmp = include_once $path;
 if (gettype($tmp) == "array") {
  $TNTFreightPrices = $tmp;
  $PostCode = rgpost('input_52');
 }

 if ($form_id == 8) {
  $BasicChrg = $TNTFreightPrices[$PostCode]['BasicChrg'];
  
  ...

  $fid = $field['id'];
  
  if ($fid == 53) {
   $input = "<input id='input_8_53' class='gform_hidden' name='input_53' aria-invalid='false' value='$BasicChrg' type='hidden'>";
  }
  ...
 }
}
It remains to be seen whether I stay with $TNTFreightPrices and $PostCode in global space as that's a carryover from other experiments.

It was part fun and part hairloss but at least we're closer to a solution. Probably there are better ways. WooCommerce?


© Copyright Bruce M. Axtens., 2018

Monday, February 12, 2018

[dotnet] core, standard and framework

Riiiiiight, now I get it ... maybe.

Check the original posting on StackOverflow for the full description.

© Copyright Bruce M. Axtens, 2018