dancingrobot84


Algorithms 101: Basic Data Structures Pt. 1

Aug 12, 2015 in Algorithms

This article is intended to cover some basic data structures: arrays, linked lists, stacks and queues; their applications and implementations in Java. Source code of implementations used in this article is available on Github.

Abstract and concrete data structures

Abstract data structure is a mathematical model, an interface declaring desired behaviour. Concrete data structure is an implementation of such interface. For example, collection or container is an abstract data structure. It says only that some items of particular type are stored inside it and declares methods for accessing and updating them. Array and list, on the other side, are concrete data structures. They describe the way items are stored (in continuous memory chunk versus as a chain of pointers) and implement methods declared in collection’s interface.

Collections

Collection (Container) is an abstract data structure. It holds several items of some specified type T and offers methods for accessing and updating them. The following interface will be used throughout this article to describe containers:

package com.dancingrobot84.algorithms.datastructures;

public interface Collection<T> {
    /** Insert item at the beginning of collection **/
    void append(T item);

    /** Insert item at the end of collection **/
    void prepend(T item);

    /** Insert item at specified place of collection **/
    void insert(int index, T item);

    /** Retrieve item at specified place **/
    T get(int index);

    /** Return the size of collection **/
    int size();

    /** Remove item at specified place from collection **/
    void remove(int index);
}

Arrays

Array is a container that holds a number of items in contiguous area of memory. In its simplest form, static array, the capacity of a container is set up at the moment of its creation and may not be changed. Dynamic arrays, however, can grow automatically when current capacity is exceeded.

Arrays are used both on its own and as an underlying data structure for more sophisticated structures, e.g. heaps, associative arrays and adjacency matrices.

Arrays are supported out of the box in overwhelming majority of modern programming languages. Usually static arrays present as a syntactic feature. Here is an example of creating static array of 10 ints in Java:

int[] arrayOfInts = new int[10];

Dynamic arrays often shipped as utility classes of standard library (std::vector in C++ and ArrayList in Java).

Dynamic array implementation

Idea: let’s start with a small static array. If there is no free space left to insert new item, then allocate new static array with extended capacity and copy all items from the old array into the new one. It is proven that allocating new array twice as large as the old one gives you O(1) amortized complexity of inserting new item at the end of an array.

Here is a simple implementation of dynamic array in Java:

package com.dancingrobot84.algorithms.datastructures.impl;

import java.util.Arrays;
import com.dancingrobot84.algorithms.datastructures.Collection;

public class DynamicArray<T> implements Collection<T> {

    public static <T> Collection<T> empty() {
        return new DynamicArray<T>();
    }

    @Override
    public void append(T item) {
        ensureCapacity(size + 1);
        items[size] = item;
        size += 1;
    }

    @Override
    public void prepend(T item) {
        ensureCapacity(size + 1);
        System.arraycopy(items, 0, items, 1, size);
        items[0] = item;
        size += 1;
    }

    @Override
    public void insert(int index, T item) {
        assert index >= 0 : "Index is out of range: " + Integer.toString(index);
        size = Math.max(index + 1, size + 1);
        ensureCapacity(size);
        System.arraycopy(items, index, items, index+1, size-index-1);
        items[index] = item;
    }

    @Override
    public void remove(int index) {
        checkRange(index);
        System.arraycopy(items, index+1, items, index, size-index-1);
        size -= 1;
    }

    @Override
    public T get(int index) {
        checkRange(index);
        return (T)items[index];
    }

    public void set(int index, T item) {
        checkRange(index);
        items[index] = item;
    }

    @Override
    public int size() {
        return size;
    }

    private int size = 0;
    private Object[] items = new Object[1];

    private DynamicArray() {
        // Disable subclassing
    }

    private void ensureCapacity(int capacity) {
        if (items.length < capacity) {
            int enlargeTo = Math.max(2 * items.length, capacity);
            items = Arrays.copyOf(items, enlargeTo);
        }
    }

