DEV Community: Mohamed Allam

Physical vs Logical vs Abstract Data Types (DST) and data structure (DS)

Mohamed Allam — Sat, 17 Dec 2022 00:51:42 +0000

Physical vs Logical vs Abstract Data Types (DST) and data structure (DS)

All computer science is about abstraction as everything is binary, and thats why its sometimes hard to learn, lets break down this terminology.

Abastract data types

Also known as ADT, lets start our discussion about the primitives or scalar types.

Abstract data types is abstracting away 0 and 1 from us,
Representation and operations, each data types, is represented in some specific way, and can have a set of operations to it.
- 16 bit intger is 15 bit of 1 and 0, and the left most bit is wether its a signed or unsigned integer.
- Arthmetic Operations can be done on integers addition, subtraction, multiplication division modulos
  - Relational operations, less than greater than, increment than decrement..ect
Primitives or scalar types, is the programming language provided types, like integers, strings, floats..ect
We dont concern our selves too much how internally this operations are performed.

When we learn programming languages, we mostly learn about representation of data, mostly scalar types, or primitive types and the operations we can do to them.

So the concept of representation and definition of data, and operations on the. while hiding the internal details is in essence abstract data types

For example in programming languages, we define classes, which has objects, and we give those special behaviours and different details, this is how we define them and there operations. for example we can create a class of linkedlists, with different operations

Add(element, index) or inserrt(element, index)
Append(element)
Remove(element)
Set(element)
Get(index)
Search(key)
Sort()
….

This is how we create our own abstract data types, but the thing is, there is some very known and efficient data types, we call them data structure, they allow us to efficiently utilize the resources, the main memory in the most ideal way, and we extend the programming languages to perform what we want us, us developers.

Physical data structure

Data structure is collection of data structure, so multiple data stored together.

This data structure defines how memory is allocated, they define how the memory will be organized in order for them to store the data.

Arrays

Most programming languages supports arrays
its a collection of memory allocation, side by side, back to back.
Arrays are fixed size, or arrays size is static, we cannot increase or decrease an array size after its creation, we can only assign to it, or desctruct it (deallocate the memory)
Arrays can be created in the stack or the heap, we use a pointer to allocate arrays in the heap.
We use arrays when we know the maximum number of elements we need

Linedlist

Lined lists are dynamic by nature, you can add more elements or delete them.
its a collceiton of data, where each piece is called a node
Each node holds data, and a pointer to the next node.
Lined lists live in the heap, the head pointer can be in the stack.

Logical data structure

This data structure, are an abstraction over the physical datastructure, Physical data structure store the data in memory, physically, but the logical data strucutre is the protocol, the discipline or the set of rules and policies we use to use the physical data structures in way we want for better organiztion of our data.

All operations we do to this data structure are defined also by the logic we set. the API.

This data structure can be split into two types, linear data structure, and non linear data structure.

Linear data sturcture

linear data structure include

Stack (LIFO)
Queue (FIFO)

Non linear data structure

Tree
Graph

Tabluar

Hash tables

Big O notatian

Its how we analyse algorithms and operations on them, how efficient they are specially when we approach infinity. in respect of N input.

Time complexity

To measure the performance of our data structure, our job is to find out how much work we do per N elements, means for example if to find a word in a dictionary takes you iterating through every single word, means thats Order of N, if you can find the word by just looking at a fraction of the book or a subset, there is high chances, its a log to the two of N, so time complexity is always in respect of our input, or how much element exists in the data we are working with, the job is not to find the exact time it takes, because that varies from machine to machine or from buzy processors to another..ect
Our job is to find the least amount of time we need to process N elements, we analyse the behaviour, how much more time we need to get the task done. a behaviour not an exact time.

Space complexity

Many times, when we do something, we need extra memory than what we are working with, so in that case, we would have to consider that, because we dont always have extra memory, so thats the memory complexity it can be order of N or less or more, depends on the data type or algorithm we are working with.

Trees data structure with types (uses cases included)

Mohamed Allam — Sat, 10 Dec 2022 09:40:07 +0000

Whats a tree

