-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy paththeres-fast-code-and-theres-fast-code.html
252 lines (220 loc) · 12 KB
/
theres-fast-code-and-theres-fast-code.html
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=Edge"/>
<title>Warren Bates - There's fast code and there's fast code</title>
<meta name="description" content="Warren Bates" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link type="application/rss+xml" rel="alternate" title="Warren Bates" href="/feed.rss" />
<link type="application/atom+xml" rel="alternate" title="Warren Bates" href="/feed.atom" />
<link rel="shortcut icon" href="/favicon.ico" type="image/x-icon">
<link rel="icon" href="/favicon.ico" type="image/x-icon">
<link href="/assets/css/bootstrap.min.css" rel="stylesheet" />
<link href="/assets/css/highlight.css" rel="stylesheet">
<link href="/assets/css/clean-blog.css" rel="stylesheet" />
<link href="/assets/css/master.css" rel="stylesheet" />
<link href="/assets/css/font-awesome.min.css" rel="stylesheet" type="text/css">
<link href='//fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic' rel='stylesheet' type='text/css'>
<link href='//fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800' rel='stylesheet' type='text/css'>
<link href="/assets/css/override.css" rel="stylesheet" />
<meta name="application-name" content="Warren Bates" />
<meta name="msapplication-tooltip" content="Warren Bates" />
<meta name="msapplication-starturl" content="/" />
<meta property="og:title" content="Warren Bates - There's fast code and there's fast code" />
<meta property="og:type" content="website" />
<meta property="og:url" content="https://wbates.net/posts/theres-fast-code-and-theres-fast-code" />
<!-- TODO: More social graph meta tags -->
<script src="/assets/js/jquery.min.js"></script>
<script src="/assets/js/bootstrap.min.js"></script>
<script src="/assets/js/highlight.pack.js"></script>
<script src="/assets/js/clean-blog.js"></script>
<script src="/assets/js/d3.v3.min.js"></script>
<script src="/assets/js/trianglify.min.js"></script>
<script src="/assets/js/Please-compressed.js"></script>
<script src="/assets/js/background-check.min.js"></script>
<!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
<!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
<!--[if lt IE 9]>
<script src="/assets/js/html5shiv.js"></script>
<script src="/assets/js/respond.min.js"></script>
<![endif]-->
</head>
<body>
<!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
<div class="container-fluid">
<!-- Brand and toggle get grouped for better mobile display -->
<div class="navbar-header page-scroll">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target="#navbar-collapse">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a class="navbar-brand" href="/">Warren Bates</a>
</div>
<!-- Collect the nav links, forms, and other content for toggling -->
<div class="collapse navbar-collapse" id="navbar-collapse">
<ul class="nav navbar-nav navbar-right">
<li><a href="/posts">Archive</a></li>
<li><a href="/tags">Tags</a></li>
<li><a href="/about">About Me</a></li>
</ul>
</div>
<!-- /.navbar-collapse -->
</div>
<!-- /.container -->
</nav>
<!-- Page Header -->
<header class="intro-header" id="intro-header">
<div class="container">
<div class="row">
<div class="col-md-12">
<div class="post-heading">
<h1>There's fast code and there's fast code</h1>
<div class="meta">
Published on 24 May 2015<br> </div>
<div class="tags">
<a role="button" href="/tags/C%23" class="btn btn-default btn-xs">C#</a>
<a role="button" href="/tags/CSharp" class="btn btn-default btn-xs">CSharp</a>
<a role="button" href="/tags/Math" class="btn btn-default btn-xs">Math</a>
<a role="button" href="/tags/Timing" class="btn btn-default btn-xs">Timing</a>
</div>
</div>
</div>
</div>
</div>
</header>
<!-- Main Content -->
<div class="container">
<div class="row">
<div id="content" class="col-md-12">
<p>I was solving a problem recently and came across a number of different ways of solving it. I decided to test them each out to see which was the quickest. The functions purpose was to return the number of digits in an integer. I've tried four different methods out. Two of them are single line solutions, one uses a bit of looping to solve the problem and the final one... well you'll see.</p>
<h1 id="log-method">Log Method</h1>
<p>Logarithms return the power a number needs to be raised to in order to give that number. For example if our number is 1000. Log to the base 10 will return 3, because 1000 = 10^3. Any number up to 10000 will return a decimal value which rounds down to 3. e.g. log10(9999) = 3.99956568.... so we can use a combination of Math.Floor and Math.Log10 to give us the number of digits required. Our function should look something like this.</p>
<pre><code class="language-csharp">private int IntegerLength_Log(int num)
{
return (int)Math.Floor(Math.Log10(num) + 1);
}
</code></pre>
<p>Note: You need to add 1 to the return of the log value to get the number of digits.</p>
<h1 id="string-method">String method</h1>
<p>This method relies on built in methods of converting the integer to a string and using the length property. This is probably the simplest and most versatile technique (it should handle negatives), but I was also convinced that because of the overhead associated with converting the integer to a string that this would be the least efficient method.</p>
<p>The only code required is</p>
<pre><code class="language-csharp">private int IntegerLength_String(int num)
{
return num.ToString().Length;
}
</code></pre>
<h1 id="looping-method">Looping method</h1>
<p>This method loops, whilst increasing a variable's value by a power of 10 each cycle until that number is larger than the input.</p>
<pre><code class="language-csharp">private int IntegerLength_Loop(int num)
{
int length = 1;
int comparator = 10;
while (num > comparator)
{
comparator *= 10;
length++;
}
return length;
}
</code></pre>
<h1 id="if-statements">if statements</h1>
<p>The final method is easily the lengthiest to write, and also one that as a problem solving mathematical type makes me cringe a little. There's no elegance to this solution, just a bit of brute force and lots of repetitive code. It requires using a series of if statements to check the integers value and return the length when we know what number it is less than. This is effectively the same as the above method but without the loop.</p>
<pre><code class="language-csharp">private int IntegerLength_If(int num)
{
if (num < 10)
{
return 1;
}
else if (num < 100)
{
return 2;
}
else if (num < 1000)
{
return 3;
}
else if (num < 10000)
{
return 4;
}
else if (num < 100000)
{
return 5;
}
else if (num < 1000000)
{
return 6;
}
else if (num < 10000000)
{
return 7;
}
else if (num < 100000000)
{
return 8;
}
else if (num < 1000000000)
{
return 9;
}
else
{
return 10;
}
}
</code></pre>
<p>If using a comparison like this on a BigInteger even more if statements would be required to cover up to the maximum value, but for C#'s int type this has us covered.</p>
<h1 id="timing">Timing</h1>
<p>Each of these functions was then run using a for loop varying the input from 1'000 to 10'000'000 and the number of ticks taken to complete was recorded.</p>
<p>The results are in: String method 2'937'886 ticks, Log Method 1'119'507, the Looping method 642'857 & the If method 437'401. The cringey set of if statements method is nearly 7 times faster than the string conversion method and 2.5 times faster than the log method.</p>
<p>I think if this were for production code I'd probably use the looping method after changing it to handle integers of any type (i.e. BigInteger) and negative values because of the versatility and ease of rewriting should any problems be found, but this had definitely made me rethink some the assumptions I've built up over the years about how quickly code will run in comparison to how many lines of code there are.</p>
</div>
</div>
</div>
<hr>
<!-- Footer -->
<footer>
<div class="container">
<div class="row">
<div class="col-md-12 text-center">
<p class="copyright text-muted">
Copyright © 2018
<br />
<a href="/feed.rss"><i class="fa fa-rss"></i> RSS Feed</a>
|
<a href="/feed.atom"><i class="fa fa-rss"></i> Atom Feed</a>
<br />
<strong><a href="https://wyam.io">Generated by Wyam</a></strong>
</p>
</div>
</div>
</div>
</footer>
<script>hljs.initHighlightingOnLoad();</script>
<script type="text/javascript">
// Header background
var colors = Please.make_color({
colors_returned: 3,
saturation: .6
});
var t = new Trianglify({
x_gradient: colors,
y_gradient: ["#FFFFFF"]
});
var header = document.getElementById("intro-header");
var pattern = t.generate(header.clientWidth, header.clientHeight);
header.setAttribute('style', 'background-image: ' + pattern.dataUrl);
</script>
<script>
BackgroundCheck.init({
targets: '.intro-header,.navbar',
images: '.intro-header'
});
</script>
</body>
</html>