    private void checkRange(int index) {
        assert index >= 0 && index < size : "Index is out of range: " + Integer.toString(index);
    }
}

Advanced implementation can shrink array when the number of items drops below some point, say, half of capacity. However, it should be implemented with cautious, because too eager behaviour can cause drastic change of complexity. Imagine an array which shrinks itself in half as soon as the number of items drops below half of capacity; when there are n/2 items and you remove one, then insert one and repeat these actions m times the overall complexity will be O(mn). It’s better to shrink array by lesser amount, a third or a fourth of capacity for example.

Linked lists

Linked list is also a container. It stores its items in nodes. Each node consists of at least two fields: a value to store and a pointer to another node. Nodes are chained one to another and, thus, can be located in arbitrary places of memory (contrary to arrays). Linked lists can be divided into several groups according to the number of pointers in its nodes: singly-linked, doubly-linked and multiply-linked.

Linked lists can be used either on its own or as an underlying data structure for such ADTs as adjacency lists, stacks, queues and for collision resolution in hash tables.

Linked lists are present in many programming languages, for example, std::list in C++ and LinkedList in Java. Usually they are implemented as doubly-linked lists.

Doubly-linked list implementation

Idea: key idea of this implementation is to use head and tail sentinel nodes. They are constant for particular linked list object; they point to each other when the list is empty and to the first/last node otherwise. Head sentinel’s prev is always null, just as tail sentinel’s next. Main purpose of such sentinel nodes is to save us time and energy playing around null checks: this way we can be sure that list always has head and tail nodes, though they’re merely decorative.

Here is a simple implementation of doubly-linked list in Java:

package com.dancingrobot84.algorithms.datastructures.impl;

import java.util.Arrays;
import com.dancingrobot84.algorithms.datastructures.Collection;

public class DoublyLinkedList<T> implements Collection<T> {

    public static <T> Collection<T> empty() {
        return new DoublyLinkedList<T>();
    }

    @Override
    public void append(T item) {
        insertBefore(tail, new Node(item));
        size++;
    }

    @Override
    public void prepend(T item) {
        insertAfter(head, new Node(item));
        size++;
    }

    @Override
    public void insert(int index, T item) {
        Node target = searchForInsertion(index);
        insertBefore(target, new Node(item));
        size++;
    }

    @Override
    public void remove(int index) {
        Node target = search(index);
        target.prev.next = target.next;
        target.next.prev = target.prev;
        size--;
    }

    @Override
    public T get(int index) {
        return search(index).value;
    }

    @Override
    public int size() {
        return size;
    }

    private class Node {
        T value;
        Node prev;
        Node next;

        public Node(T value) {
            this.value = value;
        }
    }

    private final Node head = new Node(null);
    private final Node tail = new Node(null);
    private int size = 0;

    private DoublyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    private void insertAfter(Node target, Node node) {
        node.next = target.next;
        node.prev = target;
        if (target.next != null) {
            target.next.prev = node;
        }
        target.next = node;
    }

    private void insertBefore(Node target, Node node) {
        node.next = target;
        node.prev = target.prev;
        if (target.prev != null) {
            target.prev.next = node;
        }
        target.prev = node;
    }

    private Node search(int index) {
        Node target = searchForInsertion(index);
        assert target != head && target != tail : "Item at index " + Integer.toString(index) + " is not found";
        return target;
    }

    private Node searchForInsertion(int index) {
        assert index >= 0 && index <= size : "Index is out of range: " + Integer.toString(index);
        int mid = size / 2;
        return index > mid ? searchBackward(size - index) : searchForward(index);
    }

    private Node searchForward(int index) {
        Node target = head.next;
        int position = 0;
        while (target != tail && position < index) {
            target = target.next;
            position++;
        }
        return target;
    }

    private Node searchBackward(int index) {
        Node target = tail;
        int position = 0;
        while (target != head && position < index) {
            target = target.prev;
            position++;
        }
        return target;
    }
}

