Convolutional Neural Networks

Giriş

Image classification için kullanılabilir. CNN ile "pre-trained" modeller kullanılabilir. Açıklaması şöyle

CNN usually picks up an input which is an image, allot significant features of the image, and then makes the prediction. CNN is much better than the feedforward neural networks due to the way it captivates spatial dependencies from the image. Simply said, CNN understands the image’s composition much better than any other neural network. 

Specifically, CNNs are used to classify images. 

Loss Function

Açıklaması şöyle

The reduction in resolution is a fundamental step in CNN to accelerate processing time

Açıklaması şöyle

 A CNN looks for other features. It tries to minimize a loss function. And the fastest way to do this is often not the intended way. E.g. you think that a cow has like 4 legs and a certain shape of a head. A CNN might think that it is enough if there is something with 4 legs and a green background (because 9 of 10 images in the training dataset are like that). So for most of the cases the CNN does fine when it identifies a cow by these features.

Skip List

Giriş

Bu veri yapısı sanırım en çok concurrent yani çoklu thread kullanan ortamlarda daha verimli. Binary Search Tree gibi veri yapılarında rebalance işlemi için tüm ağacı kilitlemek gerekiyor. Açıklaması şöyle

The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked.

Bu yüzden Java'da

ConcurrentSkipListSet

ConcurrentSkipListMap

gibi concurrent veri yapıları da var

Nasıl Çalışır

Bir anlamda Linked List'e benzer. Farklı olarak her düğüm ilave olarak N sonraki düğümlere de pointer tutar. N sayısı 2, 4 gibi bir şey olabilir.

Örnek

Şeklen şöyle. Burada her düğüm 2 sonraki düğüme de pointer tutuyor. Dolayısıyla 80 değerini aramak için 7 defa işlem yerine, 4 işlem yeterli.

Algoritma Analizi - O(n2) - İkinci Dereceden Yani Quadratic

Giriş

En basit örneği iç içe iki tane döngüdür.

Örnek - complexity of two nested loops over different datasets

Elimizde şöyle bir kod olsun

for things in list_a {
  for things in list_b {
    if (list_a.thing relates to list_b.thing) go ping
  }
}

Açıklaması şöyle. İki listenin de büyüklüğü farklı olabilse dahi en kötü durum düşünüleceği için sonuç O(n * m) yerine O(n^2)  olarak söylenir

It'd be O(n*m) where the worst case is n = m or n*n thus O(n^2). We are interested in worst case run time for Big O. If the data sets sizes are different then it will still be in O(n^2) since we can't guarantee that, for example, the second dataset will be a logarithmic relation to the first. If we could, they wouldn't necessarily be independent. They might be but again, we are looking at worst case and O(n logn) is within O(n^2).

Örnek - complexity of two nested loops one has fixed size

Bu soru anagramları gruplama sorusu. Şöyle yaparız. Algoritma analizi O (n * 26)'dır. Yani aslında O(n)'dir. complexity of two nested loops over different datasets sorusu ile farkını göstermek için ekledim

Her string için harf frekansı hesaplanır. Yani abbccc için şunu gibidir #1#2#3#0#0#0...#0. Her anagram aynı string'i verecektir. Böylece string'ler gruplanır.

public static List<List<String>> groupTitles(String[] strs){
  if (strs.length == 0) 
    return new ArrayList<List<String>>();

  Map<String, List<String>> res = new HashMap<>();
  int[] count = new int[26];
  for (String s : strs) {
    Arrays.fill(count, 0);
    for (char c : s.toCharArray()){
      int index = c - 'a';
      count[index]++;
    }
    StringBuilder delimStr = new StringBuilder("");
    for (int i = 0; i < 26; i++) {
      delimStr.append('#');
      delimStr.append(count[i]);
    }
            
    String key = delimStr.toString();
    if (!res.containsKey(key)) 
      res.put(key, new ArrayList<String>());
            
    res.get(key).add(s);
  }
  return new ArrayList<List<String>>(res.values());
}

Kullanmak için şöyle yaparız. duel,dule,deul bir grup, speed,spede bir grup, cars ise tek başına bir grup olur

