Pull to refresh
245.29

Algorithms *

Everything about algorithms

Show first
Rating limit
Level of difficulty

How to build a high-performance application on Tarantool from scratch

Reading time 33 min
Views 2.2K
VK corporate blog High performance *Algorithms *Lua *Tarantool *
Tutorial
image

I came to Mail.ru Group in 2013, and I required a queue for one task. First of all, I decided to check what the company had already got. They told me they had this Tarantool product, and I checked how it worked and decided that adding a queue broker to it could work perfectly well.

I contacted Kostja Osipov, the senior expert in Tarantool, and the next day he gave me a 250-string script that was capable of managing almost everything I needed. Since that moment, I have been in love with Tarantool. It turned out that a small amount of code written with a quite simple script language was capable of ensuring some totally new performance for this DBMS.

Today, I’m going to tell you how to instantiate your own queue in Tarantool 2.2.
Read more →
Total votes 18: ↑18 and ↓0 +18
Comments 0

Implementation of Linked List in PHP

Reading time 3 min
Views 5.5K
Programming *Algorithms *
Sandbox

A linked list is a linear data structure, which contains node structure and each node contains two elements. A data part that stores the value at that node and next part that stores the link to the next node as shown in the below image:


Linked List Node

The first node also known as HEAD is usually used to traverse through the linked list. The last node (next part of the last node) points to NULL. The list can be visualized as a chain of nodes, where every node points to the next node.


Linked List

Implementation of Singly Linked List


Representation:


In PHP, singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.


//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }
};

Read more →
Total votes 7: ↑5 and ↓2 +3
Comments 4

MEMS accelerometers, magnetometers and orientation angles

Reading time 8 min
Views 9.1K
Global Positioning Systems *Algorithms *Mathematics *Robotics
Translation


When it's necessary to evaluate the orientation angles of an object you may have the question — which MEMS sensor to choose. Sensors manufacturers provide a great amount of different parameters and it may be hard to understand if the sensor fit your needs.

Brief: this article is the description of the Octave/Matlab script which allows to estimate the orientation angles evaluation errors, derived from MEMS accelerometers and magnetometers measurements. The input data for the script are datasheet parameters for the sensors. Article can be useful for those who start using MEMS sensors in their devices. You can find the project on GitHub.
Read more →
Total votes 5: ↑5 and ↓0 +5
Comments 0

Queue Implementation in JavaScript / Algorithm and Data Structure

Reading time 4 min
Views 6K
JavaScript *Algorithms *
Tutorial
Recovery mode
What do you imagine when you hear the word "Queue"? If you are not familiar with Programming you maybe think about the queue in shop or hospital. But if you are a programmer you associate it 99% with Data Structures and Algorithms. Whoever you are, today we will discuss how to implement Queue Data Structure in JavaScript and what are its differences with a simple Array. Let's get started!


Read more →
Total votes 5: ↑0 and ↓5 -5
Comments 0

Ray Cast Visual Search (RCVS). Fast and simple algorithm for searching 3D objects with similar shapes

Reading time 8 min
Views 2.9K
Search engines *Working with 3D-graphics *Algorithms *CGI *
image
For me, these two models are quite similar, but in fact they don’t have obvious characteristics to measure this similarity. These models have different numbers of vertices, edges and polygons. They are of different sizes, rotated differently and both have the same transforms (Location = [0,0,0], Rotation in radians = [0,0,0], Scale = [1,1,1]). So how to determine their similarity?
Total votes 3: ↑3 and ↓0 +3
Comments 0

Quick Sort Algorithm in JavaSript (pivot as the first element + pivot as the random element)

Reading time 5 min
Views 14K
JavaScript *Algorithms *
Tutorial

Introduction


Quick Sort is one of the most famous and effective Sorting Algorithms. The comprehension of how it works will undoubtedly help you in your JavaScript learning. Also, questions on algorithms are popular in job interviews, so there is a big chance you will be asked to describe how Quick Sort works.

I’m sure that I convinced you that Quick Sort is important. Let’s start!


Read more →
Total votes 7: ↑5 and ↓2 +3
Comments 2

Free API Moscow Stock Exchange (MOEX) in Google Sheets

Reading time 2 min
Views 7.5K
Data Mining *Algorithms *API *Google API *Finance in IT
Last year the number of private investors at Moscow Stock Exchange (MOEX) has doubled and reached 3.86 million: about 1.9 million people have opened accounts at MOEX in 2019. The Saint Petersburg Stock Exchange which specializes in trading of foreign company shares has seen its accounts increase three times from 910,000 to 3,06 million over the past year.