A tree is a collection of nodes, each node holds some data, one of the nodes is the root node, and other nodes. are disjoints subsets and each subset is a tree or a sub tree.

Each node has exactly one parent, and can have one or more children, no single node has more than one parent.

Trees are everywhere:

If you wrote any switch statement but didnt knew why its more efficient than a bunch of if-else statements, the answer is Look up tables (LUT) which may use BST
Operating systems use trees for File system.
The syntactic representation of a programming language is Abstract syntax tree. AST
Browser Document object model (DOM)
Databases use Log structured merge tree. LSM tree
SQL index use b-tree.
Dynamic memory management uses heap. which is a type of a tree.
A trie for dictionaries or auto complete algorithms.
Priority queues as well use heap.
Garbage collectors also use trees.

https://en.wikipedia.org/wiki/Tree_(graph_theory)

https://en.wikipedia.org/wiki/Tree_(data_structure)

Nodes or vertices

Nodes is every unit of data

Edges or paths (links)

Its the connection between each two nodes, if we have N nodes we would have N-1 edges, because each node as parent, except the root node.

Root

Is the upmost node, who has no parent, and have only children, for the children nodes this is their most parent node, generally in the top of the tree.

Parent-Children

A node is a parent to its very next descendants. the descendants are the children to whom its connected with one single edge.

Siblings

Are the children connected to the same node.

Descendants

When we want to talk about children and their children, and the children of their children..etc we would say descendants.

It means the set of nodes we can reach from a particular node going to its children. so all the subtree.

Ansestors

From that node to the root node, all this nodes are considered anscestors.

Degree of nodes

Is the number of children a node has, so the direct children.

A degree of a tree cannot be told from a tree, but its predefined, we can say its a binary tree. but if its unbalanced, we would see it in a form of a linkedlist.

Leaf nodes, external or terminal

All nodes who has no children. so with nodes with degree 0

Levels

Levels starting from first level 1, the root, as we categorize each level by all the nodes who take the same number of edges to get to the root node.

Height

Hight of nodes, is the same as the levels but it starts from 0, its very useful for analysis.

Forest

A collection of a tree is called a forest. which at least has a root node.

To convert a forest to a tree, we attach the roots of the present trees, to one single root.

Types of trees

There is many types of trees, and they are extremely useful and popular. for example

Binary tree

One of the most popular trees, is the binary tree,

Its tree of degree 2, means every node can have 0,1 or 2 children, but not more than 2.

deg(T)=2

$children={{0,1,2}}$

Because the nodes can have only 2 nodes, we call them left child and right child. or left node and right node.
If we come across a tree that is unbalanced, means it forms something like a linked list, but to the left side, we call it left skewed binary tree. or right skewed binary tree

Binary search tree

The binary search tree or BST , is a derivate of binary tree, but with a constraint in the data, Its a rooted binary tree, where every node (data) on the left side is grater than nodes on the right side.

$deg(T)=2$

AVL Tree

Another tree named after inventors Adelson-Velsky and Landis, is a self balancing binary search tree.

Decision Tree

Its one of the popular ones for classification and prediction.

Fenwich Tree

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

Link to wiki

Log structured Merge Tree

Or LSM tree one of the trees used in databases like influxDB.

How to work with paths join or change directories in Golang

Mohamed Allam — Fri, 18 Nov 2022 21:52:43 +0000

Path join in Golang

Manipulating filename paths in a way that is compatible with the any target operating system-defined file paths.

Path joining

When you start changing directories, you have to work with both forward slash and backward slash, depending on the operating system, Unix or Windows, Go takes care of that using path.FilePath.Join function, to use Join, you have to provide the name of the folders, and Go will use the appropriate slash for you

// https://pkg.go.dev/path/filepath#Join
func Join(elem ...string) string {
...
}

Join joins any number of path elements into a single path, separating them with an OS specific Separator. Empty elements are ignored. The result is Cleaned. However, if the argument list is empty or all its elements are empty, Join returns an empty string. On Windows, the result will only be a UNC path if the first non-empty element is a UNC path.

To use that, let's change directory using Go.

Change directory `cd`