Complexity comparison

Here is complexity comparision of dynamic array and doubly linked list for all operations in Collection interface. As you see, linked list wins on prepending, while dynamic array wins on random access.

Operation Array Linked list
append(item) Oam(1) O(1)
prepend(item) O(n) O(1)
insert(index, item) O(n) O(n)
remove(index) O(n) O(n)
get(index) O(1) O(n)
size() O(1) O(1)
Additional space used O(n) O(n)

Stacks and queues

Stacks and queues are abstract data structures that support limited access to their elements: they allow only appending and retrieval. They are distinguished by the particular retrieval order they support: stack is LIFO container (“last-in-first-out”) and queue is FIFO container (“first-in-first-out”). Interfaces of stack and queue are presented below:

package com.dancingrobot84.algorithms.datastructures;

public interface Stack<T> {
    /** Insert new item at the end of stack **/
    void push(T item);

    /** Retrieve and remove item from the end of stack **/
    T pop();

    /** Return number of elements in stack **/
    int size();
}
package com.dancingrobot84.algorithms.datastructures;

public interface Queue<T> {
    /** Insert new item at the end of queue **/
    void enqueue(T item);

    /** Retrieve and remove item from the beginning of queue **/
    T dequeue();

    /** Return number of elements in queue **/
    int size();
}

Both stacks and queues are widely applicable in modern software engineering. Examples of stack usage are:

  • Function calls are stored in stack while program is executed
  • Many parsing and expression evaluation algorithms use stacks to hold values or currently processed lexemes
  • JVM is a stack-based virtual machine. It does not use registers; instead it stores all variables on stack

Examples of queue usage are:

  • Concurrent applications; for example, concurrent access to some resource means that there is a queue of requests and they are processed in order
  • Buffering and data transfer

Usually stacks and queues are implemented as adapters to another containers, for example, linked lists or dynamic arrays. In Java Queue is an interface implemented by classes ArrayDeque, LinkedList and others. Stack is a concrete class, but it is obsolete. It is recommended to use interface Deque instead and its implementations as it has methods of both stacks and queues.

Stack implementation

Explanations skipped as the implementation is quite straightforward.

package com.dancingrobot84.algorithms.datastructures.impl;

import com.dancingrobot84.algorithms.datastructures.Collection;
import com.dancingrobot84.algorithms.datastructures.Stack;

public class ArrayStack<T> implements Stack<T> {

    public static <T> Stack<T> empty() {
        return new ArrayStack<T>();
    }

    @Override
    public void push(T item) {
        items.append(item);
    }

    @Override
    public T pop() {
        assert items.size() > 0 : "Stack is empty";
        int index = items.size() - 1;
        T item = items.get(index);
        items.remove(index);
        return item;
    }

    @Override
    public int size() {
        return items.size();
    }

    private Collection<T> items = DynamicArray.empty();

    private ArrayStack() {
        // Disable subclassing
    }
}

Implementation of stack using doubly-linked list will be exactly the same. Complexity of operations is O(1) amortized for array and O(1) for list.

Queue implementation using dynamic array

Idea: this is standard two-pointer implementation of a queue.

Because in queue we need to retrieve element from the beginning of a queue, it is inefficient to shift the whole array back each time dequeue is called. Instead lets create a pointer to location where the real beginning of a queue is and shift it forward on dequeue. On enqueue, however, lets insert new item not just at the end of an array, but, if possible, in the free place between array’s beginning and queue’s beginning. In order to achieve this lets create another pointer to store location of the real end of a queue. When this two pointers meet lets relocate the whole array so that queue’s beginning and end will be the same as underlying array’s are.

package com.dancingrobot84.algorithms.datastructures.impl;

import com.dancingrobot84.algorithms.datastructures.Queue;

public class ArrayQueue<T> implements Queue<T> {

    public static <T> Queue<T> empty() {
        return new ArrayQueue<T>();
    }

