lion137
2019-01-03 14:34
tdudzik

@lion137: jeszcze jedno pytanie, jest sens czytać tą książkę (o algorytmach) bez znajomości matematyki dyskretnej? Tzn. czy jest ona napisana w taki sposób, że można nauczyć się algorytmów od tej praktycznej strony, bez dogłebnej analizy złożoności itp i umieć je wykorzystywać w praktyce? Oczywiście analize też chce ogarnąć, ale tak jakoś za pół roku jak już będę po matematyce dyskretnej :)

lion137

Wystarczy na bieżąco uzupełniać, plus znac podstawy.

lion137
2018-12-28 00:32

Recurrence Solver

się rozwinął. Mała biblioteczka w Pythonie do rozwiązywania problemów na Project Euler. Może być, jakiekolwiek "competitive coding", wrzuciłem to tym razem też na blog (trzeba go odświeżyć:)):
https://lion137.blogspot.com/[...]/competitive-math-helper.html
Pomysły co użytecznego dodać, mile widziane.
#theory #computation #python

Aryman1983

zsh czy fish? i co to za theme w tym terminalu? ;-)

lion137

zsh z oh_my_zsh zainstalowanym, + terminator: https://gnometerminator.blogspot.com/ :)

lion137
2018-12-19 02:19

Linear Recurrence Solver

Koniec problemów z rozwiązywaniem rekurencji:) oto mini projekcik, rozwiązywanie dowolnej liniowej rekurencji (dokładnie jednorodnej), jak, np. Fibonacci.
https://github.com/lion137/Linear_Recurrence_Solver
Napisane w C++, funkcje w pełni generyczne, przykłady w testach.
#theory #computation #C++

Dregorio

@lion137: Jakie książki? Plus mówienie, że zmiana Python na C++ to Na zdrowie to już choroba :P

lion137

Stepanov - "From Mathematics To Generic Programming", Stroustrup - "A Tour of C++ ", Stroustrup - "The C++ Programming Language 4th Ed" (to jest cegła,jej polowa, już 3/4:)). Następne na celowniku: http://elementsofprogramming.com/. Zdrowia w Nowym Roku Życzę!:)

lion137
2018-12-13 17:50

Sito Erastotenesa

Było coś obiecane z nowej książk i jest. Najpierw kod:

#include <iostream>
#include <vector>
#include <iterator>
#include <cctype>

#define RandomAccessIterator typename
#define Integer typename

template <RandomAccessIterator I, Integer N>
void mark_array(I first, I last, N factor) {
    first = false;
    while (last - first > factor) {
        first = first + factor;
        *first = false;
    }
}

template <RandomAccessIterator I, Integer N>
void erastosthenes_sieve(I first, N n) {
    I last = first + n;
    std::fill(first, last, true);
    N i(0);
    N index_square(3);
    N factor(3);
    while (index_square < n) {
        if (first[i]) {
            mark_sieve(first + index_square, last, factor);
        }
        ++i;
        index_square += factor;
        factor += N(2);
        index_square += factor;
    }
}

Szkoda, że nie można sobie już definiować konceptów / pojęć? Tylko takie haki preprocesorem, ale każdy się chyba domyśli, jaki typ dać w miejsce Integer:). Jak widać nie ma nigdzie tablicy z wartościami liczb pierwszych, nie potrzeba, można je sobie wyciągnąć z mutowanej(void) w sicie tablicy, generalnie czegokolwiek, na co będzie wskazywał Iterator(true jest na 2i + 3 miejscu).

std::vector<int> primes;
primes.push_back(2); // dodanie dwójki
    for (int i = 0; i < vec1.size(); i++){ // vec1 - wektor "wysłany" do sita 
        if (it1[i]){ // wskazuje na vec1
            primes.push_back(2 * i + 3);
        }
    }

W miarę szybkie (milion liczb pierwszych w 0.1 sek.), do matematyki rekreacyjnej i na uczelnię wystarczy:)
#theory #computation #primes

lion137

Myślałem o tym, ale chciałem zanęcić trochę concepts, które mają się pojawić niedługo:)

lion137
2018-12-13 01:04

Powinienem iść spać, ale lektura nie pozwala, polecam:
https://www.amazon.com/Mathem[...]xander-Stepanov/dp/0321942043
Na pewno jakiś algorytmik się pojawi:)
#theory #computation

no_solution_found

co w tym jest takiego ciekawego? :)

lion137

To co kochamy, abstrakcyjna algebra, matematyka, algorytmy...:)

lion137
2018-11-28 00:08

TDD in C++

Ciąg dalszy, po tam jakiś teoretycznych próbkach, napisałem coś bardziej praktycznego:): ADT geneyczny graf w C++. Niestety założenia uczyniły interfejs tłustym, jak tłusty bankowy kocur:); przytaczam klasę w całości:

/*
 * template class Graph ADT (undirected)
 */

template <class T>
class Graph {

    int V;
    int E;  
    std::unordered_map<T, std::forward_list<T>> adj;
    std::vector<T> vert;

    void construct(int _V){
        V = _V;
        E = 0;
        count = 0;
        std::forward_list<T> a;
        T el;
        for (int i = 0; i < V; i++){
            vert.push_back(el);
        }
    }

    public:

    std::unordered_map<T, bool> marked;
    int count;  // #connected components

    Graph(int _V) {
        construct(_V);
    }

    Graph(std::string fname){
        std::ifstream in(fname);
        int a, e;
        in >> a;
        in >> e;
        construct(a);
        T ver;
        std::forward_list<T> a_list;
        for (int i = 0; i < V; i++){
            in >> ver;
            vert[i] = ver;
            marked[ver] = false;
            adj[ver] = a_list;
        }
        T v, w;
        for (int i = 0; i < e; i++){
            in >> v >> w;
            add_edge(v, w); 
        }
    }

    ~Graph() {}

    int vertices() {return V;}  // num of vertices
    int edges() {return E;}     // num of edges
    T const& vertex(int v) {return vert[v];} // vertex v

    void add_edge(T _elem_v, T _elem_w){
        adj[_elem_v].push_front(_elem_w);
        adj[_elem_w].push_front(_elem_v);
        E++;
    }

    std::forward_list<T> const& adjacent(T v){
        return adj[v];
    } 

    // helper functions
    bool is_marked(T v){
        return marked[v];
    }

    void print_graph(){
        std::cout << V << " vertices, " << E << " edges"<<"\n";
            for (auto x: adj){
                std::cout << x.first << ": ";
                for (auto it = x.second.begin(); it != x.second.end(); ++it){
                    std::cout << *it << " ";
                } 
                std::cout<< "\n";
            } 
            std::cout << '\n';
    }       
};

Jak widać sporo dodatkowych struktur, jak marked, czy vert, ale za to upraszczamy kod klienta, może być umieszczony w oddzielnym module czy przestrzeni nazw (nie potrzebuje dodatkowych klas, ale coś za coś, paskudna mutowalność grafu:/). Np., sprawdzanie czy spójny(przy założeniu, że mamy działający dfs), może wyglądać tak:

template <class T>
bool is_connected(Graph<T>& g, T v){
    dfs(g, v);
    if (g.count == g.vertices()) return true;
    else return false;
}

Będa updaty:)
Podziękowania dla:

Pijak

Gnwno kod, ale zawsze można się pochwalić.

lion137

Bardzo dziękujemy za merytoryczny komentarz:-)

lion137
2018-11-22 12:16

TDD w C++

Tym razem:). Potestowałem sobie (przyda się) googletest. Powiem, że całkiem przyzwoite extreme programming wychodzi:)
I powstała, a jakże immutable list w stylu funkcyjnym, w C++ (jeśli w ogóle mając wskaźniki coś może być immutable:)). Kod, jeszcze nie uczesany:), tutaj:
https://github.com/lion137/C-Immutable-List/tree/master
#theory #c++ #functional

slsy

@lion137 nie znam się dobrze na scali, ale wydaje mi sie, to o czym napisałeś to po prostu hack pamiętający czasy Javy pozwalający na osiągnięcie sum type wykorzystując abstrakcyjny trait i jego rózne implementacje. Zresztą Dotty wprowadza bardziej elegancki mechanizm: https://dotty.epfl.ch/docs/reference/enums/adts.html . Niestety w C++ nie możesz ograniczyć możliwości dziedziczenia po interfejsie ImmutableList tak jak w Scali, więc musisz się spodziewać, że ktoś będzie mógł stworzyć własną implementację tego typu.

lion137

@jarekr000000: Under development, may change:)

lion137
2018-11-05 22:44

Kto mówi, że

W C nie da się używać TDD:) Oto taki sobie side project, toy project w C: generic linked list (via void pointers). Napisany właśnie w stylu TDD:
https://github.com/lion137/C_[...]ee/master/generic_linked_list
A po co to? Palce mi się zastały od tego pisania w Pythongu, musiałem coś w normalnym języku stworzyć:-P
#C #theory

vpiotr

Czulem ze te intuicyjne inaczej nazwy maja dluga historie.

lion137

Czyli sposób jaki został wybrany w Common Lisp. Osobiście taki design mi się podoba, mamy swoje is_empty które się z tym nie kłóci. Natomiast, rzeczywiście, w dzisiejszych czasach, programiści spodziewają się, że jak dojdzie do pop z pustej kolekcji, to nie dzieje się dobrze.