This means that almost 2 million newbies without any actual trading experience and lacking any specialized software for trading/position analysis have entered the market.
Read more →
Total votes 4: ↑4 and ↓0 +4
Comments 1

Five Methods For Database Obfuscation

Reading time 20 min
Views 6.7K
Яндекс corporate blog Open source *Algorithms *Big Data *Machine learning *
ClickHouse users already know that its biggest advantage is its high-speed processing of analytical queries. But claims like this need to be confirmed with reliable performance testing. That's what we want to talk about today.



We started running tests in 2013, long before the product was available as open source. Back then, just like now, our main concern was data processing speed in Yandex.Metrica. We had been storing that data in ClickHouse since January of 2009. Part of the data had been written to a database starting in 2012, and part was converted from OLAPServer and Metrage (data structures previously used by Yandex.Metrica). For testing, we took the first subset at random from data for 1 billion pageviews. Yandex.Metrica didn't have any queries at that point, so we came up with queries that interested us, using all the possible ways to filter, aggregate, and sort the data.

ClickHouse performance was compared with similar systems like Vertica and MonetDB. To avoid bias, testing was performed by an employee who hadn't participated in ClickHouse development, and special cases in the code were not optimized until all the results were obtained. We used the same approach to get a data set for functional testing.

After ClickHouse was released as open source in 2016, people began questioning these tests.

Read more →
Total votes 11: ↑9 and ↓2 +7
Comments 4

SpaceFusion: Structuring the unstructured latent space for conversational AI

Reading time 4 min
Views 980
Microsoft corporate blog Algorithms *Machine learning *Artificial Intelligence
A palette makes it easy for painters to arrange and mix paints of different colors as they create art on the canvas before them. Having a similar tool that could allow AI to jointly learn from diverse data sources such as those for conversations, narratives, images, and knowledge could open doors for researchers and scientists to develop AI systems capable of more general intelligence.


A palette allows a painter to arrange and mix paints of different colors. SpaceFusion seeks to help AI scientists do similar things for different models trained on different datasets.
Read more →
Total votes 5: ↑5 and ↓0 +5
Comments 0

How elliptic curve cryptography works in TLS 1.3

Reading time 20 min
Views 18K
Qrator Labs corporate blog Information Security *Cryptography *Algorithms *Mathematics *
image

A couple of reader alerts:

In order to (somewhat) simplify the description process and tighten the volume of the article we are going to write, it is essential to make a significant remark and state the primary constraint right away — everything we are going to tell you today on the practical side of the problematics is viable only in terms of TLS 1.3. Meaning that while your ECDSA certificate would still work in TLS 1.2 if you wish it worked, providing backwards compatibility, the description of the actual handshake process, cipher suits and client-server benchmarks covers TLS 1.3 only. Of course, this does not relate to the mathematical description of algorithms behind modern encryption systems.

This article was written by neither a mathematician nor an engineer — although those helped to find a way around scary math and reviewed this article. Many thanks to Qrator Labs employees.

(Elliptic Curve) Diffie-Hellman (Ephemeral)

The Diffie–Hellman legacy in the 21 century

Of course, this has started with neither Diffie nor Hellman. But to provide a correct timeline, we need to point out main dates and events.

There were several major personas in the development of modern cryptography. Most notably, Alan Turing and Claud Shannon both laid an incredible amount of work over the field of theory of computation and information theory as well as general cryptanalysis, and both Diffie and Hellman, are officially credited for coming up with the idea of public-key (or so-called asymmetric) cryptography (although it is known that in the UK there were made serious advances in cryptography that stayed under secrecy for a very long time), making those two gentlemen pioneers.

In what exactly?
Read more →
Total votes 21: ↑21 and ↓0 +21
Comments 0

A City Without Traffic Jams

Reading time 55 min
Views 3.5K
Algorithms *Mathematics *Transport Urbanism

Chapter 2.
(the link to Chapter 1)

The Art of Designing Road Networks


Transport problems of a city through the eyes of a Computer Scientist


If I were recommended an article with the title “The Art of Designing Road Networks,” I would immediately ask how many road networks were built with the participation of its author. I must admit, my professional activity was far from road construction and was recently associated with the design of microprocessors where I, among other responsibilities, was engaged in the resource consumption of data switching. At that time my table stood just opposite the panoramic window which opened up a beautiful view of the long section of the Volgograd Highway and part of the Third Transport Ring with their endless traffic jams from morning to evening, from horizon to horizon. One day, I had a sudden shock of recognition: “The complexities of the data switching process that I struggle with on a chip may be similar to the difficulties the cars face as they flow through the labyrinth of road network”.
Probably, this view from the outside and the application of methods that were not traditional for the area in question gave me a chance to understand the cause of traffic jams and make recommendations on how to overcome the problem in practice.
Read more →
Total votes 13: ↑13 and ↓0 +13
Comments 2

