DEV Community: Adavidoaiei Dumitru-Cornel

Least Frequently Used Cache Implementation

Adavidoaiei Dumitru-Cornel — Fri, 03 Jul 2020 05:01:47 +0000

https://github.com/adavidoaiei/LeastFrequentlyUsedCache

Overview

The idea behind least frequently cache policy is that for each item from cache it keeps a use count which increments each time when the item is accessed, when cache exceed the limit this evicts(removes) the element with minimum use count freeing memory for a new element.

Installation

NuGet package manager:

Install-Package LfuCache -Version 1.0.0

Example Using

ICache<string, string> cache = new LfuCache<string, string>(1000);
cache.Add("name", "Helene");
cache.Add("surname", "Stuart");
var name = cache.Get("name");

Implementation

The LfuCache implements interface ICache.

It's needed a data structure to store elements from cache sorted by use count, the current implementation uses a SortedList where key is use count and Value is LinkedList of elements from cache with the same use count, SortedList sorts LinkedLists by use count using a binary tree.
This data structure allows to run Add/Get operations in O(log n) time.

Performance benchmark

1000.000 add/get operations on implemented Least Frequently Used Cache of size 90.000 using elements from a list with 100.000 takes 466ms.

This cache runs faster than MemoryCache from .NET Framework and consumes less memory than this on the same benchmark.

The Add/Get operations sequence is generated random in an operations array of size OperationsCount, this operations process elements from a list of size EelementsCount using selected cache.

Performance benchmarks have been run with the following library PerformanceDotNet.

Unit Tests Code Coverage

The unit tests are written using MSTest framework and the code coverage report is generated with Azure Pipeline.

How to compile and run Minix 3 operating system under linux

Adavidoaiei Dumitru-Cornel — Mon, 08 Jun 2020 19:20:24 +0000

The Minix operating system was created by Andrew S. Tanenbaum and inspired Linus Torvalds in creation of Linux operating system.

Andrew S. Tanenbaum wrote two reference books in Computer Science Modern Operating Systems and Computer Networks

MINIX 3 is a free, open-source, operating system designed to be highly reliable, flexible, and secure. It is based on a tiny microkernel running in kernel mode with the rest of the operating system running as a number of isolated, protected, processes in user mode. It runs on x86 and ARM CPUs, is compatible with NetBSD, and runs thousands of NetBSD packages.

Install depedencies

Before attempting to cross-compile MINIX, you need a working C toolchain, Git and some additional software on your host platform.

For Debian-based operating systems, run the following command as super-user:

Note: Also on Ubuntu, if you get an error stating that “'/lib/cpp' fails sanity check”, you need to install the GNU C++ compiler:

Note: On FreeBSD and Minix (compiling for ARM on x86, e.g.), if you get a message along the lines of “Skipping image creation: missing tool 'mcopy'”, please install the emulators/mtools package.

Getting the sources

Once the required tools are installed, the next step is to obtain the sources. Run the following commands in a terminal:

NOTE: The releasetools script will generate object files and put them outside the source directory; i.e., if you've cloned to ~/minix/src/ and build from there, things will start showing up in ~/minix/ as an artifact of the build process.

Cross-building for x86

It's time to build MINIX itself. There are some wrapper scripts that will build ready-to-boot images from scratch (i.e. just the minix source tree) for either x86 or ARM. These scripts produce a lot of output and will take a while to complete the first time - a cross-toolchain based on LLVM is built from scratch.

A command line for running the result in a KVM virtual machine is printed at the end of the process.

To install quemu run:

To boot this image on kvm using the bootloader:

A basic implementation of Model-View-Controller pattern in only 20 lines of code based on OOP

Adavidoaiei Dumitru-Cornel — Tue, 21 Apr 2020 13:38:05 +0000

I will present in this article a easy way to separate PHP code from HTML code using Model-View-Controller pattern, almost all PHP MVC frameworks implement this, at the beginning of PHP was common to interpolate PHP code with HTML code, the PHP code runs on server and generate HTML code.

index.php

.htacces redirects all requests to index.php.

What is doing the following request: http://localhost/forecast/index ?
It is searching the class forecast in the controllers folder if exists creates object forecast, after that checks if exists method index and invokes it, this is a basic implementation of routing in a common MVC frameworks.
Root of web application has the following structure:
-folder controllers
-folder models
-foder views
-file .htaccess
-file index.php

/controllers/forecast.php

/views/forecast.html

/models/money_per_month.php

The complete code could you find on GitHub: https://github.com/adavidoaiei/Model-View-Controller-Pattern