And also we generally you would need to use the [chdir](https://pkg.go.dev/os#Chdir) you specify the name of the directory you want to go to, and this function would change the current directory for you

// https://pkg.go.dev/os#Chdir
func Chdir(dir string) error {
...
}

Chdir changes the current working directory to the named directory. If there is an error, it will be of type *PathError.

Lets combine this two, which does allow us to work with either windows or linux who use / or \ backslash and forward slash for each system, and change directory to for now the names we pass in the ChangeDir

func ChangeDir(elem ...string) {
    path := filepath.Join("./", filepath.Join(elem...))

    err := os.Chdir(path)
    if err != nil {
        fmt.Println("Cant change the workig directory", err)
    }
}

Joining strings

On the same note, if for whatever reason you want to join folder names, based on something different, or if is any strings joined, there is in the Go standard package, a string package that has a join method that is as below

https://pkg.go.dev/strings#Join
func Join(elems []string, sep string) string

Join concatenates the elements of its first argument to create a single string. The separator string sep is placed between elements in the resulting string.

And as the official documentation:

s := []string{"foo", "bar", "baz"}
fmt.Println(strings.Join(s, ", "))
//Output
//foo, bar, baz

Protocol buffer and gRPC: Beginners guide

Mohamed Allam — Mon, 07 Nov 2022 09:23:57 +0000

Protocol buffer and gRPC: Beginners guide

Intro

Modern software applications rarely operate in isolation. Rather, they are connected with each other through computer networks and communicate and coordinate their actions by passing messages to one another.

Wether you are looking to weather in your iPhone, or Paying a service/product in websites, inter and public communications between different code bases is always required to implement such functionalities.

The problem

There is more than a thousand programming languages, and lot of different communications

What are protocol buffers?

https://developers.google.com/protocol-buffers

https://github.com/protocolbuffers/protobuf

https://en.wikipedia.org/wiki/Protocol_Buffers

Accordring to Protocol buffer official doocumentation:

Protocol buffers are Google's language-neutral, platform-neutral, extensible mechanism for serializing structured data – think XML, but smaller, faster, and simpler. You define how you want your data to be structured once, then you can use special generated source code to easily write and read your structured data to and from a variety of data streams and using a variety of languages.

Accordring to Wikipedia:

Protocol Buffers (Protobuf) is a free and open-source cross-platform data format used to serialize structured data. It is useful in developing programs to communicate with each other over a network or for storing data. The method involves an interface description language that describes the structure of some data and a program that generates source code from that description for generating or parsing a stream of bytes that represents the structured data.

As for comparison:

Comparison of data-serialization formats - Wikipedia


syntax = "proto3" // this defines which version of protocol buffer we use

// the messages we send is defined with "message"
// field type (int, string, boolean)
// field name
// field tag
message myMessage {
    int32 id = 1;
    string first_name = 2;
    string last_name = 3;
}

Scalar types:

Language Guide (proto3) | Protocol Buffers | Google Developers

https://developers.google.com/protocol-buffers/docs/proto3#scalar

For numbers we find this types:

double, float, int32, int64, uint32, uint64, sint32, sint64, fixed32, fixed64, sfixed64.

We find other common ones:

bool for boolean,

string for strings, which are UTF-8 or 7-bit ASCII text.

and bytes. or bytes array, we can use bytes for maybe a small image or something like that.

All types are zero valued

When a message is parsed, if the encoded message does not contain a particular singular element, the corresponding field in the parsed object is set to the default value for that field. These defaults are type-specific:

For strings, the default value is the empty string.
For bytes, the default value is empty bytes.
For bools, the default value is false.
For numeric types, the default value is zero.
For Enum types, default value is first value.
For repeated values, empty list.

syntax = "proto3"

message Person {
    uint32 age = 1;
    string first_name = 2;
    string last_name = 3;
    bytes small_picture = 4;
    bool profile_verified = 5;
    float height = 6;
}

Import from other proto files

To import a type from another file, we have to use import syntax, where we start from the folder directory

import "my_root_project/date.proto";

message Person {
    uint32 age = 1;
    string first_name = 2;
    string last_name = 3;
    bytes small_picture = 4;
    bool profile_verified = 5;
    float height = 6;
    repeated string address = 7;

    // enums of the possible eye color
    enum EyeColor {
        UKNOWN_EYE_COLOR = 0;
        EYE_GREEN = 1;
        EYE_BROWN = 2;
        EYE_BLUE = 3;
    }
    EyeColor eye_color = 8
    Date birthday = 9
}

Packages

WE can add packages to have percise type naming convetino


// mydate is the pacakge name
// Date is message definiton
message Address {
    string first_name = 1;
    my.date.Date bithday = 2;
}

Getting started with ProtoBuf

Basics

Protocol buffers uses .proto files, in which a message is the message we send or receive, a basic message look like this

message Product {
    string title = 1;
    float price = 2;
}

Proto files has 3 versions, to indicate the version in the beginning of the file, we declare the version we want to use, the lastest one is version 3.

syntax = "proto3"

message Product {
    string title = 1;
    float price = 2;
    bool available = 3;
}

The scalar types

double, float, int32, int64, uint32, uint64, sint32, sint64, fixed32, fixed64, sfixed64.

We find other common ones:

bool for boolean,

string for strings, which are UTF-8 or 7-bit ASCII text.

and bytes. or bytes array, we can use bytes for maybe a small image or something like that.

did you know what happened today?

Mohamed Allam — Tue, 19 Jul 2022 11:12:02 +0000

Liquid syntax error: Tag '{%' was not properly terminated with regexp: /\%\}/

