Крутий курс Compilers на Coursera

Недавно пройшов класний курс по компіляторах. Alex Aiken зрозуміло і для простих смертних (без матчасті) показує на практичних прикладах важкі концепції, проблеми при проектуванні простої мови.

Особливо якісно викладена тема по Garbage Collector на прикладі трьох його реалізаціях (Mark and Sweep, Stop and Copy, Reference Counting).

Пояснюється різниця і що взагалі таке семантика, синтаксис, кодогенерація, activation records, stack machines, регістри.
Найважче в компіляторах це локальна, глобальна оптимізація, хоча в курсі найважча була тема парсингу Bottom Up Parsing.

10/10 level up курс

https://class.coursera.org/compilers/lecture

Крутий курс Compilers на Coursera

How to delay repeatedly invoked operation in order to save performance

Виникла задача зробити автоматичне збереження.
Щоб при зміні значення не тиснути submit.
Тобто має відсилатись автоматичний запит на збереження.

Перший варіант відправляти запит при зміні кожного елемента:

$('input').on('change', function(){
    $.ajax(url);
})

Коли змінити 50 елементів, то відправить 50 запитів, що не є ефективно.

Тому для цього є throttle.
За допомогою цієї функції відправиться тільки 1 запит, якщо оновлення між елементами не більше time значення.

How to delay repeatedly invoked operation in order to save performance

Algorithm to сheck curly brackets pairs

Ідея видаляти ліву та праву дужку, як тільки зустрічається права дужка, що є парою для лівої.

Алгортм для валідації парності дужок:

function areСurlyBracesBalanced(s){
  var a = s.split('');  

  for(var l = 0; l < a.length; l++) {
    if(a[l] === '(') { 
      for(var r=l+1; r < a.length; r++){ 
        if(a[r] === ')') {
          delete a[l];
          delete a[r]; 
          break;
        }
      }
    }
  }
  return a.join('').length === 0;
}

Прийшлось написати a.join(”).length замість a.length тому, що delete не видаляє, а тільки undefined’ує. Можна звичайно використати функцію a.slice, яка справді видаляє.

Тест

function rand(from, to){
  return Math.floor((Math.random() * to) + from);
};

function generateBraces(count){
  var str = '';
  for(var i=0; i < count; i++){
    var side = rand(1,2);
    if(side % 2 === 0) {
      str += '(';
    } else {
      str += ')';
    }
  }
  return str;
};

for(var i=0; i < 1000; i++){
   var braces = generateBraces(rand(2, 16));
   if (areСurlyBracesBalanced(braces)) {
     console.log('correct', braces);
   };
}

correct ()() 
correct () 
correct ()() 
correct ((()(())(()))) 
correct (()()()(())) 
correct () 
correct (()(((())))()) 
correct () 
correct ()(()) 
correct (()((())())) 
correct (())(()(())) 
correct ()()() 
correct (()) 
correct ()(((()))) 
correct () 
correct ((())(()))()() 
correct () 
correct (()) 
correct () 
correct (()()) 
correct () 
correct ()()()() 
correct ()(()) 
correct (()())(()) 
correct () 
correct ()() 
correct () 
correct (()) 
correct ()(())()((())) 
correct () 
correct ()(()) 

Ще один варіант, але вже з книжки ‘Understanding Computation From Simple Machines to Impossible Programs’ це стековий.
Якщо на вхід ( тоді пуш щось в стек.
Якщо на вхід ) і стек пустий значить парності немає, вертаєм фолс.
Якщо на вхід ) і стек непустий видаляє один елемент.

function areСurlyBracesBalancedViaStack(str){
  var brackats = str.split("");
  var stack = [];
  for(var i = 0; i  0)  {
      stack.pop();
    } else if (brackats[i] == ')' && stack.length == 0) {
      return false;
    }
  }
  return stack.length === 0;
}
Algorithm to сheck curly brackets pairs

Вивід деревоподібної структури

Моя спроба написати дамп дерева у вигляді

                         a
             b                       c                       
       d           e           f           g           
    h     i     j     k     l     m     n     o     
  p  q  r  s  t  u  v  w  x  y  z  1  2  3  4  5  

З таких вхідні даних:

a
b c
d e f g
h i j k l m n o
p q r s t u v w x y z 1 2 3 4 5

Сам скрипт тривіальний

class Tree

  def initialize file_name
    content = File.read file_name
    @lines = content.split("n")
  end

  def print_tree
    current = {first: tree_size ** 2, step: 0}
    @lines.each do |line|
      print " " * current[:first]
      line.split(" ").each do |leaf_v|
        print leaf_v
        print " " * current[:step]
      end
      current = get_pos(current)
      puts
    end
  end

  def get_pos(parent)
    {first: (parent[:first].to_f / 2).round(), 
     step: parent[:first] - 2}
  end

  def tree_size
    return @lines.length if @lines.length.odd?
    @lines.length + 1
  end

