Abstraction in algorithms

I asked some questions about algorithms, and some replied they are abstract concepts, however I don’t know what abstraction means for algorithms or how it applies.

For objects, I know if we remove the details of an object we have made it abstract, for example a Person is more abstract than Student

I thought maybe they mean removing details of an algorithm and just specifying it with its input and output for example A = Sort(A) is more abstract than bubble sort implementation.

Am I correct?

Don’t get afraid by words : Abstraction is the process of removing every aspect of the issue that is not useful to solve it.

-So you can concentrate on only what matters-

Abstraction is so widely used because there exist a number of ‘patterns’ in programming that keeps repeating in every application. Find the pattern corresponding to your issue, find the abstract solution to it, implement it and you’re done.
Even better : most (?all?) coding langages provides some built-in abstract patterns, which are most easy to use. Some API also provides more advanced patterns.

Abstracting is removing, so you can reach different level of abstraction by removing more or less aspect of your issue. But if you remove too much elements, you’ll say nothing about nothing (expl : A=sort(A) won’t solve much issues..).
On the other hand, if you keep too much details you might not see what’s relevant to solve the issue.
Balance.

Let’s take the sorting issue : It’s not relevant what kind of object you want to use, neither the kind of storage you are using for those objects. ( And not either the platform or the programming language you’re using).
Sorting all breaks down to :
– having a collection of object in which you can iterate.
– having a way to compare two elements.
Then the purpose of the sort is to have every two successive items correctly ordered.

Now you can think bubble sort / quick sort / … for any kind of iterable collection of comparable items.
Solve the issue once, and use it any time you encounter this issue, it doesn’t matter if you are using a list, an array, a stack…. to store dates, or graphic objects, or … : the abstract algorithm will be the same.

Javascript for instance as a built-in Collection called an Array (it is in fact a dynamic array that can be sparse), which has a sort method. The only thing you have to do to sort the array is to provide the comparison function to the sort method -Great !-.

small example :

  // let's define a collection of information about travels.
  var travels = [ travel1, travel2, travel3, ...  ] ;
  // sort the travels on their start date
  // : just provide the right comparison function to the sort method.
  travels.sort(  function ( t1, t2 ) { return t1.startDate - t2.startDate } );
  ==> done !

Rq : Abstraction is used for algorithm, but also for general software design : that’s what design patterns are about.
Just one small example : imagine you have one object very costly to create that you might not even use, what can you do ?
(see that this question is very ‘abstract’ there’s no useless details about the object type, the resource being used, …, there’s only the problem’s skeleton).

Answer is –>>> use the lazy initialization pattern : do not create the object until it’s actually asked by your application.

class SomeClass {

    public get someHeavyObject { 
         // create object if it was not created already
         if (_someHeavyObject == null) _someHeavyObject = new SomeHeavyObject();
         // return the object
         return _someHeavyObject;
    }

    private _someHeavyObject = null;
}

(more on design patterns here http://en.wikipedia.org/wiki/Software_design_pattern )

Another great advantage of abstraction is that when you’re seeking help, be it on forums or with a mate, not everyone will want to hear/read the 30 minutes description of what you’re building.
If you go straight to the point by abstracting the issue, you greatly raise your chances to be understood and to get your reply.

You will win a great deal of time by reusing the right abstract data types / algorithm / patterns, so do not hesitate to dig into it.

No, you’re not correct about what that person meant; your reference to objects is a rather technical detail of OO languages (which concerns abstractions the code is modelling), and talking about an algorithm only in terms of input and output is a different level of abstraction, one step too high (but at the same time too low because you seem to think about it again in terms of a programming language).

Algorithms are abstract concepts in the sense that the definition of a specific algorithm (let’s say Bubblesort) is independent of how it’s implemented. You can implement Bubblesort in any programming language you like, Haskell, Java, C, assembler, or even directly in hardware. You can even do it manually. But it will always be Bubblesort, it will always do things in the same way, and always have the characteristics (O(n^2) worst case running time, O(n) on presorted data) of Bubblesort.

In general an abstraction is a simplification or a simplified representation of something, so to produce an abstraction of an algorithm would be state its form in the simplest way – for a sort this would be state it without the details of how the comparisons or the substitutions worked, for instance.

Filed under: softwareengineering - @ 18:36

Thẻ: abstraction, algorithms

Thiết kế website giá rẻ

Danh mục

Abstraction in algorithms