MetaProg

Описание: Разработка и отладка приложений. Упор на 3D-графику.

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3579
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#67 dyvniy » Сб, 23 июня 2018, 15:57:48

Оказывается парсить инфоксную запись в дерево не сложнее, чем строить из дерева.
http://pascal.net.ru/Алгоритмы на графах и деревьях
Вот что у меня получилось на питоне:

Код: Выделить всё

class Tree:
    L = None
    R 
= None
    data 
= None
    def __init__
(self, d=None):
        self.data = d
    def print
(self, t, level=0):
        if t.L:
            self.print(t.L, level + 1)
        print(str(level) + ' ' + str(t.data))
        if t.R:
            self.print(t.R, level + 1)
def read(s):
    return s.pop()
def parce(s):
    a = []
    for w in s:
        a.insert(0, w)
    return infix(a)
def infix(s):
    c = read(s)
    if c == '(':
        p = Tree()
        p.= infix(s)
        p.data = read(s)
        p.= infix(s)
        read(s) # '>'
    else:
        p = Tree(c)
    return p
#t = infix([')', 2, '+', 3, '('])
= parce('(2+(3*(4-5)))')
t.print(t

Тут главное чтобы присутствовали все скобки.
Без них работать не будет.
Думаю с префиксной и постфиксной записью ещё проще.
Отсюда, переделано
http://pascal.net.ru/Алгоритмы на графах и деревьях
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3579
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#68 dyvniy » Ср, 11 июля 2018, 16:57:51

Бинарные деревья - это просто
https://habr.com/post/267855/
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3579
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#69 dyvniy » Вт, 17 июля 2018, 14:29:39

Драйвера сетевух, неофициальные.
https://www.ath-drivers.eu/atheros-wireless-drivers.html
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3579
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#70 dyvniy » Чт, 19 июля 2018, 18:55:09

Сортировка двоичным деревом.
Идеальна для потоков.
Требует 4н памяти.
https://ru.wikipedia.org/wiki/Сортировка_с_помощью_двоичного_дерева
Спойлер
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например из файла, сокета или консоли).

Содержание
1 Алгоритм
2 Эффективность
3 Примеры реализации
4 См. также
Алгоритм
1. Построение двоичного дерева.

2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.

Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Соответственно, для n объектов сложность будет составлять O(n log(n)), что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n²).

При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.

Примеры реализации
В простой форме функционального программирования на Haskell данный алгоритм будет выглядеть так:

data Tree a = Leaf | Node (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x (Node t y t') | x <= y = Node (insert x t) y t'
insert x (Node t y t') | x > y = Node t y (insert x t')

flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node t x t') = flatten t ++ [x] ++ flatten t'

treesort :: Ord a => [a] -> [a]
treesort = flatten . foldr insert Leaf
Реализация на C++14:

Код: Выделить всё

#include <memory>
#include <cassert>
#include <algorithm>

#include <vector>
#include <iostream>

using namespace std;

// класс, представляющий бинарное дерево
class BinaryTree
{
protected:
  
// узел бинарного дерева
  
struct BinaryTreeNode
  
{
    
shared_ptr<BinaryTreeNodeleftright// левое и правое поддерево
    
int key// ключ
  
};

  
shared_ptr<BinaryTreeNodem_root// корень дерева
  
protected:
  
// рекурсивная процедура вставки ключа
  // cur_node - текущий узел дерева, с которым сравнивается вставляемый узел
  // node_to_insert - вставляемый узел
  
void insert_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const shared_ptr<BinaryTreeNode>& node_to_insert)
  {
      
assert(cur_node != nullptr);
      
// сравнение
      
bool insertIsLess node_to_insert->key cur_node->key;
      if(
insertIsLess)
      {
        
// вставка в левое поддерево
        
if(cur_node->left == nullptr)
          
cur_node->left node_to_insert;
        else
          
insert_recursive(cur_node->leftnode_to_insert);
      }
      else
      {
        
// вставка в правое поддерево
        
if(cur_node->right == nullptr)
          
cur_node->right node_to_insert;
        else
          
insert_recursive(cur_node->rightnode_to_insert);
      }
  }

public:
  
void insert(int key)
  {
    
shared_ptr<BinaryTreeNodenode_to_insert(new BinaryTreeNode);
    
node_to_insert->key key;

    if(
m_root == nullptr)
    {
        
m_root node_to_insert;
        return;
    }

    
insert_recursive(m_rootnode_to_insert);
  }

public:
  
typedef function<void(int key)> Visitor;

protected:
  
// рекурсивная процедура обхода дерева
  // cur_node - посещаемый в данный момент узел
  
void visit_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const Visitorvisitor)
  {
    
assert(cur_node != nullptr);

    
// сначала посещаем левое поддерево
    
if(cur_node->left != nullptr)
      
visit_recursive(cur_node->leftvisitor);

    
// посещаем текущий элемент
    
visitor(cur_node->key);

    
// посещаем правое поддерево
    
if(cur_node->right != nullptr)
      
visit_recursive(cur_node->rightvisitor);
  }

public:
  
void visit(const Visitorvisitor)
  {
    if(
m_root == nullptr)
      return;
    
visit_recursive(m_rootvisitor);
  }
};

