diff options
-rw-r--r-- | asymptotic-notation.html.markdown | 128 | ||||
-rw-r--r-- | c.html.markdown | 2 | ||||
-rw-r--r-- | csharp.html.markdown | 123 | ||||
-rw-r--r-- | elixir.html.markdown | 5 | ||||
-rw-r--r-- | objective-c.html.markdown | 23 | ||||
-rw-r--r-- | ru-ru/json-ru.html.markdown | 61 |
6 files changed, 306 insertions, 36 deletions
diff --git a/asymptotic-notation.html.markdown b/asymptotic-notation.html.markdown new file mode 100644 index 00000000..c8187526 --- /dev/null +++ b/asymptotic-notation.html.markdown @@ -0,0 +1,128 @@ +--- +category: Algorithms & Data Structures +contributors: + - ["Jake Prather", "http://github.com/JakeHP"] +--- + +# Asymptotic Notations + +## What are they? + +Asymptotic Notations are languages that allow us to analyze an algorithm's running time by +identifying its behavior as the input size for the algorithm increases. This is also known as +an algorithm's growth rate. Does the algorithm suddenly become incredibly slow when the input +size grows? Does it mostly maintain its quick run time as the input size increases? +Asymptotic Notation gives us the ability to answer these questions. + +## Are there alternatives to answering these questions? + +One way would be to count the number of primitive operations at different input sizes. +Though this is a valid solution, the amount of work this takes for even simple algorithms +does not justify its use. + +Another way is to physically measure the amount of time an algorithm takes to complete +given different input sizes. However, the accuracy and relativity (times obtained would +only be relative to the machine they were computed on) of this method is bound to +environmental variables such as computer hardware specifications, processing power, etc. + +## Types of Asymptotic Notation + +In the first section of this doc we described how an Asymptotic Notation identifies the +behavior of an algorithm as the input size changes. Let us imagine an algorithm as a function +f, n as the input size, and f(n) being the running time. So for a given algorithm f, with input +size n you get some resultant run time f(n). This results in a graph where the Y axis is the +runtime, X axis is the input size, and plot points are the resultants of the amount of time +for a given input size. + +You can label a function, or algorithm, with an Asymptotic Notation in many different ways. +Some examples are, you can describe an algorithm by its best case, worse case, or equivalent case. +The most common is to analyze an algorithm by its worst case. You typically don't evaluate by best case because those conditions aren't what you're planning for. A very good example of this is sorting algorithms; specifically, adding elements to a tree structure. Best case for most algorithms could be as low as a single operation. However, in most cases, the element you're adding will need to be sorted appropriately through the tree, which could mean examining an entire branch. This is the worst case, and this is what we plan for. + +### Types of functions, limits, and simplification +``` +Logarithmic Function - log n +Linear Function - an + b +Quadratic Function - an^2 + bn + c +Polynomial Function - an^z + . . . + an^2 + a*n^1 + a*n^0, where z is some constant +Exponential Function - a^n, where a is some constant +``` + +These are some basic function growth classifications used in various notations. The list starts at the slowest growing function (logarithmic, fastest execution time) and goes on to the fastest growing (exponential, slowest execution time). Notice that as 'n', or the input, increases in each of those functions, the result clearly increases much quicker in quadratic, polynomial, and exponential, compared to logarithmic and linear. + +One extremely important note is that for the notations about to be discussed you should do your best to use simplest terms. This means to disregard constants, and lower order terms, because as the input size (or n in our f(n) +example) increases to infinity (mathematical limits), the lower order terms and constants are of little +to no importance. That being said, if you have constants that are 2^9001, or some other ridiculous, +unimaginable amount, realize that simplifying will skew your notation accuracy. + +Since we want simplest form, lets modify our table a bit... +``` +Logarithmic - log n +Linear - n +Quadratic - n^2 +Polynomial - n^z, where z is some constant +Exponential - a^n, where a is some constant +``` + +### Big-Oh +Big-Oh, commonly written as O, is an Asymptotic Notation for the worst case, or ceiling of growth +for a given function. Say `f(n)` is your algorithm runtime, and `g(n)` is an arbitrary time complexity +you are trying to relate to your algorithm. `f(n)` is O(g(n)), if for any real constant c (c > 0), +`f(n)` <= `c g(n)` for every input size n (n > 0). + +*Example 1* +``` +f(n) = 3log n + 100 +g(n) = log n +``` + +Is `f(n)` O(g(n))? +Is `3 log n + 100` O(log n)? +Let's look to the definition of Big-Oh. +``` +3log n + 100 <= c * log n +``` +Is there some constant c that satisfies this for all n? +``` +3log n + 100 <= 150 * log n, n > 2 (undefined at n = 1) +``` +Yes! The definition of Big-Oh has been met therefore `f(n)` is O(g(n)). + +*Example 2* +``` +f(n) = 3*n^2 +g(n) = n +``` + +Is `f(n)` O(g(n))? +Is `3 * n^2` O(n)? +Let's look at the definition of Big-Oh. +``` +3 * n^2 <= c * n +``` +Is there some constant c that satisfies this for all n? +No, there isn't. `f(n)` is NOT O(g(n)). + +### Big-Omega +Big-Omega, commonly written as Ω, is an Asymptotic Notation for the best case, or a floor growth rate +for a given function. + +`f(n)` is Ω(g(n)), if for any real constant c (c > 0), `f(n)` is >= `c g(n)` for every input size n (n > 0). + +Feel free to head over to additional resources for examples on this. Big-Oh is the primary notation used +for general algorithm time complexity. + +### Ending Notes +It's hard to keep this kind of topic short, and you should definitely go through the books and online +resources listed. They go into much greater depth with definitions and examples. +More where x='Algorithms & Data Structures' is on its way; we'll have a doc up on analyzing actual +code examples soon. + +## Books + +* [Algorithms](http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X) +* [Algorithm Design](http://www.amazon.com/Algorithm-Design-Foundations-Analysis-Internet/dp/0471383651) + +## Online Resources + +* [MIT](http://web.mit.edu/16.070/www/lecture/big_o.pdf) +* [KhanAcademy](https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation) diff --git a/c.html.markdown b/c.html.markdown index 7670824a..1696d28f 100644 --- a/c.html.markdown +++ b/c.html.markdown @@ -85,7 +85,7 @@ int main() { // doubles are usually 64-bit floating-point numbers double x_double = 0.0; // real numbers without any suffix are doubles - // integer types may be unsigned (only positive) + // integer types may be unsigned (greater than or equal to zero) unsigned short ux_short; unsigned int ux_int; unsigned long long ux_long_long; diff --git a/csharp.html.markdown b/csharp.html.markdown index 47dd9683..479b7f01 100644 --- a/csharp.html.markdown +++ b/csharp.html.markdown @@ -5,6 +5,7 @@ contributors: - ["Max Yankov", "https://github.com/golergka"] - ["Melvyn Laïly", "http://x2a.yt"] - ["Shaun McCarthy", "http://www.shaunmccarthy.com"] + - ["Wouter Van Schandevijl", "http://github.com/laoujin"] filename: LearnCSharp.cs --- @@ -18,22 +19,29 @@ C# is an elegant and type-safe object-oriented language that enables developers Multi-line comments look like this */ /// <summary> -/// This is an XML documentation comment +/// This is an XML documentation comment which can be used to generate external +/// documentation or provide context help within an IDE /// </summary> +//public void MethodOrClassOrOtherWithParsableHelp() {} -// Specify namespaces application will be using +// Specify the namespaces this source code will be using +// The namespaces below are all part of the standard .NET Framework Class Libary using System; using System.Collections.Generic; -using System.Data.Entity; using System.Dynamic; using System.Linq; -using System.Linq.Expressions; using System.Net; using System.Threading.Tasks; using System.IO; -// defines scope to organize code into "packages" -namespace Learning +// But this one is not: +using System.Data.Entity; +// In order to be able to use it, you need to add a dll reference +// This can be done with the NuGet package manager: `Install-Package EntityFramework` + +// Namespaces define scope to organize code into "packages" or "modules" +// Using this code from another source file: using Learning.CSharp; +namespace Learning.CSharp { // Each .cs file should at least contain a class with the same name as the file // you're allowed to do otherwise, but shouldn't for sanity. @@ -125,7 +133,7 @@ on a new line! ""Wow!"", the masses cried"; // Use const or read-only to make a variable immutable // const values are calculated at compile time - const int HOURS_I_WORK_PER_WEEK = 9001; + const int HoursWorkPerWeek = 9001; /////////////////////////////////////////////////// // Data Structures @@ -242,8 +250,15 @@ on a new line! ""Wow!"", the masses cried"; int fooDoWhile = 0; do { - //Iterated 100 times, fooDoWhile 0->99 + // Start iteration 100 times, fooDoWhile 0->99 + if (false) + continue; // skip the current iteration + fooDoWhile++; + + if (fooDoWhile == 50) + break; // breaks from the loop completely + } while (fooDoWhile < 100); //for loop structure => for(<start_statement>; <conditional>; <step>) @@ -301,7 +316,7 @@ on a new line! ""Wow!"", the masses cried"; // Converting data // Convert String To Integer - // this will throw an Exception on failure + // this will throw a FormatException on failure int.Parse("123");//returns an integer version of "123" // try parse will default to type default on failure @@ -315,6 +330,11 @@ on a new line! ""Wow!"", the masses cried"; Convert.ToString(123); // or tryInt.ToString(); + + // Casting + // Cast decimal 15 to a int + // and then implicitly cast to long + long x = (int) 15M; } /////////////////////////////////////// @@ -367,8 +387,12 @@ on a new line! ""Wow!"", the masses cried"; } // Methods can have the same name, as long as the signature is unique - public static void MethodSignatures(string maxCount) + // A method that differs only in return type is not unique + public static void MethodSignatures( + ref int maxCount, // Pass by reference + out int count) { + count = 15; // out param must be assigned before control leaves the method } // GENERICS @@ -400,6 +424,10 @@ on a new line! ""Wow!"", the masses cried"; MethodSignatures(3, 1, 3, "Some", "Extra", "Strings"); MethodSignatures(3, another: 3); // explicity set a parameter, skipping optional ones + // BY REF AND OUT PARAMETERS + int maxCount = 0, count; // ref params must have value + MethodSignatures(ref maxCount, out count); + // EXTENSION METHODS int i = 3; i.Print(); // Defined below @@ -435,6 +463,31 @@ on a new line! ""Wow!"", the masses cried"; Func<int, int> square = (x) => x * x; // Last T item is the return value Console.WriteLine(square(3)); // 9 + // ERROR HANDLING - coping with an uncertain world + try + { + var funBike = PennyFarthing.CreateWithGears(6); + + // will no longer execute because CreateWithGears throws an exception + string some = ""; + if (true) some = null; + some.ToLower(); // throws a NullReferenceException + } + catch (NotSupportedException) + { + Console.WriteLine("Not so much fun now!"); + } + catch (Exception ex) // catch all other exceptions + { + throw new ApplicationException("It hit the fan", ex); + // throw; // A rethrow that preserves the callstack + } + // catch { } // catch-all without capturing the Exception + finally + { + // executes after try or catch + } + // DISPOSABLE RESOURCES MANAGEMENT - let you handle unmanaged resources easily. // Most of objects that access unmanaged resources (file handle, device contexts, etc.) // implement the IDisposable interface. The using statement takes care of @@ -595,10 +648,26 @@ on a new line! ""Wow!"", the masses cried"; public BikeBrand Brand; // After declaring an enum type, we can declare the field of this type + // Decorate an enum with the FlagsAttribute to indicate that multiple values can be switched on + [Flags] // Any class derived from Attribute can be used to decorate types, methods, parameters etc + public enum BikeAccessories + { + None = 0, + Bell = 1, + MudGuards = 2, // need to set the values manually! + Racks = 4, + Lights = 8, + FullPackage = Bell | MudGuards | Racks | Lights + } + + // Usage: aBike.Accessories.HasFlag(Bicycle.BikeAccessories.Bell) + // Before .NET 4: (aBike.Accessories & Bicycle.BikeAccessories.Bell) == Bicycle.BikeAccessories.Bell + public BikeAccessories Accessories { get; set; } + // Static members belong to the type itself rather then specific object. // You can access them without a reference to any object: // Console.WriteLine("Bicycles created: " + Bicycle.bicyclesCreated); - static public int BicyclesCreated = 0; + public static int BicyclesCreated { get; set; } // readonly values are set at run time // they can only be assigned upon declaration or in a constructor @@ -682,7 +751,7 @@ on a new line! ""Wow!"", the masses cried"; // All though this is not entirely useful in this example, you // could do bicycle[0] which yields "chris" to get the first passenger or // bicycle[1] = "lisa" to set the passenger. (of this apparent quattrocycle) - private string[] passengers = { "chris", "phil", "darren", "regina" } + private string[] passengers = { "chris", "phil", "darren", "regina" }; public string this[int i] { @@ -737,10 +806,17 @@ on a new line! ""Wow!"", the masses cried"; } set { - throw new ArgumentException("You can't change gears on a PennyFarthing"); + throw new InvalidOperationException("You can't change gears on a PennyFarthing"); } } + public static PennyFarthing CreateWithGears(int gears) + { + var penny = new PennyFarthing(1, 1); + penny.Gear = gears; // Oops, can't do this! + return penny; + } + public override string Info() { string result = "PennyFarthing bicycle "; @@ -784,7 +860,7 @@ on a new line! ""Wow!"", the masses cried"; /// EntityFramework Code First is awesome (similar to Ruby's ActiveRecord, but bidirectional) /// http://msdn.microsoft.com/en-us/data/jj193542.aspx /// </summary> - public class BikeRepository : DbSet + public class BikeRepository : DbContext { public BikeRepository() : base() @@ -798,13 +874,15 @@ on a new line! ""Wow!"", the masses cried"; ## Topics Not Covered - * Flags * Attributes - * Static properties - * Exceptions, Abstraction - * ASP.NET (Web Forms/MVC/WebMatrix) - * Winforms - * Windows Presentation Foundation (WPF) + * async/await, yield, pragma directives + * Web Development + * ASP.NET MVC & WebApi (new) + * ASP.NET Web Forms (old) + * WebMatrix (tool) + * Desktop Development + * Windows Presentation Foundation (WPF) (new) + * Winforms (old) ## Further Reading @@ -817,7 +895,4 @@ on a new line! ""Wow!"", the masses cried"; * [ASP.NET Web Matrix Tutorials](http://www.asp.net/web-pages/tutorials) * [ASP.NET Web Forms Tutorials](http://www.asp.net/web-forms/tutorials) * [Windows Forms Programming in C#](http://www.amazon.com/Windows-Forms-Programming-Chris-Sells/dp/0321116208) - - - -[C# Coding Conventions](http://msdn.microsoft.com/en-us/library/vstudio/ff926074.aspx) + * [C# Coding Conventions](http://msdn.microsoft.com/en-us/library/vstudio/ff926074.aspx) diff --git a/elixir.html.markdown b/elixir.html.markdown index 0a20e3df..fb5f183a 100644 --- a/elixir.html.markdown +++ b/elixir.html.markdown @@ -91,6 +91,11 @@ string. <<1,2,3>> <> <<4,5>> #=> <<1,2,3,4,5>> "hello " <> "world" #=> "hello world" +# Ranges are represented as `start..end` (both inclusive) +1..10 #=> 1..10 +lower..upper = 1..10 # Can use pattern matching on ranges as well +[lower, upper] #=> [1, 10] + ## --------------------------- ## -- Operators ## --------------------------- diff --git a/objective-c.html.markdown b/objective-c.html.markdown index caad49a5..56640a87 100644 --- a/objective-c.html.markdown +++ b/objective-c.html.markdown @@ -55,7 +55,7 @@ int main (int argc, const char * argv[]) id myObject2 = nil; // Weak typing // %@ is an object // 'description' is a convention to display the value of the Objects - NSLog(@"%@ and %@", myObject1, [myObject2 description]); // Print "(null) and (null)" + NSLog(@"%@ and %@", myObject1, [myObject2 description]); // prints => "(null) and (null)" // String NSString *worldString = @"World"; @@ -128,9 +128,10 @@ int main (int argc, const char * argv[]) // May contain different data types, but must be an Objective-C object NSArray *anArray = @[@1, @2, @3, @4]; NSNumber *thirdNumber = anArray[2]; - NSLog(@"Third number = %@", thirdNumber); // Print "Third number = 3" - // NSMutableArray is mutable version of NSArray allowing to change items in array - // and extend or shrink array object. Convenient, but not as efficient as NSArray + NSLog(@"Third number = %@", thirdNumber); // prints => "Third number = 3" + // NSMutableArray is a mutable version of NSArray, allowing you to change + // the items in the array and to extend or shrink the array object. + // Convenient, but not as efficient as NSArray. NSMutableArray *mutableArray = [NSMutableArray arrayWithCapacity:2]; [mutableArray addObject:@"Hello"]; [mutableArray addObject:@"World"]; @@ -140,7 +141,7 @@ int main (int argc, const char * argv[]) // Dictionary object NSDictionary *aDictionary = @{ @"key1" : @"value1", @"key2" : @"value2" }; NSObject *valueObject = aDictionary[@"A Key"]; - NSLog(@"Object = %@", valueObject); // Print "Object = (null)" + NSLog(@"Object = %@", valueObject); // prints => "Object = (null)" // NSMutableDictionary also available as a mutable dictionary object NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionaryWithCapacity:2]; [mutableDictionary setObject:@"value1" forKey:@"key1"]; @@ -210,7 +211,7 @@ int main (int argc, const char * argv[]) while (ii < 4) { NSLog(@"%d,", ii++); // ii++ increments ii in-place, after using its value - } // => prints "0," + } // prints => "0," // "1," // "2," // "3," @@ -220,7 +221,7 @@ int main (int argc, const char * argv[]) for (jj=0; jj < 4; jj++) { NSLog(@"%d,", jj); - } // => prints "0," + } // prints => "0," // "1," // "2," // "3," @@ -230,7 +231,7 @@ int main (int argc, const char * argv[]) for (NSNumber *value in values) { NSLog(@"%@,", value); - } // => prints "0," + } // prints => "0," // "1," // "2," // "3," @@ -238,7 +239,7 @@ int main (int argc, const char * argv[]) // Object for loop statement. Can be used with any Objective-C object type for (id item in values) { NSLog(@"%@,", item); - } // => prints "0," + } // prints => "0," // "1," // "2," // "3," @@ -255,7 +256,7 @@ int main (int argc, const char * argv[]) } @finally { NSLog(@"Finally. Time to clean up."); - } // => prints "Exception: File Not Found on System" + } // prints => "Exception: File Not Found on System" // "Finally. Time to clean up." // NSError objects are useful for function arguments to populate on user mistakes. @@ -627,7 +628,7 @@ int main (int argc, const char * argv[]) { @end // Instances of Car now have access to the protocol. Car *carInstance = [[Car alloc] init]; -[[carInstance setEngineOn:NO]; +[carInstance setEngineOn:NO]; [carInstance turnOnEngine]; if ([carInstance engineOn]) { NSLog(@"Car engine is on."); // prints => "Car engine is on." diff --git a/ru-ru/json-ru.html.markdown b/ru-ru/json-ru.html.markdown new file mode 100644 index 00000000..52af3696 --- /dev/null +++ b/ru-ru/json-ru.html.markdown @@ -0,0 +1,61 @@ +--- +language: json +filename: learnjson-ru.json +contributors: + - ["Anna Harren", "https://github.com/iirelu"] + - ["Marco Scannadinari", "https://github.com/marcoms"] +translators: + - ["Dmitry Bessonov", "https://github.com/TheDmitry"] +lang: ru-ru +--- + +JSON - это очень простой формат обмена данными, и это будет самый легкий +курс из когда-либо представленных "Learn X in Y Minutes". + +В чистом виде у JSON нет фактических комментариев, но большинство парсеров примут +комментарии в Си-стиле (//, /\* \*/). Для таких целей, конечно, все правильно +будет на 100% с точки зрения JSON. К счастью, в нашем случае данные скажут сами за себя. + +```json +{ + "ключ": "значение", + + "ключи": "должны всегда заключаться в двойные кавычки", + "числа": 0, + "строки": "Пρивет, миρ. Допускаются все unicode-символы вместе с \"экранированием\".", + "содержит логический тип?": true, + "ничего": null, + + "большое число": 1.2e+100, + + "объекты": { + "комментарий": "Большинство ваших структур будут представлять из себя объекты.", + + "массив": [0, 1, 2, 3, "Массивы могут содержать в себе любой тип.", 5], + + "другой объект": { + "комментарий": "Они могут быть вложенными, и это очень полезно." + } + }, + + "бессмыслие": [ + { + "источники калия": ["бананы"] + }, + [ + [1, 0, 0, 0], + [0, 1, 0, 0], + [0, 0, 1, "нео"], + [0, 0, 0, 1] + ] + ], + + "альтернативный стиль": { + "комментарий": "проверьте это!" + , "позиция запятой": "неважна, хоть и перед значением, все равно правильно" + , "еще один комментарий": "как хорошо" + }, + + "это было недолго": "И вы справились. Теперь вы знаете все о JSON." +} +``` |