    @Override
    public void enqueue(T item) {
        if (items.size() == queueEnd) {
            if (queueStart == 0) {
                items.append(item);
            } else {
                queueEnd = 0;
                items.set(0, item);
            }
            queueEnd++;
        } else {
            items.set(queueEnd, item);
            queueEnd++;
            if (queueEnd == queueStart) {
                relocate();
            }
        }
    }

    @Override
    public T dequeue() {
        assert queueEnd != queueStart : "Queue is empty";

        T item;
        item = items.get(queueStart);
        queueStart++;

        if (queueStart == queueEnd) {
            queueStart = 0;
            queueEnd = 0;
        } else if (queueStart == items.size()) {
            queueStart = 0;
        }

        return item;
    }

    @Override
    public int size() {
        if (queueEnd == queueStart) {
            return 0;
        } else if (queueEnd > queueStart) {
            return queueEnd - queueStart;
        } else {
            return items.size() - (queueStart - queueEnd);
        }
    }

    private DynamicArray<T> items = (DynamicArray) DynamicArray.empty();
    private int queueStart = 0;
    private int queueEnd = 0;

    private ArrayQueue() {
        // Disable subclassing
    }

    private void relocate() {
        DynamicArray<T> newItems = (DynamicArray) DynamicArray.empty();

        queueEnd--;
        for (int i = queueStart; i != queueEnd; i = (i+1) % items.size()) {
            newItems.append(items.get(i));
        }
        newItems.append(items.get(queueEnd));

        items = newItems;
        queueStart = 0;
        queueEnd = items.size();
    }
}

Complexity of this solution is O(1) amortized for both operations.

Queue implementation using doubly-linked list

This implementation is much easier, because in doubly-linked list we can remove item from both beginning and end in O(1).

package com.dancingrobot84.algorithms.datastructures.impl;

import com.dancingrobot84.algorithms.datastructures.Collection;
import com.dancingrobot84.algorithms.datastructures.Queue;

public class ListQueue<T> implements Queue<T> {

    public static <T> Queue<T> empty() {
        return new ListQueue<T>();
    }

    @Override
    public void enqueue(T item) {
        items.append(item);
    }

    @Override
    public T dequeue() {
        assert items.size() > 0 : "Queue is empty";
        T item = items.get(0);
        items.remove(0);
        return item;
    }

    @Override
    public int size() {
        return items.size();
    }

    private Collection<T> items = DoublyLinkedList.empty();

    private ListQueue() {
        // Disable subclassing
    }
}

Complexity of this solution is O(1) for both operations.


  1. Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms

  2. Skiena. The Algorithm Design Manual

Let's write DBMS in Haskell: project management with Cabal

Mar 8, 2015 in Programming

Last term has passed and I’ve got a lot of time to spend on writing master thesis and doing other stuff. I’ve decided that improving FP and Haskell skills is the thing I’d like to do and the best way to do this is to write a couple of small, but rather serious projects. We’ve had some interesting ones in university, but, to be honest, my architecture decisions were not so good sometimes and by the end of a term projects become surrounded with all kinds of workarounds and it was too late to rewrite them from scratch. Now I have no hard deadlines and requirements so why not write these projects properly?

Projects I’m talking about are database management system (like Sqlite) and virtual machine implementation with JIT compilation and some simple optimizations (like Hotspot). The former I wrote more than a year ago, the latter was written a couple of months ago. I’ll start with the first one because it has been written in Haskell, so it will be easier to fix my previous mistakes. Another reason is that I’m starting to forget things about DBMS and it would be great to freshen them up.

I will store my code on Github and keep the link to the state of project by the time of writing a post on top of it. Current specifications and requirements are here; in short: it will be a simple database supporting three fixed-size types (ints, doubles and varchars), b-tree indexes, cross joins and ‘vacuum’ operation. I will cover internal architecture more in latter posts; now I’m going to talk about project management with Cabal.