int main()
{
  
BinaryTree tree;
  
// добавление элементов в дерево
  
vector<intdata_to_sort = {1027314732};
  for(
int value data_to_sort)
  {
    
tree.insert(value);
  }
  
// обход дерева
  
tree.visit([](int visited_key)
  {
    
cout<<visited_key<<" ";
  });
  
cout<<endl;

  
// результат выполнения: 2 3 7 7 10 14 32
  
return 0;
}
 

Пример создания бинарного дерева и сортировки на языке Java:

Код: Выделить всё

// Скомпилируйте и введите java TreeSort
class Tree {
   public 
Tree left;            // левое и правое поддеревья и ключ
   
public Tree right;
   public 
int key;

   public 
Tree(int k) {        // конструктор с инициализацией ключа
      
key k;
   }

/*  insert (добавление нового поддерева (ключа))
    сравнить ключ добавляемого поддерева (К) с ключом корневого узла (X).
    Если K>=X, рекурсивно добавить новое дерево в правое поддерево.
    Если K<X, рекурсивно добавить новое дерево в левое поддерево.
    Если поддерева нет, то вставить на это место новое дерево
*/
   
public void insertTree aTree) {
     if ( 
aTree.key key )
        if ( 
left != null left.insertaTree );
        else 
left aTree;
     else
        if ( 
right != null right.insertaTree );
        else 
right aTree;
   }

/*  traverse (обход)
    Рекурсивно обойти левое поддерево.
    Применить функцию f (печать) к корневому узлу.
    Рекурсивно обойти правое поддерево.
*/
   
public void traverse(TreeVisitor visitor) {
      if ( 
left != null
            
left.traversevisitor );

      
visitor.visit(this);

      if ( 
right != null 
            
right.traversevisitor );
   }
}

interface 
TreeVisitor {
  public 
void visit(Tree node);
};

class 
KeyPrinter  implements TreeVisitor {
  public 
void visit(Tree node) {
      
System.out.println" " node.key );
  }
};

class 
TreeSort {
  public static 
void main(String args[]) {
     
Tree myTree;
     
myTree = new Tree);       // создать дерево (с ключом)
     
myTree.insert( new Tree) );  // присоединять поддеревья
     
myTree.insert( new Tree) );
     
myTree.traverse(new KeyPrinter());
  }
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3579
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#71 dyvniy » Вт, 25 июня 2019, 13:47:54

Колмагоровская сложность
https://ru.wikipedia.org/wiki/Колмогоровская_сложность
Это чёткий научный критерий, которым можно чмырить современное монструозное ПО.
Надо этим заняться, в свободное время)

Алгоритмическую теорию информации надо выучить
https://ru.wikipedia.org/wiki/Алгоритмическая_теория_информации

Это тоже почитать
https://ru.wikipedia.org/wiki/Эффект_Матфея
Изображение

dyvniy M
Автор темы, Администратор
Администратор
Аватара
dyvniy M
Автор темы, Администратор
Администратор
Возраст: 41
Репутация: 1
Лояльность: 1
Сообщения: 3579
Зарегистрирован: Ср, 10 октября 2012
С нами: 11 лет 5 месяцев
Профессия: Программист
Откуда: Россия, Москва
ICQ Сайт Skype ВКонтакте

