Partager via


Chasing state of the art

Exploring best practices in problem solving

Parallel partition phase for quick sort

A while ago I was wrapping my head around parallel merge sort. Since it requires additional O(n)...

Date: 03/04/2012

Load-balancing partitioner with work stealing, part two

In part one work stealing range was introduced that allows stealing of work items in contiguous...

Date: 08/10/2011

Load-balancing partitioner with work stealing, part one

Data parallelism is a computing parallelization technique where data can be separated into...

Date: 08/08/2011

Infernal dinner synchronization problem

Imagine group of hungry people with spoons sitting around pot of stew. Spoon’s handle long...

Date: 07/19/2011

Shared rooms synchronization problem

Recently I came across another interesting synchronization problem. Assume there are n rooms....

Date: 06/29/2011

Single Responsibility Principle – discovering violations

Single Responsibility Principle states: A class should have only one reason to change....

Date: 06/15/2011

Inject or locate dependencies?

Inversion of Control pattern allows to decouple components (consumers) from their dependencies and...

Date: 06/13/2011

Sleeping barber synchronization problem

Sleeping barber problem is a classic synchronization problem proposed by Dijkstra that goes as...

Date: 06/12/2011

Concurrent Object Pool

Object pool is a set of initialized objects that are kept ready to use, rather than allocated and...

Date: 05/01/2011

Concurrent set based on sorted singly linked list

Set is an abstract data structure that can store certain values, without any particular order, and...

Date: 04/06/2011

Merge binary search trees in place

Binary search tree is a fundamental data structure that is used for searching and sorting. It also...

Date: 03/27/2011

Merge sequences in parallel

In practice you may find yourself in a situation when you have several sequences of data that you...

Date: 02/25/2011

Longest consecutive elements sequence

A tiny detail that can be uncovered by looking at a problem on a different angle usually is the key...

Date: 02/12/2011

Parallel string matching

String matching is about searching for occurrence (first or all occurrences – it makes...

Date: 01/05/2011

Graph is a concept used to describe relationships between things where vertices (or nodes) represent...

Date: 12/26/2010

Joining Microsoft

Find a job you like and you add five days to every week. - H. Jackson Brown, Jr. I decided to join...

Date: 11/11/2010

Parallel merge sort

Divide and conquer algorithm solves the problem by: dividing problem into two or more smaller...

Date: 10/17/2010

Traverse binary tree in level order by spiral

Another puzzle is at stake, folks. This time it is binary tree related (not necessarily binary...

Date: 09/19/2010

External merge sort

If data to be sorted doesn’t fit into main memory external sorting is applicable. External...

Date: 08/24/2010

Recently I came across simple yet interesting coding problem. So here is the deal. You are given...

Date: 08/17/2010

Suffix array

Find all occurrences of a pattern (of length m) in a text (of length n) is quite commonly...

Date: 04/04/2010

Selecting k smallest or largest elements

There are cases when you need to select a number of best (according to some definition) elements out...

Date: 03/17/2010

K-way merge

The classic merge (the one used in Merge Sort) takes as input some sorted lists and at each step...

Date: 03/04/2010

Right-hand side Enumerable.Zip

With Reactive Extensions for .NET (Rx) and .NET Framework 4 a new LINQ operator was introduced...

Date: 02/22/2010

Binary heap based priority queue

Design of container that supports items ordering raises lots of interesting design questions to...

Date: 02/08/2010

Queue based on a single stack

Looking at things from different perspectives allows to understand them better. On the other hand...

Date: 01/17/2010

Disposing sequence of resources with Reactive Extensions

Recall my previous post on Disposing sequence of resources where we were solving imperatively the...

Date: 12/29/2009

Chaining responsibilities

The idea behind Chain of Responsibility pattern is quite simple and powerful: Avoid coupling the...

Date: 12/22/2009

Making callbacks more explicit

Recall my previous post Events and Callbacks vs. Explicit Calls that outlined pros and cons of both...

Date: 12/21/2009

Disposing sequence of resources

C# “using” statement has several advantages over its expanded equivalent: Shortcut is...

Date: 11/04/2009