Cabal is recommended1 build tool for Haskell. Its name stays for “Common Architecture for Building Applications and Libraries”. It is split in two parts: cabal-install package which contains cabal executable and Cabal library which contains some advanced things for complex builds. Be sure to have the former installed in order to proceed with the instructions below.

Project configuration

Creating new Cabal project is simple: create new directory, cd into it, run

$ cabal init

and answer some questions about your project. A couple of files will be generated: <your-project>.cabal, a declarative definition of your project’s build and Setup.hs, a build script. Here is possible contents of generated .cabal file:

-- Initial my-project.cabal generated by cabal init.  For further
-- documentation, see http://haskell.org/cabal/users-guide/

name:                my-project
version:             0.1.0.0
synopsis:            My precious project
-- description:
license:             MIT
license-file:        LICENSE
author:              Nikolay Obedin
maintainer:          dancingrobot84@gmail.com
-- copyright:
-- category:
build-type:          Simple
-- extra-source-files:
cabal-version:       >=1.10

executable my-project
  main-is:             Main.hs
  -- other-modules:
  -- other-extensions:
  build-depends:       base >=4.7 && <4.8
  -- hs-source-dirs:

-- ... other sections

Syntax is pretty straightforward: indentation is used to distinguish entries and their contents, “--” to comment things out. Global properties are on top of the file, they are pretty simple too: name of your project, version, short description, license, category on Hackage, etc. One interesting field is build-type which is used to tell Cabal what type of build is going to be used: Simple is for builds configured via .cabal file, Custom is for more complex builds using Setup.hs2. I’ll stick with Simple build type for now and then.

A set of sections is placed after global properties. Each section should belong to one of four types: library, executable, test suite or benchmark. I’m going to take a look at first three of them.

Library section and common settings

library
  other-modules:    Foo.Bar
  exposed-modules:  Foo.Baz
  hs-source-dirs:   src
  default-extensions:
        CPP, ForeignFunctionInterface
  build-tools:      alex, happy
  build-depends:
        base
      , array

Library is a collection of Haskell modules that can be reused by other libraries and applications. Project may contain at most one library, its name matches the name of a project. Each module of a library should be either in other-modules entry or exposed-modules entry based on its visibility to end user – the latter are visible and the former aren’t. If you chose library in cabal init then all your existent modules have been automatically added to exposed-modules.

The rest of settings in this example are common to all types of sections. hs-source-dirs is comma-separated list of directories where Cabal will search for source files. default-extensions is list of language extensions enabled by default for all source files.

build-tools is list of programs used to process specific files before compiling them. Note that these executables for some reason ARE NOT installed automatically3, you should do it manually. In this example alex is used to process files with .x extension and happy processes files with .y extension to generate lexer and parser respectively.

build-depends is list of packages your project depends on. Each package may be constrained4, but be careful with it as inadequate constraints may lead Cabal to inability of installing your dependencies. Usually, I use Stackage to constrain dependencies for me while leaving them unconstrained in build-depends. However, this approach is useful only if you’re developing internal library or application – if you’re going to publish it on Hackage then you should set sane constraints to your dependencies, but, I guess, by that time you will know these things better than me:)

Executable and Test-Suite sections

executable my-program
  hs-source-dirs:   src
  build-depends:    base
  main-is:          Main.hs

Executable is a standalone program. Its name is not required to be the same as package’s one and project may have many executables. The only thing it requires is to have an entry point which is main :: IO () function. A source file having this function should be specified in main-is entry.

test-suite tests
  type:             exitcode-stdio-1.0
  main-is:          Main.hs
  hs-source-dirs:   test
  build-depends:
        base
      , hspec

Project also may contain many test suite sections and each of these sections should use one of supported testing interfaces. The interface used by particular test-suite is defined in its type field. Cabal supports two testing interfaces out of the box: exitcode-stdio and detailed. I prefer the first one because it is simpler – it just compiles and runs your test application checking its exit code: if its non-zero then test has failed. The only required field for exitcode-stdio is main-is which means exactly the same thing as in executable section - it is a source file of your test program.

