We begin our journey into data structures by taking a deep dive into primitives while Allen makes Michael blush and Joe crashes his browser.
Reading these show notes via your podcast player? Head to https://www.codingblocks.net/episode94 to view this show’s full show notes and participate in the discussion.
- Coder.com – Sign up to use Visual Studio Code in the browser and server power your IDE with access of up to 96 cores.
- Datadog.com/codingblocks – Sign up today for a free 14 day trial and get a free Datadog t-shirt after creating your first dashboard.
- Special thanks to everyone that took a moment to leave us a review. It means a lot to us.
- iTunes: Praslisa, Techanda, Raj Agz, hartzell.jkh
- Stitcher: Scott_V, HotGarbage, btsui, Michael Tippett, GreenPlane, MPDaves, JoesTheBest, stephencweiss, Zhuul303
About data structures
- Data structures and algorithms are the heart of computer science.
- Data structures refer specifically to how we store and interact with data in our programs.
- The data structures you choose can have a huge impact on resources.
- Different languages often have built-in support for data structures.
- Some data structures cannot truly be built in some languages:
Examples of Some Standard Data Structures
- Basic: Arrays, Linked Lists.
- More advanced: Trees, Tries, Hash tables, Heaps.
- Each has their own strengths and weaknesses.
- Primitives are the most basic types that all other types are built on.
- Primitives refer to one of 2 things:
- Basic types – sorta like elements on the periodic table, they can’t be broken down into anything smaller.
- Built in types – most languages also include composite types as well, mainly for convenience. In C#, String is built-in, but not considered a primitive, as well as DateTime, Enums, too.
- Wikipedia lists the basic primitive types as…
- Fixed-point numbers
- A note about rounding in C# – By default, Math.Round() rounds to nearest even number if halfway between two numbers.
- Decimal has more storage, but it’s range is less than that of a double…
A tangent about floating-point numbers
Why do we need floating-point types?
- We know how to represent integers in binary form. For example, we can represent 10 in binary as 00001010. Or 3 would be 00000011 in binary.
- So if 1 in binary is 00000001 and 3 is 00000011, how would we represent 1/3 in binary?
- Even on paper, we actually can’t do it. So to get around it, we use symbols. So we’ll say 1/3 = 0.3333 with a line over the last 3 representing that it goes on forever.
- So, what about 1/3 + 1/3?
- On paper, we might write this as 0.6667 and consider this approximation good enough.
Why is a float called a float?
- Because the placement of the decimal point can vary from one number to the next. This is based on how it is stored.
- Floating-point number storage is made up of three parts:
- the sign,
- the mantissa, aka coefficient of significand,
- and the exponent.
- Storage is made up of 3 parts:
- For a 32-bit float: 1 bit for the sign, 23 bits of mantissa, and 8 bits of exponent.
- For a 64-bit float: 1 bit for the sign, 52 bits of mantissa, and 11 bits of exponent.
Fixed-point numbers, the alternative to float-point
- Using the explanation above for floating-point numbers, consider the alternative to a floating-point number, i.e. a fixed-point number.
- For a fixed-point number, the position of the decimal place is a known constant, such as the money and smallmoney types in SQL Server which have, at most, 4 decimal places.
Floating-point numbers in .NET
- There are two types of real numbers in .NET: binary floating-point numbers and decimal floating-point numbers.
- For binary floating-point numbers, there is float and double (or System.Single and System.Double).
- Binary floating-point numbers are base 2 in regards to the formula we use to calculate what number the structure is representing.
- For decimal floating-point numbers, there is the decimal type.
- Decimal floating-point numbers are similar to binary floating-point numbers, except they are base 10 instead of base 2 in regards to the formula we use to calculate what number the structure is representing.
- Floating-point arithmetic is sometimes considered bad, because the results aren’t what we might expect.
- However, floating-point arithmetic can be fine depending on how you’re using it.
- If your variable represents money, it’s best to stick with precise numbers like the decimal type.
- However, calculations using decimals is an order of magnitude slower than floating-point types (and also use at least twice the memory).
- But if what your variable represents is something in the real world, say the measurement of a piece of wood, a float or double might be good enough, since the likelihood of the measure is already inexact by its nature.
Precision vs Accuracy
- Precision refers to the amount of information used to represent a number.
- Accuracy indicates how close a value is to its true value.
- If we represent pi as an approximate value using the number 3, it is only accurate to one decimal place. Regardless of what the precision of the variable is.
Back to primitives
- First thought here, isn’t everything in C#/Python/Ruby an Object?
- Answers, is … not quite
- Just about everything in C# is derived from System.Object, including most of the primitives
- Every type in C# directly or indirectly derives from the object class type, and object is the ultimate base class of all types. Values of reference types are treated as objects simply by viewing the values as type object.
- That’s why you can do things like 12.ToString().
- Interfaces and pointers are not children of System.Object.
- So why aren’t there just 3 primitives? Object and Int/UIntPtr?
- Well, C# types have a property called “IsPrimitive” so you can do typeof(MyClass).isPrimitive to see what C# has to say about it.
Resources We Like
- The Imposter’s Handbook (bigmachine.io)
- List of data structures (Wikipedia)
- Decimal vs Double and Other Tips About Number Types in .NET (Exception Not Found)
- Why do you need float/double? (Stack Overflow)
- Binary floating point and .NET (C# in Depth)
- Decimal floating point in .NET (C# in Depth)
- Floating Point in .NET part 1: Concepts and Formats (Extreme Optimization)
- IEEE Standard for Floating-Point Arithmetic (IEEE 754) (Wikipedia)
- Difference between decimal, float and double in .NET? (Stack Overflow)
- String caching. Memory optimization and re-use (Stack Overflow) (aka string interning)
- Metaprogramming in ES6: Symbols and why they’re awesome (Keith Cirkel)
Tip of the Week
Got a tip you want to share? Submit your tip at https://www.codingblocks.net/tips.
- Theme your Visual Studio Code to your liking (code.visualstudio.com)
- Thanks to Brianmm02!
- Like Git, but not a cmdline fan? Check out GitKraken (gitkraken.com)
- Thank you Lee Oades!
- Set up multiple users within Chrome to ease your testing burden as different users.
- Learn how to use R and Python within SQL Server with SQL Server Machine Learning Services (microsoft.github.io)