How we made landmark recognition in Cloud Mail.ru, and why

Reading time 11 min
Views 2.2K
VK corporate blog Algorithms *Image processing *Machine learning *Artificial Intelligence


With the advent of mobile phones with high-quality cameras, we started making more and more pictures and videos of bright and memorable moments in our lives. Many of us have photo archives that extend back over decades and comprise thousands of pictures which makes them increasingly difficult to navigate through. Just remember how long it took to find a picture of interest just a few years ago.

One of Mail.ru Cloud’s objectives is to provide the handiest means for accessing and searching your own photo and video archives. For this purpose, we at Mail.ru Computer Vision Team have created and implemented systems for smart image processing: search by object, by scene, by face, etc. Another spectacular technology is landmark recognition. Today, I am going to tell you how we made this a reality using Deep Learning.
Read more →
Total votes 45: ↑44 and ↓1 +43
Comments 0

Automatic respiratory organ segmentation

Reading time 8 min
Views 1.7K
Inobitec corporate blog Working with 3D-graphics *Algorithms *Image processing *Data visualization *

Manual lung segmentation takes about 10 minutes and it requires a certain skill to get the same high-quality result as with automatic segmentation. Automatic segmentation takes about 15 seconds.


I assumed that without a neural network it would be possible to get an accuracy of no more than 70%. I also assumed, that morphological operations are only the preparation of an image for more complex algorithms. But as a result of processing of those, although few, 40 samples of tomographic data on hand, the algorithm segmented the lungs without errors. Moreover, after testing in the first five cases, the algorithm didn’t change significantly and correctly worked on the other 35 studies without changing the settings.


Also, neural networks have a disadvantage — for their training we need hundreds of training samples of lungs, which need to be marked up manually.


Read more →
Total votes 11: ↑10 and ↓1 +9
Comments 1

AI-Based Photo Restoration

Reading time 7 min
Views 17K
VK corporate blog Algorithms *Image processing *Machine learning *


Hi everybody! I’m a research engineer at the Mail.ru Group computer vision team. In this article, I’m going to tell a story of how we’ve created AI-based photo restoration project for old military photos. What is «photo restoration»? It consists of three steps:

  • we find all the image defects: fractures, scuffs, holes;
  • we inpaint the discovered defects, based on the pixel values around them;
  • we colorize the image.

Further, I’ll describe every step of photo restoration and tell you how we got our data, what nets we trained, what we accomplished, and what mistakes we made.
Read more →
Total votes 34: ↑33 and ↓1 +32
Comments 5

Even more secret Telegrams

Reading time 6 min
Views 4.6K
Information Security *Instant Messaging *Python *Algorithms *Development of communication systems *

We used to think of Telegram as a reliable and secure transmission medium for messages of any sort. But under the hood it has a rather common combination of a- and symmetric encryptions. Where’s fun in that? And why would anyone trust their private messages to a third-party anyway?
Spy vs Spy by Antonio Prohías
TL;DR — inventing a private covert channel through users blacklisting each other.

Read more →
Total votes 12: ↑8 and ↓4 +4
Comments 0

How does a barcode work?

Reading time 6 min
Views 12K
Python *Programming *Algorithms *Popular science Systems engineering *
Hi all!

Every person is using barcodes nowadays, mostly without noticing this. When we are buying the groceries in the store, their identifiers are getting from barcodes. Its also the same with goods in the warehouses, postal parcels and so on. But not so many people actually know, how it works.

What is 'inside' the barcode, and what is encoded on this image?



Lets figure it out, and also lets write our own bar decoder.
Read more →
Total votes 27: ↑25 and ↓2 +23
Comments 0

Kalman Filter

Reading time 9 min
Views 5.8K
Algorithms *Mathematics *
Tutorial
Translation


There are a lot of different articles on Kalman filter, but it is difficult to find the one which contains an explanation, where all filtering formulas come from. I think that without understanding of that this science becomes completely non understandable. In this article I will try to explain everything in a simple way.

Kalman filter is very powerful tool for filtering of different kinds of data. The main idea behind this that one should use an information about the physical process. For example, if you are filtering data from a car’s speedometer then its inertia give you a right to treat a big speed deviation as a measuring error. Kalman filter is also interesting by the fact that in some way it is the best filter. We will discuss precisely what does it mean. In the end of the article I will show how it is possible to simplify the formulas.
Read more →
Total votes 21: ↑21 and ↓0 +21
Comments 1

Authors' contribution