Installing dependencies, building and running

Now that the project is configured it is time to build it. But first you need to install the dependencies stated in build-depends fields. I strongly recommend that you use Cabal sandboxes to avoid possible conflicts. To create new sandbox run:

$ cabal sandbox init

and then install dependencies:

$ cabal install --dependencies-only

If you’re using build-tools install them manually:

$ cabal install alex happy <any-other-build-tool>

Now you can build your project:

$ cabal configure && cabal build

Then you can test it and run:

$ cabal test && cabal run

If you want to try something in ghci you can start it with all dependencies of your project available by running:

$ cabal repl

These are the commands you’re going to use rather frequently; the rest of available commands and flags can be found by running cabal --help.

In the end

Haskell is a great language and Cabal is a sane build tool if it’s used properly. Use sandboxes and careful version constraints, do not install many packages in global scope – remember that Cabal is not a package manager and you’ll be fine.


Things I Read This Week, Pt. 2

Aug 4, 2014 in Programming

Actually I wanted to make a new post for this series every week, but I’ve been pretty busy working full-time at JetBrains on Scala plugin and spending my free time on Purescript Express.js bindings and Coursera assignments. So this is actually what I’ve been reading over the last month.

Phantom types for extra safety in Haskell

Part 1 Part 2

Great articles about interesting technique of taking some errors down to compile time. Though I prefer GADTs approach, Phantom types are pretty cool too.

Type classes: confluence, coherence and global uniqueness

Link

This post is about surprising behaviour of GHC when resolving type-class constraints: though it requires for type-class instances to be non-overlapping, it doesn’t check this constraint eagerly (it may increase compile time). Thus if you have different instances of a type-class in different modules you can accidentally write a program that will use both of this instances simultaneously. And if one of these instances has been kept by mistake (e.g. forgot to delete old code) this can lead to strange runtime errors which would be not so easy to locate. That’s why this is a “must-know” thing for every haskeller.

GHC plans for 7.10.1 (+ 7.8.3 is out)

Reddit discussion

Seems like with kind cohersion and equality Haskell dives deeper into dependent types. And finally Applicative will become a superclass of Monad :)

Rust for functional programmers

Link

Rust is definitely interesting language that caught my attention some time ago, but due to its instability and constant changes in API and syntax I’ve decided to wait and see where it’ll come. The presence of articles like this shows that Rust is moving towards things I appreciate most in modern programming: explicit mutability, higher-order fns, algebraic datatypes, etc. Paired with C-like performance it should make a great language.

This article covers a lot of Rust syntax compared to OCaml and Haskell examples achieving the same things. Plus it has an explanation of Rust’s sophisticated memory model. I hope by the time I’ll finally decide to dive deeper in Rust this article will help a lot.

Mutable algorithms in immutable languages

Part 1 Part 2 Part 3

In this series of posts author implements ST monad step by step. In the 1st part we build abstract interface of monad that’ll create and manage mutable references. The 2nd part brings us implementations of this interface based on IO monad and on Int map. The 3rd part fixes some locality breaches in previous implementations using Rank-N-Types and Phantom types (hi there!) and introduces ST-based implementation. Overall, these posts cover a lot of interesting ideas and useful techniques applicable in functional programming.

Things I Read This Week, Pt. 1

Jun 29, 2014 in Programming

The algebra of algebraic data types

Part 1 Part 2 Part 3

It is a series of articles about connection between algebra and data types. These posts extend the presentation author gave at London Haskell. As for me the first two parts are quite easy while the third is definitely the most interesting and mind-blowing. Thanks to it I was forced to look into the idea of Zippers again and I think that I finally understood it.

CPU Cache Essentials

Link