Fundamental Data Structures and Algorithms in C#

Adavidoaiei Dumitru-Cornel — Fri, 17 Apr 2020 11:54:50 +0000

Stack
Queue
Linked List
Hashtable
Binary Search
Binary Search Tree
Graphs
Sorting Algorithms

The importance of the algorithms complexity is given by the fact that it tells us if the code is scaling. Most fundamental data structures and algorithms are already implemented in the .NET Framework, it is important to know how these data structures work and what time, memory complexity they have for the basic operations: accessing element, searching element, deleting element, adding element.

To get an idea of what a good complexity means and a less good one we have the following chart:

In the .NET Framework we have implemented the following data structures: array, stack, queue, linked list and algorithms: binary search, the rest which we do not find in the .NET Framework can be found in NuGet packages or on GitHub. Array is one of the most used and well-known data structures and I will not go into detail with the operating principle.

Stack

Stack is a data structure implemented in the .NET Framework in two ways, simple stack in System.Collections namespace, and stack as generic data structure in System.Collections.Generic namespace, the principle of stack structure operation is LIFO (last in first out), the last element entered first out.

Example of using simple stack from the namespace System.Collections:



using System;
using System.Collections;
public class SamplesStack  {

   public static void Main()  {

      // Creates and initializes a new Stack.
      Stack myStack = new Stack();
      myStack.Push("Hello");
      myStack.Push("World");
      myStack.Push("!");

      // Displays the properties and values of the Stack.
      Console.WriteLine( "myStack" );
      Console.WriteLine( "\tCount:    {0}", myStack.Count );
      Console.Write( "\tValues:" );
      PrintValues( myStack );
   }

   public static void PrintValues( IEnumerable myCollection )  {
      foreach ( Object obj in myCollection )
         Console.Write( "    {0}", obj );
      Console.WriteLine();
   }
}


/*
This code produces the following output.
myStack
    Count:    3
    Values:    !    World    Hello
*/

Example of using generic stack from the namespace System.Collections.Generic:



using System;
using System.Collections.Generic;

class Example
{
    public static void Main()
    {
        Stack<string> numbers = new Stack<string>();
        numbers.Push("one");
        numbers.Push("two");
        numbers.Push("three");
        numbers.Push("four");
        numbers.Push("five");

        // A stack can be enumerated without disturbing its contents.
        foreach( string number in numbers )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nPopping '{0}'", numbers.Pop());
        Console.WriteLine("Peek at next item to destack: {0}",
            numbers.Peek());
        Console.WriteLine("Popping '{0}'", numbers.Pop());

        // Create a copy of the stack, using the ToArray method and the
        // constructor that accepts an IEnumerable<T>.
        Stack<string> stack2 = new Stack<string>(numbers.ToArray());

        Console.WriteLine("\nContents of the first copy:");
        foreach( string number in stack2 )
        {
            Console.WriteLine(number);
        }

        // Create an array twice the size of the stack and copy the
        // elements of the stack, starting at the middle of the
        // array.
        string[] array2 = new string[numbers.Count * 2];
        numbers.CopyTo(array2, numbers.Count);

        // Create a second stack, using the constructor that accepts an
        // IEnumerable(Of T).
        Stack<string> stack3 = new Stack<string>(array2);

        Console.WriteLine("\nContents of the second copy, with duplicates and nulls:");
        foreach( string number in stack3 )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nstack2.Contains(\"four\") = {0}",
            stack2.Contains("four"));

        Console.WriteLine("\nstack2.Clear()");
        stack2.Clear();
        Console.WriteLine("\nstack2.Count = {0}", stack2.Count);
    }
}

/* This code example produces the following output:
five
four
three
two
one
Popping 'five'
Peek at next item to destack: four
Popping 'four'
Contents of the first copy:
one
two
three
Contents of the second copy, with duplicates and nulls:
one
two
three
stack2.Contains("four") = False
stack2.Clear()
stack2.Count = 0
 */

Stack applications:

undo / redo functionality
word reversal
stack back/forward on browsers
backtracking algorithms
bracket verification

Queue

Queue is a data structure implemented in the .NET Framework in two ways, the simple queue in System.Collections namespace, and the queue as the generic data structure in System.Collections.Generic namespace, the working principle of queue structures is FIFO (first in first out), the first element entered first out.