#72 dyvniy » Вт, 22 октября 2019, 14:59:43

Алан Кей, статья 2016г
https://habr.com/ru/company/hexlet/blog/303754/
Спойлер
Алан Кэй, создатель ООП, про разработку, Лисп и ООП
Автор оригинала: mythz
Блог компании Hexlet,
Программирование,
Lisp,
ООП
Перевод
image

Если вы никогда не слышали про Алана Кэя, то как минимум слышали его знаменитые цитаты. Например, это высказывание 1971 года:
The best way to predict the future is to invent it.
Лучший способ предсказать будущее это изобрести его.


У Алана очень яркая карьера в информатике. Он получил Премию Киото и Премию Тьюринга за работу над парадигмой объектно-ориентированного программирования. Он был одним из первопроходцев в области персональных компьютеров и графического интерфейса, он разработал Smalltalk — один из первых самых влиятельных языков программирования всех времен.

У нас в Хекслете, особенно в чате, постоянно поднимается вопрос «что такое ООП» и «что имел ввиду Алан Кэй на самом деле». В этой заметке собраны интересные цитаты Алана о состоянии современной разработки, ООП и языке Лисп.

Про разработку ПО

Алан Кэй считает, что компьютерная революция еще впереди (The Real Computer Revolution Hasn’t Happened Yet), и разработка ПО развивается обратно пропорционально Закону Мура: железо улучшается каждый год, а софт становится раздутее без надобности:
проблема в слабых, плохо масштабируемых идеях и инструментах, лени, нехватке знаний и т.д.


Эту ситуацию хорошо описывает короткая шутка:
What Andy giveth, Bill taketh away
Энди дал, Билл взял


Энди Грув, CEO Интела, и Билл Гейтс, тогдашний CEO Майкрософта.

Улучшение текущего состояние разработки было целью исследовательского проекта STEPS Toward The Reinvention of Programming (pdf). Задача — достигнуть «Закона Мура» в выразительности через «сокращение количества необходимого кода в 100, 1000, 10000 раз и больше».

В его открывающем глаза докладе Programming and Scaling (видео) эта тема рассматриватеся подробнее. По мнению Алана, software engineering заглох и становится забытой наукой, которая не успевает за железом, другими науками и инженерными дисциплинами. Большие проекты стали свалками кода и достигли такой точки, когда никто не способен понять 100 миллионов строк кода MS Vista или MS Word. А в реальности кода в таких проектах должно быть на порядок меньше.

Алан считает Интернет, протоколы TCP/IP, интерпретаторы LISP, Nile (Math DSL for Vector Graphics) и OMeta (OO PEG) (PDF) примерами элегантного софта с минимальным кодом.

Он называет Интернет (TCP/IP) одним из немногих масштабных софтверных проектов, который был правильно разработан, и его уровень сложности — в балансе с уровнем комплексности (complication vs. complexity). Этот проект, в котором меньше 20 тысяч строк кода, работает как живая, динамическая система, способная поддерживать миллиарды узлов, и она ни разу не отключалась после первого запуска в сентябре 1969 года. Мы просто перестали считать Интернет нормальным софт-проектом, созданным людьми:
Интернет разработан настолько хорошо, что многие относятся к нему как к естественному ресурсу, вроде Тихого океана, а не к плоду человеческого труда. Когда в последний раз мы видели настолько стабильную, четкую технологию без ошибок? Для сравнения, Веб это ерунда. Веб создан дилетантами.


Про объектно-ориентированное программирование

Первое, что меня интересовало, это его первоначальное видение ООП. Его опыт в микробиологии сыграл важную роль:
Я считал объекты чем-то вроде биологических клеток, и/или отдельных компьютеров в сети, которые могут общаться только через сообщения.


и опыт в математике:
Мой опыт в математике заставил меня понять, что каждый объект может иметь несколько алгебр, они могут объединяться в семейства, и это может быть очень полезным.


Идеи позднего свзяывания и мощных мета-возможностей LISPa:
Вторая фаза — это понимание LISPa и использование этого понимания для создания более удобных, маленьких и мощных структур и более позднее связывание.