Short post based on ideas of Scott Meyer’s presentation about writing CPU cache aware code. Not that this post is reopening America, but it’s worth reading once in a while as a reminder to yourself. BTW the presentation itself worth checking out. There is a list of interesting literature about how memory/CPU works at the end of presentation.

Google Material Design

Link

Following recently started Google I/O event they launched site that contains a lot of guidelines and best practices for designers for upcoming Android L operating system. Despite of the world-wide design trend to minimize, simplify and “flatten” interfaces started with Windows Phone and then (poorly) supported by Apple, Google maintained pretty good and consistent design worth taking a look. Well, lets wait and see how they’re going to actually implement their own rules.

Inside the Mirrortocracy

Link

I’m not a big fan of “metaindustry” posts, but this one caught my attention because the problem it reveals sounds totally crazy to me. I thought that tech entrepreneurs have much more common sense to not base their decisions on how employee dresses and looks or how much he can drink on a party, but it seems that your score depends on these more than on your professional skills. I hope that this is a minor threat, but reading redditors’ comments proves that I’m wrong (actually, that’s why I posted here a link to reddit, comments there are totally worth reading).

Питание

Jan 25, 2013 in Misc

Может показаться, что это несколько необычная статья для блога с преимущественно технической тематикой, однако я считаю, что каждому человеку стоит знать основы правильного питания. В конце концов, потребление пищи – это необходимый для любой жизни процесс и поэтому от качества еды будет во многом зависеть и качество жизни.

Также стоит отметить то, что эта статья есть обобщение информации, полученной мной из различных источников и для краткости изложения я опущу различные научные исследования и доказательства, которые стоят за фактами изложенными здесь. Однако замечу, что прежде чем бросаться в омут с головой и применять на себе нижеизложенные правила, все-таки стоит уделить немного внимания первоисточникам, в которых достаточно подробно изложены некоторые тонкости приведенных здесь обобщений.

Вот небольшой список источников, которыми я руководствовался при подготовке этой статьи:

  • Yougifted Russia – ценнейший ресурс с огромным количеством видео, посвященных питанию, фитнесу и бодибилдингу. Строго рекомендую.
  • SportsWiki – отличный сайт с множеством статей спортивной тематики, но поскольку построен на принципе Википедии, то стоит критически относится к изложенной на нем информации. Советую выбирать статьи, которые проверенны экспертами сайта.
  • Bodybuilding.com – последний в списке, но далеко не последний по значимости. Огромный сайт (а также интернет-магазин) с кучей полезной информации, но, к сожалению, для его использования вам потребуется довольно неплохие english skills.

Что есть питание и почему оно важно

В самом простом объяснении процесс питания есть процесс поедания пищи. Правильное же питание есть система, на основе которой человек выбирает пищу, необходимую для достижения каких-либо целей (например, похудеть или наоборот, набрать мышечную массу), либо если никаких определенных целей у него нет, то для поддержания своего тела в текущем состоянии.

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

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

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

Калорийность = 4 * белки + 4 * углеводы + 9 * жиры

Рассмотрим подробнее каждое из этих веществ и его влияние на организм.

Белки (proteins)

Белки являются не только основным “строительным” материалом в организме, но также выполняют множество различных полезных функций на клеточном уровне и в различных биохимических реакциях. Недостаток белка чреват тем, что снижается иммунная функция организма. При избытке же вследствие увеличения выделяемой из организма жидкости также увеличивается выделение некоторых веществ, например, кальция, что может привести к хрупкости костей.

Белки в процессе переработки в организме расщепляются на аминокислоты. В этом деле активно задействуются щелочи и жирные кислоты, а поскольку жирные кислоты в организме получаются, как ни странно, из жира, то повышенное потребление белка положительно сказывается на уменьшении жировой прослойки и увеличении мышечной массы.

По скорости усвоения белки делятся на быстрые и медленные. К первой группе относят белки, содержащиеся в рыбе, яйцах, мясе; во вторую группу попадают растительные белки и казеин, который содержится в молочных продуктах. Быстрые протеины стоит принимать с утра, перед тренировками и после них, медленные лучше оставить на вечер. Также занимающимся стоит учесть то, что белки из обыкновенной пищи должны преобладать над белками из спортивного питания.