end


Tree.new('tree.ini').print_tree

Кількість ліній не має бути кратна 2, тому метод tree_size приводить номери до odd.
Ріст бінарного дерева є степінь по 2 від висоти дерева, тобто перша гілка A має відступ: [глибина дерева] ^ 2
Кожна лінія листків має перший відступ: parent / 2, а відступи між сусідніми листами parent – 2

shockone відрефакторив мій дамп пам’яті код
https://gist.github.com/shockone/80e4fad0bb4a19c1e7f7

Там правильна відповідальність та декомпозиція методів

Вивід деревоподібної структури

Задача перетворення плоского списку нодів в ієрархічний

Потрібно перетворити

 
[
  {
    "id":1,
    "name":"firstFolder",
    "parent_id":null
  },
  {
    "id":2,
    "name":"secondFolder",
    "parent_id":1
  },
  {
    "id":3,
    "name":"thirdFolder",
    "parent_id":1
  },
  {
    "id":4,
    "name":"fourthFolder",
    "parent_id":2
  },
  {
    "id":5,
    "name":"fifthFolder",
    "parent_id":3
  }
]

У вигляд з вкладеними чілдами в паренти

[
   {
      "id":1,
      "name":"firstFolder",
      "parent_id":null
      "child":[
         {
            "id":2,
            "name":"secondFolder",
            "parent_id":1,
            "child":[
               {
                  "id":4,
                  "name":"fourthFolder",
                  "parent_id":2
               }
            ]
         },
         {
            "id":3,
            "name":"thirdFolder",
            "parent_id":1,
            "child":[
               {
                  "id":5,
                  "name":"fifthFolder",
                  "parent_id":3
               }
            ]
         }
      ]
   }
]

Спочатку потрібно сортувати по parent_id.
Це суттєво спростить алгоритм оскільки цикл поступово збиратиме чілдів до їхніх парентів один за одним.
Вистачить одного проходження циклом.

function makeHierarchie(list) {
    var nodes = list.slice();
    var popChildren;
    nodes.sort(function(a, b) {
        if (a.parent_id < b.parent_id) {
            return -1;
        }
        if (a.parent_id > b.parent_id) {
            return 1;
        }
        return 0;
    })

    popChildren = function(id) {
        var children = [];
        for (var i = nodes.length - 1; i >= 0; i--) {
            if (nodes[i] && nodes[i].parent_id == id) {
                children.push(nodes[i]);
                delete nodes[i];
            }
        }
        return children;
    };
    for (var i = nodes.length - 1; i >= 0; i--) {
        nodes[i].children = popChildren(nodes[i].id);
    }
    return nodes;
}

Цей алгоритм не підійде для випадків, коли паренти мають більші id ніж їхні чілди.
В такому випадку можна ввести level пропертю і сортувати по ній.

Задача перетворення плоского списку нодів в ієрархічний

Книга Programming Clojure by Stuart Halloway

Книга про основи Clojure читається на одному диханні та підходить для новачків у фн програмуванні. Розказуається про базові оператори, підходи, синтаксис та трішки про імутабельність даних. Кложура ліспоподібна мова і вона маленька, якщо рівняти з монстрами C++, C#. Має 4 структури даних (list), [vector], {:hash map}, #{set} з хитрими способами імутабельності. Clojure працює поверх JVM (має інтерфейси для викликання коду з Java). Також інсує варіант кложі ClojureScript котрий компілюється у JavaScript. Кложа продуманіша за js.
Переваги ClojureScript над JavaScript:

  • має неймспейси
  • більший та продуманіший вибір структур даних (list), [vector], {:hash map}, #{set}
  • вмонтована модульність у мову, а не через велосипеди у вигляді стороніх ліб (requirejs)
  • в кложі немає Hoisting, тобто змінна яка оголошена нище ніж де викликається викличе помилку. У js просто undefined.
  • є Variable Destructuring  a, b = b, a
  • перевірка на ідентичність по значенню, а не по інстансу (= [‘a’,’b’] [‘a’,’b’]) // в js буде false
  • нема приведення типів при перевірці з булевими операторами 1 == “1” // false в кложі
  • повернення з функції може робитись без return
  • Dispatch on arity
    (defn foo
      ([a] "one")
      ([a b] "two")
      ([a b c] "three"))
    (foo 1) ;; => "one"
    (foo 1 2) ;; => "two"
    (foo 1 2 3) ;; => "three"
  • Named Parameters & Defaults
  • Uniform Iteration For All Types
  • так як це промисловий лісп там є потужна система розширеня мови через defmacro

Докладніше про js vs clj

Отож оцінка книги 7/10

Книга Programming Clojure by Stuart Halloway