String titles[] = {"duel","dule","speed","spede","deul","cars"};
List<List<String>> grups = groupTitles(titles);

String query = "spede";
// Iterate over groups
for (List<String> group : groups) {
  if (group.contains(query))
    System.out.println(g);
}

Örnek

Elimizde şöyle bir kod olsun. Burada da ikinci döngü aslında sabit bir değere bakarak dönmüyor. Ancak yine de sonuç O(n^2)

int n = ...;
int x = 0;
for (int i = 0; i < n; ++i) {
  for (int i = j; j < n; ++j) {
    ++x;
  }
}

Selection Sort

Bu sıralama algoritmasında içteki döngü dıştaki sıralanmamış eleman ile karşılaştırma yaparak, en küçük elemanı bulur ve yer değiştirir. Örnek burada.

Bubble Sort
n² (n kare) arama için Bubble Sort güzel bir örnek. Bu algoritma yanyana bulunan çiftlerin karşılaştırılması şeklinde çalışıyor. Her bir eleman yanındaki ile yer değiştirmeye ihtiyaç duymayıncaya kadar tüm liste tekrar tekrar dolaşılıyor.

Data Skewness - Verinin Çarpıklığı/Kayması

Giriş

Skewness bir dağılımın simetrik olmama derecesidir. Örneğin normal distribution bir dağılımda skewness derecesi 0'dır. Yani veri simetrik şekilde dağılmıştır.

Stream Processing

Stream Processing yazılımlarında skewness verinin bazı düğümlere daha fazla gelmesine sebep olur. Bu da toplamda stream pipeline' ınında gecikmeye sebep olabilir. Açıklaması şöyle

Such an imbalance can cause lower throughput and higher end-to-end latency.

Clock Skew

Bir zaman kaynağının gerçek göstermesi gereken zaman yerine ileri veya geri kayarak sapması anlamına gelir.

OpenMP Critical Section

Giriş 

Mutex ile aynı anlama gelir. Söz dizimi şöyle

#pragma omp critical(name)

Açıklaması şöyle,

The critical section names are global to the entire program (regardless of module boundaries). So if you have a critical section by the same name in multiple modules, not two of them can be executed at the same time. If the name is omitted, a default name is assumed.

Örnek

Eğer paralel kod içinde mutex kullanmak istersek şöyle yaparız.

#pragma omp critical
{
    //code only be written from a thread
}

Örnek

Şöyle yaparız

#include <iostream>

int main(int argc, char** argv)
{
  int someVar = 0;

  #pragma omp parallel for
  for (int i = 0; i < 1000; i++)
  {
    #pragma omp critical
    ++someVar;
  }

  std::cout << someVar << std::endl;

  return 0;
}

Eğer OpenMP yerine normal C++ kullanmak istersek şöyle yaparız.

#include <iostream>
#include <mutex>

int main(int argc, char** argv)
{
  int someVar = 0;
  std::mutex someVar_mutex;

  #pragma omp parallel for
  for (int i = 0; i < 1000; i++)
  {
    std::lock_guard<std::mutex> lock(someVar_mutex);
    ++someVar;
  }

  std::cout << someVar << std::endl;

  return 0;
}

DO-178B Software Design Process

Giriş

Aslında aşağıdaki cümleleri DO-178C'den aldım ancak çoğu DO-178B için de geçerli. Software Design Process kabaca şu faaliyetleri içerir. Yani bu safha sonunda Low Level Requirements ve Derived Requirements çıkar

1. Development of Software Architecture

2. Development of Low Level Requirements

3. Development of Derived Requirements

4. Considerations of User-Modifiable Software

5. Deactivated Code

Low Level Requirements - LLR

LLR yazılırken pseudo kod benzeri bir dil kullanılabilir. LLR ve SLOC arasında 20/1 oranı iyi bir oran.

"Our requirements are almost pseudo-code"

Örnek

Bir projede LLR'nin Use Case gibi yazıldığını gördüm. Kabaca şöyleydi

Main Use Case - Receive Foo

1. Context : This use case is initiated in Operational state