Example of using the simple queue from the namespace System.Collections:



 using System;
 using System.Collections;
 public class SamplesQueue  {

    public static void Main()  {

       // Creates and initializes a new Queue.
       Queue myQ = new Queue();
       myQ.Enqueue("Hello");
       myQ.Enqueue("World");
       myQ.Enqueue("!");

       // Displays the properties and values of the Queue.
       Console.WriteLine( "myQ" );
       Console.WriteLine( "\tCount:    {0}", myQ.Count );
       Console.Write( "\tValues:" );
       PrintValues( myQ );
    }

    public static void PrintValues( IEnumerable myCollection )  {
       foreach ( Object obj in myCollection )
          Console.Write( "    {0}", obj );
       Console.WriteLine();
    }
 }
 /*
 This code produces the following output.
 myQ
     Count:    3
     Values:    Hello    World    !
*/

Example of using the generic queue from the namespace System.Collections.Generic:



using System;
using System.Collections.Generic;

class Example
{
    public static void Main()
    {
        Queue<string> numbers = new Queue<string>();
        numbers.Enqueue("one");
        numbers.Enqueue("two");
        numbers.Enqueue("three");
        numbers.Enqueue("four");
        numbers.Enqueue("five");

        // A queue can be enumerated without disturbing its contents.
        foreach( string number in numbers )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nDequeuing '{0}'", numbers.Dequeue());
        Console.WriteLine("Peek at next item to dequeue: {0}",
            numbers.Peek());
        Console.WriteLine("Dequeuing '{0}'", numbers.Dequeue());

        // Create a copy of the queue, using the ToArray method and the
        // constructor that accepts an IEnumerable<T>.
        Queue<string> queueCopy = new Queue<string>(numbers.ToArray());

        Console.WriteLine("\nContents of the first copy:");
        foreach( string number in queueCopy )
        {
            Console.WriteLine(number);
        }

        // Create an array twice the size of the queue and copy the
        // elements of the queue, starting at the middle of the
        // array.
        string[] array2 = new string[numbers.Count * 2];
        numbers.CopyTo(array2, numbers.Count);

        // Create a second queue, using the constructor that accepts an
        // IEnumerable(Of T).
        Queue<string> queueCopy2 = new Queue<string>(array2);

        Console.WriteLine("\nContents of the second copy, with duplicates and nulls:");
        foreach( string number in queueCopy2 )
        {
            Console.WriteLine(number);
        }

        Console.WriteLine("\nqueueCopy.Contains(\"four\") = {0}",
            queueCopy.Contains("four"));

        Console.WriteLine("\nqueueCopy.Clear()");
        queueCopy.Clear();
        Console.WriteLine("\nqueueCopy.Count = {0}", queueCopy.Count);
    }
}

/* This code example produces the following output:
one
two
three
four
five
Dequeuing 'one'
Peek at next item to dequeue: two
Dequeuing 'two'
Contents of the copy:
three
four
five
Contents of the second copy, with duplicates and nulls:
three
four
five
queueCopy.Contains("four") = True
queueCopy.Clear()
queueCopy.Count = 0
 */

Real life example of queue:
The system from the point of sale of a restaurant.

Linked List

Linked List is a data structure implemented in the .NET Framework as a generic data structure in System.Collections.Generic namespace, the principle of functioning of the linked list structures is that each node in the list has a reference to the next node, except the tail of the list, which has no reference to the next node.

An example of search in linked list of the third item starting from the end:

Example of using the generic linked list from namespace System.Collections.Generic:



using System;
using System.Text;
using System.Collections.Generic;

