Monday, December 30, 2013

Debian Release 7.3. Reboot issue: /dev/sda1 was not cleanly unmounted check forced.

I have faced with issue in Debian 7.3 release.
On restarting or shutdown - OS was hanging: i had a black screen and nothing was happening after that.
At first time i thought that it could be only once, but it was repeated on each restarting or shutting down.
After PC hanged nothing was possible to do - only turning off and turning on PC - even reset button didn't work.
So, i needed to start PC manually and on next boot i was receiving error message:
/dev/sda1 was not cleanly unmounted check forced.
So, to restart my PC i needed to shutdown with shutdown button, then start, wait when harddisk is checked and then run fsck utility manually to check disk.
It was very boring, so i decided to fix the issue.

At first time i thought, that it could be because of Debian is installed on external USB HDD which is on USB 3.0.
I was trying to use another USB 3.0 port and use USB 2.0, but was no luck.
Then i have checked logs and there also was no errors related with /dev/sda1.
Then i started to search in web and i found that someone also have faced with similar problems, but there was no the solution.
In common i spent about all day to fix the issue, i tried a different things, i wrote on forums - nobody gave me the answer.

Then my best friend give me advice - try to update Debian to newer version.
I have updated Debian from version:
Linux m4p-debian 3.2.0-4-amd64 #1 SMP Debian 3.2.51-1 x86_64 GNU/Linux
to
Linux m4p-debian 3.12.0-031200-generic #201311031935 SMP Mon Nov 4 00:36:54 UTC 2013 x86_64 GNU/Linux

After update - restarting shutdowning is ok and i am really greatful to my friend.
Thank you, Vitya!

Hope this post will be helpful to someone.

Thursday, December 26, 2013

How to create bootable USB flash for Linux install from Windows?

Supposed user is using Windows OS and want to make bootable USB flash for Linux distributive.
Steps that is needed to do:
  1. It is needed to download distributive of linux as iso image.
  2. It is needed to download Win32DiskImager
  3. Run Win32DiskImager and select the image file.
  4. Select device.
  5. Press Write.
Enjoy!

Sunday, December 1, 2013

What are database normal forms: 1NF, 2NF, 3NF, BCNF? Difference between 3NF and BCNF.

Assumed reader is already acquainted with relational databases theory.
Definitions of 2 NF and 3 NF is given asusming only one candidate key, which is thus the primary key.

1 NF

A relation is in 1NF if and only if all underlying domains contain scalar values only.

2 NF

A relation is in 2NF if and only if it is in 1NF and every nonkey attribute is irreducibly dependent on the primary key.

3NF

A relation is in 3NF if and only if it is in 2NF and every nonkey attribute is nontransitively dependent on the primary key.

BCNF

A relation R is in BCNF if and only if for every one of its functional dependencies X → Y, at least one of the following conditions hold:
  • X → Y is a trivial functional dependency (Y ⊆ X)
  • X is a superkey for relation R
Superkey is a set of attributes of a relation schema upon which all attributes of the schema are functionally dependent. For example, if we have relation schema with attributes {X, Y, Z, Value}, then superkey is a subset  {X, Y, Z}→ Value.


Difference between 3NF and BCNF

Difference between 3NF and BCNF forms could be only if relation has at least two potential keys which is composite and two or more potential keys are overlapped  (i.e. has one or more common attributes).
Let suppose we had relation variable SST with attributes  Student, Subject, Teacher.
There is two constraints for this relation:
  • Every student is learning the subject only in the one teacher;
  • Every teacher teaches only one subject, but each subject could be teached by several teachers.

Below is the example of relation variable value:

Functional dependencies which determinated by constraints:
{ Student, Subject} → Teacher
{Teacher} → {Subject}

Candidate keys: {Student, Subject}, {Student, Teacher}.
As you see we have two candidate keys which is composite and it are overlapped, because attribute Student is common attribute.

Is relation variable SST in 3NF?

Answer is yes, because in both cases non-key attribute has irreducibly non-transitive dependency from key: {Student, Subject} → Teacher or {Student, Teacher} → Subject.

Is relation variable SST in BCNF?

Answer is no, because for dependency {Teacher} → Subject we don't have potential key where determinant of it is Teacher.


Refrences
[1]. Normal forms on trumpetpower.com
[2]. Date, C. J. (1999), An Introduction to Database Systems (8th ed.). Addison-Wesley Longman. ISBN 0-321-19784-4.
[3]. Candidate key, the free encyclopedia

Sunday, October 20, 2013

C++. How to call non-const method from const method?


There is two ways how to call non-constant method from constant method in C++:
1. Call non-const method from const_casted this pointer.
2. Use reinterpret_cast to cast pointer of non-const method to const method pointer.