Hello, World!

Mohamed Allam — Tue, 19 Jul 2022 09:47:51 +0000

Hello DEV, this is my first post

Why you should learn go?

Mohamed Allam — Fri, 29 Apr 2022 00:04:38 +0000

Intro

Its 2022, 5 years since I started my first Laravel application, and I never wanted to look to anything else, to embrace the framework and learn it intimately.

The beginning of this year, I made a little research in the programming languages and tried to figure out another programming language to learn.

Right of the bad, I did see some comparisons and saw a difference in old vs new programming languages, and my heart instantly fell in love with new programming languages.

The newer programming languages

So in the landscape of more than a thousands choice, I have limited my choices to:

Dart (Flutters' language)
Swift (Apple snob?)
Elixir (Atom model)
Golang (yeah)

Most hardwares that existed when C or PHP was created, are not only obsolete but also different, particularly multi threaded processors.
Therefor the languages too had to make some changes, through updates, patches, new versions.
But when it comes to this new language, they are built from the ground up to consume and embrace the hardware of today.

In my research I come across

StackOverFlow surveys
JetBrains surveys
Tiobe index
PYPL
HackerRank report
Hired reportd
Github Octoverse

Extra

As an extra, I did scroll through some benchmarking frameworks.

Buttom line

Golang is among best programming languages to learn in 2022
.

Test driven development

Mohamed Allam — Tue, 27 Jul 2021 22:32:16 +0000

My first post

DEV Community: Mohamed Allam

Physical vs Logical vs Abstract Data Types (DST) and data structure (DS)

Physical vs Logical vs Abstract Data Types (DST) and data structure (DS)

Abastract data types

Physical data structure

Arrays

Linedlist

Logical data structure

Linear data sturcture

Non linear data structure

Tabluar

Big O notatian

Time complexity

Space complexity

Trees data structure with types (uses cases included)

Whats a tree

Nodes or vertices

Edges or paths (links)

Root

Parent-Children

Siblings

Descendants

Ansestors

Degree of nodes

Leaf nodes, external or terminal

Levels

Height

Forest

Types of trees

Binary tree

Binary search tree

AVL Tree

Decision Tree

Fenwich Tree

Log structured Merge Tree

How to work with paths join or change directories in Golang

Path join in Golang

Path joining

Change directory cd

Joining strings

Protocol buffer and gRPC: Beginners guide

Protocol buffer and gRPC: Beginners guide

Intro

The problem

What are protocol buffers?

Scalar types:

All types are zero valued

Tags

Import from other proto files

Packages

Getting started with ProtoBuf

Basics

did you know what happened today?

Hello, World!

Why you should learn go?

Intro

The newer programming languages

In my research I come across

Extra

Buttom line

Test driven development

Change directory `cd`