public class Example
{
    public static void Main()
    {
        // Create the link list.
        string[] words =
            { "the", "fox", "jumps", "over", "the", "dog" };
        LinkedList<string> sentence = new LinkedList<string>(words);
        Display(sentence, "The linked list values:");
        Console.WriteLine("sentence.Contains(\"jumps\") = {0}",
            sentence.Contains("jumps"));

        // Add the word 'today' to the beginning of the linked list.
        sentence.AddFirst("today");
        Display(sentence, "Test 1: Add 'today' to beginning of the list:");

        // Move the first node to be the last node.
        LinkedListNode<string> mark1 = sentence.First;
        sentence.RemoveFirst();
        sentence.AddLast(mark1);
        Display(sentence, "Test 2: Move first node to be last node:");

        // Change the last node to 'yesterday'.
        sentence.RemoveLast();
        sentence.AddLast("yesterday");
        Display(sentence, "Test 3: Change the last node to 'yesterday':");

        // Move the last node to be the first node.
        mark1 = sentence.Last;
        sentence.RemoveLast();
        sentence.AddFirst(mark1);
        Display(sentence, "Test 4: Move last node to be first node:");

        // Indicate the last occurence of 'the'.
        sentence.RemoveFirst();
        LinkedListNode<string> current = sentence.FindLast("the");
        IndicateNode(current, "Test 5: Indicate last occurence of 'the':");

        // Add 'lazy' and 'old' after 'the' (the LinkedListNode named current).
        sentence.AddAfter(current, "old");
        sentence.AddAfter(current, "lazy");
        IndicateNode(current, "Test 6: Add 'lazy' and 'old' after 'the':");

        // Indicate 'fox' node.
        current = sentence.Find("fox");
        IndicateNode(current, "Test 7: Indicate the 'fox' node:");

        // Add 'quick' and 'brown' before 'fox':
        sentence.AddBefore(current, "quick");
        sentence.AddBefore(current, "brown");
        IndicateNode(current, "Test 8: Add 'quick' and 'brown' before 'fox':");

        // Keep a reference to the current node, 'fox',
        // and to the previous node in the list. Indicate the 'dog' node.
        mark1 = current;
        LinkedListNode<string> mark2 = current.Previous;
        current = sentence.Find("dog");
        IndicateNode(current, "Test 9: Indicate the 'dog' node:");

        // The AddBefore method throws an InvalidOperationException
        // if you try to add a node that already belongs to a list.
        Console.WriteLine("Test 10: Throw exception by adding node (fox) already in the list:");
        try
        {
            sentence.AddBefore(current, mark1);
        }
        catch (InvalidOperationException ex)
        {
            Console.WriteLine("Exception message: {0}", ex.Message);
        }
        Console.WriteLine();

        // Remove the node referred to by mark1, and then add it
        // before the node referred to by current.
        // Indicate the node referred to by current.
        sentence.Remove(mark1);
        sentence.AddBefore(current, mark1);
        IndicateNode(current, "Test 11: Move a referenced node (fox) before the current node (dog):");

        // Remove the node referred to by current.
        sentence.Remove(current);
        IndicateNode(current, "Test 12: Remove current node (dog) and attempt to indicate it:");

        // Add the node after the node referred to by mark2.
        sentence.AddAfter(mark2, current);
        IndicateNode(current, "Test 13: Add node removed in test 11 after a referenced node (brown):");

        // The Remove method finds and removes the
        // first node that that has the specified value.
        sentence.Remove("old");
        Display(sentence, "Test 14: Remove node that has the value 'old':");

        // When the linked list is cast to ICollection(Of String),
        // the Add method adds a node to the end of the list.
        sentence.RemoveLast();
        ICollection<string> icoll = sentence;
        icoll.Add("rhinoceros");
        Display(sentence, "Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':");

        Console.WriteLine("Test 16: Copy the list to an array:");
        // Create an array with the same number of
        // elements as the linked list.
        string[] sArray = new string[sentence.Count];
        sentence.CopyTo(sArray, 0);

        foreach (string s in sArray)
        {
            Console.WriteLine(s);
        }

        // Release all the nodes.
        sentence.Clear();

        Console.WriteLine();
        Console.WriteLine("Test 17: Clear linked list. Contains 'jumps' = {0}",
            sentence.Contains("jumps"));

        Console.ReadLine();
    }

    private static void Display(LinkedList<string> words, string test)
    {
        Console.WriteLine(test);
        foreach (string word in words)
        {
            Console.Write(word + " ");
        }
        Console.WriteLine();
        Console.WriteLine();
    }

    private static void IndicateNode(LinkedListNode<string> node, string test)
    {
        Console.WriteLine(test);
        if (node.List == null)
        {
            Console.WriteLine("Node '{0}' is not in the list.\n",
                node.Value);
            return;
        }

        StringBuilder result = new StringBuilder("(" + node.Value + ")");
        LinkedListNode<string> nodeP = node.Previous;

        while (nodeP != null)
        {
            result.Insert(0, nodeP.Value + " ");
            nodeP = nodeP.Previous;
        }

        node = node.Next;
        while (node != null)
        {
            result.Append(" " + node.Value);
            node = node.Next;
        }

        Console.WriteLine(result);
        Console.WriteLine();
    }
}

//This code example produces the following output:
//
//The linked list values:
//the fox jumps over the dog

//Test 1: Add 'today' to beginning of the list:
//today the fox jumps over the dog

//Test 2: Move first node to be last node:
//the fox jumps over the dog today

//Test 3: Change the last node to 'yesterday':
//the fox jumps over the dog yesterday

//Test 4: Move last node to be first node:
//yesterday the fox jumps over the dog

//Test 5: Indicate last occurence of 'the':
//the fox jumps over (the) dog