1.2 Actors :  I/O system is the actor of this use case

1.3 Goal : To process the received message and inform user

1.4 Pre Conditions : The system must be in Operational state

1.5 Post Conditions : The Foo message is consumed

1.6 Description : The use stats when system received Foo message with a TCP connection

1.7 The system shall reject the Foo message if CRC is incorrect

1.8 The system shall reject the Foo message if Source is 0

1.9 The system shall reject the Foo message if Minute field is illegal

1.10 If Foo exist with the received ID, Sub Flow : Exists is executed

1.11 If Foo does not exist with the received ID, Sub Flow : Not Exists is executed

1. Sub Flow Exists

1 If the type of received Foo and existing Foo are different, the system discards the message and this use case ends

2 The received Foo message is copied over the existing Foo

2. Sub Flow Not Exists

1. The received Foo message is copied over the existing Foo

3. Sub Flow Capacity

1. If the total number of Foo units is 100 Sub Flow Full Capacity is executed

3.1 Sub Flow Full Capacity

1. The system deletes the oldest Foo

2. The system shall send a alert to inform the user

Safety Assessment For Derived Requirements
Derived olarak işaretli bir gereksinimler, sistem seviyesindeki gereksinimlere dayanmayan ancak yazılımın çalışması için gerekli gereksinimler. Sistem gereksinimleri safety assessment 'a tabi tutuldukları için, sisteme doğru izlenebilirliği olan HLR ve LLR gereksinimlerini tekrar değerlendirmek gerekmez. Ancak derived gereksinimler tekrar  safety assessment 'a tabi tutulur. Gözden geçirilerek bir rapor yazılır.

Derived gereksinimlere örnek:

Sistem açılışında partition tarafından yapılan bazı kaynak yaratmaları ve ayarlamalar.

Redis - String Veri Yapısı

Giriş

Key olarak string, value olarak string kullanılır. SET, GET kullanılır. Açıklaması şöyle

Redis Strings are probably the most used (and abused) Redis data structure.

One of their main advantages is that they are binary-safe — This means you can save any type of binary data in Redis.

But as it turns out, most Redis users are serializing objects to JSON strings and storing them inside Redis.

İsmi String ama aslında Integer gibi sayılar için de kullanılabilir. Açıklaması şöyle

Q : Difference between storing Integers and Strings in Redis

A : No, there is no difference; both are stored as strings. 

Şeklen şöyle. Burada Simple Dynamic Strings (SDS) kullanıldığı görülebilir

DEL

Örnek

Şöyle yaparız

127.0.0.1:6379> SET foo "Hello World"
OK // setting a key

127.0.0.1:6379> GET foo
"Hello World" // getting a key

127.0.0.1:6379> DEL foo
(integer) 1 // key just got deleted

127.0.0.1:6379> GET foo
(nil) // since key is deleted therefore, result is nil.

INCR

Açıklaması şöyle

Increments the number stored at key by one. If the key does not exist, it is set to 0 before performing the operation. An error is returned if the key contains a value of the wrong type or contains a string that can not be represented as integer. This operation is limited to 64 bit signed integers.

Note: this is a string operation because Redis does not have a dedicated integer type. The string stored at the key is interpreted as a base-10 64 bit signed integer to execute the operation.

Redis stores integers in their integer representation, so for string values that actually hold an integer, there is no overhead for storing the string representation of the integer.

Örnek

Şöyle yaparız. Burada value string olmasına rağmen integer gibi artırılabiliyor.

127.0.0.1:6379> incr y
(integer) 1
127.0.0.1:6379> incr y
(integer) 2
127.0.0.1:6379> get y
"2"

Unique ID üretmek için kullanılabilir. Şeklen şöyle

SETEX (Setting a key with an expiry)

Örnek

Şöyle yaparız. Verinin bayatlamasına ne kadar kaldığını görmek için TTL kullanılır

127.0.0.1:6379> SETEX foo 40 "I said, Hello World!"
OK // key has been set with 40 seconds as expiration

127.0.0.1:6379> TTL foo
(integer) 36 // 36 seconds left to timeout