И вскоре Алан стал поддерживать идею того, что динамические языки это будущее разработки ПО (pdf). В частности, ему важна легкость изменения:
Позднее связывание позволяет с меньшими усилиями встраивать в проект идеи, которые возникли позже в процессе разработки (по сравнению с системами с более ранним связыванием вроде C, C++, Java, и пр.)


И потенциал для изменений на ходу и более быстрых итераций:
Одна из ключевых идей: система должна продолжать работу во время тестирования о особенно во время произведения изменений. Даже крупные изменения должны быть поэтапными и занимать не больше доли секунды.


который отсутствует в статически-типизированных языках:
Если вы используете языки с ранним связыванием, как это делает большинство, то вы запираете себя в рамки того, что уже написали. Переформулировать с легкостью уже не получится.


Удивительно, но его мысл про ООП ограничивались этим:
ООП для меня это сообщения, локальное удержание и защита, скрытие состояния и позднее связывание всего. Это можно сделать в Smalltalk и в LISP.


И ничего про наследование. Это не тот ООП, который мы знаем сегодня:
Мне жаль, что давным давно я использовал термин «объект» для этой темы, потому что из-за этого многие люди фокусируются на меньшей из идей.


Большая идея, которой не хватает современным статически-типизированным ОО-языкам:
Большая идея это «сообщения»


Он считает, что нужно фокусироваться на сообщениях, слабой связи и взаимодействии модулей, а не на внутренностях объекта:
Ключ к созданию хороших масштабируемых систем это проработка механизмов общения модулей, а не проработка их внутренних свойств и поведения.


Статически-типизированные языки кажутся ему неполноценными:
Я не против типов, но мне не знакома ни одна система типов, которая не вызывала бы боли. Так что мне все еще нравится динамическая типизация.


Некоторые популярные языки сегодня используют идеи передачи сообщений Smalltalk'а, позднее связывание, и конструкцию doesNotUnderstand: forwardInvocation в Objective-C, method_missing в Ruby и noSuchMethod в Гугловском Dart.

Уничтожить все и создать что-то лучше

У Алана есть интересная теория о развитии информатики:
Мне кажется, что существует только один тип компьютерной науки, и это наука похожа на строительство мостов. Кто-то строит мосты, а кто-то разрушает их и создает новые теории. И нам нужно продолжать строить мосты.


Про LISP

Алан Кэй считает Лисп
лучшим языком программирования всех времен


И что его должен изучать каждый выпускник в computer science:
Большинство людей, получающих дипломы в CS, не понимают всей важности Lisp. Lisp это самая важная идея в computer science.


Про правильную атмосферу и контекст

Он часто вспоминает об уникальной атмосфере в Xerox PARC и ARPA, где «видение важнее целей» и «финансирование людей, а не проектов».
Точка зрения дает 80 баллов IQ.


Алан Кэй считает:
История ARPA/PARC демонстрирует, как комбинация видения, скромного финансирования, правильного контекста и процесса может волшебным образом рождать новые технологии, которые не только влияют на цивилизацию, но и создают огромную ценность для общества.


И это правда. Взгляните на впечатляющий список изобретений PARC, многие из которых сыграли очень важную роль в развитии нашего мира. Например:
Лазерные принтеры
Объектно-ориентированное программирование / Smalltalk
Персональные компьютеры
Ethernet / распределенные вычисления
GUI / компьютерная мышь / WYSIWYG


А в ARPA создали ARPANET, который стал прародителем Интернета.

Интерпретатор лиспа на питоне
https://habr.com/ru/post/115206/
Изображение


Название раздела: Программирование (под Desktop и Android)
Описание: Разработка и отладка приложений. Упор на 3D-графику.

Быстрый ответ


Введите код в точности так, как вы его видите. Регистр символов не имеет значения.
Код подтверждения
:) ;) :hihi: :P :hah: :haha: :angel: :( :st: :_( :cool: 8-| :beee: :ham: :rrr: :grr: :* :secret: :stupid: :music: Ещё смайлики…
   

Вернуться в «Программирование (под Desktop и Android)»

Кто сейчас на форуме (по активности за 15 минут)

Сейчас этот раздел просматривают: 6 гостей