//Test 6: Add 'lazy' and 'old' after 'the':
//the fox jumps over (the) lazy old dog

//Test 7: Indicate the 'fox' node:
//the (fox) jumps over the lazy old dog

//Test 8: Add 'quick' and 'brown' before 'fox':
//the quick brown (fox) jumps over the lazy old dog

//Test 9: Indicate the 'dog' node:
//the quick brown fox jumps over the lazy old (dog)

//Test 10: Throw exception by adding node (fox) already in the list:
//Exception message: The LinkedList node belongs a LinkedList.

//Test 11: Move a referenced node (fox) before the current node (dog):
//the quick brown jumps over the lazy old fox (dog)

//Test 12: Remove current node (dog) and attempt to indicate it:
//Node 'dog' is not in the list.

//Test 13: Add node removed in test 11 after a referenced node (brown):
//the quick brown (dog) jumps over the lazy old fox

//Test 14: Remove node that has the value 'old':
//the quick brown dog jumps over the lazy fox

//Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':
//the quick brown dog jumps over the lazy rhinoceros

//Test 16: Copy the list to an array:
//the
//quick
//brown
//dog
//jumps
//over
//the
//lazy
//rhinoceros

//Test 17: Clear linked list. Contains 'jumps' = False
//

Hashtable

Hashtable is a data structure implemented in the .NET Framework in two ways, simple Hashtable in the namespace System.Collections and as generic data structure Dictionary in System.Collections.Generic namespace, it is recommended to use Dictionary instead of Hashtable, the working principle of Hashtable and Dictionary is that construct a hash that is index into an array usually using polynomials. Searching in a Hashtable and Dictionary has the complexity of time O(1).

Example of using generic Dictionary from System.Collections.Generic namespace:



// Create a new dictionary of strings, with string keys.
//
Dictionary<string, string> openWith =
    new Dictionary<string, string>();

// Add some elements to the dictionary. There are no
// duplicate keys, but some of the values are duplicates.
openWith.Add("txt", "notepad.exe");
openWith.Add("bmp", "paint.exe");
openWith.Add("dib", "paint.exe");
openWith.Add("rtf", "wordpad.exe");

// The Add method throws an exception if the new key is
// already in the dictionary.
try
{
    openWith.Add("txt", "winword.exe");
}
catch (ArgumentException)
{
    Console.WriteLine("An element with Key = \"txt\" already exists.");
}

// The Item property is another name for the indexer, so you
// can omit its name when accessing elements.
Console.WriteLine("For key = \"rtf\", value = {0}.",
    openWith["rtf"]);

// The indexer can be used to change the value associated
// with a key.
openWith["rtf"] = "winword.exe";
Console.WriteLine("For key = \"rtf\", value = {0}.",
    openWith["rtf"]);

// If a key does not exist, setting the indexer for that key
// adds a new key/value pair.
openWith["doc"] = "winword.exe";

// The indexer throws an exception if the requested key is
// not in the dictionary.
try
{
    Console.WriteLine("For key = \"tif\", value = {0}.",
        openWith["tif"]);
}
catch (KeyNotFoundException)
{
    Console.WriteLine("Key = \"tif\" is not found.");
}

// When a program often has to try keys that turn out not to
// be in the dictionary, TryGetValue can be a more efficient
// way to retrieve values.
string value = "";
if (openWith.TryGetValue("tif", out value))
{
    Console.WriteLine("For key = \"tif\", value = {0}.", value);
}
else
{
    Console.WriteLine("Key = \"tif\" is not found.");
}

// ContainsKey can be used to test keys before inserting
// them.
if (!openWith.ContainsKey("ht"))
{
    openWith.Add("ht", "hypertrm.exe");
    Console.WriteLine("Value added for key = \"ht\": {0}",
        openWith["ht"]);
}

// When you use foreach to enumerate dictionary elements,
// the elements are retrieved as KeyValuePair objects.
Console.WriteLine();
foreach( KeyValuePair<string, string> kvp in openWith )
{
    Console.WriteLine("Key = {0}, Value = {1}",
        kvp.Key, kvp.Value);
}

// To get the values alone, use the Values property.
Dictionary<string, string>.ValueCollection valueColl =
    openWith.Values;

// The elements of the ValueCollection are strongly typed
// with the type that was specified for dictionary values.
Console.WriteLine();
foreach( string s in valueColl )
{
    Console.WriteLine("Value = {0}", s);
}

// To get the keys alone, use the Keys property.
Dictionary<string, string>.KeyCollection keyColl =
    openWith.Keys;

