STL sort strangeness August 2, 2008
Posted by Olexandr Melnyk in : Programming , 5commentsWorking on a simple Sudoku solver, I’ve run across a memory-related issue, which isn’t uncommon when developing C/C++ programs, but in my case it seemed somewhat weird since I haven’t been doing any dynamic memory allocations or using pointers explicitly.
After spending some time searching for the bug, I realized that the problem lied in the array shuffling code, which was similar to the code below:
#include <vector>
#include <algorithm>
...
bool random_cmp(const int a, const int b)
{
return (rand() % 2 == 0);
}
...
vector<int> a;
sort(a.begin(), a.end(), random_cmp);
After running it a couple of times in the loop, we get a “double free or corruption” error with a couple dozen lines long backtrace and memory map (program was compiled with G++ 4.1.3). The reason of this, at the first glance, strange behaviour was the fact that comparison function must be deterministic (if a < b and b < c then a < c must be true as well). In the other case, the sort() behaviour is undefined, which it really was in our case. :)
This just teaches me once more to read the documentation carefully before doing something.
P. S. In the end, I used a simple shuffling algorithm, suggested by Sergij Tyhanskij:
void shuffle(vector<int> nums)
{
int a, b, count = nums.size();
for (int i = 0; i < count; i++)
{
a = rand() % count;
b = rand() % count;
swap(nums[a], nums[b]);
}
}
As for the Sudoku solver, I have added a dedicated page for it and updated this website projects section.
Paul McCartney concert June 15, 2008
Posted by Olexandr Melnyk in : Travelling , add a commentJust about nine hours ago I have arrived home from Sir Paul McCartney’s performace on the Independence Square in Kyiv. The concert was astonishing, even though Paul has brought the English weather with himself. :)
In the afternoon, when I have arrived to Kyiv, the weather in Kyiv was rather sunny and promising to be good at the show time.
One of the screens to show the concert
But, to my disappointment, a huge area around the stage was blocked by the policemen.
Blocked area
After that I went ot the largest book bazar in Ukraine and met with my friend Ihor Nikiforov. We got back to the city center around 17:30, thinking about going through Kyiv’s places of interest before the concert.
Ihor (left) and me (right)
However, around 18:00, when we were staying in a few hundred meters in front of the stage, the sky got darker and a serious rainstorm started. We were lucky enough that I had an umbrella.
Cloudy sky
But, as time proved it wasn’t sufficient to not get totally wet.
Some guy under rain
In a short while, after the rain had calmed down, the crowd broke through the fence and we used our chance to get closer to the stage. But the rainstorm got harder again.
Raining
Around 21:20, a 20-minute countdown started, after which Paul with his crew fininally entered the stage, saying “Pryvit, druzi” (stands for “Hello, friends”).
He was also saying several other Ukrainian phrases during the concert, such as “Dyakuyu” (and its Russian equivalent “Spasibo”) and “Vidryvayemos!”, which stand for “Thank you” and “Let’s have fun!”, respectively.
Show started with The Beatles hit Drive My Car, and was followed by a bunch of other songs from Paul’s solo albums. as well, as those from Wings and The Beatles repertoires. Two of The Beatles songs were dedicated to George Harrison and John Lennon.
After 20 minutes of the concert
After 40 minutes of the concert
The rainstorm was going on, periodically decreasing and increasing throughout the concert. In the middle of the concert, when the rain was almost over, Paul invited the public to get back to history for a bit, and played Back in the U.S.S.R. It was an impressive play and had warmed up the public even more, as Ukraine is mentioned in that song:
Well the Ukraine girls really knock me out
They leave the west behind
…
:)
Another song was accompanied by the fireworks.
The fireworks
Among all songs “Hey, Jude” and “Let It Be” were among my favorites.
Hey, Jude
Around 23:50, the crew left the stage and the crowd started crying “Yesterday!”. In less than a minute, the whole crew came back and played one of the best songs of all time.
It was followed by Sgt. Pepper’s Lonely Hearts Club Band, which was the last song played on the concert. Paul thanked the crowd, said “See you again” and the crew left the stage. After that both me and Ihor left the square, but people on the way back still reminded about the concert.
Guy in the metro
Important to note is that, although the concert was free to visit, money raised from the concert sponsors will be spent on diagnostic equipment for Ukraine’s National Cancer Institute’s children’s department.
MySQL views gotcha October 23, 2007
Posted by Olexandr Melnyk in : Databases , 3commentsLet’s suppose we have a simple posts table and a view, corresponding to the posts of the current week (let’s keep values hardcoded, for the sake of simplicity):
create table posts (
id integer not null auto_increment,
title varchar(128) not null,
content text not null,
submit_time datetime not null,
primary key (id),
key (submit_time)
);
create view posts_this_week as
select *
from posts
where submit_time >= '2007-10-21 00:00:00'
and submit_time < '2007-10-28 00:00:00';
So, say, you want to add an extra field to the posts table:
alter table posts add last_edit_time datetime not null;
You expect the field to be fetched by view as well, right? Wrong. In MySQL, the list of the fields to be fetched by a view is made up on view definition, rather than once the view used.
Often, such behaviour can lead to wrong assumptions (much due to classical explanation of views as query aliases), such as: server being out-of-sync when using replication, thus the table not containing the new field. So, when designing your application, keep in mind, that views, which should contain all fields from the table, have to be redifened every time table structure is altered.
Illegal to use Mac Opera? June 24, 2007
Posted by Olexandr Melnyk in : Fun, Web , add a commentAs someone has pointed out on the Opera-Users mail list, from the license of Opera 9.21 for Macintosh:
“You may not use the Software on non-PC products, devices, or embedded in any other product…”
So are all Mac users infringing the license? ;)
Using views with variables in MySQL June 18, 2007
Posted by Olexandr Melnyk in : Databases , add a commentOne of MySQL’s restriction when using views is that they cannot refer to local variables. So, for example, this statement will produce an error:
create view thematical_books as
select title
, author
from books
where subject = @book_subject
A workaround for this limitation is quite simple: to use a function which returns variable value. For example:
create function book_subject
returns varchar(64) as
return @book_subject;
create view thematical_books as
select title
, author
from books
where subject = book_subject()
Selecting colums that are not in GROUP BY May 14, 2007
Posted by Olexandr Melnyk in : Databases , add a commentAfter reading one more post on SitePoint forums about selecting not aggregated values of columns, which were not specified in the GROUP BY clause, I decided it is worth to highlight in my blog what is wrong with queries that make use of this approach.
At the start, I’d like to mention such queries are allowed only in MySQL, which is known for its unstrict behaviour. Other database servers with produce errors in such case.
One of the most common reasoning for such queries, for example:
select user_id
, post_time
from posts
group
by user_id
is the wrong assumption that query will return the most recent entry for ungrouped columns (latest post time for each user in this case).
As MySQL manual says, returned value for ungrouped column can be any value from the group it belongs to. So the query above, is free to return time of user’s any post.
A solution for such cases is to use an aggregate function:
select user_id
, max(post_time)
from posts
group
by user_id
This will guarant that returned post time for each group is the latest within the group.
Although, MySQL manual states that in case you are sure that values within a group are constant, using columns in SELECT (or HAVING), but not in GROUP BY can give performance increase by avoiding unnecessary grouping, I highly suggest to keep away from this technique as it is not standard (supported by MySQL only), and it makes behaviour of queries unclear, increasing possibility of queries working not as expected.
Happy Birthday, Mom! February 19, 2007
Posted by Olexandr Melnyk in : Life, Family , add a commentIt was my mother’s birthday on Saturday. I wish her love, wisdom, good friends, all of her dreams to come true and everything best!
PHP short open tag December 23, 2006
Posted by Olexandr Melnyk in : Programming, Web , add a commentI’ve had a problem when using XML declaration in a web page:
which was caused by a conflict with PHP short open tag. The solution was to disable it with .htaccess (what was allowed by my friend’s VPS, where this website is currently hosted):
This is yet another argument against using short open tag (not to mention that it’s support is likely to be dropped in PHP 6).
UPDATE: Short open tag is likely to stay in PHP 6, but because of the problems like the one described above, I would still recommend against using it.
CakePHP: ungreedy grabbing October 23, 2006
Posted by Olexandr Melnyk in : Programming , add a commentSometimes it takes a while to solve simple problems.
A while ago, when working on a project in CakePHP, I needed to set up more complex fetching rules than just changing recursion depth. Fortunately, CakePHP offered such flexibility.
Say, we have such relations schema:
Team hasMany Coach, Player Coach, Player hasMany Hobby
And we want to grab team info with its coaches and their hobbies and its players (without hobbies). What I first though of was:
$this->Team->recursion = 2;
$this->Player->unbindModel(
array( 'hasMany' =>
array( 'Hobby' )
)
);
$team = $this->Team->findById($id);
But it didn’t work. I’ve been trying different code variations until I found the right one:
$this->Team->recursion = 2;
$this->Team->Player->unbindModel(
array( 'hasMany' =>
array( 'Hobby' )
)
);
$team = $this->Team->findById($id);
Notice the Team between $this and Player.
The Knowledge Day September 1, 2006
Posted by Olexandr Melnyk in : Education , add a commentToday we had the Knowledge Day celebrations at the university. Actually, it was much like the ones at school, the main difference being the count of officials present there. The solemn part took around 2-3 hours, after what we went to our cathedra, where we’ve listened to some information regarding the educational process.
The lessons will start on Monday, and the first lesson I will attend at the university will be physics. The other subjects I will study during the first semester are: linear algebra and applied geometry, mathematical analysis, programming basics, informational technologies basics, Ukrainian, English, history of Ukraine and physical culture. Probably I’ve missed something, as I don’t have the classes schedule near me.
Talking of my group, I am aquainted only to several people from it, one of them being my former classmate and a good friend.
