Time: Using It to Compare Resource Use

Time – time a simple command or give resource usage (linux man-pages)

terminal prompt 
1

$ /usr/bin/time -v [program/script]

Example

In this example I’m going to use the time command to check my character indexing script (github).

In brief these script’s first determine the total unique combinations of a given string of characters, and then returns the where the string input would belong in that alphabetical index.

For this case, I’m going to use an alphabetical 10 character string. Which has a total of 3628800 possible combinations (10!).

Dictionary Lookup

The first script solves this problem thru a dictionary lookup. First the unique combinations are generated into an array, then the script searches the array for the input string, once found the index is returned.

Dictionary Lookup Check 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

$ /usr/bin/time -v ruby ranking_dictionary_lookup.rb ABCDEFGHIJ

The input 'ABCDEFGHIJ' is ranked # 1
---------------------------------------
Time elapsed 107858.65 milliseconds, memory used: 1231576KB
---------------------------------------

  Command being timed: "ruby ranking_dictionary_lookup.rb ABCDEFGHIJ"
  User time (seconds): 12.61
  System time (seconds): 0.70
  Percent of CPU this job got: 12%
  Elapsed (wall clock) time (h:mm:ss or m:ss): 1:48.00
  Average shared text size (kbytes): 0
  Average unshared data size (kbytes): 0
  Average stack size (kbytes): 0
  Average total size (kbytes): 0
  Maximum resident set size (kbytes): 1237964
  Average resident set size (kbytes): 0
  Major (requiring I/O) page faults: 0
  Minor (reclaiming a frame) page faults: 380986
  Voluntary context switches: 6345
  Involuntary context switches: 11620
  Swaps: 0
  File system inputs: 0
  File system outputs: 0
  Socket messages sent: 0
  Socket messages received: 0
  Signals delivered: 0
  Page size (bytes): 4096
  Exit status: 0

In this case, 10! combinations generated a whopping 1.23gb array in memory, taking 1 minute and 48 seconds to complete.

Algorithm

For the case of an input string made up of unique characters, the results per character can be determined when the array length is divided by the amount of unique characters (10!/10) = 362880. Knowing the possibilities per character lets the algorithm set the range.

Multiplying the possibilities per character by the alphabetic disorder of the leading character found by looking up the leading character inside an alphabeted list, and using the index as the integer. In this case, 362880 * 0 = 0.

This concept continues in a recursive loop eliminating the the leading character, repeating as such: (9!/9, 8!/8 etc), while summing the iteratively smaller minimum range.

Once the input string is exhausted, the minimum ranges are summed, and added by 1 to convert back to an ordinal number system. This is because the first position of a list or an array is always 0, being first is otherwise referred to as 1.

Algorithm Check 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

$ /usr/bin/time -v ruby ranking.rb ABCDEFGHIJ

The input 'ABCDEFGHIJ' is ranked # 1
---------------------------------------
Time elapsed 6.052 milliseconds, memory used: 124KB
---------------------------------------

  Command being timed: "ruby ranking.rb ABCDEFGHIJ"
  User time (seconds): 0.01
  System time (seconds): 0.02
  Percent of CPU this job got: 95%
  Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.04
  Average shared text size (kbytes): 0
  Average unshared data size (kbytes): 0
  Average stack size (kbytes): 0
  Average total size (kbytes): 0
  Maximum resident set size (kbytes): 6912
  Average resident set size (kbytes): 0
  Major (requiring I/O) page faults: 0
  Minor (reclaiming a frame) page faults: 3845
  Voluntary context switches: 10
  Involuntary context switches: 10
  Swaps: 0
  File system inputs: 0
  File system outputs: 0
  Socket messages sent: 0
  Socket messages received: 0
  Signals delivered: 0
  Page size (bytes): 4096
  Exit status: 0

Meanwhile this algorithm really sped things up. Fourty milliseconds compared to 108 seconds of computation time. While using 6.9megabytes of memory in comparison to 1,237MB.