// The elements of the KeyCollection are strongly typed
// with the type that was specified for dictionary keys.
Console.WriteLine();
foreach( string s in keyColl )
{
    Console.WriteLine("Key = {0}", s);
}

// Use the Remove method to remove a key/value pair.
Console.WriteLine("\nRemove(\"doc\")");
openWith.Remove("doc");

if (!openWith.ContainsKey("doc"))
{
    Console.WriteLine("Key \"doc\" is not found.");
}

/* This code example produces the following output:
An element with Key = "txt" already exists.
For key = "rtf", value = wordpad.exe.
For key = "rtf", value = winword.exe.
Key = "tif" is not found.
Key = "tif" is not found.
Value added for key = "ht": hypertrm.exe
Key = txt, Value = notepad.exe
Key = bmp, Value = paint.exe
Key = dib, Value = paint.exe
Key = rtf, Value = winword.exe
Key = doc, Value = winword.exe
Key = ht, Value = hypertrm.exe
Value = notepad.exe
Value = paint.exe
Value = paint.exe
Value = winword.exe
Value = winword.exe
Value = hypertrm.exe
Key = txt
Key = bmp
Key = dib
Key = rtf
Key = doc
Key = ht
Remove("doc")
Key "doc" is not found.
*/

Hashtable applications:

is used in fast data lookup - the compiler symbol table
indexing the database
caches
unique data representation

Of course, the .NET Framework contains several data structures optimized for certain problems, the purpose of this article is not to present all data structures from .NET Framework, I presented only common data structures from courses of algorithms and data structures.

Binary Search

Search algorithms are another topic in the courses of algorithms and data structures, we can use sequential search with O(n) complexity, or binary search with O(log n) complexity if the elements are sorted.
The idea behind binary search is that we access the middle element and compare with the searched one if it is smaller repeats the recursive process for the first half, otherwise it is searching in the second half, the binary search in the .NET Framework is implemented with Array.BinarySearch.

An example of using binary search using the Array.BinarySearch method in the .NET Framework:



ass Program  
{  
    static void Main(string[] args)  
    {  
        // Create an array of 10 elements    
        int[] IntArray = new int[10] { 1, 3, 5, 7, 11, 13, 17, 19, 23, 31 };  
        // Value to search for    
        int target = 17;  
        int pos = Array.BinarySearch(IntArray, target);  
        if (pos >= 0)  
            Console.WriteLine($"Item {IntArray[pos].ToString()} found at position {pos + 1}.");  
        else  
            Console.WriteLine("Item not found");  
        Console.ReadKey();  
    }

Binary Search Tree

A GitHub repository with custom implementations for most data structures: https://github.com/aalhour/C-Sharp-Algorithms.
I will continue to present a binary search tree. The idea is to have a node root, each node has at most two child nodes, the one on the left is smaller than the root, as well as the left subtree, the right node is larger than the root, so is the right subtree.
Example of binary tree construction:

Searching in a binary search tree has the complexity of time O(log n) , example of searching in binary tree:

Binary search tree traversal:
Preorder

Root through
Go through the left subtree
Go through the right subtree

Inorder

Go through the left subtree
Root through
Go through the right subtree

Postorder

Go through the left subtree
Go through the right subtree
Root through

In the .NET Framework , the SortedList data structure uses internally a binary tree to keep the sorted elements.

Graphs

The graphs are data structures characterized by nodes and edges joining the nodes, usually using the notation G = (V, E) where, V represents the set of nodes (vertices, vertices), and E represents the set of edges (edges), in the programming language is represented by adjacency matrices for example a [i, j] = k, this means that between node i and j we have an edge with weight k, and adjacent lists are also used for their representation.

The graphs and trees can also be crossed in breadth(BREADTH FIRST) with a queue, depth(DEPTH FIRST) with a stack.

Sorting Algorithms

Sorting algorithms are another topic from the courses of algorithms and data structures, a table with their complexities:

New feature in Visual Studio 16.6.0 Preview 2, a better integration with Git and GitHub

Adavidoaiei Dumitru-Cornel — Tue, 17 Mar 2020 10:18:29 +0000

In Visual Studio 16.6.0 Preview 2 we have option for new git experience, to activate you should go to Tools > Options > Preview Features

After activating this option you should restart Visual Studio, and you will see a new option in Visual Studio menu.

The Git docked window was updated with redesigned look and feel.

Structuri de date si algoritmi fundamentali in C#

Adavidoaiei Dumitru-Cornel — Thu, 05 Mar 2020 18:46:15 +0000

Stiva (Stack)
Coada (Queue)
Lista Inlatuita (Linked List)
Tablou De Dispersie (Hashtable)
Cautare Binara (Binary Search)
Arbore Binar De Cautare (Binary Search Tree)
Grafuri (Graphs)

Importanta complexitati algoritmilor este data de faptul ca ne zice daca codul se scaleaza. Majoritatea structurilor de date si a algoritmilor fundamentali sunt deja implementati in .NET Framework, e important sa stim cum functioneaza aceste structuri de date si ce complexitate de timp, memorie au la operatiile de baza: accesare element, cautare element, stergere element, adaugare element.

Ca sa ne facem o idee ce inseamna o complexitate buna si una mai putin buna avem urmatorul grafic:

In .NET Framework avem implementate urmatoarele structuri de date: array, stack, queue, linked list si algoritmi: cautare binara(binary search), restul pe care nu le gasim in .NET Framework se pot gasi in pachete NuGet sau pe GitHub.
Array este una dintre cele mai folosite si cunoscute structuri de date si nu am sa detaliez cu exemple principiul de functionare.

Stiva (Stack)

Stiva (Stack) este o structura de date implementata in .NET Framework sub doua forme, stiva simpla in namespace System.Collections, si stiva ca structura de date generica in namespace System.Collections.Generic, principiul de functionare a structuri stack este LIFO(last in first out), ultimul element intrat primul iesit.

Exemplu de folosire stiva simpla din namespace System.Collections:

Exemplu de folosire stiva generica din namespace System.Collections.Generic:

Coada (Queue)

Coada (Queue) este o structura de date implementata in .NET Framework sub doua forme, coada simpla in namespace System.Collections, si coada ca structura de date generica in namespace System.Collections.Generic, principiul de functionare a structuri queue este FIFO(first in first out), primul element intrat primul iesit.

Exemplu de folosire coada simpla din namespace System.Collections:

Exemplu de folosire coada generica din namespace System.Collections.Generic:

Lista Inlantuita (Linked List)

Lista Inlantuita (Linked List) este o structura de date implementata in .NET Framework ca structura generica in namespace System.Collections.Generic, principiul de functionare a structuri lista inlatuita este ca fiecare nod din lista are o referinta la nodul urmator, exceptand coada listei care nu are o referinta la urmatorul nod.

Un exemplu de cautare in lista inlatuita a celui de al treilea element incepand de la sfarsit:

Exemplu de folosire lista inlatuita generica din namespace System.Collections.Generic:

Tablou De Dispersie (Hashtable)

Tablou De Dispersie (Hashtable) este o structura de date implementata in .NET Framework sub doua forme Hashtable simplu in namespace System.Collections si Dictionary ca structura de date generica in namespace System.Collections.Generic, este recomandat sa folosim Dictionary in loc de Hashtable, principiul de functionare a structuri Hashtable, Dictionary este ca se construieste un hash care e index intr-un array de obicei folosind polinoame.
Cautarea intr-un Hashtable, Dictionary are complexitatea de timp O(1).

Exemplu de folosire Dictionary generic din namespace System.Collections.Generic:

Desigur .NET Framework contine mai multe structuri de date optimizate pe anumite probleme, scopul acestui articol este sa prezint echivalente la structurile de date implementate in cursurile de algoritmi si structuri de date.

Cautare Binara (Binary Search)

Algoritmi de cautare reprezinta un alt topic din cursurile de algoritmi si structuri de date, putem folosi cautare secventiala cu complexitate O(n), sau binara daca elementele sunt sortate cu complexitate O(log n).
Ideea din spatele binary search este ca accesam elementul din mijloc si comparam cu cel cautat daca e mai mic se repeta procesul recursiv pentru prima jumatate, altfel se cauta in a doua jumatate, cautarea binara in .NET Framework se realizeaza cu Array.BinarySearch.

Un exemplu de folosire cautare binara folosind metoda Array.BinarySearch din .NET Framework:

Arbore Binar De Cautare (Binary Search Tree)

Un repository GitHub cu implementari custom pentru majoritatea structurilor de date cu cod sursa: https://github.com/aalhour/C-Sharp-Algorithms
Am sa prezint in continuare arbore binar de cautare (binary search tree) ideea e ca ai un nod radacina, fiecare nod are cel mult doua noduri copii, cel din stanga e mai mic decat radacina, la fel tot subarbore stang, nodul drept este mai mare decat radacina, la fel tot subarbore drept.
Exemplu de construire arbore binar:

Cautarea intr-un arbore binar de cautare are complexitatea de timp O(log n), exemplu de cautare in arbore binar:

Metode de parcurgere arbori binari:
Preordine

Se parcurge rădăcina
Se parcurge subarborele stâng
Se parcurge subarborele drept

Inordine

Se parcurge subarborele stâng
Se parcurge rădăcina
Se parcurge subarborele drept

Postordine

Se parcurge subarborele stâng
Se parcurge subarborele drept
Se parcurge rădăcina

In .NET Framework, structura de date SortedList foloseste intern un arbore binar ca sa pastreze elementele sortate.

Graphs

Grafurile sunt structuri de date caracterizate prin noduri si muchii care unesc nodurile, se foloseste de obicei notatia G=(V, E)
unde, V reprezinta multimea de noduri(varfuri, vertices), si E reprezinta multimea de edges(muchii), in limbajul de programare se reprezinta prin matrice de adiacenta de exemplu a[i, j] = k, asta inseamna ca intre nodul i si j avem o muchie cu pondere k, se mai folosesc si liste de adiacenta pentru reprezentarea lor.

Grafurile si arbori pot fi parcursi si in latime(BREADTH FIRST) cu o coada, adancime(DEPTH FIRST) cu o stiva.

Algoritmi de sortare sunt un alt topic din cursurile de algoritmi si structuri de date, un tabel cu complexitatile acestora:

Implementare Least Frequently Used Cache in .NET cu teste unitare si teste de performanta

Adavidoaiei Dumitru-Cornel — Thu, 05 Mar 2020 18:27:59 +0000

Principiul de functionare la Least Frequently Used Cache este urmatorul: fiecare element din cache pastreaza intr-o variabila numarul de accesari al respectivului element, cand cache-ul depaseste limita maxima se elimina elementul cu numarul minim de accesari, lasand loc unui nou element sa fie adaugat in cache.

Implementare Structura de Date

Este nevoie de o structura de date care sa pastreze elementele din cache sortate dupa numarul de accesari, astfel operatia de eliminare a elementului cu numarul minim de accesari sa ruleze in O(log n). Implementarea curenta foloseste un SortedList unde cheia este numarul de accesari iar valoarea este o lista intantuita cu elementele din cache care au acelas numar de accesari. SortedList sorteaza listele inlantuite folosind un arbore binar. Aceasta structura de date permite rulare operatilor de adaugare si accesare elemente din cache in complexitate de timp O(log n)

Am creat o interfata generica pe care clasa LFUCache sa o implementeze:

Implementarea clasa LfuCache este sub forma de structura de date generica care implementeaza interfata ICache, permite crearea unui cache care sa stocheze elemente de orice tip, impreuna cu operatiile Add si Get:

Un exemplu de utilizare al clasei LfuCache:

Acest proiect este publicat pe GitHub si ca pachet NuGet.
Daca vreti sa folositi acest cache in proiectul dumneavoastra il puteti instala ca si pachet NuGet cu urmatoarea comanda din Visual Studio sau din interfata grafica:

Teste Unitare

In scrierea testelor unitare am folosit framework-ul MSTest de la Microsoft, acestea urmeaza pattern-ul Arrange - Act - Assert.
Implementarea testelor unitare:

Testele unitare se pot rula local din Visual Studio > Test Explorer sau ca pas in procesul de integrare continua pe server folosind un serviciu ca si Azure Pipeline.

Un aspect important in testele unitare e code coverage, cat din cod e acoperit de testele unitare, in cazul nostru code coverage este 100%, pentru a masura code coverage se poate folosi local dotCover de la JetBrains.

Teste de Performanta

Pentru testele de performanta am folosit urmatoarea librarie PerformanceDotNet, aceasta masoara timpul de executie si cantitatea de memorie consumata.
Secventa de operatii pe cache de adaugare/accesare este generata aleatoriu intr-un array de operatii de lungime OperationsCount, aceste operatii proceseaza elementele dintr-o lista de dimensiune EelementsCount folosind LFUCache.

Pentru rularea testelor de performanta se poate folosi urmatoarea extensie pentru Visual Studio: BenchmarkDotNet VS Runner.

Un exemplu de raport HTML cu rezultatul la benchmark:

PerformanceDotNet poate genera rapoarte cu rezultatele la benchmark in format HTML, CSV, MarkDown GitHub, RPlotExporter(grafic).
Rezultatele la benchmark pot varia in functie de performanta masini pe care se ruleaza testele de performanta, cea mai importanta este performanta procesorului pe care se executa dar mai poate depinde si de runtime daca este .NET Core sau .Net Framework, si de versiunea acestuia.