The first way is more acceptable and easy.

Below here is C++ code with example of this two ways.


 

Wednesday, October 2, 2013

C++. How to inherit operators from int?

The short answer - nohow.
But still, exists way to use int operators for your class.
It could be reached by defining implicit convertion operator to int.
Below here is demonstrative example of implementation which is useless in real programs.
 

Wednesday, July 31, 2013

Reversing bits in byte in C

Question is: what is the fastest and portable way to reverse bits in byte in C?


I have read article on corner.squareup.com and choose two faster portable functions.
I made additional comparing of function performance.
Comparing environment: ideone.com. Compiler: gcc-4.7.2.
Below is code:

 
Here is results of performance testing: 
200000000 calls of ReverseBitsSimpleAndElegant takes 1.660000 seconds.
200000000 calls of ReverseBitsLookupTable takes 0.980000 seconds.
200000000 calls of ReverseBits7ops32bit takes 0.920000 seconds.

So, function ReverseBits7ops32bit is the fastest way which i has found.
Let me know if you find faster way. I will check.

Wednesday, July 24, 2013

What does std::make_heap do?


std::make_heap reorder elements in container to satisfy definition of binary max heap.

Building binary max heap algorithm
Here is algorithm from wiki in pseudo code.
Function Build-Max-Heap calls Max-Heapify which do the main part of job [1].

Max-Heapify (A, i):
 left ← 2i
 right ← 2i + 1
 largesti
 if leftheap_length[A] and A[left] > A[largest] then:
 largestleft
 if rightheap_length[A] and A[right] > A[largest] then:
 largestright
 if largesti then:
 swap A[i] ↔ A[largest]  
 Max-Heapify(A, largest)

Build-Max-Heap (A):
 heap_length[A] ← length[A]
 for ifloor(length[A]/2) downto 1 do
 Max-Heapify(A, i)

Implemenation of building binary max heap algorithm in C++
Below is code with implemenation of functions defined in pseudo code above.



Result of code execution is:
9 8 7 4 5 6 3 2 1 
 
Execution result it is result positions of elements in vector:
 
 

Representation of this array as binary heap:




Refrences
[1]. Binary heap From Wikipedia, the free encyclopedia.

Sunday, July 21, 2013

What is faster: std::sort or std::make_heap + std::sort_heap?

At first lets consider time complexity of algorithms.

Time complexity of std::sort.
According to the C++ standard, sort is required to perform O(NlogN) comparsions on average but has worst-case complexity of O(N*N), where N is last - first. This latitude, however, is unnecessary. It is possible to implement sort so that the number of comparsions, both average and worst-case, is only O(NlogN) [1].

Time complexity of std::make_heap.
Linear. At most 3N comparsions, where N is last - first.

Time complexity of std::sort_heap.
At most NlogN comparsions, where N is last - first.

Time complecity of std::make_heap +std::sort_heap in the worst-case is 3N + NlogN.

Performance testing.
Code below has been run on ideone.com with gcc 4.7.2. in testing purpose.


Performance testing results.
On reverse range std::sort can be slower than std:make_heap + std::sort_heap in 2 times.
==== Comparing std::sort vs std::sort_heap performance. ===
==== Range types: sorted, reversed, random  ===
==== Range size is 10000000.    ===

==== std::sort results:
Consumed time for sorted range: 0.340000 sec.
Consumed time for reversed range: 2.520000 sec.
Consumed time for random range: 1.110000 sec.

==== std::make_heap+std::sort_heap results:
Consumed time for sorted range: 1.060000 sec.
Consumed time for reversed range: 1.260000 sec.
Consumed time for random range: 4.660000 sec

Conclusions
std::sort can be slower then std::make_heap +std::sort_heap in N/(3 + logN) times in worst-case. But, in average std::sort is faster.

References
[1]. Generic Programming and the STL: Using and Extending the C++ Standard Template Library

 

Wednesday, July 10, 2013

What is faster: multidimensional array or inline function?


Suppose given simple function which depends from four parameters f(i, j, c, k) = abs(i-c) + abs(c-k), where i, j, c, k are less than 100.
The question is: what is the faster way: use inline function which compute each result every time or to build multidimensional array res[i][j][c][k] once with all possible answers?

I have checked this case with i, j, c, k is less than 45 with using gcc 4.7.2.
Here are results: 
Time for array is: 5.410000 sec. 
Time for inline function is: 5.410000 sec. 

Conclusions. Time of executions is the same, because inline function is quite simple. Benefit of inline function is more understandable way of result calculation without using extra memory. So, if function is quite simple there is no reason to create multidimensonal array with cached results.

Below is the code which I used to check performance.