Углеводы (carbohydrates)

Функции углеводов в организме довольно разнообразны, но в вопросах питания важно то, что углеводы являются основным и относительно быстрым источником энергии. В организме они расщепляются до глюкозы, а глюкоза – до гликогена, который несет энергию в клетки. Недостаток углеводов заставляет организм производить глюкозу из белков и аминокислот, что в свою очередь может вызвать их недостаток и нарушение обмена веществ. Последствия же избытка углеводов таковы, что организм начинает перерабатывать и запасть их в жиры чтобы понизить уровень глюкозы в крови.

Углеводы делятся на три группы: простые, сложные и неусваиваемые. К первым относятся моно- и дисахариды (все сладкое), ко вторым – полисахариды (крупы, бобовые, овощи), к третьим – пищевые волокна (клетчатка).

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

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

Жиры (fats)

Жиры являются одной из самых темных тем в питании: с одной стороны не стоит ими злоупотреблять, потому что иначе гарантировано увеличение количества жира в теле; с другой стороны, совершенно исключать их из рациона тоже не стоит, потому что они участвуют во многих процессах, в частности, в образовании гормонов.

Жиры делятся на насыщенные и ненасыщенные. Первые считаются “плохими”, так как в их число входит небезызвестный холестерин, злоупотребление которым врачи связывают с множеством болезней. Такие жиры содержатся в мясных и молочных продуктах и кондитерских изделиях. Ко вторым относятся Омега-3, которые важны для здоровья. Их можно найти в рыбе, орехах и растительном масле.

Конечно то, что в мясе и молоке содержатся насыщенные жиры не должно останавливать вас от их употребления, но стоит выбирать такие продукты, которые содержат их в минимуме: нежирное молоко и творог; нежирные виды мяса, например, мясо птицы или говядину; нежирные части мяса, например, антрекот или лопатка.

Сочетание пищевых веществ и как часто надо кушать

Осталось рассмотреть еще пару важных вопросов.

Начнем с пропорций. Поскольку основная энергия получается из углеводов, то им отводится основное место в рационе, белки и жиры делятся примерно пополам. Итого для обычного человека пропорции энергии, получаемой из различных источников составляют примерно 70% углеводов, 15% белков и 15% жиров. Для желающих похудеть можно немного увеличить количество белков в пользу уменьшения количества жиров и углеводов, например, 65/25/10. Для набирающих массу можно порезать лишь жиры, например, 70/20/10.

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

  • Обязательно надо завтракать!
  • Нельзя переедать
  • Пищу чаще варить или запекать, чем жарить
  • Вечером лучше заменить углеводы и жиры белками

Мой рацион

В качестве примера, а также для того, чтобы позже сделать самому сравнение, я напишу также о своем текущем рационе. В общем случае он состоит из трех больших приемов пищи и нескольких перекусов, в основном фруктами. Итак:

  • Завтрак (сложные углеводы, быстрые белки): овсяная или другая каша, молоко, немного вареного мяса птицы (или какого есть в холодильнике)
  • Обед (сложные углеводы, любые белки, немного простых углеводов и жиров): различные супы на первое, каши или картофель на гарнир с мясом или рыбой, немного шоколада
  • Ужин (медленные белки): тарелка творога со сметаной, пара стаканов молока, может быть немного вареного мяса

Обед получился таким разноплановым потому, что я съедаю его обычно после тренировки, во время “углеводного окна”, когда можно кушать любые углеводы для того, чтобы пополнить запас энергии.

Заключение

Вот и все. Конечно, здесь еще многое не сказано, однако, статья и не претендовала на то, чтобы полностью охватить сложную проблему правильного питания. Напоследок могу только сказать: кушайте и будьте здоровы!